[SimplifyCFG] Don't speculatively execute BB if it's predictably not taken

[lebedev.ri]

Summary

If the branch isn't unpredictable, and it is predicted to *not* branch
to the block we are considering speculatively executing,
then it seems counter-productive to execute the code that is predicted not to be executed.

[spatel]

LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2380–2384

I think it would be easier to read without the potential double complement:

if (BI->extractProfMetadata(TWeight, FWeight) && (TWeight + FWeight) != 0) {
  uint64_t EndWeight = Invert ? TWeight : FWeight;
  BranchProbability BIEndProb =
      BranchProbability::getBranchProbability(EndWeight, TWeight + FWeight);

(although the meaning of Invert seems reversed from the code example in the function comment at line 2331)

llvm/test/Transforms/SimplifyCFG/speculatively-execute-block-profmd.ll

254

Add one more negative test to verify that we are respecting the TTI setting? It would need a different metadata - { 98, 2 } or similar.

[lebedev.ri]

In D106650#2902270, @spatel wrote:

LGTM

Thank you for the review!
Please note that D106717 is another similar patch.
I do hope to merge these two functions, but later.

[lebedev.ri]

A bit of necro-posting, but i was looking at this code again, and i'm wondering,
if the profile says that the only block that we are about to speculate
is predictably taken, does it actually make sense to speculate it,
incurring the cost of the select?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
   // to swap the select operands later.
   bool Invert = false;
   if (ThenBB != BI->getSuccessor(0)) {
     assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
     Invert = true;
   }
   assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
 
+  // If the branch is non-unpredictable, and is predicted to *not* branch to
+  // the `then` block, then avoid speculating it.
+  if (!BI->getMetadata(LLVMContext::MD_unpredictable)) {
+    uint64_t TWeight, FWeight;
+    if (BI->extractProfMetadata(TWeight, FWeight) && (TWeight + FWeight) != 0) {
+      uint64_t EndWeight = Invert ? TWeight : FWeight;
+      BranchProbability BIEndProb =
+          BranchProbability::getBranchProbability(EndWeight, TWeight + FWeight);
+      BranchProbability Likely = TTI.getPredictableBranchThreshold();
+      if (BIEndProb >= Likely)
+        return false;
+    }
+  }
+
   // Keep a count of how many times instructions are used within ThenBB when
   // they are candidates for sinking into ThenBB. Specifically:
   // - They are defined in BB, and
   // - They have no side effects, and
   // - All of their uses are in ThenBB.
   SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
 
   SmallVector<Instruction *, 4> SpeculatedDbgIntrinsics;

llvm/test/Transforms/SimplifyCFG/speculatively-execute-block-profmd.ll

 define i32 @predictably_nontaken(i1 %c, i32 %a, i32 %b) {
 ; CHECK-LABEL: @predictably_nontaken(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    call void @sideeffect0()
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[DISPATCH:%.*]], label [[END:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    call void @sideeffect1()
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[END]], label [[COND_TRUE:%.*]], !prof [[PROF0]]
+; CHECK:       cond.true:
 ; CHECK-NEXT:    [[VAL:%.*]] = add i32 [[A]], [[B]]
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP]], i32 0, i32 [[VAL]], !prof [[PROF0]]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ -1, [[ENTRY:%.*]] ], [ [[SPEC_SELECT]], [[DISPATCH]] ]
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ -1, [[ENTRY:%.*]] ], [ 0, [[DISPATCH]] ], [ [[VAL]], [[COND_TRUE]] ]
 ; CHECK-NEXT:    call void @sideeffect2()
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   call void @sideeffect0()
   br i1 %c, label %dispatch, label %end
 
 dispatch:
cond.true:
   br label %end
 
 end:
   %res = phi i32 [ -1, %entry ], [ 0, %dispatch ], [ %val, %cond.true ]
   call void @sideeffect2()
   ret i32 %res
 }
 
 !0 = !{!"branch_weights", i32 99, i32 1}
 !1 = !{!"branch_weights", i32 70, i32 1}
 !2 = !{}
 
 ; CHECK: !0 = !{!"branch_weights", i32 99, i32 1}
 ; CHECK: !1 = !{!"branch_weights", i32 70, i32 1}
 ; CHECK: !2 = !{}