lower __builtin_expect() directly to prof metadata instead of LLVM intrinsic

[spatel]

Summary

__builtin_expect() is a GCC-derived builtin that's used as a hint for branch prediction:
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

The Clang/LLVM implementation of this feature introduced an LLVM intrinsic to convey the hint to the optimizer:
https://marc.info/?l=llvm-commits&m=130997676129580&w=4

There are problems with this (and several were noted in the above thread, but it didn't change the outcome):

1. We created an intrinsic to improve perf, but the intrinsic can harm optimization by interfering with other passes.

2. To solve that, create a pass to always transform the intrinsic into metadata at a very early stage. But now every program is paying a compile-time tax for a feature that is rarely used.

3. The IR lowering uses profile weight metadata as the means for conveying the hint. But the hint is meant to be a programmer override for profile data. That is, "I don't care what the profile says; I want my code to use this source-level hint." So it should use a different kind of metadata, not profile weight. We added the inverse programmer hint as metadata - __builtin_unpredictable():

http://llvm.org/docs/LangRef.html#unpredictable-metadata
http://reviews.llvm.org/D12341
so I think we can enhance that to solve this problem.

This patch is an intermediate step. It doesn't try to solve #3 above, but it handles #1 and clears the way to deprecate the llvm.expect intrinsic and delete the LowerExpectIntrinsic pass (problem #2).

This is part of solving:
https://llvm.org/bugs/show_bug.cgi?id=27344
But to complete that, we need to make changes in SimplifyCFG and possibly other places, so that we're propagating and using the expect/unpredictable metadata as intended. Ref: D18133, D18220, rL264527, rL266442

[davidxl]

I like the direction this patch is going. Will look into details soon.

[deadalnix]

lib/CodeGen/CGStmt.cpp

1565–1593

If I understand properly this is transitional and eventually, you want to remove the intrinsic ? I think I like it, having 2 ways to hint here is only making things more complicated without adding much value.

[spatel]

lib/CodeGen/CGStmt.cpp

1565–1593

Yes, I want to merge the handling of builtin_expect and builtin_unpredictable. Currently, the 'unpredictable' metadata has no parameters; it is an empty string like:

br i1 %or.cond, label %bb3, label %bb4, !unpredictable !2
...
!2 = !{}

In D12341, we considered having an integer parameter value that would be a measure of the unpredictability. For example, this could be used with PGO if someone had collected branch mispredict data as part of a profiling run.

So as a first proposal, let's say we add an integer parameter for predictability for this metadata type. We could define '-1' to mean 'perfectly predictable' and so builtin_expect would map to this:

!2 = !{-1 42}   <--- perfectly predictable with expected value of '42'

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

So, yes this patch is transitional - hopefully, no more than a few days. I'm going to audit where we actually use profile data to make transform decisions. Once those places (I'm assuming they actually exist!) are updated to look at the unpredictable metadata, we can fix up this clang code to match the optimizer's algorithms.

[spatel]

[reposting this as a general comment because the inline comment did not seem to make it to the mailing list]

Yes, I want to merge the handling of builtin_expect and builtin_unpredictable. Currently, the 'unpredictable' metadata has no parameters; it is an empty string like:

br i1 %or.cond, label %bb3, label %bb4, !unpredictable !2
...
!2 = !{}

In D12341, we considered having an integer parameter value that would be a measure of the unpredictability. For example, this could be used with PGO if someone had collected branch mispredict data as part of a profiling run.

So as a first proposal, let's say we add an integer parameter for predictability for this metadata type. We could define '-1' to mean 'perfectly predictable' and so builtin_expect would map to this:

!2 = !{-1 42}   <--- perfectly predictable with expected value of '42'

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

So, yes this patch is transitional - hopefully, no more than a few days. I'm going to audit where we actually use profile data to make transform decisions. Once those places (I'm assuming they actually exist!) are updated to look at the unpredictable metadata, we can fix up this clang code to match the optimizer's algorithms.

[davidxl]

lib/CodeGen/CGBuiltin.cpp

636–637

Can this be reordered with unpredicatle case so that it can handle arg 1 and fall through?

lib/CodeGen/CGStmt.cpp

1550

update the comment here.

1567

I am not sure about this. builtin_expect can be used to do general value profiling annotation (single value). For instance,

if (builtin_expect(a, 20) > 10) {
}

should have same effect as

if (builtin_expect(a > 10), true) {

}

The above can be handled by gcc, but not LLVM.

It can be useful for switch case annotation:

switch (__builtin_expect(v, 20) ) {
case 10: ...
case 20: ...
...
}
where compiler can do switch peeling.

Longer term, I am thinking extending builtin_expect to take list of values with probabilities and predicatibiity hint.

1571

Unpredicable meta data is probably not suitable for switch annotation. builtin_expect can be used to specify one case that is more likely to be taken thus helping switch lowering decision (not used in the cases such as if conversion).

