Follow-up patch of http://reviews.llvm.org/D19948 to handle missing profiles when simplifying CFG.

[danielcdh]

Summary

Set default branch weight to 1:1 if one of the branch has profile missing when simplifying CFG.

[davidxl]

lib/Transforms/Utils/SimplifyCFG.cpp

2256

Can you refactor the code into a helper function:

extractPredSuccWeights that returns true if either Pred or Succ has weights?

[danielcdh]

Refactor the common helper function.

[davidxl]

lgtm

The code change looks fine to me -- but I have not audited the test case changes. Please do this at some point if not done(validate the output BP make sense -- there could be bugs exposed else where).

[danielcdh]

The test is validated. For most cases, the prof id just shifted by one. For
test1 and test3, the changes are intended.

Dehao

lib/Transforms/Utils/SimplifyCFG.cpp

for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 
     if (BI->isConditional()) {
       Instruction *NewCond =
         cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(),
                                             New, "or.cond"));
       PBI->setCondition(NewCond);
 
       uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
       bool PredHasWeights =
           PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight);
       bool SuccHasWeights =
           BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight);
       SmallVector<uint64_t, 8> NewWeights;
 
       if (PBI->getSuccessor(0) == BB) {
-        if (PredHasWeights && SuccHasWeights) {
+        if (PredHasWeights || SuccHasWeights) {
+          if (!PredHasWeights)
+            PredTrueWeight = PredFalseWeight = 1;
+          if (!SuccHasWeights)
+            SuccTrueWeight = SuccFalseWeight = 1;
           // PBI: br i1 %x, BB, FalseDest
           // BI:  br i1 %y, TrueDest, FalseDest
           //TrueWeight is TrueWeight for PBI * TrueWeight for BI.
           NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
           //FalseWeight is FalseWeight for PBI * TotalWeight for BI +
           //               TrueWeight for PBI * FalseWeight for BI.
           // We assume that total weights of a BranchInst can fit into 32 bits.
           // Therefore, we will not have overflow using 64-bit arithmetic.
           NewWeights.push_back(PredFalseWeight * (SuccFalseWeight +
                SuccTrueWeight) + PredTrueWeight * SuccFalseWeight);
         }
         AddPredecessorToBlock(TrueDest, PredBlock, BB);
         PBI->setSuccessor(0, TrueDest);
       }
       if (PBI->getSuccessor(1) == BB) {
-        if (PredHasWeights && SuccHasWeights) {
+        if (PredHasWeights || SuccHasWeights) {
+          if (!PredHasWeights)
+            PredTrueWeight = PredFalseWeight = 1;
+          if (!SuccHasWeights)
+            SuccTrueWeight = SuccFalseWeight = 1;
           // PBI: br i1 %x, TrueDest, BB
           // BI:  br i1 %y, TrueDest, FalseDest
           //TrueWeight is TrueWeight for PBI * TotalWeight for BI +
           //              FalseWeight for PBI * TrueWeight for BI.
           NewWeights.push_back(PredTrueWeight * (SuccFalseWeight +
               SuccTrueWeight) + PredFalseWeight * SuccTrueWeight);
           //FalseWeight is FalseWeight for PBI * FalseWeight for BI.
           NewWeights.push_back(PredFalseWeight * SuccFalseWeight);

test/Transforms/SimplifyCFG/preserve-branchweights.ll

 
 ; Make sure the metadata name string is "branch_weights" before propagating it.
 
 define void @fake_weights(i1 %a, i1 %b) {
 ; CHECK-LABEL: @fake_weights(
 entry:
   br i1 %a, label %Y, label %X, !prof !12
 ; CHECK:        %or.cond = and i1 %a.not, %c
-; CHECK-NEXT:   br i1 %or.cond, label %Z, label %Y
-; CHECK-NOT:    !prof !0
+; CHECK-NEXT:   br i1 %or.cond, label %Z, label %Y, !prof !1
 ; CHECK:      Y:
 X:
   %c = or i1 %b, false
   br i1 %c, label %Z, label %Y, !prof !1
 
 Y:
   call void @helper(i32 0)
   ret void
 
 Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test2(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test2(
 entry:
   br i1 %a, label %X, label %Y, !prof !1
-; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1
+; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !2
 ; CHECK-NOT: !prof
 
 X:
   %c = or i1 %b, false
   br i1 %c, label %Z, label %Y, !prof !2
 
 Y:
   call void @helper(i32 0)
   ret void
 
 Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test3(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test3(
-; CHECK-NOT: !prof
+; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1
 entry:
   br i1 %a, label %X, label %Y, !prof !1
 
 X:
   %c = or i1 %b, false
   br i1 %c, label %Z, label %Y
 
 Y:
   call void @helper(i32 0)
   ret void
 
 Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test4(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test4(
-; CHECK-NOT: !prof
+; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1
 entry:
   br i1 %a, label %X, label %Y
 
 X:
   %c = or i1 %b, false
   br i1 %c, label %Z, label %Y, !prof !1
 
 Y:
switch i32 %N, label %sw2 [
     i32 1, label %sw2
     i32 2, label %sw.bb
     i32 3, label %sw.bb1
   ], !prof !3
 ; CHECK-LABEL: @test5(
 ; CHECK: switch i32 %N, label %sw2 [
 ; CHECK: i32 3, label %sw.bb1
 ; CHECK: i32 2, label %sw.bb
-; CHECK: ], !prof !2
+; CHECK: ], !prof !3
 
 sw.bb:
   call void @helper(i32 0)
   br label %sw.epilog
 
 sw.bb1:
   call void @helper(i32 1)
   br label %sw.epilog
switch i32 %N, label %sw2 [
     i32 2, label %sw.bb
     i32 3, label %sw.bb1
   ], !prof !4
 ; CHECK-LABEL: @test6(
 ; CHECK: switch i32 %N, label %sw.epilog
 ; CHECK: i32 3, label %sw.bb1
 ; CHECK: i32 2, label %sw.bb
 ; CHECK: i32 4, label %sw.bb5
-; CHECK: ], !prof !3
+; CHECK: ], !prof !4
 
 sw.bb:
   call void @helper(i32 0)
   br label %sw.epilog
 
 sw.bb1:
   call void @helper(i32 1)
   br label %sw.epilog
sw.epilog:
   ret void
 }
 
 ;; This test is based on test1 but swapped the targets of the second branch.
 define void @test1_swap(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1_swap(
 entry:
   br i1 %a, label %Y, label %X, !prof !0
-; CHECK: br i1 %or.cond, label %Y, label %Z, !prof !4
+; CHECK: br i1 %or.cond, label %Y, label %Z, !prof !5
 
 X:
   %c = or i1 %b, false
   br i1 %c, label %Y, label %Z, !prof !1
 
 Y:
   call void @helper(i32 0)
   ret void
 
 Z:
   call void @helper(i32 1)
   ret void
 }
 
 define void @test7(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test7(
 entry:
   %c = or i1 %b, false
   br i1 %a, label %Y, label %X, !prof !0
-; CHECK: br i1 %brmerge, label %Y, label %Z, !prof !5
+; CHECK: br i1 %brmerge, label %Y, label %Z, !prof !6
 
 X:
   br i1 %c, label %Y, label %Z, !prof !6
 
 Y:
   call void @helper(i32 0)
   ret void
 
 Z:
   call void @helper(i32 1)
   ret void
 }
 
 ; Test basic folding to a conditional branch.
 define void @test8(i64 %x, i64 %y) nounwind {
 ; CHECK-LABEL: @test8(
 entry:
     %lt = icmp slt i64 %x, %y
-; CHECK: br i1 %lt, label %a, label %b, !prof !6
+; CHECK: br i1 %lt, label %a, label %b, !prof !7
     %qux = select i1 %lt, i32 0, i32 2
     switch i32 %qux, label %bees [
         i32 0, label %a
         i32 1, label %b
         i32 2, label %b
     ], !prof !7
 a:
     call void @helper(i32 0) nounwind
switch i32 %x, label %bees [
         i32 1, label %end
         i32 2, label %end
     ], !prof !7
 ; CHECK: switch i32 %x, label %bees [
 ; CHECK: i32 0, label %a
 ; CHECK: i32 1, label %end
 ; CHECK: i32 2, label %end
 ; CHECK: i32 92, label %end
-; CHECK: ], !prof !7
+; CHECK: ], !prof !8
 
 a:
     call void @helper(i32 0) nounwind
     %reta = icmp slt i32 %x, %y
     ret i1 %reta
 
 bees:
     %tmp = icmp eq i32 %x, 92

 
 lor.end:
  call void @helper(i32 0) nounwind
  ret void
 
 ; CHECK-LABEL: @test10(
 ; CHECK: %x.off = add i32 %x, -1
 ; CHECK: %switch = icmp ult i32 %x.off, 3
-; CHECK: br i1 %switch, label %lor.end, label %lor.rhs, !prof !8
+; CHECK: br i1 %switch, label %lor.end, label %lor.rhs, !prof !9
 }
 
 ; Remove dead cases from the switch.
 define void @test11(i32 %x) nounwind {
   %i = shl i32 %x, 1
   switch i32 %i, label %a [
     i32 21, label %b
     i32 24, label %c
   ], !prof !8
 ; CHECK-LABEL: @test11(
 ; CHECK: %cond = icmp eq i32 %i, 24
-; CHECK: br i1 %cond, label %c, label %a, !prof !9
+; CHECK: br i1 %cond, label %c, label %a, !prof !10
 
 a:
  call void @helper(i32 0) nounwind
  ret void
 b:
  call void @helper(i32 1) nounwind
  ret void
 c:

 }
 
 ;; When folding branches to common destination, the updated branch weights
 ;; can exceed uint32 by more than factor of 2. We should keep halving the
 ;; weights until they can fit into uint32.
 @max_regno = common global i32 0, align 4
 define void @test14(i32* %old, i32 %final) {
 ; CHECK-LABEL: @test14
-; CHECK: br i1 %or.cond, label %for.exit, label %for.inc, !prof !10
+; CHECK: br i1 %or.cond, label %for.exit, label %for.inc, !prof !11
 for.cond:
   br label %for.cond2
 for.cond2:
   %i.1 = phi i32 [ %inc19, %for.inc ], [ 0, %for.cond ]
   %bit.0 = phi i32 [ %shl, %for.inc ], [ 1, %for.cond ]
   %tobool = icmp eq i32 %bit.0, 0
   br i1 %tobool, label %for.exit, label %for.body3, !prof !10
 for.body3:

 }
 
 ; Don't drop the metadata.
 
 define i32 @HoistThenElseCodeToIf(i32 %n) {
 ; CHECK-LABEL: @HoistThenElseCodeToIf(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 %n, 0
-; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL]], i32 1, i32 234, !prof !11
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL]], i32 1, i32 234, !prof !12
 ; CHECK-NEXT:    ret i32 [[DOT]]
 ;
 entry:
   %tobool = icmp eq i32 %n, 0
   br i1 %tobool, label %if, label %else, !prof !0
 
 if:
   br label %return
 
 else:
   br label %return
 
 return:
   %retval.0 = phi i32 [ 1, %if ], [ 234, %else ]
   ret i32 %retval.0
 }
 
 ; The selects should have freshly calculated branch weights.
 
 define i32 @SimplifyCondBranchToCondBranch(i1 %cmpa, i1 %cmpb) {
 ; CHECK-LABEL: @SimplifyCondBranchToCondBranch(
 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 %cmpa, %cmpb
-; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 %cmpa, i32 0, i32 2, !prof !12
-; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !13
+; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 %cmpa, i32 0, i32 2, !prof !13
+; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !14
 ; CHECK-NEXT:    ret i32 [[OUTVAL]]
 ;
 block1:
   br i1 %cmpa, label %block3, label %block2, !prof !13
 
 block2:
   br i1 %cmpb, label %block3, label %exit, !prof !14
 

 ; Swap the operands of the compares to verify that the weights update correctly.
 
 define i32 @SimplifyCondBranchToCondBranchSwap(i1 %cmpa, i1 %cmpb) {
 ; CHECK-LABEL: @SimplifyCondBranchToCondBranchSwap(
 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    [[CMPA_NOT:%.*]] = xor i1 %cmpa, true
 ; CHECK-NEXT:    [[CMPB_NOT:%.*]] = xor i1 %cmpb, true
 ; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[CMPA_NOT]], [[CMPB_NOT]]
-; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[CMPA_NOT]], i32 0, i32 2, !prof !14
-; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !15
+; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[CMPA_NOT]], i32 0, i32 2, !prof !15
+; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !16
 ; CHECK-NEXT:    ret i32 [[OUTVAL]]
 ;
 block1:
   br i1 %cmpa, label %block2, label %block3, !prof !13
 
 block2:
   br i1 %cmpb, label %exit, label %block3, !prof !14
 
 block3:
   %cowval = phi i32 [ 2, %block2 ], [ 0, %block1 ]
   br label %exit
 
 exit:
   %outval = phi i32 [ %cowval, %block3 ], [ 1, %block2 ]
   ret i32 %outval
 }
 
 define i32 @SimplifyCondBranchToCondBranchSwapMissingWeight(i1 %cmpa, i1 %cmpb) {
 ; CHECK-LABEL: @SimplifyCondBranchToCondBranchSwapMissingWeight(
 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    [[CMPA_NOT:%.*]] = xor i1 %cmpa, true 
 ; CHECK-NEXT:    [[CMPB_NOT:%.*]] = xor i1 %cmpb, true
 ; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[CMPA_NOT]], [[CMPB_NOT]]
 ; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 [[CMPA_NOT]], i32 0, i32 2
-; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !16
+; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !17
 ; CHECK-NEXT:    ret i32 [[OUTVAL]]
 ;
 block1:
   br i1 %cmpa, label %block2, label %block3, !prof !13
 
 block2:
   br i1 %cmpb, label %exit, label %block3
 

 !9 = !{!"branch_weights", i32 7, i32 6}
 !10 = !{!"branch_weights", i32 672646, i32 21604207}
 !11 = !{!"branch_weights", i32 6960, i32 21597248}
 !12 = !{!"these_are_not_the_branch_weights_you_are_looking_for", i32 3, i32 5}
 !13 = !{!"branch_weights", i32 2, i32 3}
 !14 = !{!"branch_weights", i32 4, i32 7}
 
 ; CHECK: !0 = !{!"branch_weights", i32 5, i32 11}
-; CHECK: !1 = !{!"branch_weights", i32 1, i32 5}
-; CHECK: !2 = !{!"branch_weights", i32 7, i32 1, i32 2}
-; CHECK: !3 = !{!"branch_weights", i32 49, i32 12, i32 24, i32 35}
-; CHECK: !4 = !{!"branch_weights", i32 11, i32 5}
-; CHECK: !5 = !{!"branch_weights", i32 17, i32 15}
-; CHECK: !6 = !{!"branch_weights", i32 9, i32 7}
-; CHECK: !7 = !{!"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17}
-; CHECK: !8 = !{!"branch_weights", i32 24, i32 33}
-; CHECK: !9 = !{!"branch_weights", i32 8, i32 33}
+; CHECK: !1 = !{!"branch_weights", i32 1, i32 3}
+; CHECK: !2 = !{!"branch_weights", i32 1, i32 5}
+; CHECK: !3 = !{!"branch_weights", i32 7, i32 1, i32 2}
+; CHECK: !4 = !{!"branch_weights", i32 49, i32 12, i32 24, i32 35}
+; CHECK: !5 = !{!"branch_weights", i32 11, i32 5}
+; CHECK: !6 = !{!"branch_weights", i32 17, i32 15}
+; CHECK: !7 = !{!"branch_weights", i32 9, i32 7}
+; CHECK: !8 = !{!"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17}
+; CHECK: !9 = !{!"branch_weights", i32 24, i32 33}
+; CHECK: !10 = !{!"branch_weights", i32 8, i32 33}
 ;; The false weight prints out as a negative integer here, but inside llvm, we
 ;; treat the weight as an unsigned integer.
-; CHECK: !10 = !{!"branch_weights", i32 112017436, i32 -735157296}
-; CHECK: !11 = !{!"branch_weights", i32 3, i32 5}
-; CHECK: !12 = !{!"branch_weights", i32 22, i32 12}
-; CHECK: !13 = !{!"branch_weights", i32 34, i32 21}
-; CHECK: !14 = !{!"branch_weights", i32 33, i32 14}
-; CHECK: !15 = !{!"branch_weights", i32 47, i32 8}
-; CHECK: !16 = !{!"branch_weights", i32 8, i32 2}
+; CHECK: !11 = !{!"branch_weights", i32 112017436, i32 -735157296}
+; CHECK: !12 = !{!"branch_weights", i32 3, i32 5}
+; CHECK: !13 = !{!"branch_weights", i32 22, i32 12}
+; CHECK: !14 = !{!"branch_weights", i32 34, i32 21}
+; CHECK: !15 = !{!"branch_weights", i32 33, i32 14}
+; CHECK: !16 = !{!"branch_weights", i32 47, i32 8}
+; CHECK: !17 = !{!"branch_weights", i32 8, i32 2}