RFC: Add getLikelyBranchWeight helper function

[MatzeB]

Summary

• Add getLikelyBranchWeight() function returning the value of the -likely-branch-weight option defaulting to 2000.
• Remove -unlikely-branch-weight option and just use 1.

[MatzeB]

Putting this out as a strawman/RFC. Should we add this function to allow LLVM passes to construct "likely"/"unlikely" branch_weights metadata? (I need this in D158642 and D157462)

[paulkirth]

My initial reaction to this was that we should keep the --unlikely-branch-weights flag available, even if we decide to move forward with the other changes. but given that you haven't had to update many tests, I think its probably fine to go this way. Probably just an FYI on discourse is sufficient to notify potential downstream consumers.

As for exposing the Likely/unlikely weights ... I'm a bit conflicted. On one hand, I would love a simple way to query the current weights for MisExpect diagnostics, and some of the other things we've been prototyping like suggesting places where annotations would be profitable. On the other hand, I dislike exposing some internal detail of a pass.

That said, it seems like these have more value when exposed, so I think it woudl be fine, as long as we can prevent frontends from using the APIs, like you mentioned in https://reviews.llvm.org/D158642#4611025.

I'm not sure how to separate the APIs the way we want, though. Most of the APIs in "ProfDataUtils.h" are desirable to be public, which means include is a good place for them, but getLikelyBranchWeight may not fit well in that regard... Maybe we need an internal header in lib? or perhaps I'm thinking bout this too much...

[MatzeB]

My initial reaction to this was that we should keep the --unlikely-branch-weights flag available

I don't feel strongly about it and can put it back. But can you give some reasoning? I only see this flag having a real use to express small ratios like 3:2 which doesn't really seem helpful to express "likely"/"unlikely"...

[MatzeB]

On the other hand, I dislike exposing some internal detail of a pass.

I think the question to ask is whether a concept like "likely branch" or "unlikely branch" shouldn't be more universal and not be a pass internal detail? Otherwise it feels like my patches and other places would need to insert new llvm.expect usages into the IR and add more instances of LowerExpect pass into the pipeline to not risk pass ordering problems for the small gain of having a more abstract representation...

[MatzeB]

And as another strawman / discussion-starter I put up D158680 where I use !{"branch_weights", i32 1, i32 0} to represent likely branches and the actual "LikelyWeight" mostly becomes an internal implementation detail of the BranchProbabilityInfo class... This seemed like a neat way to get an abstract "likely", "unlikely" notation, but not sure of the effects if we no longer would have "truly zero" weights because they would be interpreted differently now...

[paulkirth]

In D158668#4611842, @MatzeB wrote:

My initial reaction to this was that we should keep the --unlikely-branch-weights flag available

I don't feel strongly about it and can put it back. But can you give some reasoning? I only see this flag having a real use to express small ratios like 3:2 which doesn't really seem helpful to express "likely"/"unlikely"...

I think the rest of the comment agrees w/ you that it probably isn't that useful :)

My concern was testing, but given that you've barley had to update anything, I'd say that early feeling is just wrong, since we aren't using it except in a handful of cases. As such I think it can go away w/ only a short FYI about a planned change.

In D158668#4611845, @MatzeB wrote:

On the other hand, I dislike exposing some internal detail of a pass.

I think the question to ask is whether a concept like "likely branch" or "unlikely branch" shouldn't be more universal and not be a pass internal detail? Otherwise it feels like my patches and other places would need to insert new llvm.expect usages into the IR and add more instances of LowerExpect pass into the pipeline to not risk pass ordering problems for the small gain of having a more abstract representation...

Again, I think the comments directly following agree w/ your position:

That said, it seems like these have more value when exposed, so I think it would be fine, as long as we can prevent frontends from using the APIs, like you mentioned in https://reviews.llvm.org/D158642#4611025.

I think he fact that we're discussing this means it isn't functionally internal anymore, so that's maybe reason enough to do this.

So to clarify, I'm broadly in favor of this direction. I'd also posit, that maybe since we're changing this we should reevaluate the numbers we use as defaults.

[MatzeB]

I'd also posit, that maybe since we're changing this we should reevaluate the numbers we use as defaults.

