diff options
author | Chris Lattner <sabre@nondot.org> | 2004-04-02 20:23:17 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2004-04-02 20:23:17 +0000 |
commit | 53e677abadadf71ef33f2f69533a32c1fa3d168f (patch) | |
tree | ac6dfe22c0b018c95404da39ce9121b067fd2d7b | |
parent | 7aa773bc07fd6125c0e4a965760fa06c5679cc8d (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.h | 270 | ||||
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 2482 |
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 |