Add a new analysis

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

1 files changed, 2482 insertions, 0 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
new file mode 100644
index 0000000000..ab0ed4be61
--- /dev/null
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -0,0 +1,2482 @@
+//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file contains the implementation of the scalar evolution analysis
+// engine, which is used primarily to analyze expressions involving induction
+// variables in loops.
+//
+// There are several aspects to this library.  First is the representation of
+// scalar expressions, which are represented as subclasses of the SCEV class.
+// These classes are used to represent certain types of subexpressions that we
+// can handle.  These classes are reference counted, managed by the SCEVHandle
+// class.  We only create one SCEV of a particular shape, so pointer-comparisons
+// for equality are legal.
+//
+// One important aspect of the SCEV objects is that they are never cyclic, even
+// if there is a cycle in the dataflow for an expression (ie, a PHI node).  If
+// the PHI node is one of the idioms that we can represent (e.g., a polynomial
+// recurrence) then we represent it directly as a recurrence node, otherwise we
+// represent it as a SCEVUnknown node.
+//
+// In addition to being able to represent expressions of various types, we also
+// have folders that are used to build the *canonical* representation for a
+// particular expression.  These folders are capable of using a variety of
+// rewrite rules to simplify the expressions.
+// 
+// Once the folders are defined, we can implement the more interesting
+// higher-level code, such as the code that recognizes PHI nodes of various
+// types, computes the execution count of a loop, etc.
+//
+// Orthogonal to the analysis of code above, this file also implements the
+// ScalarEvolutionRewriter class, which is used to emit code that represents the
+// various recurrences present in a loop, in canonical forms.
+//
+// TODO: We should use these routines and value representations to implement
+// dependence analysis!
+//
+//===----------------------------------------------------------------------===//
+//
+// There are several good references for the techniques used in this analysis.
+//
+//  Chains of recurrences -- a method to expedite the evaluation
+//  of closed-form functions
+//  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
+//
+//  On computational properties of chains of recurrences
+//  Eugene V. Zima
+//
+//  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
+//  Robert A. van Engelen
+//
+//  Efficient Symbolic Analysis for Optimizing Compilers
+//  Robert A. van Engelen
+//
+//  Using the chains of recurrences algebra for data dependence testing and
+//  induction variable substitution
+//  MS Thesis, Johnie Birch
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
+#include "llvm/Value.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/ConstantRange.h"
+#include "llvm/Support/InstIterator.h"
+#include "Support/Statistic.h"
+using namespace llvm;
+
+namespace {
+  RegisterAnalysis<ScalarEvolution>
+  R("scalar-evolution", "Scalar Evolution Analysis Printer");
+
+  Statistic<>
+  NumBruteForceEvaluations("scalar-evolution",
+                           "Number of brute force evaluations needed to calculate high-order polynomial exit values");
+  Statistic<>
+  NumTripCountsComputed("scalar-evolution",
+                        "Number of loops with predictable loop counts");
+  Statistic<>
+  NumTripCountsNotComputed("scalar-evolution",
+                           "Number of loops without predictable loop counts");
+}
+
+//===----------------------------------------------------------------------===//
+//                           SCEV class definitions
+//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
+// Implementation of the SCEV class.
+//
+namespace {
+  enum SCEVTypes {
+    // These should be ordered in terms of increasing complexity to make the
+    // folders simpler.
+    scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr,
+    scAddRecExpr, scUnknown, scCouldNotCompute
+  };
+
+  /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
+  /// than the complexity of the RHS.  If the SCEVs have identical complexity,
+  /// order them by their addresses.  This comparator is used to canonicalize
+  /// expressions.
+  struct SCEVComplexityCompare {
+    bool operator()(SCEV *LHS, SCEV *RHS) {
+      if (LHS->getSCEVType() < RHS->getSCEVType())
+        return true;
+      if (LHS->getSCEVType() == RHS->getSCEVType())
+        return LHS < RHS;
+      return false;
+    }
+  };
+}
+
+SCEV::~SCEV() {}
+void SCEV::dump() const {
+  print(std::cerr);
+}
+
+/// getValueRange - Return the tightest constant bounds that this value is
+/// known to have.  This method is only valid on integer SCEV objects.
+ConstantRange SCEV::getValueRange() const {
+  const Type *Ty = getType();
+  assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!");
+  Ty = Ty->getUnsignedVersion();
+  // Default to a full range if no better information is available.
+  return ConstantRange(getType());
+}
+
+
+SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
+
+bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
+  assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+}
+
+const Type *SCEVCouldNotCompute::getType() const {
+  assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+}
+
+bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
+  assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+  return false;
+}
+
+Value *SCEVCouldNotCompute::expandCodeFor(ScalarEvolutionRewriter &SER,
+                                          Instruction *InsertPt) {
+  assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+  return 0;
+}
+
+
+void SCEVCouldNotCompute::print(std::ostream &OS) const {
+  OS << "***COULDNOTCOMPUTE***";
+}
+
+bool SCEVCouldNotCompute::classof(const SCEV *S) {
+  return S->getSCEVType() == scCouldNotCompute;
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVConstant - This class represents a constant integer value.
+//
+namespace {
+  class SCEVConstant;
+  // SCEVConstants - Only allow the creation of one SCEVConstant for any
+  // particular value.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<ConstantInt*, SCEVConstant*> SCEVConstants;
+
+  class SCEVConstant : public SCEV {
+    ConstantInt *V;
+    SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
+
+    virtual ~SCEVConstant() {
+      SCEVConstants.erase(V);
+    }
+  public:
+    /// get method - This just gets and returns a new SCEVConstant object.
+    ///
+    static SCEVHandle get(ConstantInt *V) {
+      // Make sure that SCEVConstant instances are all unsigned.
+      if (V->getType()->isSigned()) {
+        const Type *NewTy = V->getType()->getUnsignedVersion();
+        V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy));
+      }
+
+      SCEVConstant *&R = SCEVConstants[V];
+      if (R == 0) R = new SCEVConstant(V);
+      return R;
+    }
+
+    ConstantInt *getValue() const { return V; }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const {
+      return ConstantRange(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 { return V->getType(); }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt) {
+      return getValue();
+    }
+    
+    virtual void print(std::ostream &OS) const {
+      WriteAsOperand(OS, V, false);
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVConstant *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scConstant;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVTruncateExpr - This class represents a truncation of an integer value to
+// a smaller integer value.
+//
+namespace {
+  class SCEVTruncateExpr;
+  // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
+  // particular input.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates;
+
+  class SCEVTruncateExpr : public SCEV {
+    SCEVHandle Op;
+    const Type *Ty;
+    SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
+      : SCEV(scTruncate), Op(op), Ty(ty) {
+      assert(Op->getType()->isInteger() && Ty->isInteger() &&
+             Ty->isUnsigned() &&
+             "Cannot truncate non-integer value!");
+      assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() &&
+             "This is not a truncating conversion!");
+    }
+
+    virtual ~SCEVTruncateExpr() {
+      SCEVTruncates.erase(std::make_pair(Op, Ty));
+    }
+  public:
+    /// get method - This just gets and returns a new SCEVTruncate object
+    ///
+    static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+    const SCEVHandle &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);
+    }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const {
+      return getOperand()->getValueRange().truncate(getType());
+    }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+    
+    virtual void print(std::ostream &OS) const {
+      OS << "(truncate " << *Op << " to " << *Ty << ")";
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVTruncateExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scTruncate;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVZeroExtendExpr - This class represents a zero extension of a small
+// integer value to a larger integer value.
+//
+namespace {
+  class SCEVZeroExtendExpr;
+  // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
+  // particular input.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<std::pair<SCEV*, const Type*>, SCEVZeroExtendExpr*> SCEVZeroExtends;
+
+  class SCEVZeroExtendExpr : public SCEV {
+    SCEVHandle Op;
+    const Type *Ty;
+    SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
+      : SCEV(scTruncate), Op(Op), Ty(ty) {
+      assert(Op->getType()->isInteger() && Ty->isInteger() &&
+             Ty->isUnsigned() &&
+             "Cannot zero extend non-integer value!");
+      assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() &&
+             "This is not an extending conversion!");
+    }
+
+    virtual ~SCEVZeroExtendExpr() {
+      SCEVZeroExtends.erase(std::make_pair(Op, Ty));
+    }
+  public:
+    /// get method - This just gets and returns a new SCEVZeroExtend object
+    ///
+    static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+    const SCEVHandle &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);
+    }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const {
+      return getOperand()->getValueRange().zeroExtend(getType());
+    }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+    
+    virtual void print(std::ostream &OS) const {
+      OS << "(zeroextend " << *Op << " to " << *Ty << ")";
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scZeroExtend;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVCommutativeExpr - This node is the base class for n'ary commutative
+// operators.
+
+namespace {
+  class SCEVCommutativeExpr;
+  // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
+  // particular input.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<std::pair<unsigned, std::vector<SCEV*> >,
+           SCEVCommutativeExpr*> SCEVCommExprs;
+
+  class SCEVCommutativeExpr : public SCEV {
+    std::vector<SCEVHandle> Operands;
+
+  protected:
+    SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
+      : SCEV(T) {
+      Operands.reserve(ops.size());
+      Operands.insert(Operands.end(), ops.begin(), ops.end());
+    }
+
+    ~SCEVCommutativeExpr() {
+      SCEVCommExprs.erase(std::make_pair(getSCEVType(),
+                                         std::vector<SCEV*>(Operands.begin(),
+                                                            Operands.end())));
+    }
+
+  public:
+    unsigned getNumOperands() const { return Operands.size(); }
+    const SCEVHandle &getOperand(unsigned i) const {
+      assert(i < Operands.size() && "Operand index out of range!");
+      return Operands[i];
+    }
+
+    const std::vector<SCEVHandle> &getOperands() const { return Operands; }
+    typedef std::vector<SCEVHandle>::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;
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+        if (getOperand(i)->hasComputableLoopEvolution(L)) return true;
+      return false;
+    }
+
+    virtual const Type *getType() const { return getOperand(0)->getType(); }
+
+    virtual const char *getOperationStr() const = 0;
+    
+    virtual void print(std::ostream &OS) const {
+      assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
+      const char *OpStr = getOperationStr();
+      OS << "(" << *Operands[0];
+      for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+        OS << OpStr << *Operands[i];
+      OS << ")";
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddExpr ||
+             S->getSCEVType() == scMulExpr;
+    }
+  };
+}
+
+//===----------------------------------------------------------------------===//
+// SCEVAddExpr - This node represents an addition of some number of SCEV's.
+//
+namespace {
+  class SCEVAddExpr : public SCEVCommutativeExpr {
+    SCEVAddExpr(const std::vector<SCEVHandle> &ops)
+      : SCEVCommutativeExpr(scAddExpr, ops) {
+    }
+
+  public:
+    static SCEVHandle get(std::vector<SCEVHandle> &Ops);
+
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return get(Ops);
+    }
+
+    static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1,
+                          const SCEVHandle &Op2) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(Op0);
+      Ops.push_back(Op1);
+      Ops.push_back(Op2);
+      return get(Ops);
+    }
+
+    virtual const char *getOperationStr() const { return " + "; }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVAddExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddExpr;
+    }
+  };
+}
+
+//===----------------------------------------------------------------------===//
+// SCEVMulExpr - This node represents multiplication of some number of SCEV's.
+//
+namespace {
+  class SCEVMulExpr : public SCEVCommutativeExpr {
+    SCEVMulExpr(const std::vector<SCEVHandle> &ops)
+      : SCEVCommutativeExpr(scMulExpr, ops) {
+    }
+
+  public:
+    static SCEVHandle get(std::vector<SCEVHandle> &Ops);
+
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return get(Ops);
+    }
+
+    virtual const char *getOperationStr() const { return " * "; }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVMulExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scMulExpr;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVUDivExpr - This class represents a binary unsigned division operation.
+//
+namespace {
+  class SCEVUDivExpr;
+  // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
+  // input.  Don't use a SCEVHandle here, or else the object will never be
+  // deleted!
+  std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs;
+
+  class SCEVUDivExpr : public SCEV {
+    SCEVHandle LHS, RHS;
+    SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+      : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
+
+    virtual ~SCEVUDivExpr() {
+      SCEVUDivs.erase(std::make_pair(LHS, RHS));
+    }
+  public:
+    /// get method - This just gets and returns a new SCEVUDiv object.
+    ///
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS);
+
+    const SCEVHandle &getLHS() const { return LHS; }
+    const SCEVHandle &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 const Type *getType() const {
+      const Type *Ty = LHS->getType();
+      if (Ty->isSigned()) Ty = Ty->getUnsignedVersion();
+      return Ty;
+    }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+    
+    virtual void print(std::ostream &OS) const {
+      OS << "(" << *LHS << " /u " << *RHS << ")";
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVUDivExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scUDivExpr;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+
+// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
+// count of the specified loop.
+//
+// All operands of an AddRec are required to be loop invariant.
+//
+namespace {
+  class SCEVAddRecExpr;
+  // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
+  // particular input.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<std::pair<const Loop *, std::vector<SCEV*> >,
+           SCEVAddRecExpr*> SCEVAddRecExprs;
+
+  class SCEVAddRecExpr : public SCEV {
+    std::vector<SCEVHandle> Operands;
+    const Loop *L;
+
+    SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
+      : SCEV(scAddRecExpr), Operands(ops), L(l) {
+      for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+        assert(Operands[i]->isLoopInvariant(l) &&
+               "Operands of AddRec must be loop-invariant!");
+    }
+    ~SCEVAddRecExpr() {
+      SCEVAddRecExprs.erase(std::make_pair(L,
+                                           std::vector<SCEV*>(Operands.begin(),
+                                                              Operands.end())));
+    }
+  public:
+    static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step,
+                          const Loop *);
+    static SCEVHandle get(std::vector<SCEVHandle> &Operands,
+                          const Loop *);
+    static SCEVHandle get(const std::vector<SCEVHandle> &Operands,
+                          const Loop *L) {
+      std::vector<SCEVHandle> NewOp(Operands);
+      return get(NewOp, L);
+    }
+
+    typedef std::vector<SCEVHandle>::const_iterator op_iterator;
+    op_iterator op_begin() const { return Operands.begin(); }
+    op_iterator op_end() const { return Operands.end(); }
+
+    unsigned getNumOperands() const { return Operands.size(); }
+    const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; }
+    const SCEVHandle &getStart() const { return Operands[0]; }
+    const Loop *getLoop() const { return L; }
+
+
+    /// getStepRecurrence - This method constructs and returns the recurrence
+    /// indicating how much this expression steps by.  If this is a polynomial
+    /// of degree N, it returns a chrec of degree N-1.
+    SCEVHandle getStepRecurrence() const {
+      if (getNumOperands() == 2) return getOperand(1);
+      return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()),
+                                 getLoop());
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+      if (L == QL) return true;
+      /// FIXME: What if the start or step value a recurrence for the specified
+      /// loop?
+      return false;
+    }
+
+
+    virtual bool isLoopInvariant(const Loop *QueryLoop) const {
+      // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
+      // contain L.
+      return !QueryLoop->contains(L->getHeader());
+    }
+
+    virtual const Type *getType() const { return Operands[0]->getType(); }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt);
+
+
+    /// isAffine - Return true if this is an affine AddRec (i.e., it represents
+    /// an expressions A+B*x where A and B are loop invariant values.
+    bool isAffine() const {
+      // We know that the start value is invariant.  This expression is thus
+      // affine iff the step is also invariant.
+      return getNumOperands() == 2;
+    }
+
+    /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
+    /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
+    /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
+    bool isQuadratic() const {
+      return getNumOperands() == 3;
+    }
+
+    /// evaluateAtIteration - Return the value of this chain of recurrences at
+    /// the specified iteration number.
+    SCEVHandle evaluateAtIteration(SCEVHandle It) const;
+
+    /// getNumIterationsInRange - Return the number of iterations of this loop
+    /// that produce values in the specified constant range.  Another way of
+    /// looking at this is that it returns the first iteration number where the
+    /// value is not in the condition, thus computing the exit count.  If the
+    /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
+    /// returned.
+    SCEVHandle getNumIterationsInRange(ConstantRange Range) const;
+
+
+    virtual void print(std::ostream &OS) const {
+      OS << "{" << *Operands[0];
+      for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+        OS << ",+," << *Operands[i];
+      OS << "}<" << L->getHeader()->getName() + ">";
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVAddRecExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddRecExpr;
+    }
+  };
+}
+
+
+//===----------------------------------------------------------------------===//
+// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
+// value, and only represent it as it's LLVM Value.  This is the "bottom" value
+// for the analysis.
+//
+namespace {
+  class SCEVUnknown;
+  // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any
+  // particular value.  Don't use a SCEVHandle here, or else the object will
+  // never be deleted!
+  std::map<Value*, SCEVUnknown*> SCEVUnknowns;
+
+  class SCEVUnknown : public SCEV {
+    Value *V;
+    SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
+
+  protected:
+    ~SCEVUnknown() { SCEVUnknowns.erase(V); }
+  public:
+    /// get method - For SCEVUnknown, this just gets and returns a new
+    /// SCEVUnknown.
+    static SCEVHandle get(Value *V) {
+      if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+        return SCEVConstant::get(CI);
+      SCEVUnknown *&Result = SCEVUnknowns[V];
+      if (Result == 0) Result = new SCEVUnknown(V);
+      return Result;
+    }
+
+    Value *getValue() const { return V; }
+
+    Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+                         Instruction *InsertPt) {
+      return V;
+    }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      // All non-instruction values are loop invariant.  All instructions are
+      // loop invariant if they are not contained in the specified loop.
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        return !L->contains(I->getParent());
+      return true;
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+      return false; // not computable
+    }
+
+    virtual const Type *getType() const { return V->getType(); }
+
+    virtual void print(std::ostream &OS) const {
+      WriteAsOperand(OS, V, false);
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVUnknown *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scUnknown;
+    }
+  };
+}
+
+//===----------------------------------------------------------------------===//
+//                      Simple SCEV method implementations
+//===----------------------------------------------------------------------===//
+
+/// getIntegerSCEV - Given an integer or FP type, create a constant for the
+/// specified signed integer value and return a SCEV for the constant.
+static SCEVHandle getIntegerSCEV(int Val, const Type *Ty) {
+  Constant *C;
+  if (Val == 0) 
+    C = Constant::getNullValue(Ty);
+  else if (Ty->isFloatingPoint())
+    C = ConstantFP::get(Ty, Val);
+  else if (Ty->isSigned())
+    C = ConstantSInt::get(Ty, Val);
+  else {
+    C = ConstantSInt::get(Ty->getSignedVersion(), Val);
+    C = ConstantExpr::getCast(C, Ty);
+  }
+  return SCEVUnknown::get(C);
+}
+
+/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type.  If the type must be extended, it is zero
+/// extended.
+static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) {
+  const Type *SrcTy = V->getType();
+  assert(SrcTy->isInteger() && Ty->isInteger() &&
+         "Cannot truncate or zero extend with non-integer arguments!");
+  if (SrcTy->getPrimitiveSize() == Ty->getPrimitiveSize())
+    return V;  // No conversion
+  if (SrcTy->getPrimitiveSize() > Ty->getPrimitiveSize())
+    return SCEVTruncateExpr::get(V, Ty);
+  return SCEVZeroExtendExpr::get(V, Ty);
+}
+
+/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
+///
+static SCEVHandle getNegativeSCEV(const SCEVHandle &V) {
+  if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+    return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue()));
+  
+  return SCEVMulExpr::get(V, getIntegerSCEV(-1, V->getType()));
+}
+
+/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
+///
+static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+  // X - Y --> X + -Y
+  return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS));
+}
+
+
+/// Binomial - Evaluate N!/((N-M)!*M!)  .  Note that N is often large and M is
+/// often very small, so we try to reduce the number of N! terms we need to
+/// evaluate by evaluating this as  (N!/(N-M)!)/M!
+static ConstantInt *Binomial(ConstantInt *N, unsigned M) {
+  uint64_t NVal = N->getRawValue();
+  uint64_t FirstTerm = 1;
+  for (unsigned i = 0; i != M; ++i)
+    FirstTerm *= NVal-i;
+
+  unsigned MFactorial = 1;
+  for (; M; --M)
+    MFactorial *= M;
+
+  Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial);
+  Result = ConstantExpr::getCast(Result, N->getType());
+  assert(isa<ConstantInt>(Result) && "Cast of integer not folded??");
+  return cast<ConstantInt>(Result);
+}
+
+/// PartialFact - Compute V!/(V-NumSteps)!
+static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) {
+  // Handle this case efficiently, it is common to have constant iteration
+  // counts while computing loop exit values.
+  if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
+    uint64_t Val = SC->getValue()->getRawValue();
+    uint64_t Result = 1;
+    for (; NumSteps; --NumSteps)
+      Result *= Val-(NumSteps-1);
+    Constant *Res = ConstantUInt::get(Type::ULongTy, Result);
+    return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType()));
+  }
+
+  const Type *Ty = V->getType();
+  if (NumSteps == 0)
+    return getIntegerSCEV(1, Ty);
+  
+  SCEVHandle Result = V;
+  for (unsigned i = 1; i != NumSteps; ++i)
+    Result = SCEVMulExpr::get(Result, getMinusSCEV(V, getIntegerSCEV(i, Ty)));
+  return Result;
+}
+
+
+/// evaluateAtIteration - Return the value of this chain of recurrences at
+/// the specified iteration number.  We can evaluate this recurrence by
+/// multiplying each element in the chain by the binomial coefficient
+/// corresponding to it.  In other words, we can evaluate {A,+,B,+,C,+,D} as:
+///
+///   A*choose(It, 0) + B*choose(It, 1) + C*choose(It, 2) + D*choose(It, 3)
+///
+/// FIXME/VERIFY: I don't trust that this is correct in the face of overflow.
+/// Is the binomial equation safe using modular arithmetic??
+///
+SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const {
+  SCEVHandle Result = getStart();
+  int Divisor = 1;
+  const Type *Ty = It->getType();
+  for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
+    SCEVHandle BC = PartialFact(It, i);
+    Divisor *= i;
+    SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
+                                       getIntegerSCEV(Divisor, Ty));
+    Result = SCEVAddExpr::get(Result, Val);
+  }
+  return Result;
+}
+
+
+//===----------------------------------------------------------------------===//
+//                    SCEV Expression folder implementations
+//===----------------------------------------------------------------------===//
+
+SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) {
+  if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+    return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
+
+  // If the input value is a chrec scev made out of constants, truncate
+  // all of the constants.
+  if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
+    std::vector<SCEVHandle> Operands;
+    for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
+      // FIXME: This should allow truncation of other expression types!
+      if (isa<SCEVConstant>(AddRec->getOperand(i)))
+        Operands.push_back(get(AddRec->getOperand(i), Ty));
+      else
+        break;
+    if (Operands.size() == AddRec->getNumOperands())
+      return SCEVAddRecExpr::get(Operands, AddRec->getLoop());
+  }
+
+  SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
+  if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
+  return Result;
+}
+
+SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
+  if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+    return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
+
+  // FIXME: If the input value is a chrec scev, and we can prove that the value
+  // did not overflow the old, smaller, value, we can zero extend all of the
+  // operands (often constants).  This would allow analysis of something like
+  // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
+
+  SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
+  if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
+  return Result;
+}
+
+// get - Get a canonical add expression, or something simpler if possible.
+SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) {
+  assert(!Ops.empty() && "Cannot get empty add!");
+
+  // Sort by complexity, this groups all similar expression types together.
+  std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
+
+  // If there are any constants, fold them together.
+  unsigned Idx = 0;
+  if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+    ++Idx;
+    while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+      // We found two constants, fold them together!
+      Constant *Fold = ConstantExpr::getAdd(LHSC->getValue(), RHSC->getValue());
+      if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
+        Ops[0] = SCEVConstant::get(CI);
+        Ops.erase(Ops.begin()+1);  // Erase the folded element
+        if (Ops.size() == 1) return Ops[0];
+      } else {
+        // If we couldn't fold the expression, move to the next constant.  Note
+        // that this is impossible to happen in practice because we always
+        // constant fold constant ints to constant ints.
+        ++Idx;
+      }
+    }
+
+    // If we are left with a constant zero being added, strip it off.
+    if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) {
+      Ops.erase(Ops.begin());
+      --Idx;
+    }
+  }
+
+  if (Ops.size() == 1)
+    return Ops[0];
+  
+  // Okay, check to see if the same value occurs in the operand list twice.  If
+  // so, merge them together into an multiply expression.  Since we sorted the
+  // list, these values are required to be adjacent.
+  const Type *Ty = Ops[0]->getType();
+  for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
+    if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
+      // Found a match, merge the two values into a multiply, and add any
+      // remaining values to the result.
+      SCEVHandle Two = getIntegerSCEV(2, Ty);
+      SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two);
+      if (Ops.size() == 2)
+        return Mul;
+      Ops.erase(Ops.begin()+i, Ops.begin