[SCEV] Pick backedge values for phi nodes correctly

[sanjoy]

Summary

getConstantEvolutionLoopExitValue and ComputeExitCountExhaustively
assumed all phi nodes in the loop header have the same order of incoming
values. This is not correct, and this commit changes
getConstantEvolutionLoopExitValue and ComputeExitCountExhaustively
to lookup the backedge value of a phi node using the loop's latch block.

Unfortunately, there is still some code duplication
getConstantEvolutionLoopExitValue and ComputeExitCountExhaustively.
At some point in the future we should extract out a helper class /
method that can evolve constant evolution phi nodes across iterations.

Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis!

Depends on D13457.

[reames]

LGTM.

lib/Analysis/ScalarEvolution.cpp

5745 ↗

(On Diff #36589)

This line should probably be below the following comment.

5759 ↗

(On Diff #36589)

Please put a comment that says not all phis have to list their arguments in the same order. This is subtle and easily confused.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (BEs.ugt(MaxBruteForceIterations))
     return ConstantEvolutionLoopExitValue[PN] = nullptr;  // Not going to evaluate it.
 
   Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
 
   DenseMap<Instruction *, Constant *> CurrentIterVals;
   BasicBlock *Header = L->getHeader();
   assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
 
-  // Since the loop is canonicalized, the PHI node must have two entries.  One
+  BasicBlock *Latch = L->getLoopLatch();
+  if (!Latch)
+    return nullptr;
+
+  // Since the loop has one latch, the PHI node must have two entries.  One
   // entry must be a constant (coming in from outside of the loop), and the
   // second must be derived from the same PHI.
-  bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
+
+  BasicBlock *NonLatch = Latch == PN->getIncomingBlock(0)
+                             ? PN->getIncomingBlock(1)
+                             : PN->getIncomingBlock(0);
+
+  assert(PN->getNumIncomingValues() == 2 && "Follows from having one latch!");
+
+  // Note: not all PHI nodes in the same block have to have their incoming
+  // values in the same order, so we use the basic block to look up the incoming
+  // value, not an index.
+
   for (auto &I : *Header) {
     PHINode *PHI = dyn_cast<PHINode>(&I);
     if (!PHI) break;
     auto *StartCST =
-      dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
+        dyn_cast<Constant>(PHI->getIncomingValueForBlock(NonLatch));
     if (!StartCST) continue;
     CurrentIterVals[PHI] = StartCST;
   }
   if (!CurrentIterVals.count(PN))
     return RetVal = nullptr;
 
-  Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
+  Value *BEValue = PN->getIncomingValueForBlock(Latch);
 
   // Execute the loop symbolically to determine the exit value.
   if (BEs.getActiveBits() >= 32)
     return RetVal = nullptr; // More than 2^32-1 iterations?? Not doing it!
 
   unsigned NumIterations = BEs.getZExtValue(); // must be in range
   unsigned IterationNum = 0;
   const DataLayout &DL = F.getParent()->getDataLayout();
for (const auto &I : CurrentIterVals) {
       PHIsToCompute.emplace_back(PHI, I.second);
     }
     // We use two distinct loops because EvaluateExpression may invalidate any
     // iterators into CurrentIterVals.
     for (const auto &I : PHIsToCompute) {
       PHINode *PHI = I.first;
       Constant *&NextPHI = NextIterVals[PHI];
       if (!NextPHI) {   // Not already computed.
-        Value *BEValue = PHI->getIncomingValue(SecondIsBackedge);
+        Value *BEValue = PHI->getIncomingValueForBlock(Latch);
         NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI);
       }
       if (NextPHI != I.second)
         StoppedEvolving = false;
     }
 
     // If all entries in CurrentIterVals == NextIterVals then we can stop
     // iterating, the loop can't continue to change.
const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L,
   // If the loop is canonicalized, the PHI will have exactly two entries.
   // That's the only form we support here.
   if (PN->getNumIncomingValues() != 2) return getCouldNotCompute();
 
   DenseMap<Instruction *, Constant *> CurrentIterVals;
   BasicBlock *Header = L->getHeader();
   assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
 
-  // One entry must be a constant (coming in from outside of the loop), and the
-  // second must be derived from the same PHI.
-  bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
+  BasicBlock *Latch = L->getLoopLatch();
+  assert(Latch && "Should follow from NumIncomingValues == 2!");
+
+  // NonLatch is the preheader, or something equivalent.
+  BasicBlock *NonLatch = Latch == PN->getIncomingBlock(0)
+                             ? PN->getIncomingBlock(1)
+                             : PN->getIncomingBlock(0);
+
+  // Note: not all PHI nodes in the same block have to have their incoming
+  // values in the same order, so we use the basic block to look up the incoming
+  // value, not an index.
+
   for (auto &I : *Header) {
     PHINode *PHI = dyn_cast<PHINode>(&I);
     if (!PHI)
       break;
     auto *StartCST =
-        dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
+      dyn_cast<Constant>(PHI->getIncomingValueForBlock(NonLatch));
     if (!StartCST) continue;
     CurrentIterVals[PHI] = StartCST;
   }
   if (!CurrentIterVals.count(PN))
     return getCouldNotCompute();
 
   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
   // the loop symbolically to determine when the condition gets a value of
for (const auto &I : CurrentIterVals) {
       PHINode *PHI = dyn_cast<PHINode>(I.first);
       if (!PHI || PHI->getParent() != Header) continue;
       PHIsToCompute.push_back(PHI);
     }
     for (PHINode *PHI : PHIsToCompute) {
       Constant *&NextPHI = NextIterVals[PHI];
       if (NextPHI) continue;    // Already computed!
 
-      Value *BEValue = PHI->getIncomingValue(SecondIsBackedge);
+      Value *BEValue = PHI->getIncomingValueForBlock(Latch);
       NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI);
     }
     CurrentIterVals.swap(NextIterVals);
   }
 
   // Too many iterations were needed to evaluate.
   return getCouldNotCompute();
 }

llvm/trunk/test/Transforms/IndVarSimplify/pr25060.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+define i16 @fn1() {
+; CHECK-LABEL: @fn1(
+entry:
+  br label %bb1
+
+bb1:
+  %i = phi i16 [ 0, %entry ], [ 1, %bb1 ]
+  %storemerge = phi i16 [ %storemerge2, %bb1 ], [ 0, %entry ]
+  %storemerge2 = phi i16 [ 10, %entry ], [ 200, %bb1 ]
+  %tmp10 = icmp eq i16 %i, 1
+  br i1 %tmp10, label %bb5, label %bb1
+
+bb5:
+  %storemerge.lcssa = phi i16 [ %storemerge, %bb1 ]
+; CHECK: ret i16 10
+  ret i16 %storemerge.lcssa
+}
+
+define i16 @fn2() {
+; CHECK-LABEL: @fn2(
+entry:
+  br label %bb1
+
+bb1:
+  %canary = phi i16 [ 0, %entry ], [ %canary.inc, %bb1 ]
+  %i = phi i16 [ 0, %entry ], [ %storemerge, %bb1 ]
+  %storemerge = phi i16 [ 0, %bb1 ], [ 10, %entry ]
+  %canary.inc = add i16 %canary, 1
+  %_tmp10 = icmp eq i16 %i, 10
+  br i1 %_tmp10, label %bb5, label %bb1
+
+bb5:
+; CHECK: ret i16 1
+  ret i16 %canary
+}