Propagate branch metadata when some branch probability is missing.

[danielcdh]

Summary

In sample profile, some branches may have profile missing due to profile inaccuracy. We want existing branch probability still valid after propagation.

[spatel]

Note that this patch is dependent on D19674 which was reverted at rL268577.

I've been trying to locate the msan failure that caused the revert, but no luck so far: I don't see any problems running under valgrind. Trying to repro using msan directly now. If anyone can help spot the bug, I'd appreciate it.

[spatel]

I changed D19674 in order to avoid the msan bot failure; it seems unnecessarily ugly to me, but it's passing on that bot now. There's still an Apple internal bot issue that seems to be triggered by rL268767 , so it may need some other change.

For this patch, I'm wondering if we should be doing a one-off correction for a missing weight. Wouldn't it be better to fill in all of the missing info before we reach SimplifyCFG?

[danielcdh]

In D19948#424226, @spatel wrote:

I changed D19674 in order to avoid the msan bot failure; it seems unnecessarily ugly to me, but it's passing on that bot now. There's still an Apple internal bot issue that seems to be triggered by rL268767 , so it may need some other change.

For this patch, I'm wondering if we should be doing a one-off correction for a missing weight. Wouldn't it be better to fill in all of the missing info before we reach SimplifyCFG?

In sample profiler, we only annotate weights if we have profile for the branch. Yes, we can filling in missing weights like we do here, but those weights seem useless to other optimizations and it will unnecessarily increase IR size. Additionally, for case like this, if we assume that two branches should both (or none) have weights, we probably better assert instead of checking with "&&" condition, otherwise we may lose optimization opportunity without being notified.

[spatel]

In D19948#424803, @danielcdh wrote:

In D19948#424226, @spatel wrote:

For this patch, I'm wondering if we should be doing a one-off correction for a missing weight. Wouldn't it be better to fill in all of the missing info before we reach SimplifyCFG?

In sample profiler, we only annotate weights if we have profile for the branch. Yes, we can filling in missing weights like we do here, but those weights seem useless to other optimizations and it will unnecessarily increase IR size. Additionally, for case like this, if we assume that two branches should both (or none) have weights, we probably better assert instead of checking with "&&" condition, otherwise we may lose optimization opportunity without being notified.

I'll defer to David or Hal's better judgment on this. I don't know what the correct solution is.

[davidxl]

please add some comments to the code.

lgtm.

[danielcdh]

Rebase the patch to resolve conflicts. Now this patch does not depend on http://reviews.llvm.org/D19674

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
 
   // Modify PBI to branch on the new condition to the new dests.
   PBI->setCondition(Cond);
   PBI->setSuccessor(0, CommonDest);
   PBI->setSuccessor(1, OtherDest);
 
   // Update branch weight for PBI.
   uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
+  uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
   bool PredHasWeights =
       PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight);
   bool SuccHasWeights =
       BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight);
-  if (PredHasWeights && SuccHasWeights) {
-    uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
-    uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight;
-    uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
-    uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
+  bool HasWeights = PredHasWeights || SuccHasWeights;
+  if (HasWeights) {
+    if (!PredHasWeights) {
+      PredFalseWeight = PredTrueWeight = 1;
+    }
+    if (!SuccHasWeights) {
+      SuccFalseWeight = SuccTrueWeight = 1;
+    }
+    PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
+    PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
+    SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
+    SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
     // The weight to CommonDest should be PredCommon * SuccTotal +
     //                                    PredOther * SuccCommon.
     // The weight to OtherDest should be PredOther * SuccOther.
     uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
                                   PredOther * SuccCommon,
                               PredOther * SuccOther};
     // Halve the weights if any of them cannot fit in an uint32_t
     FitWeights(NewWeights);

test/Transforms/SimplifyCFG/preserve-branchweights.ll

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:    ret i32 [[OUTVAL]]
+;
+block1:
+  br i1 %cmpa, label %block2, label %block3, !prof !13
+
+block2:
+  br i1 %cmpb, label %exit, label %block3
+
+block3:
+  %cowval = phi i32 [ 2, %block2 ], [ 0, %block1 ]
+  br label %exit
+
+exit:
+  %outval = phi i32 [ %cowval, %block3 ], [ 1, %block2 ]
+  ret i32 %outval
+}
 
 !0 = !{!"branch_weights", i32 3, i32 5}
 !1 = !{!"branch_weights", i32 1, i32 1}
 !2 = !{!"branch_weights", i32 1, i32 2}
 !3 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
 !4 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
 !5 = !{!"branch_weights", i32 7, i32 6, i32 5}
 !6 = !{!"branch_weights", i32 1, i32 3}

 ;; 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}