[CodeGen] Implement [[likely]] and [[unlikely]] for the iteration statements

[aaron.ballman]

Thank you for this!

clang/include/clang/Basic/AttrDocs.td

1773

How about: Below are some example usages of the likelihood attributes and their effects:

1854

The loop the likely -> The loop is the likely

Also, mentioning that this applies to range-based for loops may not be a bad thing either.

1861

Oye, I don't know how I feel about this. According to the standard (http://eel.is/c++draft/stmt.pre#1), the unlikely attribute appertains to the compound statement, not the expression within the while loop and that compound statement is required to be entered at least once so this just feels really unintuitive to me. WDYT?

1866

This is a bit of an edge case where I can't tell whether we should or should not diagnose. On the one hand, the user wrote something and we think it's meaningless, which we would usually diagnose as being an ignored attribute so the user can maybe react to it. On the other hand, "has no effect" is perhaps not the same as "ignored", as with i + 0 (it's not really ignored but you would expect it to have no effect either).

1867

elides comparison -> elides the comparison

1871

elides comparison -> elides the comparison

clang/lib/CodeGen/CodeGenFunction.h

1410

attribe -> attribute

[Mordante]

clang/include/clang/Basic/AttrDocs.td

1854

I was doubting whether to mention the range-based for loop separately. I'm not sure how many developers see it as an entirely different for loop. But I'll add an example.

1861

I like the current approach. I agree it feels a bit odd, the initial path of execution will always be the substatement. Whether the substatement will be executed after the condition in the while isn't known upfront so there the likelihood attribute can help. If we don't allow it here I see no other way to express the fact the user expects it unlikely the loop more than one iteration.

I just did a short test with GCC and MSVC and it seems to have no effect on the generated assembly code. So maybe it would be better to remove it for now and discuss it later with the other vendors. Do you agree?

1866

In this case it's ignored since the CodeGen doesn't create a branch instruction. GCC does the same at -O0, MSVC creates the branch at -O0, but removes it at higher optimization levels. So since the other two main compilers also remove the branch I think we could issue a diagnostic in this case we can do that when the CodeGen determines the branch isn't needed. In that case I don't expect false positives. Agreed?

1871

If we keep the do/while likelihood and issue a diagnostic for while(1) we should do the same here.

[aaron.ballman]

clang/include/clang/Basic/AttrDocs.td

1861

I just did a short test with GCC and MSVC and it seems to have no effect on the generated assembly code. So maybe it would be better to remove it for now and discuss it later with the other vendors. Do you agree?

I think that's a great approach, thank you!

The reason I am uncomfortable with the current approach is that we went to a lot of effort to make appertainment clear for attributes and *not* let them slide around like GNU-style attributes, and that's effectively what this one is doing. So while the behavior we get is not the worst, it opens the door to more "oh, but I know better than the user where this belongs" sort of shenanigans that we should be resistant to.

1866

I think that's reasonable if it's easy enough for you to do, but I don't insist on a diagnostic if it turns out to be tricky to support for some reason.

1871

Agreed, good catch!

[Mordante]

Thanks for the feedback. I'll update the patch after making the requested changes.

clang/include/clang/Basic/AttrDocs.td

1866

Emitting it from the CodeGen is trivial, there it's known whether the branch is emitted. Emitting it from the Sema would be harder, since there it isn't known whether the branch will be omitted. This would mean a -fsyntax-only run won't emit the diagnostic. I'm not sure whether doing the check in the CodeGen affects third-party tools that show diagnostics to the user. For users compiling code it makes no difference.

[aaron.ballman]

clang/include/clang/Basic/AttrDocs.td

1866

I don't spend a whole lot of time in CodeGen so I was surprised there were CodeGen-specific diagnostics, but I see now that we do have some and they live with the other frontend diagnostics. I think doing the work from CodeGen is reasonable, but I'm also not certain if third-parties will find it difficult. Given that we already support diagnostics in CodeGen, I'd say it's fine to add another one.

[Mordante]

Addressed the review comments:

• The likelhood attribute no longer affects the do statement.
• Added a diagnotic when a likelihood attribute is used on an infinite while loop. Note the diagnostic uses a select since I already use this diagnostic for a WIP patch. That patch issues a diagnostic when the likelihood attribute annotates an if constexpr. Since the attribute has no effect on the do statement there's no warning for do [[likely]] { ... } while(0);. The warning would imply the attribute has an effect on a normal do statement.
• Various minor fixes.

[aaron.ballman]

LGTM aside from a request about the note. Thank you for this!

clang/include/clang/Basic/DiagnosticSemaKinds.td

3163

As @rjmccall pointed out in the other review, this isn't really a generic note. I'd mildly recommend renaming the note and removing the select.

[Mordante]

Thanks for the review.

clang/include/clang/Basic/DiagnosticSemaKinds.td

3163

I'll do that and the same for the warn.

clang/include/clang/AST/Stmt.h

public:
   static void PrintStats();
 
   /// \returns the likelihood of a set of attributes.
   static Likelihood getLikelihood(ArrayRef<const Attr *> Attrs);
 
   /// \returns the likelihood of a statement.
   static Likelihood getLikelihood(const Stmt *S);
 
+  /// \returns the likelihood attribute of a statement.
+  static const Attr *getLikelihoodAttr(const Stmt *S);
+
   /// \returns the likelihood of the 'then' branch of an 'if' statement. The
   /// 'else' branch is required to determine whether both branches specify the
   /// same likelihood, which affects the result.
   static Likelihood getLikelihood(const Stmt *Then, const Stmt *Else);
 
   /// \returns whether the likelihood of the branches of an if statement are
   /// conflicting. When the first element is \c true there's a conflict and
   /// the Attr's are the conflicting attributes of the Then and Else Stmt.

clang/include/clang/Basic/AttrDocs.td

 likelihood. The positive likelihood is the more likely of path of execution
 than the neutral likelihood.
 
 These attributes have no effect on the generated code when using
 PGO (Profile-Guided Optimization) or at optimization level 0.
 
 In Clang, the attributes will be ignored if they're not placed on
 * the ``case`` or ``default`` label of a ``switch`` statement,
-* or on the substatement of an ``if`` or ``else`` statement.
+* or on the substatement of an ``if`` or ``else`` statement,
+* or on the substatement of an ``for`` or ``while`` statement.
 The C++ Standard recommends to honor them on every statement in the
 path of execution, but that can be confusing:
 
 .. code-block:: c++
 
   if (b) {
     [[unlikely]] --b; // In the path of execution,
                       // this branch is considered unlikely.
if (b) {
     // In the path of execution: void foo(int);
     // Not in the path of execution: [[noreturn]] void foo(int);
     // This means the likelihood of the branch depends on the declaration
     // of foo().
     [[unlikely]] --b;
   }
 
 
-At the moment the attributes only have effect when used in an ``if``, ``else``,
-or ``switch`` statement.
+Below are some example usages of the likelihood attributes and their effects:
 
 .. code-block:: c++
 
   if (b) [[likely]] { // Placement on the first statement in the branch.
     // The compiler will optimize to execute the code here.
   } else {
   }
 
switch (i) {
 
     case 2:               // No likelihood attribute, code path is neutral
       [[fallthrough]];
 
     [[unlikely]] default: // This value and code path are both unlikely
       break;
   }
 
+  for(int i = 0; i != size; ++i) [[likely]] {
+    ...               // The loop is the likely path of execution
+  }
+
+  for(const auto &E : Elements) [[likely]] {
+    ...               // The loop is the likely path of execution
+  }
+
+  while(i != size) [[unlikely]] {
+    ...               // The loop is the unlikely path of execution
+  }                   // The generated code will optimize to skip the loop body
+
+  while(true) [[unlikely]] {
+    ...               // The attribute has no effect
+  }                   // Clang elides the comparison and generates an infinite
+                      // loop
+
   }];
 }
 
 def ARMInterruptDocs : Documentation {
   let Category = DocCatFunction;
   let Heading = "interrupt (ARM)";
   let Content = [{
 Clang supports the GNU style ``__attribute__((interrupt("TYPE")))`` attribute on
 ARM targets. This attribute may be attached to a function definition and
 instructs the backend to generate appropriate function entry/exit code so that

clang/include/clang/Basic/DiagnosticSemaKinds.td

def warn_attributes_likelihood_ifstmt_conflict
     : Warning<"conflicting attributes %0 are ignored">,
       InGroup<IgnoredAttributes>;
 def warn_cxx11_gnu_attribute_on_type : Warning<
   "attribute %0 ignored, because it cannot be applied to a type">,
   InGroup<IgnoredAttributes>;
 def warn_unhandled_ms_attribute_ignored : Warning<
   "__declspec attribute %0 is not supported">,
   InGroup<IgnoredAttributes>;
+def warn_attribute_has_no_effect_on_infinite_loop : Warning<
+  "attribute %0 has no effect when annotating an infinite loop">,
+   InGroup<IgnoredAttributes>;
+def note_attribute_has_no_effect_on_infinite_loop_here : Note<
+  "annotating the infinite loop here">;
 def err_decl_attribute_invalid_on_stmt : Error<
   "%0 attribute cannot be applied to a statement">;
 def err_stmt_attribute_invalid_on_decl : Error<
   "%0 attribute cannot be applied to a declaration">;
 def warn_declspec_attribute_ignored : Warning<
   "attribute %0 is ignored, place it after "
   "\"%select{class|struct|interface|union|enum}1\" to apply attribute to "
   "type declaration">, InGroup<IgnoredAttributes>;

clang/lib/AST/Stmt.cpp

 Stmt::Likelihood Stmt::getLikelihood(ArrayRef<const Attr *> Attrs) {
   return ::getLikelihood(Attrs).first;
 }
 
 Stmt::Likelihood Stmt::getLikelihood(const Stmt *S) {
   return ::getLikelihood(S).first;
 }
 
+const Attr *Stmt::getLikelihoodAttr(const Stmt *S) {
+  return ::getLikelihood(S).second;
+}
+
 Stmt::Likelihood Stmt::getLikelihood(const Stmt *Then, const Stmt *Else) {
   Likelihood LHT = ::getLikelihood(Then).first;
   Likelihood LHE = ::getLikelihood(Else).first;
   if (LHE == LH_None)
     return LHT;
 
   // If the same attribute is used on both branches there's a conflict.
   if (LHT == LHE)

clang/lib/CodeGen/CGStmt.cpp

 #include "CGDebugInfo.h"
 #include "CGOpenMPRuntime.h"
 #include "CodeGenFunction.h"
 #include "CodeGenModule.h"
 #include "TargetInfo.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Basic/Builtins.h"
+#include "clang/Basic/DiagnosticSema.h"
 #include "clang/Basic/PrettyStackTrace.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Intrinsics.h"
if (C->isOne())
       EmitBoolCondBranch = false;
 
   // As long as the condition is true, go to the loop body.
   llvm::BasicBlock *LoopBody = createBasicBlock("while.body");
   if (EmitBoolCondBranch) {
     llvm::BasicBlock *ExitBlock = LoopExit.getBlock();
     if (ConditionScope.requiresCleanups())
       ExitBlock = createBasicBlock("while.exit");
-    Builder.CreateCondBr(
-        BoolCondVal, LoopBody, ExitBlock,
-        createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody())));
+    llvm::MDNode *Weights = createProfileOrBranchWeightsForLoop(
+        S.getCond(), getProfileCount(S.getBody()), S.getBody());
+    Builder.CreateCondBr(BoolCondVal, LoopBody, ExitBlock, Weights);
 
     if (ExitBlock != LoopExit.getBlock()) {
       EmitBlock(ExitBlock);
       EmitBranchThroughCleanup(LoopExit);
     }
+  } else if (const Attr *A = Stmt::getLikelihoodAttr(S.getBody())) {
+    CGM.getDiags().Report(A->getLocation(),
+                          diag::warn_attribute_has_no_effect_on_infinite_loop)
+        << A << A->getRange();
+    CGM.getDiags().Report(
+        S.getWhileLoc(),
+        diag::note_attribute_has_no_effect_on_infinite_loop_here)
+        << SourceRange(S.getWhileLoc(), S.getRParenLoc());
   }
 
   // Emit the loop body.  We have to emit this in a cleanup scope
   // because it might be a singleton DeclStmt.
   {
     RunCleanupsScope BodyScope(*this);
     EmitBlock(LoopBody);
     incrementProfileCounter(&S);
if (ForScope.requiresCleanups())
       ExitBlock = createBasicBlock("for.cond.cleanup");
 
     // As long as the condition is true, iterate the loop.
     llvm::BasicBlock *ForBody = createBasicBlock("for.body");
 
     // C99 6.8.5p2/p4: The first substatement is executed if the expression
     // compares unequal to 0.  The condition must be a scalar type.
     llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond());
-    Builder.CreateCondBr(
-        BoolCondVal, ForBody, ExitBlock,
-        createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody())));
+    llvm::MDNode *Weights = createProfileOrBranchWeightsForLoop(
+        S.getCond(), getProfileCount(S.getBody()), S.getBody());
+    Builder.CreateCondBr(BoolCondVal, ForBody, ExitBlock, Weights);
 
     if (ExitBlock != LoopExit.getBlock()) {
       EmitBlock(ExitBlock);
       EmitBranchThroughCleanup(LoopExit);
     }
 
     EmitBlock(ForBody);
   } else {
if (ForScope.requiresCleanups())
     ExitBlock = createBasicBlock("for.cond.cleanup");
 
   // The loop body, consisting of the specified body and the loop variable.
   llvm::BasicBlock *ForBody = createBasicBlock("for.body");
 
   // The body is executed if the expression, contextually converted
   // to bool, is true.
   llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond());
