[BPI] Detect branches in loops that make themselves not taken

[john.brawn]

Summary

If we have a loop like this:

int n = 0;
while (...) {
 if (++n >= MAX) {
   n = 0;
 }
}

then the body of the 'if' statement will only be executed once every MAX iterations. Detect this by looking for branches in loops where taking the branch makes the branch condition evaluate to 'not taken' in the next iteration of the loop, and reduce the probability of such branches.

This slightly improves EEMBC benchmarks on cortex-m4/cortex-m33 due to making better choices in if-conversion, but has no effect on any other cpu/benchmark that I could detect.

[davidxl]

Why not putting this change into BranchProbablityInfo.cpp, so that other components can benefit from the more precise BP info?

[john.brawn]

In D35804#819041, @davidxl wrote:

Why not putting this change into BranchProbablityInfo.cpp, so that other components can benefit from the more precise BP info?

I'm not sure what you mean here, this change is in BranchProbabilityInfo.cpp?

[davidxl]

Sorry about the noise -- I was juggling around several different issues :)

[davidxl]

lib/Analysis/BranchProbabilityInfo.cpp

428 ↗

(On Diff #107916)

Can you extract the new logic into a separate function : computeUnlikelySuccs Or some other name?

445 ↗

(On Diff #107916)

If the logic is extracted to a helper function, do a early return here to make it clearer.

448 ↗

(On Diff #107916)

Early return if condition is not met.

458 ↗

(On Diff #107916)

limit the walk within the enclosing loop?

465 ↗

(On Diff #107916)

early return if there is no phi found?

483 ↗

(On Diff #107916)

continue if not const

488 ↗

(On Diff #107916)

move this down. The first one should always be non-null.

502 ↗

(On Diff #107916)

It is probably not too interesting to handle the opposite scenario -- the successor sets some value which makes the branch to it more likely .

test/Analysis/BranchProbabilityInfo/loop.ll

400 ↗

(On Diff #107916)

no need to check unconditional branch.

[john.brawn]

Updated patch according to review comments.

[john.brawn]

test/Analysis/BranchProbabilityInfo/loop.ll

400 ↗

(On Diff #107916)

The other tests in this file check the probabilities of all of the branches, not just the unconditional ones, so I'd rather do the same here for the sake of consistency.

[john.brawn]

Ping.

[davidxl]

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

[john.brawn]

In D35804#833008, @davidxl wrote:

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

I've finally gotten around to gathering some data on this. Over the entire LLVM test suite (which may or may not be a useful data set, I don't know), for each call to computeUnlikelySuccessors:

• 56% execute the first loop (i.e. the block does a conditional branch based on a compare with a constant)
• 19% execute the second loop (i.e. we found a suitable phi node)
• 0.11% insert at least one element into UnlikelyBlocks

I measured the increase to the overall buildtime of the LLVM test suite as 2%.

[john.brawn]

Ping.

[hfinkel]

In D35804#881223, @john.brawn wrote:

In D35804#833008, @davidxl wrote:

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

I've finally gotten around to gathering some data on this. Over the entire LLVM test suite (which may or may not be a useful data set, I don't know), for each call to computeUnlikelySuccessors:

• 56% execute the first loop (i.e. the block does a conditional branch based on a compare with a constant)
• 19% execute the second loop (i.e. we found a suitable phi node)
• 0.11% insert at least one element into UnlikelyBlocks

I measured the increase to the overall buildtime of the LLVM test suite as 2%.

How confident are you in this increase? Is this noise? An actual 2% increase in compile time seems expensive for what this is doing.

[john.brawn]

How confident are you in this increase? Is this noise? An actual 2% increase in compile time seems expensive for what this is doing.

Not very. I've finally gotten around to getting more measurements, and the result from building the LLVM test suite 10 times (average combined build time of all objects on my machine, 95% confidence intervals) is: before 741s +/- 6s, after 746s +/- 9s. So I would guess this means there's no overall difference, given that each amount lies within the confidence interval of the other plus looking at the individual objects there's none where the confidence intervals don't overlap, but I have little experience in interpreting these kinds of statistics.

[john.brawn]

Ping.

[john.brawn]

Ping.

[john.brawn]

Rebase and ping.

[john.brawn]

Ping.

[john.brawn]

Ping.

[davidxl]

The branch probability depends on other factors which is not considered here.

For instance

1. the value of MAX. In the example, if MAX is 1, then the branch probablity should be 50%
2. the step /increment of n

More generally, the predicted probability should depend on MAX/step. The larger the value, the less likely the branch is taken.

lib/Analysis/BranchProbabilityInfo.cpp

463 ↗

(On Diff #128943)

Add some documentation on the function documenting the parameters.

[john.brawn]

Add a comment to computeUnlikelySuccessors.

[john.brawn]

In D35804#1002438, @davidxl wrote:

The branch probability depends on other factors which is not considered here.

For instance

1. the value of MAX. In the example, if MAX is 1, then the branch probablity should be 50%
2. the step /increment of n

More generally, the predicted probability should depend on MAX/step. The larger the value, the less likely the branch is taken.

That's true, but making the probability more precise would make the analysis here more complicated and I don't think it's worth it. 50% is a safe lower bound: we know the branch will be not taken at least 50% of the time and never less than that, assuming a large enough number of iterations (for small numbers of iterations whether the iteration count is even/odd will have an effect, e.g. for 1 iteration the branch may be always taken, but when the loop has a small number of iterations it won't be hot so it doesn't matter what we think the probability is).

[john.brawn]

Add a FIXME comment for possible improvement to unlikelyhood measure.

[davidxl]

LGTM

llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp

 //          | (Weight = 4)
 //          V
 //         BB3
 //
 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
 static const uint32_t LBH_TAKEN_WEIGHT = 124;
 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
+// Unlikely edges within a loop are half as likely as other edges
+static const uint32_t LBH_UNLIKELY_WEIGHT = 62;
 
 /// \brief Unreachable-terminating branch taken probability.
 ///
 /// This is the probability for a branch being taken to a block that terminates
 /// (eventually) in unreachable. These are predicted as unlikely as possible.
 /// All reachable probability will equally share the remaining part.
 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
 
bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
                                    return getSCCNum(Pred, SccI) != SccNum;
                                  });
     HeaderMapIt->second = IsHeader;
     return IsHeader;
   } else
     return HeaderMapIt->second;
 }
 
+// Compute the unlikely successors to the block BB in the loop L, specifically
+// those that are unlikely because this is a loop, and add them to the
+// UnlikelyBlocks set.
+static void
+computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
+                          SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
+  // Sometimes in a loop we have a branch whose condition is made false by
+  // taking it. This is typically something like
+  //  int n = 0;
+  //  while (...) {
+  //    if (++n >= MAX) {
+  //      n = 0;
+  //    }
+  //  }
+  // In this sort of situation taking the branch means that at the very least it
+  // won't be taken again in the next iteration of the loop, so we should
+  // consider it less likely than a typical branch.
+  //
+  // We detect this by looking back through the graph of PHI nodes that sets the
+  // value that the condition depends on, and seeing if we can reach a successor
+  // block which can be determined to make the condition false.
+  //
+  // FIXME: We currently consider unlikely blocks to be half as likely as other
+  // blocks, but if we consider the example above the likelyhood is actually
+  // 1/MAX. We could therefore be more precise in how unlikely we consider
+  // blocks to be, but it would require more careful examination of the form
+  // of the comparison expression.
+  const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
+  if (!BI || !BI->isConditional())
+    return;
+
+  // Check if the branch is based on an instruction compared with a constant
+  CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
+  if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
+      !isa<Constant>(CI->getOperand(1)))
+    return;
+
+  // Either the instruction must be a PHI, or a chain of operations involving
+  // constants that ends in a PHI which we can then collapse into a single value
+  // if the PHI value is known.
+  Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
+  PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
+  Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
+  // Collect the instructions until we hit a PHI
+  std::list<BinaryOperator*> InstChain;
+  while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
+         isa<Constant>(CmpLHS->getOperand(1))) {
+    // Stop if the chain extends outside of the loop
+    if (!L->contains(CmpLHS))
+      return;
+    InstChain.push_front(dyn_cast<BinaryOperator>(CmpLHS));
+    CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
+    if (CmpLHS)
+      CmpPHI = dyn_cast<PHINode>(CmpLHS);
+  }
+  if (!CmpPHI || !L->contains(CmpPHI))
+    return;
+
+  // Trace the phi node to find all values that come from successors of BB
+  SmallPtrSet<PHINode*, 8> VisitedInsts;
+  SmallVector<PHINode*, 8> WorkList;
+  WorkList.push_back(CmpPHI);
+  VisitedInsts.insert(CmpPHI);
+  while (!WorkList.empty()) {
+    PHINode *P = WorkList.back();
+    WorkList.pop_back();
+    for (BasicBlock *B : P->blocks()) {
+      // Skip blocks that aren't part of the loop
+      if (!L->contains(B))
+        continue;
+      Value *V = P->getIncomingValueForBlock(B);
+      // If the source is a PHI add it to the work list if we haven't
+      // already visited it.
+      if (PHINode *PN = dyn_cast<PHINode>(V)) {
+        if (VisitedInsts.insert(PN).second)
+          WorkList.push_back(PN);
+        continue;
+      }
+      // If this incoming value is a constant and B is a successor of BB, then
+      // we can constant-evaluate the compare to see if it makes the branch be
+      // taken or not.
+      Constant *CmpLHSConst = dyn_cast<Constant>(V);
+      if (!CmpLHSConst ||
+          std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB))
+        continue;
+      // First collapse InstChain
+      for (Instruction *I : InstChain) {
+        CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst,
+                                        dyn_cast<Constant>(I->getOperand(1)),
+                                        true);
+        if (!CmpLHSConst)
+          break;
+      }
+      if (!CmpLHSConst)
+        continue;
+      // Now constant-evaluate the compare
+      Constant *Result = ConstantExpr::getCompare(CI->getPredicate(),
+                                                  CmpLHSConst, CmpConst, true);
+      // If the result means we don't branch to the block then that block is
+      // unlikely.
+      if (Result &&
+          ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
+           (Result->isOneValue() && B == BI->getSuccessor(1))))
+        UnlikelyBlocks.insert(B);
+    }
+  }
+}
+
 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 // as taken, exiting edges as not-taken.
 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
                                                      const LoopInfo &LI,
                                                      SccInfo &SccI) {
   int SccNum;
   Loop *L = LI.getLoopFor(BB);
   if (!L) {
     SccNum = getSCCNum(BB, SccI);
     if (SccNum < 0)
       return false;
   }
 
+  SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks;
+  if (L)
+    computeUnlikelySuccessors(BB, L, UnlikelyBlocks);
+
   SmallVector<unsigned, 8> BackEdges;
   SmallVector<unsigned, 8> ExitingEdges;
   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
+  SmallVector<unsigned, 8> UnlikelyEdges;
 
   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
     // irreducible loops.
     if (L) {
-      if (!L->contains(*I))
+      if (UnlikelyBlocks.count(*I) != 0)
+        UnlikelyEdges.push_back(I.getSuccessorIndex());
+      else 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());
     } else {
       if (getSCCNum(*I, SccI) != SccNum)
         ExitingEdges.push_back(I.getSuccessorIndex());
       else if (isSCCHeader(*I, SccNum, SccI))
         BackEdges.push_back(I.getSuccessorIndex());
       else
         InEdges.push_back(I.getSuccessorIndex());
     }
   }
 
