ScalarEvolution.h revision 467c430316b7a5b6fa8069531ca8d603b1e1197f
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" 2735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h" 281baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman#include <iosfwd> 2953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 31246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 32246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle; 35246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 36f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman class TargetData; 3753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEV - This class represent an analyzed expression in the program. These 3953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// are reference counted opaque objects that the client is not allowed to 4053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// do much with directly. 4153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 4253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEV { 4353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const unsigned SCEVType; // The SCEV baseclass this node corresponds to 44afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner mutable unsigned RefCount; 4553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 4653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner friend class SCEVHandle; 47afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void addRef() const { ++RefCount; } 48afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void dropRef() const { 49254bacd79a07632548de2f1c91d2768572764f66Chris Lattner if (--RefCount == 0) 5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner delete this; 5153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 5753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 584998264403539a8201899756193261eb4f9d7f0bDan Gohman explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 5953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 6153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the specified loop. 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const = 0; 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 6753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known way in the specified loop. This property being true implies that 6853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the value is variant in the loop AND that we can emit an expression to 6953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// compute the value of the expression at any particular loop iteration. 7053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const = 0; 7553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 76cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 77cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 78cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 79cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 80afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 81afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 82afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 83afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 84afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 859769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 86afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 87246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 88246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 89afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 905a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// dominates - Return true if elements that makes up this SCEV dominates 915a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// the specified basic block. 925a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 935a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 9453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 9553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 9653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 97b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const = 0; 98b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(std::ostream &OS) const; 995c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 10053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 10153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1059769ab22265b313171d201b5928688524a01bd87Misha Brukman 106b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 107b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 108b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 109b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 110b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 11553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 11753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 11853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 11953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 12053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVCouldNotCompute(); 123f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ~SCEVCouldNotCompute(); 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 129b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1309769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 131afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 132246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 133246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 1355a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 1365a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 1375a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 1385a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 13953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 14053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 14153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 14253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 14353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 14435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 14535738ac150afafe2359268d4b2169498c6c98c5fDan Gohman /// notified whenever a Value is deleted. 14635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman class SCEVCallbackVH : public CallbackVH { 14735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman ScalarEvolution *SE; 14835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman virtual void deleted(); 14935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman virtual void allUsesReplacedWith(Value *New); 15035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman public: 15135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 15235738ac150afafe2359268d4b2169498c6c98c5fDan Gohman }; 15335738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// freeing the objects when the last reference is dropped. 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle { 15735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *S; 15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(); // DO NOT IMPLEMENT 15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 16035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVHandle(const SCEV *s) : S(s) { 16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner assert(S && "Cannot create a handle to a null SCEV!"); 16253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 1659769ab22265b313171d201b5928688524a01bd87Misha Brukman S->addRef(); 16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner ~SCEVHandle() { S->dropRef(); } 16853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman operator const SCEV*() const { return S; } 17053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 17135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV &operator*() const { return *S; } 17235738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *operator->() const { return S; } 17353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 17435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman bool operator==(const SCEV *RHS) const { return S == RHS; } 17535738ac150afafe2359268d4b2169498c6c98c5fDan Gohman bool operator!=(const SCEV *RHS) const { return S != RHS; } 17653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 17753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(SCEV *RHS) { 17853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS) { 17953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 18053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS; 18153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 18253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 18353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 18453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 18553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 18653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const SCEVHandle &operator=(const SCEVHandle &RHS) { 18753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner if (S != RHS.S) { 18853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->dropRef(); 18953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S = RHS.S; 19053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S->addRef(); 19153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 19253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return *this; 19353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 19453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 19553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 19653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<typename From> struct simplify_type; 19753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<const SCEVHandle> { 19835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman typedef const SCEV* SimpleType; 19953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 20053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return Node; 20153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 20253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 20353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner template<> struct simplify_type<SCEVHandle> 20453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner : public simplify_type<const SCEVHandle> {}; 20553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 20653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 20753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 20853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 20953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 21053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 21135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 21235738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 213f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 214f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 215f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 216f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 217f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 218f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 219f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 220f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 221f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// TD - The target data information for the target we are targetting. 222f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 223f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman TargetData *TD; 224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// UnknownValue - This SCEV is used to represent unknown trip counts and 226f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// things. 227f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle UnknownValue; 228f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 229f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Scalars - This is a cache of the scalars we have analyzed so far. 230f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 23135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman std::map<SCEVCallbackVH, SCEVHandle> Scalars; 232f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 233a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 234a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// of a loop. This currently inclues an exact count and a maximum count. 235a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 236a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman struct BackedgeTakenInfo { 237a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the exact backedge-taken count of 238a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 239a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle Exact; 240a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 241a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the least maximum backedge-taken 242a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 243a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle Max; 244a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 245a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : 246a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 247a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 24835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 249a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 250a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 251a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : 252a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(max) {} 253a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 254a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 255a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 256a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 257a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 258a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman return !isa<SCEVCouldNotCompute>(Exact) || 259a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman !isa<SCEVCouldNotCompute>(Max); 260a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 261a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 262a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 263f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 264f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 265a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 266f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 267f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 268f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 269f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 270f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 271f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 272f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 273f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 2746bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// ValuesAtScopes - This map contains entries for all the instructions 2756bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// that we attempt to compute getSCEVAtScope information for without 2766bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// using SCEV techniques, which can be expensive. 2776bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 2786bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 279f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 280f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 281f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle createSCEV(Value *V); 282f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 283f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 284f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 285f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle createNodeForPHI(PHINode *PN); 286f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 28726466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 28826466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 289fb791608115b5193419549b02825ed4337fd3a37Dan Gohman SCEVHandle createNodeForGEP(User *GEP); 29026466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 291f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 292f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// for the specified instruction and replaces any references to the 293f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// symbolic value SymName with the specified value. This is used during 294f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// PHI resolution. 295f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman void ReplaceSymbolicValueWithConcrete(Instruction *I, 296f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const SCEVHandle &SymName, 297f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const SCEVHandle &NewVal); 298f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 299a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 300a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 301a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 302a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 303a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 304f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 305f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 306a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 307f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 308f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 309f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the trip count. 310f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle 311f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 312f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *RHS, 313f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L, 314f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ICmpInst::Predicate p); 315f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 316f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 317f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// a constant number of times (the condition evolves only from constants), 318f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 319f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 320f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// evaluate the trip count of the loop, return UnknownValue. 321f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, 322f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool ExitWhen); 323f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 324f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToZero - Return the number of times a backedge comparing the 325f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value to zero will execute. If not computable, return 326f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// UnknownValue. 32735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVHandle HowFarToZero(const SCEV *V, const Loop *L); 328f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 329f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToNonZero - Return the number of times a backedge checking the 330f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value for nonzero will execute. If not computable, return 331f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// UnknownValue. 33235738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L); 333f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 334f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowManyLessThans - Return the number of times a backedge containing the 335f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified less-than comparison will execute. If not computable, return 336f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// UnknownValue. isSigned specifies whether the less-than is signed. 33735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 33835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const Loop *L, bool isSigned); 339f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 340f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 341f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 342f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 343f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 344f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 345f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 346f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 347f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 348f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 349f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 350f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 351f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 352f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 353fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// forgetLoopPHIs - Delete the memoized SCEVs associated with the 354fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// PHI nodes in the given loop. This is used when the trip count of 355fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// the loop may have changed. 356fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman void forgetLoopPHIs(const Loop *L); 357fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman 35853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 359ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 360f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 3619769ab22265b313171d201b5928688524a01bd87Misha Brukman 362af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 363af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 364af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 365af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman bool isSCEVable(const Type *Ty) const; 367af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 368af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 369af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 370af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman uint64_t getTypeSizeInBits(const Type *Ty) const; 371af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 372af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 373af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 374af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 375af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 376af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *getEffectiveSCEVType(const Type *Ty) const; 3772d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 37853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 37953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 380f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getSCEV(Value *V); 38153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 382246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(ConstantInt *V); 383246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(const APInt& Val); 384246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 385246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 386246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 387246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops); 388246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 389246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 390246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 391246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 392246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 393246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 394246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 395246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Op2) { 396246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 397246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 398246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 399246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 400246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 401246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 402246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops); 403246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 404246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> Ops; 405246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 406246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 407246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 408246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 409e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 410246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 411246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 412246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands, 413246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 414246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands, 415246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 416246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman std::vector<SCEVHandle> NewOp(Operands); 417246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 418246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 419c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 420c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky SCEVHandle getSMaxExpr(std::vector<SCEVHandle> Operands); 4213e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 4223e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getUMaxExpr(std::vector<SCEVHandle> Operands); 423246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getUnknown(Value *V); 424f4ccfcb70402b34ee55e0b5820cf287b95a8762fDan Gohman SCEVHandle getCouldNotCompute(); 425246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 426246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 427246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 428246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getNegativeSCEV(const SCEVHandle &V); 429246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4303e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 4313e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4323e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getNotSCEV(const SCEVHandle &V); 4333e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 434246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 435246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 436246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 437246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &RHS); 438246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4396f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 4406f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 4416f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 4426f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); 4436f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 444f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 445f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 446f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 447f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); 448f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 449467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 450467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 451467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 452467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty); 453467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 454467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 455467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 456467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 457467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty); 458467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 459467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 460467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 461467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 462467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty); 463467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 464246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getIntegerSCEV - Given an integer or FP type, create a constant for the 465246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 466246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 467246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 46827631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// hasSCEV - Return true if the SCEV for this value has already been 46927631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// computed. 47027631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner bool hasSCEV(Value *V) const; 47127631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 47227631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 47327631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// the specified value. 47427631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner void setSCEV(Value *V, const SCEVHandle &H); 47527631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 47653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 47753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 47853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 47953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 48053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 48153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 48253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 48353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 48453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// If this value is not computable at this scope, a SCEVCouldNotCompute 48553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// object is returned. 48666a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L); 48766a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 48866a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 48966a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 490f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getSCEVAtScope(Value *V, const Loop *L); 49153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 492c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// isLoopGuardedByCond - Test whether entry to the loop is protected by 4933d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// a conditional between LHS and RHS. This is used to help avoid max 4943d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// expressions in loop trip counts. 495c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 49635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *LHS, const SCEV *RHS); 497c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 49846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 49946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 50046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 50146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 50246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 50346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 50446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 50546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 50646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 50746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 50846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 509f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getBackedgeTakenCount(const Loop *L); 51053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 511a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 512a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 513a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 514a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle getMaxBackedgeTakenCount(const Loop *L); 515a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 51646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 51746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 518f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 51953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 52046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// forgetLoopBackedgeTakenCount - This method should be called by the 52160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman /// client when it has changed a loop in a way that may effect 52246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// ScalarEvolution's ability to compute a trip count, or if the loop 52346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// is deleted. 52446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void forgetLoopBackedgeTakenCount(const Loop *L); 52560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 52653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 52753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 52853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 529b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS, const Module* = 0) const; 530ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 5315c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 5325c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 5335c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 53453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 53553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 53653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 53753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 538