Fix Bug 18705: BranchProbabilityInfo is not using the right heuristics inside loops.

[ahatanak]

Summary

The attached patch fixes bug 18705.

http://llvm.org/bugs/show_bug.cgi?id=18705

Currently, BranchProbabilityInfo::calcLoopBranchHeuristics, which is one of the heuristics used to determine branch weights, sets the weights for all successor edges of a basic block inside a loop, even when it doesn't have enough information to estimate the branch probabilities correctly.

For example, when calcLoopBranchHeuristics handles basic block "for.body" in the code below, it classifies both successor edges of "for.body" (for.body => %if.then and for.body => %if.else) as "InEdges", since neither of them is an exit edge nor a back edge, and gives equal weights to them.

The patch fixes the function to exit early if it doesn't see any exit edges or back edges and let the later heuristics decide the weights. In the example below, it would defer the decision to calcFloatingPointHeuristics, which would set the edges weights to FPH_TAKEN_WEIGHT and FPH_NONTAKEN_WEIGHT.

for.body:

...

%cmp3 = fcmp une double %4, %5

br i1 %cmp3, label %if.then, label %if.else

if.then:

...
br label %for.inc

if.else:

...
br label %for.inc

for.inc:

...
br i1 %exitcond, label %for.end, label %for.body

[ahatanak]

Test case in pr18705.ll is a better example for explaining what this patch is trying to fix.

The current code in calcLoopBranchHeuristics gives equal weights to edges "while.body -> if.then" and "while.body -> if.else". The patch fixes it to give weights 20 (FPH_TAKEN_WEIGHT) and 12 (FPH_NONTAKEN_WEIGHT).

[ahatanak]

CC'ing list.

[dexonsmith]

LGTM.

• dpnes

[ahatanak]

Closed by commit rL206194 (authored by @ahatanak).

llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp

for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     if (!L->contains(*I))
       ExitingEdges.push_back(I.getSuccessorIndex());
     else if (L->getHeader() == *I)
       BackEdges.push_back(I.getSuccessorIndex());
     else
       InEdges.push_back(I.getSuccessorIndex());
   }
 
+  if (BackEdges.empty() && ExitingEdges.empty())
+    return false;
+
   if (uint32_t numBackEdges = BackEdges.size()) {
     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
     if (backWeight < NORMAL_WEIGHT)
       backWeight = NORMAL_WEIGHT;
 
     for (SmallVectorImpl<unsigned>::iterator EI = BackEdges.begin(),
          EE = BackEdges.end(); EI != EE; ++EI) {
       setEdgeWeight(BB, *EI, backWeight);

llvm/trunk/test/Analysis/BranchProbabilityInfo/loop.ll

 entry:
   br label %do.body
 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc3, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ]
   call void @g2()
   %inc = add nsw i32 %j.0, 1
   %cmp = icmp slt i32 %inc, %b
   br i1 %cmp, label %do.body1, label %do.end
 ; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
for.body.lr.ph:
   %cmp27 = icmp sgt i32 %b, 0
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
 
 for.body:
   %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.end ]
   call void @g1()
   br i1 %cmp27, label %for.body3, label %for.end
-; CHECK: edge for.body -> for.body3 probability is 62 / 124 = 50%
-; CHECK: edge for.body -> for.end probability is 62 / 124 = 50%
+; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
+; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
 
 for.body3:
   %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ]
   call void @g2()
   %inc = add nsw i32 %j.08, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body3
 ; CHECK: edge for.body3 -> for.end probability is 4 / 128

 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
   call void @g1()
   %0 = load i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %do.body1, label %if.end
-; CHECK: edge do.body -> do.body1 probability is 62 / 124 = 50%
-; CHECK: edge do.body -> if.end probability is 62 / 124 = 50%
+; CHECK: edge do.body -> do.body1 probability is 16 / 32 = 50%
+; CHECK: edge do.body -> if.end probability is 16 / 32 = 50%
 
 do.body1:
   %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
   call void @g2()
   %inc = add nsw i32 %j.0, 1
   %cmp2 = icmp slt i32 %inc, %b
   br i1 %cmp2, label %do.body1, label %if.end
 ; CHECK: edge do.body1 -> do.body1 probability is 124 / 128

 entry:
   br label %do.body
 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ]
   %0 = load i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %return, label %if.end
 ; CHECK: edge do.body1 -> return probability is 4 / 128
 ; CHECK: edge do.body1 -> if.end probability is 124 / 128

 entry:
   br label %do.body
 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ]
   call void @g2()
   %0 = load i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %return, label %do.cond
 ; CHECK: edge do.body1 -> return probability is 4 / 128
