Fix disabled SCEV analysis caused r141161 and add unit test.

I noticed during self-review that my previous checkin disabled some
analysis. Even with the reenabled analysis the test case runs in about
5ms. Without the fix, it will take several minutes at least.

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

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index ad176098cefa76088782b7ce620eda8606d095a8..f5804430ee23a9c361b96b414a794d99b7f4f7c3 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -4691,7 +4691,7 @@ static bool canConstantEvolve(Instruction *I, const Loop *L) {
 /// recursing through each instruction operand until reaching a loop header phi.
 static PHINode *
 getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
-                               SmallPtrSet<Instruction *, 8> &Visited) {
+                               DenseMap<Instruction *, PHINode *> &PHIMap) {
 
   // Otherwise, we can evaluate this instruction if all of its operands are
   // constant or derived from a PHI node themselves.
@@ -4705,18 +4705,26 @@ getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
     if (!OpInst || !canConstantEvolve(OpInst, L)) return 0;
 
     PHINode *P = dyn_cast<PHINode>(OpInst);
-    if (!P) {
-      // If this operand is already visited, ignore it. It's evolving phi has
-      // already been shown to be consistent on the first path that reached it.
-      if (!Visited.insert(OpInst)) continue;
-
-      P = getConstantEvolvingPHIOperands(OpInst, L, Visited);
+    if (P) {
+      if (PHI && PHI != P) return 0; // Evolving from multiple different PHIs.
+      PHI = P;
+      continue;
     }
-    if (P == 0) return 0;  // Not evolving from PHI
-    if (PHI == 0)
+
+    // If this operand is already visited, reuse the prior result.
+    P = PHIMap.lookup(OpInst);
+    if (P) {
+      assert(!PHI || P == PHI && "inconsitent data flow");
       PHI = P;
-    else if (PHI != P)
-      return 0;  // Evolving from multiple different PHIs.
+      continue;
+    }
+    // Recurse and memoize the results, whether a phi is found or not.
+    // This recursive call invalidates pointers into PHIMap.
+    P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap);
+    PHIMap[OpInst] = P;
+    if (P == 0) return 0;        // Not evolving from PHI
+    if (PHI && PHI != P) return 0;  // Evolving from multiple different PHIs.
+    PHI = P;
   }
   // This is a expression evolving from a constant PHI!
   return PHI;
@@ -4736,9 +4744,8 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
   }
 
   // Record non-constant instructions contained by the loop.
-  SmallPtrSet<Instruction *, 8> Visited;
-  Visited.insert(I);
-  return getConstantEvolvingPHIOperands(I, L, Visited);
+  DenseMap<Instruction *, PHINode *> PHIMap;
+  return getConstantEvolvingPHIOperands(I, L, PHIMap);
 }
 
 /// EvaluateExpression - Given an expression that passes the
@@ -4748,6 +4755,7 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
 static Constant *EvaluateExpression(Value *V, const Loop *L,
                                     DenseMap<Instruction *, Constant *> &Vals,
                                     const TargetData *TD) {
+  // Convenient constant check, but redundant for recursive calls.
   if (Constant *C = dyn_cast<Constant>(V)) return C;
 
   Instruction *I = cast<Instruction>(V);
@@ -4760,8 +4768,15 @@ static Constant *EvaluateExpression(Value *V, const Loop *L,
   std::vector<Constant*> Operands(I->getNumOperands());
 
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
-    Operands[i] = EvaluateExpression(I->getOperand(i), L, Vals, TD);
-    if (Operands[i] == 0) return 0;
+    Instruction *Operand = dyn_cast<Instruction>(I->getOperand(i));
+    if (!Operand) {
+      Operands[i] = cast<Constant>(I->getOperand(i));
+      continue;
+    }
+    Constant *C = EvaluateExpression(Operand, L, Vals, TD);
+    Vals[Operand] = C;
+    if (!C) return 0;
+    Operands[i] = C;
   }
 
   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
@@ -4861,9 +4876,9 @@ const SCEV * ScalarEvolution::ComputeExitCountExhaustively(const Loop *L,
   // "ExitWhen".
   unsigned IterationNum = 0;
   unsigned MaxIterations = MaxBruteForceIterations;   // Limit analysis.
-  DenseMap<Instruction *, Constant *> PHIValMap;
   for (Constant *PHIVal = StartCST;
        IterationNum != MaxIterations; ++IterationNum) {
+    DenseMap<Instruction *, Constant *> PHIValMap;
     PHIValMap[PN] = PHIVal;
     ConstantInt *CondVal =
       dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, L, PHIValMap, TD));