lib/CodeGen/CodeGenFunction.cpp

1311–1312

Update comment here.

1331

I suggest removing these comments.

[spatel]

lib/CodeGen/CGStmt.cpp

1567

Ah, I hadn't considered extending builtin_expect in that way. In that case, it does make sense to leave it as-is here and use prof metadata because it's already set up for a list of values.

I'll clean up and re-post the patch. Thanks everyone for the reviews!

[deadalnix]

In D19299#406517, @spatel wrote:

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

You did answer my question. I don't really mind source level intrinsic, I'm more concerned about the IR and how they are lowered. Overall I like where this is going. It looks like @davidxl is on it for the review, and he seems to have a good idea of where this should go, so I'll defer to him for acceptance/change requests.

[spatel]

lib/CodeGen/CGBuiltin.cpp

636–637

I had coded it that way initially, but I think we must emit the expression for arg0 *before* the expression for arg1.

The ordering is checked by the 'main()' test in the regression test file. If you see a way to code around that, please let me know.

[spatel]

Patch updated:

1. Fixed/removed comments
2. Changed likely/unlikely profile weights to be min/max values. I'm not sure why 4 and 64 were used in LowerExpectIntrinsics, but that may not trigger the programmer's intent with builtin_expect().

[davidxl]

lgtm

[spatel]

Abandoning.

The feedback on the dev list was that handling the builtin_expect() in clang is ugly, so it's better to pay a small cost in LLVM to do it.

Note that the current llvm.expect lowering pass doesn't actually work for anything but the simplest cases. The pass needs to be enhanced to handle patterns like:

int foo(int x, int y) {
  if (__builtin_expect(x, 20) > 10) return 234;  // expected value is not 1
  return 2;
}

or:

int foo(int n) {
  int b = __builtin_expect(n, 1);  // expect is not directly used in comparison
  if (b) return 24;
  return 234;
}

Currently, the llvm.expect is discarded in these cases without generating any metadata.

lib/CodeGen/CGBuiltin.cpp

case Builtin::BI__builtin_popcountll: {
 
     llvm::Type *ResultType = ConvertType(E->getType());
     Value *Result = Builder.CreateCall(F, ArgValue);
     if (Result->getType() != ResultType)
       Result = Builder.CreateIntCast(Result, ResultType, /*isSigned*/true,
                                      "cast");
     return RValue::get(Result);
   }
-  case Builtin::BI__builtin_unpredictable: {
-    // Always return the argument of __builtin_unpredictable. LLVM does not
-    // handle this builtin. Metadata for this builtin should be added directly
-    // to instructions such as branches or switches that use it.
-    return RValue::get(EmitScalarExpr(E->getArg(0)));
-  }
+
+  case Builtin::BI__builtin_unpredictable:
   case Builtin::BI__builtin_expect: {
-    Value *ArgValue = EmitScalarExpr(E->getArg(0));
-    llvm::Type *ArgType = ArgValue->getType();
+    // Always return the first argument. LLVM does not handle these builtins.
+    // Metadata for these builtins should be added directly to instructions such
+    // as branches or switches that use the builtin.
+    Value *Arg0 = EmitScalarExpr(E->getArg(0));
 
-    Value *ExpectedValue = EmitScalarExpr(E->getArg(1));
-    // Don't generate llvm.expect on -O0 as the backend won't use it for
-    // anything.
-    // Note, we still IRGen ExpectedValue because it could have side-effects.
-    if (CGM.getCodeGenOpts().OptimizationLevel == 0)
-      return RValue::get(ArgValue);
+    // We must IRGen the expected value of builtin_expect because it could have
+    // side-effects.
+    if (BuiltinID == Builtin::BI__builtin_expect)
+      EmitScalarExpr(E->getArg(1));
 
-    Value *FnExpect = CGM.getIntrinsic(Intrinsic::expect, ArgType);
-    Value *Result =
-        Builder.CreateCall(FnExpect, {ArgValue, ExpectedValue}, "expval");
-    return RValue::get(Result);
+    return RValue::get(Arg0);
   }