-  Builder.CreateCondBr(
-      BoolCondVal, ForBody, ExitBlock,
-      createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody())));
+  llvm::MDNode *Weights = createProfileOrBranchWeightsForLoop(
+      S.getCond(), getProfileCount(S.getBody()), S.getBody());
+  Builder.CreateCondBr(BoolCondVal, ForBody, ExitBlock, Weights);
 
   if (ExitBlock != LoopExit.getBlock()) {
     EmitBlock(ExitBlock);
     EmitBranchThroughCleanup(LoopExit);
   }
 
   EmitBlock(ForBody);
   incrementProfileCounter(&S);

clang/lib/CodeGen/CodeGenFunction.h

private:
 
   /// Calculate branch weights appropriate for PGO data
   llvm::MDNode *createProfileWeights(uint64_t TrueCount,
                                      uint64_t FalseCount) const;
   llvm::MDNode *createProfileWeights(ArrayRef<uint64_t> Weights) const;
   llvm::MDNode *createProfileWeightsForLoop(const Stmt *Cond,
                                             uint64_t LoopCount) const;
 
+  /// Calculate the branch weight for PGO data or the likelihood attribute.
+  /// The function tries to get the weight of \ref createProfileWeightsForLoop.
+  /// If that fails it gets the weight of \ref createBranchWeights.
+  llvm::MDNode *createProfileOrBranchWeightsForLoop(const Stmt *Cond,
+                                                    uint64_t LoopCount,
+                                                    const Stmt *Body) const;
+
 public:
   /// Increment the profiler's counter for the given statement by \p StepV.
   /// If \p StepV is null, the default increment is 1.
   void incrementProfileCounter(const Stmt *S, llvm::Value *StepV = nullptr) {
     if (CGM.getCodeGenOpts().hasProfileClangInstr())
       PGO.emitCounterIncrement(Builder, S, StepV);
     PGO.setCurrentStmt(S);
   }

