Teach ScalarEvolution to consider loop preheaders in the search for
an if statement that guards a loop, to allow indvars to avoid smax
operations in more situations.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56232 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index db9792e..60980d2 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1480,6 +1480,12 @@
SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
bool isSigned);
+ /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
+ /// (which may not be an immediate predecessor) which has exactly one
+ /// successor from which BB is reachable, or null if no such block is
+ /// found.
+ BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
+
/// executesAtLeastOnce - Test whether entry to the loop is protected by
/// a conditional between LHS and RHS.
bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS);
@@ -1825,6 +1831,11 @@
case Instruction::Select:
// This could be a smax or umax that was lowered earlier.
// Try to recover it.
+ //
+ // FIXME: This doesn't recognize code like this:
+ // %t = icmp sgt i32 %n, -1
+ // %max = select i1 %t, i32 %n, i32 0
+ //
if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1);
@@ -2703,6 +2714,28 @@
return UnknownValue;
}
+/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
+/// (which may not be an immediate predecessor) which has exactly one
+/// successor from which BB is reachable, or null if no such block is
+/// found.
+///
+BasicBlock *
+ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
+ // If the block has a unique predecessor, the predecessor must have
+ // no other successors from which BB is reachable.
+ if (BasicBlock *Pred = BB->getSinglePredecessor())
+ return Pred;
+
+ // A loop's header is defined to be a block that dominates the loop.
+ // If the loop has a preheader, it must be a block that has exactly
+ // one successor that can reach BB. This is slightly more strict
+ // than necessary, but works if critical edges are split.
+ if (Loop *L = LI.getLoopFor(BB))
+ return L->getLoopPreheader();
+
+ return 0;
+}
+
/// executesAtLeastOnce - Test whether entry to the loop is protected by
/// a conditional between LHS and RHS.
bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
@@ -2711,14 +2744,11 @@
BasicBlock *PreheaderDest = L->getHeader();
// Starting at the preheader, climb up the predecessor chain, as long as
- // there are unique predecessors, looking for a conditional branch that
- // protects the loop.
- //
- // This is a conservative apporoximation of a climb of the
- // control-dependence predecessors.
-
- for (; Preheader; PreheaderDest = Preheader,
- Preheader = Preheader->getSinglePredecessor()) {
+ // there are predecessors that can be found that have unique successors
+ // leading to the original header.
+ for (; Preheader;
+ PreheaderDest = Preheader,
+ Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
BranchInst *LoopEntryPredicate =
dyn_cast<BranchInst>(Preheader->getTerminator());