-  if (BackEdges.empty() && ExitingEdges.empty())
+  if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty())
     return false;
 
   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
   // normalize them so that they sum up to one.
-  BranchProbability Probs[] = {BranchProbability::getZero(),
-                               BranchProbability::getZero(),
-                               BranchProbability::getZero()};
   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
+                   (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
-  if (!BackEdges.empty())
-    Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
-  if (!InEdges.empty())
-    Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
-  if (!ExitingEdges.empty())
-    Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
 
   if (uint32_t numBackEdges = BackEdges.size()) {
-    auto Prob = Probs[0] / numBackEdges;
+    BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
+    auto Prob = TakenProb / numBackEdges;
     for (unsigned SuccIdx : BackEdges)
       setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   if (uint32_t numInEdges = InEdges.size()) {
-    auto Prob = Probs[1] / numInEdges;
+    BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
+    auto Prob = TakenProb / numInEdges;
     for (unsigned SuccIdx : InEdges)
       setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   if (uint32_t numExitingEdges = ExitingEdges.size()) {
-    auto Prob = Probs[2] / numExitingEdges;
+    BranchProbability NotTakenProb = BranchProbability(LBH_NONTAKEN_WEIGHT,
+                                                       Denom);
+    auto Prob = NotTakenProb / numExitingEdges;
     for (unsigned SuccIdx : ExitingEdges)
       setEdgeProbability(BB, SuccIdx, Prob);
   }
 
+  if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
+    BranchProbability UnlikelyProb = BranchProbability(LBH_UNLIKELY_WEIGHT,
+                                                       Denom);
+    auto Prob = UnlikelyProb / numUnlikelyEdges;
+    for (unsigned SuccIdx : UnlikelyEdges)
+      setEdgeProbability(BB, SuccIdx, Prob);
+  }
+
   return true;
 }
 
 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
                                                const TargetLibraryInfo *TLI) {
   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;

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

 for.inc:
   %inc = add nsw i32 %i.addr.1, 1
   br label %for.cond
 ; CHECK:  edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 end:
   ret void
 }