Heh, same here. Internally we have a handful of functions that end up using [[likely]] loop conditions in a triple-nested loops leading to the estimated block frequencies going through the roof and unjustly dominating everything else in the program... Though admittedly I am not decided yet whether I want to blame the 2000:1 ratio or rather the programmers for using the annotation too freely.

There is also a disconnect with the GCC documentation saying __builtin_expect corresponding to a 90% probability ( https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gcc/Other-Builtins.html )

Anyway we probably need a separate/patch discussion to not derail this diff too much...

[MatzeB]

I have a feeling @mtrofin would prefer pass-specific weights rather than a unified notion of "likely"/"unlikely"... So with the latest round of patches it's probably best to abandon this for now.

[wenlei]

In D158668#4611988, @MatzeB wrote:

And as another strawman / discussion-starter I put up D158680 where I use !{"branch_weights", i32 1, i32 0} to represent likely branches and the actual "LikelyWeight" mostly becomes an internal implementation detail of the BranchProbabilityInfo class... This seemed like a neat way to get an abstract "likely", "unlikely" notation, but not sure of the effects if we no longer would have "truly zero" weights because they would be interpreted differently now...

Commented on that patch, I'm not convinced that canonicalize {X,0} -> {1,0} is a good idea mostly because: 1) we don't attempt to canonicalize {X*Z,Y*Z} -> {X,Y}; 2) there are places where the absolute values matters; 3) canonicalize branch_weights as a side effect of BPI seems not right.

Remove -unlikely-branch-weight option and just use 1.

Seems fine, I don't have a strong opinion.

Add getLikelyBranchWeight() function returning the value of the -likely-branch-weight option defaulting to 2000.

This makes sense to me.

prefer pass-specific weights rather than a unified notion of "likely"/"unlikely"... So with the latest round of patches it's probably best to abandon this for now.

I don't see them as mutually exclusive. In fact when I look at your other patches, I feel that we need a default likely/unlikely for cases where we just don't have a good answer, hence fall back to default. So the default likely/unlikely probability is a layer below pass-specific setting.

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

 // RUN: %clang_cc1 -O1 -emit-llvm %s -o - -triple=x86_64-linux-gnu | FileCheck -DLIKELY=2000 -DUNLIKELY=1 %s
-// RUN: %clang_cc1 -O1 -emit-llvm %s -triple=x86_64-linux-gnu -mllvm -likely-branch-weight=99 -mllvm -unlikely-branch-weight=42 -o - | FileCheck -DLIKELY=99 -DUNLIKELY=42 %s
+// RUN: %clang_cc1 -O1 -emit-llvm %s -triple=x86_64-linux-gnu -mllvm -likely-branch-weight=99 -o - | FileCheck -DLIKELY=99 %s
 
 extern volatile bool b;
 extern volatile int i;
 extern bool A();
 extern bool B();
 
 bool f() {
   // CHECK-LABEL: define{{.*}} zeroext i1 @_Z1fv
if (b)
     switch (i)
       [[unlikely]] {}
   else {
     // Make sure the branches aren't optimized away.
     b = true;
   }
 }
 
-// CHECK: ![[PROF_LIKELY]] = !{!"branch_weights", i32 [[UNLIKELY]], i32 [[LIKELY]]}
-// CHECK: ![[PROF_UNLIKELY]] = !{!"branch_weights", i32 [[LIKELY]], i32 [[UNLIKELY]]}
+// CHECK: ![[PROF_LIKELY]] = !{!"branch_weights", i32 1, i32 [[LIKELY]]}
+// CHECK: ![[PROF_UNLIKELY]] = !{!"branch_weights", i32 [[LIKELY]], i32 1

llvm/docs/MisExpect.rst

 
 There are 3 key places in the LLVM backend where branch weights are
 created and assigned based on profiling information or the use of the
 ``llvm.expect`` intrinsic, and our implementation focuses on these
 places to perform the verification.
 
 We calculate the threshold for emitting MisExpect related diagnostics
 based on the values the compiler assigns to ``llvm.expect`` intrinsics,
