ScalarEvolution.h revision 246b2564d3bbbafe06ebf6a67745cd24141b5cb4
153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// The LLVM Compiler Infrastructure 453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// 553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// This file was developed by the LLVM research group and is distributed under 653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===// 953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// 1053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// The ScalarEvolution class is an LLVM pass which can be used to analyze and 1153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// catagorize scalar expressions in loops. It specializes in recognizing 1253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// general induction variables, representing them with the abstract and opaque 1353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// SCEV class. Given this analysis, trip counts of loops and other important 1453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// properties can be obtained. 1553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// 1653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// This analysis is primarily useful for induction variable substitution and 1753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// strength reduction. 189769ab22265b313171d201b5928688524a01bd87Misha Brukman// 1953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===// 2053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 2153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 2253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#define LLVM_ANALYSIS_SCALAREVOLUTION_H 2353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 2453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#include "llvm/Pass.h" 25ca5183d445954a9b2a570d6bbba1bc2b00ad6442Jeff Cohen#include "llvm/Support/DataTypes.h" 26b5ebf15b2b2ce8989caf1a1114b05d80b0f9bd48Bill Wendling#include "llvm/Support/Streams.h" 2753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#include <set> 2853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 2953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 30246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 31246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Instruction; 3353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ConstantRange; 3553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Loop; 3653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class LoopInfo; 3753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle; 38246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 3953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 4053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEV - This class represent an analyzed expression in the program. These 4153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// are reference counted opaque objects that the client is not allowed to 4253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// do much with directly. 4353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 4453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEV { 4553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const unsigned SCEVType; // The SCEV baseclass this node corresponds to 46afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner mutable unsigned RefCount; 4753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 4853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner friend class SCEVHandle; 49afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void addRef() const { ++RefCount; } 50afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void dropRef() const { 51254bacd79a07632548de2f1c91d2768572764f66Chris Lattner if (--RefCount == 0) 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner delete this; 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 5753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 5853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 5953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 604998264403539a8201899756193261eb4f9d7f0bDan Gohman explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 6153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 6353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getValueRange - Return the tightest constant bounds that this value is 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known to have. This method is only valid on integer SCEV objects. 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ConstantRange getValueRange() const; 6753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the specified loop. 7053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const = 0; 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known way in the specified loop. This property being true implies that 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the value is variant in the loop AND that we can emit an expression to 7553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// compute the value of the expression at any particular loop iteration. 7653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 7753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 7953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 8053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const = 0; 8153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 82581b0d453a63f7f657248f80317976995262be11Reid Spencer /// getBitWidth - Get the bit width of the type, if it has one, 0 otherwise. 83581b0d453a63f7f657248f80317976995262be11Reid Spencer /// 84581b0d453a63f7f657248f80317976995262be11Reid Spencer uint32_t getBitWidth() const; 85581b0d453a63f7f657248f80317976995262be11Reid Spencer 86afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 87afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 88afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 89afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 90afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 919769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 92afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 93246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 94246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 95afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 9653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 9753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 9853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 9953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void print(std::ostream &OS) const = 0; 1005c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 10153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1069769ab22265b313171d201b5928688524a01bd87Misha Brukman 10753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 10853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 10953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 11053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 11553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 11653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 11753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 11853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVCouldNotCompute(); 11953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void print(std::ostream &OS) const; 1255c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1269769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 127afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 128246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 129246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 13253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 13353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 13553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// freeing the objects when the last reference is dropped. 13853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle { 13953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV *S; 14053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(); // DO NOT IMPLEMENT 14153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 142afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) { 14353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner assert(S && "Cannot create a handle to a null SCEV!"); 14453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 14553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 14653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 1479769ab22265b313171d201b5928688524a01bd87Misha Brukman S->addRef(); 14853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 14953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner ~SCEVHandle() { S->dropRef(); } 15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner operator SCEV*() const { return S; } 15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV &operator*() const { return *S; } 15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV *operator->() const { return S; } 15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner bool operator==(SCEV *RHS) const { return S == RHS; } 15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner bool operator!=(SCEV *RHS) const { return S != RHS; } 15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(SCEV *RHS) { 16053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS) { 16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 16253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS; 16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 16553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(const SCEVHandle &RHS) { 16953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS.S) { 17053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 17153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS.S; 17253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 17353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 17453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 17553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 17653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 17753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 17853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<typename From> struct simplify_type; 17953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<const SCEVHandle> { 18053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner typedef SCEV* SimpleType; 18153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 18253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return Node; 18353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 18453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 18553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<SCEVHandle> 18653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner : public simplify_type<const SCEVHandle> {}; 18753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 18853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 18953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 19053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 19153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 19253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 19353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void *Impl; // ScalarEvolution uses the pimpl pattern 19453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 195ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 196794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel ScalarEvolution() : FunctionPass((intptr_t)&ID), Impl(0) {} 1979769ab22265b313171d201b5928688524a01bd87Misha Brukman 19853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 19953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 20053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle getSCEV(Value *V) const; 20153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 202246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(ConstantInt *V); 203246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(const APInt& Val); 204246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 205246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 206246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 207246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops); 208246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 209246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 210246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 211246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 212246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 213246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 214246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 215246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Op2) { 216246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 217246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 218246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 219246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 220246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 221246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 222246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops); 223246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 224246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 225246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 226246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 227246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 228246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 229246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 230246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 231246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 232246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands, 233246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 234246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands, 235246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 236246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> NewOp(Operands); 237246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 238246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 239246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getUnknown(Value *V); 240246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 241246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 242246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 243246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getNegativeSCEV(const SCEVHandle &V); 244246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 245246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 246246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 247246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 248246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &RHS); 249246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 250246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getIntegerSCEV - Given an integer or FP type, create a constant for the 251246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 252246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 253246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 25427631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// hasSCEV - Return true if the SCEV for this value has already been 25527631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// computed. 25627631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner bool hasSCEV(Value *V) const; 25727631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 25827631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 25927631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// the specified value. 26027631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner void setSCEV(Value *V, const SCEVHandle &H); 26127631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 26253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 26353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 26453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 26553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 26653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 26753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 26853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 26953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 27053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// If this value is not computable at this scope, a SCEVCouldNotCompute 27153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// object is returned. 27253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 27353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 27453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getIterationCount - If the specified loop has a predictable iteration 27553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// count, return it, otherwise return a SCEVCouldNotCompute object. 27653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle getIterationCount(const Loop *L) const; 27753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 27853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasLoopInvariantIterationCount - Return true if the specified loop has 27953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// an analyzable loop-invariant iteration count. 28053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner bool hasLoopInvariantIterationCount(const Loop *L) const; 28153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 2825cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman /// deleteValueFromRecords - This method should be called by the 2835cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman /// client before it removes a Value from the program, to make sure 28453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// that no dangling references are left around. 2855cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman void deleteValueFromRecords(Value *V) const; 28653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 28753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 28853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 28953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 290ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 2915c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 2925c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 2935c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 29453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 29553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 29653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 29753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 298