Implement Transforms/IndVarsSimplify/complex-scev.ll, a case where we didn't

recognize some simple affine IV's.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@27982 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index f0848569ddbe36c30762c8b8381eb6b7160dfe8e..c6e32c53ab7c4bbbf530307b7d31e75b8b42058b 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1295,6 +1295,31 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
               SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
               SCEVHandle PHISCEV  = SCEVAddRecExpr::get(StartVal, Accum, L);
 
+              // Okay, for the entire analysis of this edge we assumed the PHI
+              // to be symbolic.  We now need to go back and update all of the
+              // entries for the scalars that use the PHI (except for the PHI
+              // itself) to use the new analyzed value instead of the "symbolic"
+              // value.
+              ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
+              return PHISCEV;
+            }
+          }
+        } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
+          // Otherwise, this could be a loop like this:
+          //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
+          // In this case, j = {1,+,1}  and BEValue is j.
+          // Because the other in-value of i (0) fits the evolution of BEValue
+          // i really is an addrec evolution.
+          if (AddRec->getLoop() == L && AddRec->isAffine()) {
+            SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
+
+            // If StartVal = j.start - j.stride, we can use StartVal as the
+            // initial step of the addrec evolution.
+            if (StartVal == SCEV::getMinusSCEV(AddRec->getOperand(0),
+                                               AddRec->getOperand(1))) {
+              SCEVHandle PHISCEV = 
+                 SCEVAddRecExpr::get(StartVal, AddRec->getOperand(1), L);
+
               // Okay, for the entire analysis of this edge we assumed the PHI
               // to be symbolic.  We now need to go back and update all of the
               // entries for the scalars that use the PHI (except for the PHI