+
+; Check that the for.body -> if.then edge is considered unlikely due to making
+; the if-condition false for the next iteration of the loop.
+define i32 @test10(i32 %n, i32* %p) {
+entry:
+  br label %for.cond
+; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+for.cond:
+  %count.0 = phi i32 [ 0, %entry ], [ %count.1, %for.inc ]
+  %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc3, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: edge for.cond -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge for.cond -> for.cond.cleanup probability is 0x04000000 / 0x80000000 = 3.12%
+
+for.cond.cleanup:
+  ret i32 %sum.0
+
+for.body:
+  %arrayidx = getelementptr inbounds i32, i32* %p, i32 %i.0
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %count.0, 1
+  %cmp1 = icmp sgt i32 %count.0, 6
+  br i1 %cmp1, label %if.then, label %for.inc
+; CHECK: edge for.body -> if.then probability is 0x2aaaaaab / 0x80000000 = 33.33%
+; CHECK: edge for.body -> for.inc probability is 0x55555555 / 0x80000000 = 66.67%
+
+if.then:
+  store i32 %add, i32* %arrayidx, align 4
+  br label %for.inc
+; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+for.inc:
+  %count.1 = phi i32 [ 0, %if.then ], [ %inc, %for.body ]
+  %sum.1 = phi i32 [ 0, %if.then ], [ %add, %for.body ]
+  %inc3 = add nsw i32 %i.0, 1
+  br label %for.cond
+; CHECK: edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+}
+
+; Each successor to for.body makes itself not be taken in the next iteration, so
+; both should be equally likely
+define i32 @test11(i32 %n, i32* %p) {
+entry:
+  br label %for.cond
+; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+for.cond:
+  %flip.0 = phi i32 [ 0, %entry ], [ %flip.1, %for.inc ]
+  %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: edge for.cond -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge for.cond -> for.cond.cleanup probability is 0x04000000 / 0x80000000 = 3.12%
+
+for.cond.cleanup:
+  ret i32 %sum.0
+
+for.body:
+  %tobool = icmp eq i32 %flip.0, 0
+  %arrayidx1 = getelementptr inbounds i32, i32* %p, i32 %i.0
+  %0 = load i32, i32* %arrayidx1, align 4
+  br i1 %tobool, label %if.else, label %if.then
+; CHECK: edge for.body -> if.else probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge for.body -> if.then probability is 0x40000000 / 0x80000000 = 50.00%
+
+if.then:
+  %add = add nsw i32 %0, %sum.0
+  store i32 %add, i32* %arrayidx1, align 4
+  br label %for.inc
+; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+if.else:
+  %add2 = add nsw i32 %sum.0, %0
+  br label %for.inc
+; CHECK: edge if.else -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+for.inc:
+  %flip.1 = phi i32 [ 0, %if.then ], [ 1, %if.else ]
+  %sum.1 = phi i32 [ %sum.0, %if.then ], [ %add2, %if.else ]
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+; CHECK: edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+}