ScalarEvolution.h revision b7ef72963b2215ca23c27fa8ea777bada06994d0
153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// The LLVM Compiler Infrastructure 453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// 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" 25019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Analysis/LoopInfo.h" 26ca5183d445954a9b2a570d6bbba1bc2b00ad6442Jeff Cohen#include "llvm/Support/DataTypes.h" 271baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman#include <iosfwd> 2853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 2953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 30246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 31246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 3353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle; 34246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 352d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman class TargetData; 3653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEV - This class represent an analyzed expression in the program. These 3853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// are reference counted opaque objects that the client is not allowed to 3953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// do much with directly. 4053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 4153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEV { 4253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const unsigned SCEVType; // The SCEV baseclass this node corresponds to 43afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner mutable unsigned RefCount; 4453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 4553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner friend class SCEVHandle; 46afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void addRef() const { ++RefCount; } 47afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void dropRef() const { 48254bacd79a07632548de2f1c91d2768572764f66Chris Lattner if (--RefCount == 0) 4953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner delete this; 5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 5153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 574998264403539a8201899756193261eb4f9d7f0bDan Gohman explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 5853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 6053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the specified loop. 6353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const = 0; 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known way in the specified loop. This property being true implies that 6753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the value is variant in the loop AND that we can emit an expression to 6853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// compute the value of the expression at any particular loop iteration. 6953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 7053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const = 0; 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 75cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 76cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 77cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 78cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 79afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 80afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 81afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 82afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 83afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 849769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 85afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 86246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 87246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 88afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 895a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// dominates - Return true if elements that makes up this SCEV dominates 905a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// the specified basic block. 915a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 925a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 9353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 9453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 9553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 96b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const = 0; 97b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(std::ostream &OS) const; 985c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 9953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 10053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 10153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1049769ab22265b313171d201b5928688524a01bd87Misha Brukman 105b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 106b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 107b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 108b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 109b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 11053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 11653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 11753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 11853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 11953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 12053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVCouldNotCompute(); 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 127b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1289769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 129afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 130246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 131246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 13253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 1335a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 1345a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 1355a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 1365a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 13853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 13953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 14053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 14153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 14253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 14353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// freeing the objects when the last reference is dropped. 14453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle { 14553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV *S; 14653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(); // DO NOT IMPLEMENT 14753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 148afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) { 14953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner assert(S && "Cannot create a handle to a null SCEV!"); 15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 1539769ab22265b313171d201b5928688524a01bd87Misha Brukman S->addRef(); 15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner ~SCEVHandle() { S->dropRef(); } 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner operator SCEV*() const { return S; } 15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV &operator*() const { return *S; } 16053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV *operator->() const { return S; } 16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner bool operator==(SCEV *RHS) const { return S == RHS; } 16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner bool operator!=(SCEV *RHS) const { return S != RHS; } 16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(SCEV *RHS) { 16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS) { 16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 16853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS; 16953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 17053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 17153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 17253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 17353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 17453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(const SCEVHandle &RHS) { 17553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS.S) { 17653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 17753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS.S; 17853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 17953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 18053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 18153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 18253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 18353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 18453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<typename From> struct simplify_type; 18553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<const SCEVHandle> { 18653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner typedef SCEV* SimpleType; 18753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 18853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return Node; 18953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 19053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 19153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<SCEVHandle> 19253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner : public simplify_type<const SCEVHandle> {}; 19353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 19453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 19553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 19653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 19753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 19853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 19953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void *Impl; // ScalarEvolution uses the pimpl pattern 20053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 201ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 202ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman ScalarEvolution() : FunctionPass(&ID), Impl(0) {} 2039769ab22265b313171d201b5928688524a01bd87Misha Brukman 2042d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // getTargetData - Return the TargetData object contained in this 2052d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // ScalarEvolution. 2062d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman const TargetData &getTargetData() const; 2072d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 20853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 20953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 21053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle getSCEV(Value *V) const; 21153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 212246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(ConstantInt *V); 213246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(const APInt& Val); 214246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 215246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 216246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 217246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops); 218246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 219246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 220246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 221246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 222246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 223246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 224246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 225246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Op2) { 226246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 227246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 228246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 229246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 230246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 231246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 232246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops); 233246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 234246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 235246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 236246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 237246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 238246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 239e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 240246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 241246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 242246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands, 243246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 244246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands, 245246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 246246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> NewOp(Operands); 247246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 248246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 249c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 250c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky SCEVHandle getSMaxExpr(std::vector<SCEVHandle> Operands); 2513e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 2523e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getUMaxExpr(std::vector<SCEVHandle> Operands); 253246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getUnknown(Value *V); 254f4ccfcb70402b34ee55e0b5820cf287b95a8762fDan Gohman SCEVHandle getCouldNotCompute(); 255246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 256246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 257246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 258246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getNegativeSCEV(const SCEVHandle &V); 259246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2603e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 2613e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 2623e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getNotSCEV(const SCEVHandle &V); 2633e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 264246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 265246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 266246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 267246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &RHS); 268246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2696f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 2706f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 2716f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 2726f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); 2736f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 274f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 275f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 276f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 277f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); 278f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 279246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getIntegerSCEV - Given an integer or FP type, create a constant for the 280246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 281246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 282246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 28327631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// hasSCEV - Return true if the SCEV for this value has already been 28427631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// computed. 28527631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner bool hasSCEV(Value *V) const; 28627631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 28727631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 28827631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// the specified value. 28927631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner void setSCEV(Value *V, const SCEVHandle &H); 29027631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 29153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 29253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 29353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 29453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 29553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 29653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 29753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 29853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 29953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// If this value is not computable at this scope, a SCEVCouldNotCompute 30053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// object is returned. 30153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 30253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 303c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// isLoopGuardedByCond - Test whether entry to the loop is protected by 304c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// a conditional between LHS and RHS. 305c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 306c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SCEV *LHS, SCEV *RHS); 307c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 30846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 30946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 31046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 31146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 31246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 31346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 31446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 31546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 31646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 31746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 31846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 31946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle getBackedgeTakenCount(const Loop *L) const; 32053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 32146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 32246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 32346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L) const; 32453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 32546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// forgetLoopBackedgeTakenCount - This method should be called by the 32660f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman /// client when it has changed a loop in a way that may effect 32746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// ScalarEvolution's ability to compute a trip count, or if the loop 32846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// is deleted. 32946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void forgetLoopBackedgeTakenCount(const Loop *L); 33060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3315cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman /// deleteValueFromRecords - This method should be called by the 3325cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman /// client before it removes a Value from the program, to make sure 33353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// that no dangling references are left around. 3345cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman void deleteValueFromRecords(Value *V) const; 33553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 33653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 33753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 33853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 339b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS, const Module* = 0) const; 340ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 3415c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 3425c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 3435c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 34453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 34553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 34653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 34753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 348