for.body.lr.ph:
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
 
 for.body:
   %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
   %0 = load i32* %c, align 4
   %cmp1 = icmp eq i32 %0, %i.011
   br i1 %cmp1, label %for.inc5, label %if.end
-; CHECK: edge for.body -> for.inc5 probability is 62 / 124 = 50%
-; CHECK: edge for.body -> if.end probability is 62 / 124 = 50%
+; CHECK: edge for.body -> for.inc5 probability is 16 / 32 = 50%
+; CHECK: edge for.body -> if.end probability is 16 / 32 = 50%
 
 if.end:
   call void @g1()
   br i1 %cmp38, label %for.body4, label %for.end
-; CHECK: edge if.end -> for.body4 probability is 62 / 124 = 50%
-; CHECK: edge if.end -> for.end probability is 62 / 124 = 50%
+; CHECK: edge if.end -> for.body4 probability is 20 / 32 = 62.5%
+; CHECK: edge if.end -> for.end probability is 12 / 32 = 37.5%
 
 for.body4:
   %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ]
   call void @g2()
   %inc = add nsw i32 %j.09, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body4
 ; CHECK: edge for.body4 -> for.end probability is 4 / 128
 ; CHECK: edge for.body4 -> for.body4 probability is 124 / 128
 
 for.end:
   call void @g3()
   br label %for.inc5
-; CHECK: edge for.end -> for.inc5 probability is 124 / 124 = 100%
+; CHECK: edge for.end -> for.inc5 probability is 16 / 16 = 100%
 
 for.inc5:
   %inc6 = add nsw i32 %i.011, 1
   %exitcond12 = icmp eq i32 %inc6, %a
   br i1 %exitcond12, label %for.end7, label %for.body
 ; CHECK: edge for.inc5 -> for.end7 probability is 4 / 128
 ; CHECK: edge for.inc5 -> for.body probability is 124 / 128
 
for.body.lr.ph:
   %arrayidx9 = getelementptr inbounds i32* %c, i64 2
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
 
 for.body:
   %i.019 = phi i32 [ 0, %for.body.lr.ph ], [ %inc14, %for.end ]
   call void @g1()
   br i1 %cmp216, label %for.body3, label %for.end
-; CHECK: edge for.body -> for.body3 probability is 62 / 124 = 50%
-; CHECK: edge for.body -> for.end probability is 62 / 124 = 50%
+; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
+; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
 
 for.body3:
   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %0 = load i32* %c, align 4
   %cmp4 = icmp eq i32 %0, %j.017
   br i1 %cmp4, label %for.inc, label %if.end
-; CHECK: edge for.body3 -> for.inc probability is 62 / 124 = 50%
-; CHECK: edge for.body3 -> if.end probability is 62 / 124 = 50%
+; CHECK: edge for.body3 -> for.inc probability is 16 / 32 = 50%
+; CHECK: edge for.body3 -> if.end probability is 16 / 32 = 50%
 
 if.end:
   %1 = load i32* %arrayidx5, align 4
   %cmp6 = icmp eq i32 %1, %j.017
   br i1 %cmp6, label %for.inc, label %if.end8
-; CHECK: edge if.end -> for.inc probability is 62 / 124 = 50%
-; CHECK: edge if.end -> if.end8 probability is 62 / 124 = 50%
+; CHECK: edge if.end -> for.inc probability is 16 / 32 = 50%
+; CHECK: edge if.end -> if.end8 probability is 16 / 32 = 50%
 
 if.end8:
   %2 = load i32* %arrayidx9, align 4
   %cmp10 = icmp eq i32 %2, %j.017
   br i1 %cmp10, label %for.inc, label %if.end12
-; CHECK: edge if.end8 -> for.inc probability is 62 / 124 = 50%
-; CHECK: edge if.end8 -> if.end12 probability is 62 / 124 = 50%
+; CHECK: edge if.end8 -> for.inc probability is 16 / 32 = 50%
+; CHECK: edge if.end8 -> if.end12 probability is 16 / 32 = 50%
 
 if.end12:
   call void @g2()
   br label %for.inc
-; CHECK: edge if.end12 -> for.inc probability is 124 / 124 = 100%
+; CHECK: edge if.end12 -> for.inc probability is 16 / 16 = 100%
 
 for.inc:
   %inc = add nsw i32 %j.017, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body3
 ; CHECK: edge for.inc -> for.end probability is 4 / 128
 ; CHECK: edge for.inc -> for.body3 probability is 124 / 128
 

