Allow 0-weight branches in BranchProbabilityInfo.

[dnovillo]

Summary

When computing branch weights in BPI, we used to disallow branches with
weight 0. This is a minor nuisance, because a branch with weight 0 is
different to "don't have information". In the context of
instrumentation, it may mean "never executed", in the context of
sampling, it means "never or seldom executed".

In allowing 0 weight branches, I ran into issues with the switch
expansion code in selection DAG. It is currently hardwired to not handle
branches with weight 0. To maintain the current behaviour, I changed it
to use 1 when it finds 0, but perhaps the algorithm needs changes to
tolerate branches with weight zero.

Hans, could you take a look at the code I added to compensate for 0-weight
branches in the switch lowering code? I've tried to look for a better
place to add the flooring code, but couldn't find it.

The rest of the patch just mechanically adjusts for branches that now have
the correct weight set to 0.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8016

This looks good. I can address this TODO later.

I figured this would be the only change necessary for the switch lowering code. Are the changes to getEdgeWeight() and lowerWorkItem() also necessary?

[dnovillo]

• Only floor branch weights to 1 in visitSwitch().

lib/Analysis/BranchProbabilityInfo.cpp

bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
   uint32_t WeightLimit = getMaxWeightFor(BB);
   SmallVector<uint32_t, 2> Weights;
   Weights.reserve(TI->getNumSuccessors());
   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
     ConstantInt *Weight =
         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
     if (!Weight)
       return false;
-    Weights.push_back(
-      std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
+    Weights.push_back(Weight->getLimitedValue(WeightLimit));
   }
   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     setEdgeWeight(BB, i, Weights[i]);
 
   return true;
 }
 

 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
   uint32_t Sum = 0;
 
   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
     uint32_t PrevSum = Sum;
 
     Sum += Weight;
-    assert(Sum > PrevSum); (void) PrevSum;
+    assert(Sum >= PrevSum); (void) PrevSum;
   }
 
   return Sum;
 }
 
 bool BranchProbabilityInfo::
 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
   // Hot probability is at least 4/5 = 80%
uint32_t BranchProbabilityInfo::getEdgeWeight(const BasicBlock *Src,
   return getEdgeWeight(Src, Dst.getSuccessorIndex());
 }
 
 /// Get the raw edge weight calculated for the block pair. This returns the sum
 /// of all raw edge weights from Src to Dst.
 uint32_t BranchProbabilityInfo::
 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
   uint32_t Weight = 0;
+  bool FoundWeight = false;
   DenseMap<Edge, uint32_t>::const_iterator MapI;
   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
     if (*I == Dst) {
       MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
-      if (MapI != Weights.end())
+      if (MapI != Weights.end()) {
+        FoundWeight = true;
         Weight += MapI->second;
       }
-  return (Weight == 0) ? DEFAULT_WEIGHT : Weight;
+    }
+  return (!FoundWeight) ? DEFAULT_WEIGHT : Weight;
 }
 
 /// Set the edge weight for a given edge specified by PredBlock and an index
 /// to the successors.
 void BranchProbabilityInfo::
 setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
               uint32_t Weight) {
   Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
   BranchProbabilityInfo *BPI = FuncInfo.BPI;
   CaseClusterVector Clusters;
   Clusters.reserve(SI.getNumCases());
   for (auto I : SI.cases()) {
     MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()];
     const ConstantInt *CaseVal = I.getCaseValue();
     uint32_t Weight = 1;
     if (BPI) {
-      Weight = BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex());
+      // TODO - BPI used to guarantee non-zero weights, but this produces
+      // information loss (see PR 22718). Since we can't handle zero weights
+      // here, use the same flooring mechanism previously used by BPI.
+      Weight = std::max(
+          1u, BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex()));
       assert(Weight <= UINT32_MAX / SI.getNumSuccessors());
     }
     Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight));
   }
 
   MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[SI.getDefaultDest()];
 
   if (TM.getOptLevel() != CodeGenOpt::None) {

test/Transforms/SampleProfile/branch.ll

 define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
 ; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
 
 entry:
   tail call void @llvm.dbg.value(metadata i32 %argc, i64 0, metadata !13, metadata !DIExpression()), !dbg !27
   tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
   %cmp = icmp slt i32 %argc, 2, !dbg !28
   br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 1 / 2 = 50%
-; CHECK: edge entry -> if.end probability is 1 / 2 = 50%
+; CHECK: edge entry -> return probability is 0 / 1 = 0%
+; CHECK: edge entry -> if.end probability is 1 / 1 = 100%
 
 if.end:                                           ; preds = %entry
   %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
   %0 = load i8*, i8** %arrayidx, align 8, !dbg !30, !tbaa !31
   %call = tail call i32 @atoi(i8* %0) #4, !dbg !30
   tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
   %cmp1 = icmp sgt i32 %call, 100, !dbg !35
   br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 1 / 2 = 50%
-; CHECK: edge if.end -> if.end6 probability is 1 / 2 = 50%
+; CHECK: edge if.end -> for.body probability is 0 / 1 = 0%
+; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100%
 
 for.body:                                         ; preds = %if.end, %for.body
   %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
   %s.015 = phi double [ %sub, %for.body ], [ 0x40370ABE6A337A81, %if.end ]
   %add = fadd double %s.015, 3.049000e+00, !dbg !36
   %conv = sitofp i32 %u.016 to double, !dbg !36
   %add4 = fadd double %add, %conv, !dbg !36
   tail call void @llvm.dbg.value(metadata double %add4, i64 0, metadata !18, metadata !DIExpression()), !dbg !36
   %div = fdiv double 3.940000e+00, %s.015, !dbg !37
   %mul = fmul double %div, 3.200000e-01, !dbg !37
   %add5 = fadd double %add4, %mul, !dbg !37
   %sub = fsub double %add4, %add5, !dbg !37
   tail call void @llvm.dbg.value(metadata double %sub, i64 0, metadata !18, metadata !DIExpression()), !dbg !37
   %inc = add nsw i32 %u.016, 1, !dbg !38
   tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
   %exitcond = icmp eq i32 %inc, %call, !dbg !38
   br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 1 / 10227 = 0.00977804
-; CHECK: edge for.body -> for.body probability is 10226 / 10227 = 99.9902% [HOT edge]
+; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0%
+; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge]
 
 if.end6:                                          ; preds = %for.body, %if.end
   %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
   %call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
   br label %return, !dbg !40
 ; CHECK: edge if.end6 -> return probability is 16 / 16 = 100% [HOT edge]
 
 return:                                           ; preds = %entry, %if.end6

