Instead of eagerly creating new SCEVs to replace all SCEVs that are

affected after a PHI node has been analyzed, just remove affected
SCEVs from the Scalars map, so that they'll be (lazily) recreated as
needed. This avoids creating SCEV objects that aren't actually needed.

Also, rewrite the associated def-use walking code to be non-recursive
and to continue traversing past Instructions that don't have an
entry in the Scalars map.


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

1 files changed, 19 insertions, 55 deletions

diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 830143b..99df1df 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -52,10 +52,8 @@ namespace llvm {
 
     virtual const Type *getType() const;
 
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      return this;
+    virtual bool hasOperand(const SCEV *) const {
+      return false;
     }
 
     bool dominates(BasicBlock *BB, DominatorTree *DT) const {
@@ -94,6 +92,10 @@ namespace llvm {
       return Op->hasComputableLoopEvolution(L);
     }
 
+    virtual bool hasOperand(const SCEV *O) const {
+      return Op == O || Op->hasOperand(O);
+    }
+
     virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -116,15 +118,6 @@ namespace llvm {
                      const SCEV *op, const Type *ty);
 
   public:
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
-      if (H == Op)
-        return this;
-      return SE.getTruncateExpr(H, Ty);
-    }
-
     virtual void print(raw_ostream &OS) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -145,15 +138,6 @@ namespace llvm {
                        const SCEV *op, const Type *ty);
 
   public:
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
-      if (H == Op)
-        return this;
-      return SE.getZeroExtendExpr(H, Ty);
-    }
-
     virtual void print(raw_ostream &OS) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -174,15 +158,6 @@ namespace llvm {
                        const SCEV *op, const Type *ty);
 
   public:
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
-      if (H == Op)
-        return this;
-      return SE.getSignExtendExpr(H, Ty);
-    }
-
     virtual void print(raw_ostream &OS) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -240,6 +215,13 @@ namespace llvm {
       return HasVarying;
     }
 
+    virtual bool hasOperand(const SCEV *O) const {
+      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+        if (O == getOperand(i) || getOperand(i)->hasOperand(O))
+          return true;
+      return false;
+    }
+
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
     virtual const Type *getType() const { return getOperand(0)->getType(); }
@@ -267,10 +249,6 @@ namespace llvm {
       : SCEVNAryExpr(ID, T, ops) {}
 
   public:
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const;
-
     virtual const char *getOperationStr() const = 0;
 
     virtual void print(raw_ostream &OS) const;
@@ -353,15 +331,8 @@ namespace llvm {
              RHS->hasComputableLoopEvolution(L);
     }
 
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      const SCEV *L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
-      const SCEV *R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
-      if (L == LHS && R == RHS)
-        return this;
-      else
-        return SE.getUDivExpr(L, R);
+    virtual bool hasOperand(const SCEV *O) const {
+      return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
     }
 
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
@@ -449,14 +420,10 @@ namespace llvm {
     const SCEV *getNumIterationsInRange(ConstantRange Range,
                                        ScalarEvolution &SE) const;
 
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const;
-
     /// getPostIncExpr - Return an expression representing the value of
     /// this expression one iteration of the loop ahead.
-    const SCEV *getPostIncExpr(ScalarEvolution &SE) const {
-      return SE.getAddExpr(this, getStepRecurrence(SE));
+    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
+      return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
     }
 
     bool hasNoUnsignedOverflow() const { return SubclassData & (1 << 0); }
@@ -542,11 +509,8 @@ namespace llvm {
       return false; // not computable
     }
 
-    const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym,
-                                                 const SCEV *Conc,
-                                                 ScalarEvolution &SE) const {
-      if (&*Sym == this) return Conc;
-      return this;
+    virtual bool hasOperand(const SCEV *) const {
+      return false;
     }
 
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;