+
   case Builtin::BI__builtin_assume_aligned: {
     Value *PtrValue = EmitScalarExpr(E->getArg(0));
     Value *OffsetValue =
       (E->getNumArgs() > 2) ? EmitScalarExpr(E->getArg(2)) : nullptr;
 
     Value *AlignmentValue = EmitScalarExpr(E->getArg(1));
     ConstantInt *AlignmentCI = cast<ConstantInt>(AlignmentValue);
     unsigned Alignment = (unsigned) AlignmentCI->getZExtValue();

lib/CodeGen/CGStmt.cpp

void CodeGenFunction::EmitSwitchStmt(const SwitchStmt &S) {
   }
 
   ConditionScope.ForceCleanup();
 
   // Emit continuation.
   EmitBlock(SwitchExit.getBlock(), true);
   incrementProfileCounter(&S);
 
   // If the switch has a condition wrapped by __builtin_unpredictable,
   // create metadata that specifies that the switch is unpredictable.
-  // Don't bother if not optimizing because that metadata would not be used.
+  //
+  // If the switch has a condition wrapped by __builtin_expect, create
+  // metadata that sets the profile weights to the extreme values.
+  //
+  // But don't add performance metadata if not optimizing because that metadata
+  // would not be used anyway.
   auto *Call = dyn_cast<CallExpr>(S.getCond());
   if (Call && CGM.getCodeGenOpts().OptimizationLevel != 0) {
-    auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl());
-    if (FD && FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
+    if (auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl())) {
       llvm::MDBuilder MDHelper(getLLVMContext());
+      if (FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
         SwitchInsn->setMetadata(llvm::LLVMContext::MD_unpredictable,
                                 MDHelper.createUnpredictable());
+      } else if (FD->getBuiltinID() == Builtin::BI__builtin_expect) {
+        const int LikelyWeight = ~0;
+        const int UnlikelyWeight = 0;
+        
+        llvm::Value *ExpectedVal = EmitScalarExpr(Call->getArg(1));
+        if (auto *ExpectConst = dyn_cast<llvm::ConstantInt>(ExpectedVal)) {
+          // The +1 is for the default case.
+          SmallVector<uint32_t, 16> Weights(SwitchInsn->getNumCases() + 1,
+                                            UnlikelyWeight);
+          auto ExpectedCase = SwitchInsn->findCaseValue(ExpectConst);
+          if (ExpectedCase == SwitchInsn->case_default())
+            Weights[0] = LikelyWeight;
+          else
+            Weights[ExpectedCase.getCaseIndex() + 1] = LikelyWeight;
+
+          SwitchInsn->setMetadata(llvm::LLVMContext::MD_prof,
+                                  MDHelper.createBranchWeights(Weights));
+        }
+      }
     }
   }
 
-  if (SwitchWeights) {
+  if (!SwitchInsn->getMetadata(llvm::LLVMContext::MD_prof) && SwitchWeights) {
     assert(SwitchWeights->size() == 1 + SwitchInsn->getNumCases() &&
            "switch weights do not match switch cases");
     // If there's only one jump destination there's no sense weighting it.
     if (SwitchWeights->size() > 1)
       SwitchInsn->setMetadata(llvm::LLVMContext::MD_prof,
                               createProfileWeights(*SwitchWeights));
     delete SwitchWeights;
   }
   SwitchInsn = SavedSwitchInsn;
   SwitchWeights = SavedSwitchWeights;
   CaseRangeBlock = SavedCRBlock;
 }
 
 static std::string

lib/CodeGen/CodeGenFunction.cpp

if (const CXXThrowExpr *Throw = dyn_cast<CXXThrowExpr>(Cond)) {
     // Conditional operator handling can give us a throw expression as a
     // condition for a case like:
     //   br(c ? throw x : y, t, f) -> br(c, br(throw x, t, f), br(y, t, f)
     // Fold this to:
     //   br(c, throw x, br(y, t, f))
     EmitCXXThrowExpr(Throw, /*KeepInsertionPoint*/false);
     return;
   }
 
-  // If the branch has a condition wrapped by __builtin_unpredictable,
-  // create metadata that specifies that the branch is unpredictable.
-  // Don't bother if not optimizing because that metadata would not be used.
   llvm::MDNode *Unpredictable = nullptr;
+  llvm::MDNode *Weights = nullptr;
   auto *Call = dyn_cast<CallExpr>(Cond);
+
+  // If the branch has a condition wrapped by __builtin_unpredictable,
+  // create metadata that specifies that the branch is unpredictable.
+  //
+  // If the branch has a condition wrapped by __builtin_expect, create
+  // metadata that sets the profile weights to the extreme values.
+  //
+  // But don't add performance metadata if not optimizing because that metadata
+  // would not be used anyway.
   if (Call && CGM.getCodeGenOpts().OptimizationLevel != 0) {
-    auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl());
-    if (FD && FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
+    if (auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl())) {
       llvm::MDBuilder MDHelper(getLLVMContext());
+      if (FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
         Unpredictable = MDHelper.createUnpredictable();
+      } else if (FD->getBuiltinID() == Builtin::BI__builtin_expect) {
+        const int LikelyWeight = ~0;
+        const int UnlikelyWeight = 0;
+
+        llvm::Value *ExpectedVal = EmitScalarExpr(Call->getArg(1));
+        auto *ExpectedConst = dyn_cast<llvm::ConstantInt>(ExpectedVal);
+
+        // If expecting the false case, set that side to the likely weight.
+        if (ExpectedConst && ExpectedConst->isNullValue())
+          Weights = MDHelper.createBranchWeights(UnlikelyWeight, LikelyWeight);
+        else
+          Weights = MDHelper.createBranchWeights(LikelyWeight, UnlikelyWeight);
+      }
     }
   }
 
   // Create branch weights based on the number of times we get here and the
   // number of times the condition should be true.