-which can be set through the ``-likely-branch-weight`` and
-``-unlikely-branch-weight`` LLVM options. During verification, if the
-profile weights mismatch the calculated threshold, then we will emit a
-remark or warning detailing a potential performance regression. The
-diagnostic also reports the percentage of the time the annotation was
-correct during profiling to help developers reason about how to proceed.
+which can be set through the ``-likely-branch-weight`` LLVM option.
+During verification, if the profile weights mismatch the calculated threshold,
+then we will emit a remark or warning detailing a potential performance
+regression. The diagnostic also reports the percentage of the time the
+annotation was correct during profiling to help developers reason about how
+to proceed.
 
 The diagnostics are also available in the form of optimization remarks,
 which can be serialized and processed through the ``opt-viewer.py``
 scripts in LLVM.
 
 .. option:: -pass-remarks=misexpect
 
   Enables optimization remarks for misexpect when profiling data conflicts with

llvm/include/llvm/IR/ProfDataUtils.h

 /// Retrieve the total of all weights from an instruction.
 ///
 /// \param I The instruction to extract the total weight from
 /// \param [out] TotalWeights input variable to fill with total weights
 /// \returns True on success with profile total weights filled in. False if no
 /// metadata was found.
 bool extractProfTotalWeight(const Instruction &I, uint64_t &TotalWeights);
 
+/// Return the weight for a "likely branch". A 1/LikelyBranchWeight ratio
+/// corresponds to the probability of `llvm.expect` matching the expected
+/// value.
+/// Note: There is also `TargetTransformInfo::getPredictableBranchThreshold`
+/// for a value matching the current target.
+uint32_t getLikelyBranchWeight();
+
 } // namespace llvm
 #endif

llvm/lib/IR/ProfDataUtils.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
+// These default values are chosen to represent an extremely skewed outcome for
+// a condition, but they leave some room for interpretation by later passes.
+//
+// If the documentation for __builtin_expect() was made explicit that it should
+// only be used in extreme cases, we could make this ratio higher. As it stands,
+// programmers may be using __builtin_expect() / llvm.expect to annotate that a
+// branch is likely or unlikely to be taken.
+
+static cl::opt<uint32_t> LikelyBranchWeight(
+    "likely-branch-weight", cl::Hidden, cl::init(2000),
+    cl::desc("Weight of the branch likely to be taken (default = 2000)"));
+
 namespace {
 
 // MD_prof nodes have the following layout
 //
 // In general:
 // { String name,         Array of i32   }
 //
 // In terms of Types:
bool extractProfTotalWeight(const MDNode *ProfileData, uint64_t &TotalVal) {
   }
   return false;
 }
 
 bool extractProfTotalWeight(const Instruction &I, uint64_t &TotalVal) {
   return extractProfTotalWeight(I.getMetadata(LLVMContext::MD_prof), TotalVal);
 }
 
+uint32_t getLikelyBranchWeight() { return LikelyBranchWeight; }
+
 } // namespace llvm

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/ProfDataUtils.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/MisExpect.h"
 
 #include <cmath>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lower-expect-intrinsic"
 
 STATISTIC(ExpectIntrinsicsHandled,
           "Number of 'expect' intrinsic instructions handled");
 
