aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2004-04-02 20:23:17 +0000
committerChris Lattner <sabre@nondot.org>2004-04-02 20:23:17 +0000
commit53e677abadadf71ef33f2f69533a32c1fa3d168f (patch)
treeac6dfe22c0b018c95404da39ce9121b067fd2d7b
parent7aa773bc07fd6125c0e4a965760fa06c5679cc8d (diff)
Add a new analysis
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12619 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--include/llvm/Analysis/ScalarEvolution.h270
-rw-r--r--lib/Analysis/ScalarEvolution.cpp2482
2 files changed, 2752 insertions, 0 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
new file mode 100644
index 0000000000..253217ef1a
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -0,0 +1,270 @@
+//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ScalarEvolution class is an LLVM pass which can be used to analyze and
+// catagorize scalar expressions in loops. It specializes in recognizing
+// general induction variables, representing them with the abstract and opaque
+// SCEV class. Given this analysis, trip counts of loops and other important
+// properties can be obtained.
+//
+// This analysis is primarily useful for induction variable substitution and
+// strength reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_H
+
+#include "llvm/Pass.h"
+#include <set>
+
+namespace llvm {
+ class Instruction;
+ class Type;
+ class ConstantRange;
+ class Loop;
+ class LoopInfo;
+ class SCEVHandle;
+ class ScalarEvolutionRewriter;
+
+ /// SCEV - This class represent an analyzed expression in the program. These
+ /// are reference counted opaque objects that the client is not allowed to
+ /// do much with directly.
+ ///
+ class SCEV {
+ const unsigned SCEVType; // The SCEV baseclass this node corresponds to
+ unsigned RefCount;
+
+ friend class SCEVHandle;
+ void addRef() { ++RefCount; }
+ void dropRef() {
+ if (--RefCount == 0) {
+#if 0
+ std::cerr << "DELETING: " << this << ": ";
+ print(std::cerr);
+ std::cerr << "\n";
+#endif
+ delete this;
+ }
+ }
+
+ SCEV(const SCEV &); // DO NOT IMPLEMENT
+ void operator=(const SCEV &); // DO NOT IMPLEMENT
+ protected:
+ virtual ~SCEV();
+ public:
+ SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
+
+ unsigned getSCEVType() const { return SCEVType; }
+
+ /// 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;
+
+ /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
+ /// the specified loop.
+ virtual bool isLoopInvariant(const Loop *L) const = 0;
+
+ /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
+ /// known way in the specified loop. This property being true implies that
+ /// the value is variant in the loop AND that we can emit an expression to
+ /// compute the value of the expression at any particular loop iteration.
+ virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
+
+ /// getType - Return the LLVM type of this SCEV expression.
+ ///
+ virtual const Type *getType() const = 0;
+
+ /// expandCodeFor - Given a rewriter object, expand this SCEV into a closed
+ /// form expression and return a Value corresponding to the expression in
+ /// question.
+ virtual Value *expandCodeFor(ScalarEvolutionRewriter &SER,
+ Instruction *InsertPt) = 0;
+
+
+ /// print - Print out the internal representation of this scalar to the
+ /// specified stream. This should really only be used for debugging
+ /// purposes.
+ virtual void print(std::ostream &OS) const = 0;
+
+ /// dump - This method is used for debugging.
+ ///
+ void dump() const;
+ };
+
+ inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
+ S.print(OS);
+ return OS;
+ }
+
+ /// SCEVCouldNotCompute - An object of this class is returned by queries that
+ /// could not be answered. For example, if you ask for the number of
+ /// iterations of a linked-list traversal loop, you will get one of these.
+ /// None of the standard SCEV operations are valid on this class, it is just a
+ /// marker.
+ struct SCEVCouldNotCompute : public SCEV {
+ SCEVCouldNotCompute();
+
+ // None of these methods are valid for this object.
+ virtual bool isLoopInvariant(const Loop *L) const;
+ virtual const Type *getType() const;
+ virtual bool hasComputableLoopEvolution(const Loop *L) const;
+ virtual Value *expandCodeFor(ScalarEvolutionRewriter &, Instruction *);
+ virtual void print(std::ostream &OS) const;
+
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
+ static bool classof(const SCEV *S);
+ };
+
+ /// SCEVHandle - This class is used to maintain the SCEV object's refcounts,
+ /// freeing the objects when the last reference is dropped.
+ class SCEVHandle {
+ SCEV *S;
+ SCEVHandle(); // DO NOT IMPLEMENT
+ public:
+ SCEVHandle(SCEV *s) : S(s) {
+ assert(S && "Cannot create a handle to a null SCEV!");
+ S->addRef();
+ }
+ SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
+ S->addRef();
+ }
+ ~SCEVHandle() { S->dropRef(); }
+
+ operator SCEV*() const { return S; }
+
+ SCEV &operator*() const { return *S; }
+ SCEV *operator->() const { return S; }
+
+ bool operator==(SCEV *RHS) const { return S == RHS; }
+ bool operator!=(SCEV *RHS) const { return S != RHS; }
+
+ const SCEVHandle &operator=(SCEV *RHS) {
+ if (S != RHS) {
+ S->dropRef();
+ S = RHS;
+ S->addRef();
+ }
+ return *this;
+ }
+
+ const SCEVHandle &operator=(const SCEVHandle &RHS) {
+ if (S != RHS.S) {
+ S->dropRef();
+ S = RHS.S;
+ S->addRef();
+ }
+ return *this;
+ }
+ };
+
+ template<typename From> struct simplify_type;
+ template<> struct simplify_type<const SCEVHandle> {
+ typedef SCEV* SimpleType;
+ static SimpleType getSimplifiedValue(const SCEVHandle &Node) {
+ return Node;
+ }
+ };
+ template<> struct simplify_type<SCEVHandle>
+ : public simplify_type<const SCEVHandle> {};
+
+ /// ScalarEvolution - This class is the main scalar evolution driver. Because
+ /// client code (intentionally) can't do much with the SCEV objects directly,
+ /// they must ask this class for services.
+ ///
+ class ScalarEvolution : public FunctionPass {
+ void *Impl; // ScalarEvolution uses the pimpl pattern
+ public:
+ ScalarEvolution() : Impl(0) {}
+
+ /// getSCEV - Return a SCEV expression handle for the full generality of the
+ /// specified expression.
+ SCEVHandle getSCEV(Value *V) const;
+
+ /// getSCEVAtScope - Return a SCEV expression handle for the specified value
+ /// at the specified scope in the program. The L value specifies a loop
+ /// nest to evaluate the expression at, where null is the top-level or a
+ /// specified loop is immediately inside of the loop.
+ ///
+ /// This method can be used to compute the exit value for a variable defined
+ /// in a loop by querying what the value will hold in the parent loop.
+ ///
+ /// If this value is not computable at this scope, a SCEVCouldNotCompute
+ /// object is returned.
+ SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const;
+
+ /// getIterationCount - If the specified loop has a predictable iteration
+ /// count, return it, otherwise return a SCEVCouldNotCompute object.
+ SCEVHandle getIterationCount(const Loop *L) const;
+
+ /// hasLoopInvariantIterationCount - Return true if the specified loop has
+ /// an analyzable loop-invariant iteration count.
+ bool hasLoopInvariantIterationCount(const Loop *L) const;
+
+ /// deleteInstructionFromRecords - This method should be called by the
+ /// client before it removes an instruction from the program, to make sure
+ /// that no dangling references are left around.
+ void deleteInstructionFromRecords(Instruction *I) const;
+
+ /// shouldSubstituteIndVar - Return true if we should perform induction
+ /// variable substitution for this variable. This is a hack because we
+ /// don't have a strength reduction pass yet. When we do we will promote
+ /// all vars, because we can strength reduce them later as desired.
+ bool shouldSubstituteIndVar(const SCEV *S) const;
+
+ virtual bool runOnFunction(Function &F);
+ virtual void releaseMemory();
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual void print(std::ostream &OS) const;
+ };
+
+ /// ScalarEvolutionRewriter - This class uses information about analyze
+ /// scalars to rewrite expressions in canonical form. This can be used for
+ /// induction variable substitution, strength reduction, or loop exit value
+ /// replacement.
+ ///
+ /// Clients should create an instance of this class when rewriting is needed,
+ /// and destroying it when finished to allow the release of the associated
+ /// memory.
+ class ScalarEvolutionRewriter {
+ ScalarEvolution &SE;
+ LoopInfo &LI;
+ std::map<SCEVHandle, Value*> InsertedExpressions;
+ std::set<Instruction*> InsertedInstructions;
+ public:
+ ScalarEvolutionRewriter(ScalarEvolution &se, LoopInfo &li)
+ : SE(se), LI(li) {}
+
+ /// isInsertedInstruction - Return true if the specified instruction was
+ /// inserted by the code rewriter. If so, the client should not modify the
+ /// instruction.
+ bool isInsertedInstruction(Instruction *I) const {
+ return InsertedInstructions.count(I);
+ }
+
+ /// GetOrInsertCanonicalInductionVariable - This method returns the
+ /// canonical induction variable of the specified type for the specified
+ /// loop (inserts one if there is none). A canonical induction variable
+ /// starts at zero and steps by one on each iteration.
+ Value *GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty);
+
+ /// ExpandCodeFor - Insert code to directly compute the specified SCEV
+ /// expression into the program. The inserted code is inserted into the
+ /// specified block.
+ ///
+ /// If a particular value sign is required, a type may be specified for the
+ /// result.
+ Value *ExpandCodeFor(SCEVHandle SH, Instruction *InsertPt,
+ const Type *Ty = 0);
+ };
+}
+
+#endif
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