+  if (!Weights) {
     uint64_t CurrentCount = std::max(getCurrentProfileCount(), TrueCount);
-  llvm::MDNode *Weights =
-      createProfileWeights(TrueCount, CurrentCount - TrueCount);
+    Weights = createProfileWeights(TrueCount, CurrentCount - TrueCount);
+  }
 
   // Emit the code with the fully general case.
   llvm::Value *CondV;
   {
     ApplyDebugLocation DL(*this, Cond);
     CondV = EvaluateExprAsBool(Cond);
   }
   Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights, Unpredictable);

test/CodeGen/builtin-expect.c

 // RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm -o - %s -O1 -disable-llvm-optzns | FileCheck %s --check-prefix=ALL --check-prefix=O1
 // RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm -o - %s -O0 | FileCheck %s --check-prefix=ALL --check-prefix=O0
 
-// In all tests, make sure that no expect is generated if optimizations are off.
-// If optimizations are on, generate the correct expect and preserve other necessary operations.
+// In all tests, make sure that the builtin is gone.
+// If optimizations are on, generate the correct expect metadata and preserve other necessary operations.
+// If optimizations are off, no expect metadata is generated but other operations should be preserved.
 
 int expect_taken(int x) {
 // ALL-LABEL: define i32 @expect_taken
-// O1:        call i64 @llvm.expect.i64(i64 {{%.*}}, i64 1)
-// O0-NOT:    @llvm.expect
+// ALL-NOT:   builtin_expect
+// O1:        !prof [[BR_TRUE_METADATA:.+]]
+// O0-NOT:    !prof
 
   if (__builtin_expect (x, 1))
     return 0;
   return x;
 }
 
 
 int expect_not_taken(int x) {
 // ALL-LABEL: define i32 @expect_not_taken
-// O1:        call i64 @llvm.expect.i64(i64 {{%.*}}, i64 0)
-// O0-NOT:    @llvm.expect
+// ALL-NOT:   builtin_expect
+// O1:        !prof [[BR_FALSE_METADATA:.+]]
+// O0-NOT:    !prof
 
   if (__builtin_expect (x, 0))
     return 0;
   return x;
 }
 
 
 int x;
 int y(void);
 void foo();
 
 void expect_value_side_effects() {
 // ALL-LABEL: define void @expect_value_side_effects()
 // ALL:       [[CALL:%.*]] = call i32 @y
+// ALL-NOT:   builtin_expect
 // O1:        [[SEXT:%.*]] = sext i32 [[CALL]] to i64
-// O1:        call i64 @llvm.expect.i64(i64 {{%.*}}, i64 [[SEXT]])
-// O0-NOT:    @llvm.expect
+// O1:        !prof [[BR_TRUE_METADATA:.+]]
+// O0-NOT:    !prof
 
   if (__builtin_expect (x, y()))
     foo ();
 }
 
 
 // Make sure that issigprocmask() is called before bar()?
 // There's no compare, so there's nothing to expect?
 // rdar://9330105
 void isigprocmask(void);
 long bar();
 
 int main() {
 // ALL-LABEL: define i32 @main()
 // ALL:       call void @isigprocmask()
 // ALL:       [[CALL:%.*]] = call i64 (...) @bar()
-// O1:        call i64 @llvm.expect.i64(i64 0, i64 [[CALL]])
-// O0-NOT:    @llvm.expect
+// ALL-NOT:   builtin_expect
+// ALL-NOT:   !prof
 
   (void) __builtin_expect((isigprocmask(), 0), bar());
 }
 
 
 int switch_cond(int x) {
 // ALL-LABEL: define i32 @switch_cond
-// O1:        call i64 @llvm.expect.i64(i64 {{%.*}}, i64 5)
-// O0-NOT:    @llvm.expect
+// ALL-NOT:   builtin_expect
+// O1:        !prof [[SWITCH_METADATA:.+]]
+// O0-NOT:    !prof
 
   switch(__builtin_expect(x, 5)) {
   default:
     return 0;
   case 0:
   case 1:
   case 2:
     return 1;
   case 5:
     return 5;
   };
 
   return 0;
 }
 
+// O1: [[BR_TRUE_METADATA]] = !{!"branch_weights", i32 -1, i32 0}
+// O1: [[BR_FALSE_METADATA]] = !{!"branch_weights", i32 0, i32 -1}
+// O1: [[SWITCH_METADATA]] = !{!"branch_weights", i32 0, i32 0, i32 0, i32 0, i32 -1}
+