[SimplifyCFG] propagate branch metadata when creating select

[spatel]

Summary

Hopefully, the change itself is straightforward - plug another hole where we drop branch weight metadata while creating a select.

I'm curious about the lack of use of BranchProbability in SimplifyCFG though. Is there a reason we don't use that here (and therefore need duplicate functionality like "FitWeights()")?

[davidxl]

looks fine, but can you write another more direct test case for better checking if the profile update is correct or not.

[spatel]

Patch updated:
Minimize test case to show that existing metadata on a select isn't changed and the missing weights fixed by this patch are correct.

[davidxl]

test/Transforms/SimplifyCFG/preserve-branchweights.ll

422

If I read the code correctly, should the weights for select be 9:5 ? !11 does not look correct.

423

This one is correct.

[spatel]

test/Transforms/SimplifyCFG/preserve-branchweights.ll

422

I thought the weights for the select would be equal to the weights of the original branch because they have the same comparison condition (%cmpb), 3:5. How do you calculate 9:5?

[davidxl]

test/Transforms/SimplifyCFG/preserve-branchweights.ll

422

Should it be 3 : 5 * (1/3) which 9 : 5? When block 2 is entered, there is only 1/3 probability it reaches block3.

[spatel]

test/Transforms/SimplifyCFG/preserve-branchweights.ll

422

Aha - yes. Although it's the same comparison operand, we have changed the program structure - we are speculatively executing the select, so the original branch weights no longer apply.

This brings up my question from the original summary then - do you know if there's a reason not to use the BranchProbability class for calculating the new weights?

[davidxl]

test/Transforms/SimplifyCFG/preserve-branchweights.ll

422

BPI provides general APIs to access/read branch probability information that is either from profile data, or from static branch prediction.

Here the transformation just needs to update the profile data, using low level meta data interfaces is fine (Besides BPI does not have complete update APIs either).

[spatel]

Patch updated:
The branch weights of the first select are recalculated based on the new program structure.

[davidxl]

lgtm

lib/Transforms/Utils/SimplifyCFG.cpp

2888

The select is newly created instruction that does not exist before -- it sits at the same BB where the original phi, so it is not 'speculatively' executed.

The original PBI's branch weights do not apply because the select's 'logical' edges are incoming edges of the phi that is eliminated, not the out edges of PBI.

[spatel]

Thanks, David. I think that was the last of the branch --> select branch_weights drops in SimplifyCFG.
Still need to look at switch --> select and other transforms.

[vitalybuka]

Looks like a cause of
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/11620/steps/check-llvm%20msan/logs/stdio

[vitalybuka]

I am going to revert.

[vitalybuka]

Reverted in r268577

[spatel]

In D19674#421811, @vitalybuka wrote:

Reverted in r268577

Thanks, Vitaly. I'll try to get this debugged tomorrow.

[spatel]

In D19674#421885, @spatel wrote:

In D19674#421811, @vitalybuka wrote:

Reverted in r268577

Thanks, Vitaly. I'll try to get this debugged tomorrow.

I've tried to reproduce the error using sanitized builds of opt/llc as well as running under valgrind, but I don't see it. How do I find the exact steps used by the bot to induce the bug?

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   // Merge the conditions.
   Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
 
   // 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.
+  // OtherDest may have phi nodes.  If so, add an entry from PBI's
+  // block that are identical to the entries for BI's block.
+  AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
+
+  // We know that the CommonDest already had an edge from PBI to
+  // it.  If it has PHIs though, the PHIs may have different
+  // entries for BB and PBI's BB.  If so, insert a select to make
+  // them agree.
+  PHINode *PN;
+  for (BasicBlock::iterator II = CommonDest->begin();
+       (PN = dyn_cast<PHINode>(II)); ++II) {
+    Value *BIV = PN->getIncomingValueForBlock(BB);
+    unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
+    Value *PBIV = PN->getIncomingValue(PBBIdx);
+    if (BIV != PBIV) {
+      // Insert a select in PBI to pick the right value.
+      // Transfer any original profile metadata from the branch to the select.
+      Value *NV = Builder.CreateSelect(PBICond, PBIV, BIV,
+                                       PBIV->getName() + ".mux", PBI);
+      PN->setIncomingValue(PBBIdx, NV);
+    }
+  }
+
+  // Update branch weight for PBI. We do this after the select creation above
+  // because we want to preserve the original branch weights for the select.
   uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
   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;
     // 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);
 
     PBI->setMetadata(LLVMContext::MD_prof,
                      MDBuilder(BI->getContext())
                          .createBranchWeights(NewWeights[0], NewWeights[1]));
   }
 
-  // OtherDest may have phi nodes.  If so, add an entry from PBI's
-  // block that are identical to the entries for BI's block.
-  AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
-
-  // We know that the CommonDest already had an edge from PBI to
-  // it.  If it has PHIs though, the PHIs may have different
-  // entries for BB and PBI's BB.  If so, insert a select to make
-  // them agree.
-  PHINode *PN;
-  for (BasicBlock::iterator II = CommonDest->begin();
-       (PN = dyn_cast<PHINode>(II)); ++II) {
-    Value *BIV = PN->getIncomingValueForBlock(BB);
-    unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
-    Value *PBIV = PN->getIncomingValue(PBBIdx);
-    if (BIV != PBIV) {
-      // Insert a select in PBI to pick the right value.
-      Value *NV = cast<SelectInst>
-        (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux"));
-      PN->setIncomingValue(PBBIdx, NV);
-    }
-  }
-
   DEBUG(dbgs() << "INTO: " << *PBI->getParent());
   DEBUG(dbgs() << *PBI->getParent()->getParent());
 
   // This basic block is probably dead.  We know it has at least
   // one fewer predecessor.
   return true;
 }
 
 // Simplifies a terminator by replacing it with a branch to TrueBB if Cond is
 // true or to FalseBB if Cond is false.

test/Transforms/SimplifyCFG/preserve-branchweights.ll

 
 ; The 1st select should have branch weights equal to the 1st branch.
 ; The 2nd select should have freshly calculated branch weights.
 
 define i32 @SimplifyCondBranchToCondBranch(i1 %cmpa, i1 %cmpb) {
 ; CHECK-LABEL: @SimplifyCondBranchToCondBranch(
 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 %cmpb, %cmpa
-; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 %cmpb, i32 0, i32 2
+; CHECK-NEXT:    [[DOTMUX:%.*]] = select i1 %cmpb, i32 0, i32 2, !prof !11
 ; CHECK-NEXT:    [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !12
 ; CHECK-NEXT:    ret i32 [[OUTVAL]]
 ;
 block1:
   br i1 %cmpb, label %block3, label %block2, !prof !0
 
 block2:
   br i1 %cmpa, label %block3, label %exit, !prof !2