test/Transforms/SampleProfile/calls.ll

entry:
   br label %while.cond, !dbg !13
 
 while.cond:                                       ; preds = %if.end, %entry
   %0 = load i32, i32* %i, align 4, !dbg !14
   %inc = add nsw i32 %0, 1, !dbg !14
   store i32 %inc, i32* %i, align 4, !dbg !14
   %cmp = icmp slt i32 %0, 400000000, !dbg !14
   br i1 %cmp, label %while.body, label %while.end, !dbg !14
-; CHECK: edge while.cond -> while.body probability is 5391 / 5392 = 99.9815% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 1 / 5392 = 0.018546%
+; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0%
 
 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i, align 4, !dbg !16
   %cmp1 = icmp ne i32 %1, 100, !dbg !16
   br i1 %cmp1, label %if.then, label %if.else, !dbg !16
 ; Without discriminator information, the profiler used to think that
 ; both branches out of while.body had the same weight. In reality,
 ; the edge while.body->if.then is taken most of the time.
 ;
-; CHECK: edge while.body -> if.then probability is 5752 / 5753 = 99.9826% [HOT edge]
-; CHECK: edge while.body -> if.else probability is 1 / 5753 = 0.0173822%
+; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0%
 
 
 if.then:                                          ; preds = %while.body
   %2 = load i32, i32* %i, align 4, !dbg !18
   %3 = load i32, i32* %s, align 4, !dbg !18
   %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
   store i32 %call, i32* %s, align 4, !dbg !18
   br label %if.end, !dbg !18

test/Transforms/SampleProfile/propagate.ll

if.else:                                          ; preds = %entry
   store i64 0, i64* %i, align 8, !dbg !15
   br label %for.cond, !dbg !15
 
 for.cond:                                         ; preds = %for.inc16, %if.else
   %4 = load i64, i64* %i, align 8, !dbg !15
   %5 = load i64, i64* %N.addr, align 8, !dbg !15
   %cmp1 = icmp slt i64 %4, %5, !dbg !15
   br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 10 / 11 = 90.9091% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 1 / 11 = 9.09091%
+; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0%
 
 for.body:                                         ; preds = %for.cond
   %6 = load i64, i64* %i, align 8, !dbg !18
   %7 = load i64, i64* %N.addr, align 8, !dbg !18
   %div = sdiv i64 %7, 3, !dbg !18
   %cmp2 = icmp sgt i64 %6, %div, !dbg !18
   br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
 ; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
if.else7:                                         ; preds = %if.end
   br label %for.cond8, !dbg !28
 
 for.cond8:                                        ; preds = %for.inc, %if.else7
   %13 = load i32, i32* %j, align 4, !dbg !28
   %conv9 = zext i32 %13 to i64, !dbg !28
   %14 = load i64, i64* %i, align 8, !dbg !28
   %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
   br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16192 = 99.9938% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 1 / 16192 = 0.00617589%
+; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge]
+; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0%
 
 for.body11:                                       ; preds = %for.cond8
   %15 = load i32, i32* %j, align 4, !dbg !31
   %16 = load i32, i32* %x.addr, align 4, !dbg !31
   %add12 = add i32 %16, %15, !dbg !31
   store i32 %add12, i32* %x.addr, align 4, !dbg !31
   %17 = load i32, i32* %y.addr, align 4, !dbg !33
   %sub13 = sub nsw i32 %17, 3, !dbg !33