-// These default values are chosen to represent an extremely skewed outcome for
-// a condition, but they leave some room for interpretation by later passes.
-//
-// If the documentation for __builtin_expect() was made explicit that it should
-// only be used in extreme cases, we could make this ratio higher. As it stands,
-// programmers may be using __builtin_expect() / llvm.expect to annotate that a
-// branch is likely or unlikely to be taken.
-
-// WARNING: these values are internal implementation detail of the pass.
-// They should not be exposed to the outside of the pass, front-end codegen
-// should emit @llvm.expect intrinsics instead of using these weights directly.
-// Transforms should use TargetTransformInfo's getPredictableBranchThreshold().
-static cl::opt<uint32_t> LikelyBranchWeight(
-    "likely-branch-weight", cl::Hidden, cl::init(2000),
-    cl::desc("Weight of the branch likely to be taken (default = 2000)"));
-static cl::opt<uint32_t> UnlikelyBranchWeight(
-    "unlikely-branch-weight", cl::Hidden, cl::init(1),
-    cl::desc("Weight of the branch unlikely to be taken (default = 1)"));
-
 static std::tuple<uint32_t, uint32_t>
 getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount) {
   if (IntrinsicID == Intrinsic::expect) {
     // __builtin_expect
-    return std::make_tuple(LikelyBranchWeight.getValue(),
-                           UnlikelyBranchWeight.getValue());
+    return std::make_tuple(getLikelyBranchWeight(), 1);
   } else {
     // __builtin_expect_with_probability
     assert(CI->getNumOperands() >= 3 &&
            "expect with probability must have 3 arguments");
     auto *Confidence = cast<ConstantFP>(CI->getArgOperand(2));
     double TrueProb = Confidence->getValueAPF().convertToDouble();
     assert((TrueProb >= 0.0 && TrueProb <= 1.0) &&
            "probability value must be in the range [0.0, 1.0]");

llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll

-; RUN: opt -S -passes='function(lower-expect),strip-dead-prototypes' -likely-branch-weight=2147483647 -unlikely-branch-weight=1 < %s | FileCheck %s
+; RUN: opt -S -passes='function(lower-expect),strip-dead-prototypes' -likely-branch-weight=2147483647 < %s | FileCheck %s
 
 ; The C case
 ; if (__builtin_expect_with_probability(((a0 == 1) || (a1 == 1) || (a2 == 1)), 1, 0))
 ; For the above case, all 3 branches should be annotated
 ; which should be equivalent to if (__builtin_expect(((a0 == 1) || (a1 == 1) || (a2 == 1)), 0))
 
 ; The C case
 ; if (__builtin_expect_with_probability(((a0 == 1) || (a1 == 1) || (a2 == 1)), 1, 1))

llvm/test/Transforms/PGOProfile/misexpect-branch-overflow.ll

 ; Ensure that profile counters that overflow are handled correctly.
 ; This can happen when the sum of all counters exceeds the max size of uint32_t
 
 ; RUN: llvm-profdata merge %S/Inputs/misexpect-branch-overflow.proftext -o %t.profdata
-; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -unlikely-branch-weight=2147483648 -likely-branch-weight=2147483648 -S 2>&1 | FileCheck %s --check-prefix=OVERFLOW
+; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=OVERFLOW
 
 ; OVERFLOW-NOT: warning: misexpect-branch.c:22:0: 50.00%
 ; OVERFLOW-NOT: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 50.00% (2147483648 / 4294967296) of profiled executions.
 
 ; ModuleID = 'misexpect-branch.c'
 source_filename = "misexpect-branch.c"
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
entry:
   store i32 0, ptr %x, align 4, !dbg !14, !tbaa !10
   %0 = load i32, ptr %rando, align 4, !dbg !15, !tbaa !10
   %rem = srem i32 %0, 200000, !dbg !15
   %cmp = icmp eq i32 %rem, 0, !dbg !15
   %lnot = xor i1 %cmp, true, !dbg !15
   %lnot1 = xor i1 %lnot, true, !dbg !15
   %lnot.ext = zext i1 %lnot1 to i32, !dbg !15
   %conv = sext i32 %lnot.ext to i64, !dbg !15
-  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 1), !dbg !15
-  %tobool = icmp ne i64 %expval, 0, !dbg !15
-  br i1 %tobool, label %if.then, label %if.else, !dbg !15
+  %tobool = icmp ne i64 %conv, 0, !dbg !15
+  br i1 %tobool, label %if.then, label %if.else, !dbg !15, !prof !21
 
 if.then:                                          ; preds = %entry
   %1 = load i32, ptr %rando, align 4, !dbg !16, !tbaa !10
   %call2 = call i32 @baz(i32 %1), !dbg !16
   store i32 %call2, ptr %x, align 4, !dbg !16, !tbaa !10
   br label %if.end, !dbg !17
 
 if.else:                                          ; preds = %entry

 !13 = !{!"Simple C/C++ TBAA"}
 !14 = !DILocation(line: 21, scope: !6)
 !15 = !DILocation(line: 22, scope: !6)
 !16 = !DILocation(line: 23, scope: !6)
 !17 = !DILocation(line: 24, scope: !6)
 !18 = !DILocation(line: 25, scope: !6)
 !19 = !DILocation(line: 27, scope: !6)
 !20 = !DILocation(line: 28, scope: !6)
+!21 = !{!"branch_weights", i32 2147483648, i32 2147483648}