llvm/trunk/test/Analysis/BranchProbabilityInfo/pr18705.ll

+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+
+; Since neither of while.body's out-edges is an exit or a back edge,
+; calcLoopBranchHeuristics should return early without setting the weights.
+; calcFloatingPointHeuristics, which is run later, sets the weights.
+;
+; CHECK: edge while.body -> if.then probability is 20 / 32 = 62.5%
+; CHECK: edge while.body -> if.else probability is 12 / 32 = 37.5%
+
+define void @foo1(i32 %n, i32* nocapture %b, i32* nocapture %c, i32* nocapture %d, float* nocapture readonly %f0, float* nocapture readonly %f1) {
+entry:
+  %tobool8 = icmp eq i32 %n, 0
+  br i1 %tobool8, label %while.end, label %while.body.lr.ph
+
+while.body.lr.ph:
+  %0 = sext i32 %n to i64
+  br label %while.body
+
+while.body:
+  %indvars.iv = phi i64 [ %0, %while.body.lr.ph ], [ %indvars.iv.next, %if.end ]
+  %b.addr.011 = phi i32* [ %b, %while.body.lr.ph ], [ %b.addr.1, %if.end ]
+  %d.addr.010 = phi i32* [ %d, %while.body.lr.ph ], [ %incdec.ptr4, %if.end ]
+  %c.addr.09 = phi i32* [ %c, %while.body.lr.ph ], [ %c.addr.1, %if.end ]
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %arrayidx = getelementptr inbounds float* %f0, i64 %indvars.iv.next
+  %1 = load float* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds float* %f1, i64 %indvars.iv.next
+  %2 = load float* %arrayidx2, align 4
+  %cmp = fcmp une float %1, %2
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %incdec.ptr = getelementptr inbounds i32* %b.addr.011, i64 1
+  %3 = load i32* %b.addr.011, align 4
+  %add = add nsw i32 %3, 12
+  store i32 %add, i32* %b.addr.011, align 4
+  br label %if.end
+
+if.else:
+  %incdec.ptr3 = getelementptr inbounds i32* %c.addr.09, i64 1
+  %4 = load i32* %c.addr.09, align 4
+  %sub = add nsw i32 %4, -13
+  store i32 %sub, i32* %c.addr.09, align 4
+  br label %if.end
+
+if.end:
+  %c.addr.1 = phi i32* [ %c.addr.09, %if.then ], [ %incdec.ptr3, %if.else ]
+  %b.addr.1 = phi i32* [ %incdec.ptr, %if.then ], [ %b.addr.011, %if.else ]
+  %incdec.ptr4 = getelementptr inbounds i32* %d.addr.010, i64 1
+  store i32 14, i32* %d.addr.010, align 4
+  %5 = trunc i64 %indvars.iv.next to i32
+  %tobool = icmp eq i32 %5, 0
+  br i1 %tobool, label %while.end, label %while.body
+
+while.end:
+  ret void
+}
+

llvm/trunk/test/CodeGen/ARM/ifcvt-branch-weight-bug.ll

 ; lor.lhs.false.i -> for.cond.backedge (1048575)
 ;                 -> cond.false.i (1)
 ; Afer if conversion, we have
 ; for.body -> for.cond.backedge (130023362)
 ;          -> cond.false.i (62)
 ; CHECK: BB#1: derived from LLVM BB %for.body
 ; CHECK: Successors according to CFG: BB#2(130023362) BB#4(62)
 for.body:
-  br i1 undef, label %for.cond.backedge, label %lor.lhs.false.i
+  br i1 undef, label %for.cond.backedge, label %lor.lhs.false.i, !prof !1
 
 for.cond.backedge:
   %tobool = icmp eq %classL* undef, null
   br i1 %tobool, label %for.end, label %for.body
 
 lor.lhs.false.i:
   %tobool.i.i7 = icmp eq i32 undef, 0
   br i1 %tobool.i.i7, label %for.cond.backedge, label %cond.false.i
_ZN1M6spliceEv.exit:
   unreachable
 }
 
 declare %classL* @_ZN1M1JI1LS1_EcvPS1_Ev(%classM2*)
 declare void @_ZN1F10handleMoveEb(%classF*, i1 zeroext)
 declare void @_Z3fn1v()
 
 !0 = metadata !{metadata !"clang version 3.5"}
+!1 = metadata !{metadata !"branch_weights", i32 62, i32 62}