projects / oota-llvm.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be member
[oota-llvm.git] / include / llvm / Analysis / ScalarEvolutionExpressions.h
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 0ab3b3f4a5e2ad40d4b061ca64638551da31264c..8cb533a1f295b4771aa41a8c60acdab32359d1d3 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -37,19 +37,11 @@ namespace llvm {
     friend class ScalarEvolution;
 
     ConstantInt *V;
-    SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) :
+    SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
       SCEV(ID, scConstant), V(v) {}
   public:
     ConstantInt *getValue() const { return V; }
 
-    virtual bool isLoopInvariant(const Loop *L) const {
-      return true;
-    }
-
-    virtual bool hasComputableLoopEvolution(const Loop *L) const {
-      return false;  // Not loop variant
-    }
-
     virtual const Type *getType() const;
 
     virtual bool hasOperand(const SCEV *) const {
@@ -81,21 +73,13 @@ namespace llvm {
     const SCEV *Op;
     const Type *Ty;
 
-    SCEVCastExpr(const FoldingSetNodeID &ID,
+    SCEVCastExpr(const FoldingSetNodeIDRef ID,
                  unsigned SCEVTy, const SCEV *op, const Type *ty);
 
   public:
     const SCEV *getOperand() const { return Op; }
     virtual const Type *getType() const { return Ty; }
 
-    virtual bool isLoopInvariant(const Loop *L) const {
-      return Op->isLoopInvariant(L);
-    }
-
-    virtual bool hasComputableLoopEvolution(const Loop *L) const {
-      return Op->hasComputableLoopEvolution(L);
-    }
-
     virtual bool hasOperand(const SCEV *O) const {
       return Op == O || Op->hasOperand(O);
     }
@@ -120,7 +104,7 @@ namespace llvm {
   class SCEVTruncateExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
-    SCEVTruncateExpr(const FoldingSetNodeID &ID,
+    SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
                      const SCEV *op, const Type *ty);
 
   public:
@@ -140,7 +124,7 @@ namespace llvm {
   class SCEVZeroExtendExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
-    SCEVZeroExtendExpr(const FoldingSetNodeID &ID,
+    SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
                        const SCEV *op, const Type *ty);
 
   public:
@@ -160,7 +144,7 @@ namespace llvm {
   class SCEVSignExtendExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
-    SCEVSignExtendExpr(const FoldingSetNodeID &ID,
+    SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
                        const SCEV *op, const Type *ty);
 
   public:
@@ -180,53 +164,29 @@ namespace llvm {
   ///
   class SCEVNAryExpr : public SCEV {
   protected:
-    SmallVector<const SCEV *, 8> Operands;
+    // Since SCEVs are immutable, ScalarEvolution allocates operand
+    // arrays with its SCEVAllocator, so this class just needs a simple
+    // pointer rather than a more elaborate vector-like data structure.
+    // This also avoids the need for a non-trivial destructor.
+    const SCEV *const *Operands;
+    size_t NumOperands;
 
-    SCEVNAryExpr(const FoldingSetNodeID &ID,
-                 enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops)
-      : SCEV(ID, T), Operands(ops.begin(), ops.end()) {}
+    SCEVNAryExpr(const FoldingSetNodeIDRef ID,
+                 enum SCEVTypes T, const SCEV *const *O, size_t N)
+      : SCEV(ID, T), Operands(O), NumOperands(N) {}
 
   public:
-    unsigned getNumOperands() const { return (unsigned)Operands.size(); }
+    size_t getNumOperands() const { return NumOperands; }
     const SCEV *getOperand(unsigned i) const {
-      assert(i < Operands.size() && "Operand index out of range!");
+      assert(i < NumOperands && "Operand index out of range!");
       return Operands[i];
     }
 
-    const SmallVectorImpl<const SCEV *> &getOperands() const {
-      return Operands;
-    }
-    typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator;
-    op_iterator op_begin() const { return Operands.begin(); }
-    op_iterator op_end() const { return Operands.end(); }
-
-    virtual bool isLoopInvariant(const Loop *L) const {
-      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-        if (!getOperand(i)->isLoopInvariant(L)) return false;
-      return true;
-    }
+    typedef const SCEV *const *op_iterator;
+    op_iterator op_begin() const { return Operands; }
+    op_iterator op_end() const { return Operands + NumOperands; }
 
-    // hasComputableLoopEvolution - N-ary expressions have computable loop
-    // evolutions iff they have at least one operand that varies with the loop,
-    // but that all varying operands are computable.
-    virtual bool hasComputableLoopEvolution(const Loop *L) const {
-      bool HasVarying = false;
-      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-        if (!getOperand(i)->isLoopInvariant(L)) {
-          if (getOperand(i)->hasComputableLoopEvolution(L))
-            HasVarying = true;
-          else
-            return false;
-        }
-      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;
-    }
+    virtual bool hasOperand(const SCEV *O) const;
 
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
@@ -260,10 +220,9 @@ namespace llvm {
   ///
   class SCEVCommutativeExpr : public SCEVNAryExpr {
   protected:
-    SCEVCommutativeExpr(const FoldingSetNodeID &ID,
-                        enum SCEVTypes T,
-                        const SmallVectorImpl<const SCEV *> &ops)
-      : SCEVNAryExpr(ID, T, ops) {}
+    SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
+                        enum SCEVTypes T, const SCEV *const *O, size_t N)
+      : SCEVNAryExpr(ID, T, O, N) {}
 
   public:
     virtual const char *getOperationStr() const = 0;
@@ -287,9 +246,9 @@ namespace llvm {
   class SCEVAddExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
-    SCEVAddExpr(const FoldingSetNodeID &ID,
-                const SmallVectorImpl<const SCEV *> &ops)
-      : SCEVCommutativeExpr(ID, scAddExpr, ops) {
+    SCEVAddExpr(const FoldingSetNodeIDRef ID,
+                const SCEV *const *O, size_t N)
+      : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
     }
 
   public:
@@ -315,9 +274,9 @@ namespace llvm {
   class SCEVMulExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
-    SCEVMulExpr(const FoldingSetNodeID &ID,
-                const SmallVectorImpl<const SCEV *> &ops)
-      : SCEVCommutativeExpr(ID, scMulExpr, ops) {
+    SCEVMulExpr(const FoldingSetNodeIDRef ID,
+                const SCEV *const *O, size_t N)
+      : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
     }
 
   public:
@@ -339,22 +298,13 @@ namespace llvm {
 
     const SCEV *LHS;
     const SCEV *RHS;
-    SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs)
+    SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
       : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
 
   public:
     const SCEV *getLHS() const { return LHS; }
     const SCEV *getRHS() const { return RHS; }
 
-    virtual bool isLoopInvariant(const Loop *L) const {
-      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
-    }
-
-    virtual bool hasComputableLoopEvolution(const Loop *L) const {
-      return LHS->hasComputableLoopEvolution(L) &&
-             RHS->hasComputableLoopEvolution(L);
-    }
-
     virtual bool hasOperand(const SCEV *O) const {
       return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
     }
@@ -389,13 +339,9 @@ namespace llvm {
 
     const Loop *L;
 
-    SCEVAddRecExpr(const FoldingSetNodeID &ID,
-                   const SmallVectorImpl<const SCEV *> &ops, const Loop *l)
-      : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) {
-      for (size_t i = 0, e = Operands.size(); i != e; ++i)
-        assert(Operands[i]->isLoopInvariant(l) &&
-               "Operands of AddRec must be loop-invariant!");
-    }
+    SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
+                   const SCEV *const *O, size_t N, const Loop *l)
+      : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
 
   public:
     const SCEV *getStart() const { return Operands[0]; }
@@ -411,12 +357,6 @@ namespace llvm {
                               getLoop());
     }
 
-    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
-      return L == QL;
-    }
-
-    virtual bool isLoopInvariant(const Loop *QueryLoop) const;
-
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
     bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
@@ -471,9 +411,9 @@ namespace llvm {
   class SCEVSMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
-    SCEVSMaxExpr(const FoldingSetNodeID &ID,
-                 const SmallVectorImpl<const SCEV *> &ops)
-      : SCEVCommutativeExpr(ID, scSMaxExpr, ops) {
+    SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
+                 const SCEV *const *O, size_t N)
+      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
       // Max never overflows.
       setHasNoUnsignedWrap(true);
       setHasNoSignedWrap(true);
@@ -496,9 +436,9 @@ namespace llvm {
   class SCEVUMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
-    SCEVUMaxExpr(const FoldingSetNodeID &ID,
-                 const SmallVectorImpl<const SCEV *> &ops)
-      : SCEVCommutativeExpr(ID, scUMaxExpr, ops) {
+    SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
+                 const SCEV *const *O, size_t N)
+      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
       // Max never overflows.
       setHasNoUnsignedWrap(true);
       setHasNoSignedWrap(true);
@@ -519,15 +459,28 @@ namespace llvm {
   /// value, and only represent it as its LLVM Value.  This is the "bottom"
   /// value for the analysis.
   ///
-  class SCEVUnknown : public SCEV {
+  class SCEVUnknown : public SCEV, private CallbackVH {
     friend class ScalarEvolution;
 
-    Value *V;
-    SCEVUnknown(const FoldingSetNodeID &ID, Value *v) :
-      SCEV(ID, scUnknown), V(v) {}
+    // Implement CallbackVH.
+    virtual void deleted();
+    virtual void allUsesReplacedWith(Value *New);
+
+    /// SE - The parent ScalarEvolution value. This is used to update
+    /// the parent's maps when the value associated with a SCEVUnknown
+    /// is deleted or RAUW'd.
+    ScalarEvolution *SE;
+
+    /// Next - The next pointer in the linked list of all
+    /// SCEVUnknown instances owned by a ScalarEvolution.
+    SCEVUnknown *Next;
+
+    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
+                ScalarEvolution *se, SCEVUnknown *next) :
+      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
 
   public:
-    Value *getValue() const { return V; }
+    Value *getValue() const { return getValPtr(); }
 
     /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
     /// constant representing a type size, alignment, or field offset in
@@ -539,11 +492,6 @@ namespace llvm {
     bool isAlignOf(const Type *&AllocTy) const;
     bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const;
 
-    virtual bool isLoopInvariant(const Loop *L) const;
-    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
-      return false; // not computable
-    }
-
     virtual bool hasOperand(const SCEV *) const {
       return false;
     }
C/C++ LLVM-based compilers that forbids OOTA behaviors