clang/lib/CodeGen/CodeGenFunction.cpp

 llvm::MDNode *CodeGenFunction::createBranchWeights(Stmt::Likelihood LH) const {
   Optional<std::pair<uint32_t, uint32_t>> LHW = getLikelihoodWeights(LH);
   if (!LHW)
     return nullptr;
 
   llvm::MDBuilder MDHelper(CGM.getLLVMContext());
   return MDHelper.createBranchWeights(LHW->first, LHW->second);
 }
+
+llvm::MDNode *CodeGenFunction::createProfileOrBranchWeightsForLoop(
+    const Stmt *Cond, uint64_t LoopCount, const Stmt *Body) const {
+  llvm::MDNode *Weights = createProfileWeightsForLoop(Cond, LoopCount);
+  if (!Weights && CGM.getCodeGenOpts().OptimizationLevel)
+    Weights = createBranchWeights(Stmt::getLikelihood(Body));
+
+  return Weights;
+}

clang/test/CodeGenCXX/attr-likelihood-if-branch-weights.cpp

 void WhileStmt() {
   // CHECK-LABEL: define{{.*}}WhileStmt
   // CHECK: br {{.*}} !prof !8
   if (b)
     [[unlikely]] while (B()) {}
 
   // CHECK-NOT: br {{.*}} %if.end{{.*}} !prof
   if (b)
+    // CHECK: br {{.*}} !prof !7
     while (B())
       [[unlikely]] { b = false; }
 }
 
 void DoStmt() {
   // CHECK-LABEL: define{{.*}}DoStmt
   // CHECK: br {{.*}} !prof !8
   if (b)

 void ForStmt() {
   // CHECK-LABEL: define{{.*}}ForStmt
   // CHECK: br {{.*}} !prof !8
   if (b)
     [[unlikely]] for (; B();) {}
 
   // CHECK-NOT: br {{.*}} %if.end{{.*}} !prof
   if (b)
+    // CHECK: br {{.*}} !prof !7
     for (; B();)
       [[unlikely]] {}
 }
 
 void GotoStmt() {
   // CHECK-LABEL: define{{.*}}GotoStmt
   // CHECK: br {{.*}} !prof !8
   if (b)

clang/test/CodeGenCXX/attr-likelihood-iteration-stmt.cpp

+// RUN: %clang_cc1 -O1 -disable-llvm-passes -emit-llvm %s -o - -triple=x86_64-linux-gnu -verify
+// RUN: %clang_cc1 -O1 -disable-llvm-passes -emit-llvm %s -o - -triple=x86_64-linux-gnu | FileCheck %s
+
+void wl(int e){
+  // CHECK-LABEL: define{{.*}}wl
+  // CHECK: br {{.*}} !prof !6
+  while(e) [[likely]] ++e;
+}
+
+void wu(int e){
+  // CHECK-LABEL: define{{.*}}wu
+  // CHECK: br {{.*}} !prof !9
+  while(e) [[unlikely]] ++e;
+}
+
+void w_branch_elided(unsigned e){
+  // CHECK-LABEL: define{{.*}}w_branch_elided
+  // CHECK-NOT: br {{.*}} !prof
+  // expected-warning@+2 {{attribute 'likely' has no effect when annotating an infinite loop}}
+  // expected-note@+1 {{annotating the infinite loop here}}
+  while(1) [[likely]] ++e;
+}
+
+void fl(unsigned e)
+{
+  // CHECK-LABEL: define{{.*}}fl
+  // CHECK: br {{.*}} !prof !6
+  for(int i = 0; i != e; ++e) [[likely]];
+}
+
+void fu(int e)
+{
+  // CHECK-LABEL: define{{.*}}fu
+  // CHECK: br {{.*}} !prof !9
+  for(int i = 0; i != e; ++e) [[unlikely]];
+}
+
+void f_branch_elided()
+{
+  // CHECK-LABEL: define{{.*}}f_branch_elided
+  // CHECK-NOT: br {{.*}} !prof
+  for(;;) [[likely]];
+}
+
+void frl(int (&&e) [4])
+{
+  // CHECK-LABEL: define{{.*}}frl
+  // CHECK: br {{.*}} !prof !6
+  for(int i : e) [[likely]];
+}
+
+void fru(int (&&e) [4])
+{
+  // CHECK-LABEL: define{{.*}}fru
+  // CHECK: br {{.*}} !prof !9
+  for(int i : e) [[unlikely]];
+}
+
+// CHECK: !6 = !{!"branch_weights", i32 2000, i32 1}
+// CHECK: !9 = !{!"branch_weights", i32 1, i32 2000}