ScalarEvolution.h revision 51f53b7f5a0e859ceef995c61667905166b96f1b
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" 28444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.h" 291baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman#include <iosfwd> 3053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 32246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 33246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 3553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEVHandle; 36246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 37f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman class TargetData; 38444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman template<> struct DenseMapInfo<SCEVHandle>; 3953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 406c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// SCEV - This class represents an analyzed expression in the program. These 416c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// 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; 49444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman friend class DenseMapInfo<SCEVHandle>; 50afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void addRef() const { ++RefCount; } 51afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner void dropRef() const { 52254bacd79a07632548de2f1c91d2768572764f66Chris Lattner if (--RefCount == 0) 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner delete this; 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 564a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson const ScalarEvolution* parent; 574a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson 5853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 6053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 6153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 634a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson explicit SCEV(unsigned SCEVTy, const ScalarEvolution* p) : 644a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson SCEVType(SCEVTy), RefCount(0), parent(p) {} 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 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 82cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 83cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 84cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 85cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 8670a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// isOne - Return true if the expression is a constant one. 8770a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// 8870a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman bool isOne() const; 8970a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman 90afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 91afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 92afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 93afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 94afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 959769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 96afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 97246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 98246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 99afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1005a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// dominates - Return true if elements that makes up this SCEV dominates 1015a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// the specified basic block. 1025a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 1035a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 10653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 107b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const = 0; 108b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(std::ostream &OS) const; 1095c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 11053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1159769ab22265b313171d201b5928688524a01bd87Misha Brukman 116b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 117b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 118b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 119b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 120b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 12953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 1324a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson SCEVCouldNotCompute(const ScalarEvolution* p); 133f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ~SCEVCouldNotCompute(); 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 13653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 13853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 139b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1409769ab22265b313171d201b5928688524a01bd87Misha Brukman virtual SCEVHandle 141afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 142246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 143246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 14453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 1455a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 1465a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 1475a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 1485a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 14953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 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 206444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman // Specialize DenseMapInfo for SCEVHandle so that SCEVHandle may be used 207444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman // as a key in DenseMaps. 208444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman template<> 209444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman struct DenseMapInfo<SCEVHandle> { 210444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman static inline SCEVHandle getEmptyKey() { 2114a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson static SCEVCouldNotCompute Empty(0); 212444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman if (Empty.RefCount == 0) 213444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman Empty.addRef(); 214444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman return &Empty; 215444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman } 216444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman static inline SCEVHandle getTombstoneKey() { 2174a7893b4527819aae229f539ab9c3eeecc6a10e2Owen Anderson static SCEVCouldNotCompute Tombstone(0); 218444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman if (Tombstone.RefCount == 0) 219444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman Tombstone.addRef(); 220444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman return &Tombstone; 221444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman } 222444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman static unsigned getHashValue(const SCEVHandle &Val) { 223444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman return DenseMapInfo<const SCEV *>::getHashValue(Val); 224444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman } 225444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman static bool isEqual(const SCEVHandle &LHS, const SCEVHandle &RHS) { 226444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman return LHS == RHS; 227444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman } 228444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman static bool isPod() { return false; } 229444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman }; 230444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman 23153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 23253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 23353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 23453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 23553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 2361959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 2371959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// notified whenever a Value is deleted. 2381959b7562e57f8394496e761486f23b187ac3f1bDan Gohman class SCEVCallbackVH : public CallbackVH { 2391959b7562e57f8394496e761486f23b187ac3f1bDan Gohman ScalarEvolution *SE; 2401959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void deleted(); 2411959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void allUsesReplacedWith(Value *New); 2421959b7562e57f8394496e761486f23b187ac3f1bDan Gohman public: 2431959b7562e57f8394496e761486f23b187ac3f1bDan Gohman SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 2441959b7562e57f8394496e761486f23b187ac3f1bDan Gohman }; 2451959b7562e57f8394496e761486f23b187ac3f1bDan Gohman 24635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 2475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman friend class SCEVExpander; 24835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 249f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 250f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 251f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 252f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 253f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 254f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 255f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 256f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 257f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// TD - The target data information for the target we are targetting. 258f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 259f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman TargetData *TD; 260f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 26186fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute - This SCEV is used to represent unknown trip 26286fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// counts and things. 26386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman SCEVHandle CouldNotCompute; 264f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 265f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Scalars - This is a cache of the scalars we have analyzed so far. 266f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 26735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman std::map<SCEVCallbackVH, SCEVHandle> Scalars; 268f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 269a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 270a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// of a loop. This currently inclues an exact count and a maximum count. 271a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 272a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman struct BackedgeTakenInfo { 273a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the exact backedge-taken count of 274a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 275a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle Exact; 276a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 277a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the least maximum backedge-taken 278a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 279a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle Max; 280a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 281a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : 282a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 283a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 28435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 285a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 286a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 287a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : 288a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(max) {} 289a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 290a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 291a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 292a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 293a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 294a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman return !isa<SCEVCouldNotCompute>(Exact) || 295a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman !isa<SCEVCouldNotCompute>(Max); 296a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 297a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 298a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 299f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 300f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 301a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 302f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 303f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 304f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 305f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 306f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 307f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 308f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 309f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 3106bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// ValuesAtScopes - This map contains entries for all the instructions 3116bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// that we attempt to compute getSCEVAtScope information for without 3126bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// using SCEV techniques, which can be expensive. 3136bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 3146bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 315f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 316f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 317f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle createSCEV(Value *V); 318f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 319f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 320f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 321f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle createNodeForPHI(PHINode *PN); 322f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 32326466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 32426466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 325fb791608115b5193419549b02825ed4337fd3a37Dan Gohman SCEVHandle createNodeForGEP(User *GEP); 32626466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 327f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 328f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// for the specified instruction and replaces any references to the 329f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// symbolic value SymName with the specified value. This is used during 330f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// PHI resolution. 331f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman void ReplaceSymbolicValueWithConcrete(Instruction *I, 332f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const SCEVHandle &SymName, 333f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const SCEVHandle &NewVal); 334f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 33551f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// getBECount - Subtract the end and start values and divide by the step, 33651f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// rounding up, to get the number of times the backedge is executed. Return 33751f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// CouldNotCompute if an intermediate computation overflows. 33851f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman SCEVHandle getBECount(const SCEVHandle &Start, 33951f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman const SCEVHandle &End, 34051f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman const SCEVHandle &Step); 34151f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman 342a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 343a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 344a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 345a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 346a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 347f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 348f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 349a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 350f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 351f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 352f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the trip count. 353f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle 354f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 355f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *RHS, 356f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L, 357f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ICmpInst::Predicate p); 358f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 359f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 360f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// a constant number of times (the condition evolves only from constants), 361f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 362f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 36386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// evaluate the trip count of the loop, return CouldNotCompute. 364f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, 365f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool ExitWhen); 366f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 367f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToZero - Return the number of times a backedge comparing the 368f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value to zero will execute. If not computable, return 36986fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 37035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVHandle HowFarToZero(const SCEV *V, const Loop *L); 371f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 372f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToNonZero - Return the number of times a backedge checking the 373f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value for nonzero will execute. If not computable, return 37486fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 37535738ac150afafe2359268d4b2169498c6c98c5fDan Gohman SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L); 376f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 377f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowManyLessThans - Return the number of times a backedge containing the 378f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified less-than comparison will execute. If not computable, return 37986fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. isSigned specifies whether the less-than is signed. 38035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 38135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const Loop *L, bool isSigned); 382f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 383859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// getLoopPredecessor - If the given loop's header has exactly one unique 384859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// predecessor outside the loop, return it. Otherwise return null. 385859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman BasicBlock *getLoopPredecessor(const Loop *L); 386859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman 387f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 388f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 389f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 390f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 391f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 392f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 393f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 394f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 395f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 396f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 397f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 398f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 399f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 400fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// forgetLoopPHIs - Delete the memoized SCEVs associated with the 401fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// PHI nodes in the given loop. This is used when the trip count of 402fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// the loop may have changed. 403fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman void forgetLoopPHIs(const Loop *L); 404fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman 40553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 406ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 407f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 4089769ab22265b313171d201b5928688524a01bd87Misha Brukman 409af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 410af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 411af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 412af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 413af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman bool isSCEVable(const Type *Ty) const; 414af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 415af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 416af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 417af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman uint64_t getTypeSizeInBits(const Type *Ty) const; 418af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 419af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 420af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 421af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 422af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 423af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *getEffectiveSCEVType(const Type *Ty) const; 4242d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 42553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 42653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 427f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getSCEV(Value *V); 42853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 429246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(ConstantInt *V); 430246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getConstant(const APInt& Val); 4316de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman SCEVHandle getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 432246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 433246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 434246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 4352ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman SCEVHandle getAnyExtendExpr(const SCEVHandle &Op, const Type *Ty); 436a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getAddExpr(SmallVectorImpl<SCEVHandle> &Ops); 437246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 438a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SmallVector<SCEVHandle, 2> Ops; 439246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 440246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 441246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 442246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 443246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 444246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Op2) { 445a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SmallVector<SCEVHandle, 3> Ops; 446246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 447246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 448246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 449246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 450246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 451a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getMulExpr(SmallVectorImpl<SCEVHandle> &Ops); 452246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 453a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SmallVector<SCEVHandle, 2> Ops; 454246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 455246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 456246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 457246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 458e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 459246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 460246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 461a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getAddRecExpr(SmallVectorImpl<SCEVHandle> &Operands, 462246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 463a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getAddRecExpr(const SmallVectorImpl<SCEVHandle> &Operands, 464246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 465a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SmallVector<SCEVHandle, 4> NewOp(Operands.begin(), Operands.end()); 466246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 467246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 468c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 469a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getSMaxExpr(SmallVectorImpl<SCEVHandle> &Operands); 4703e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 471a82752c9eb5fbdd1b7276fde7349ac9453eb5a75Dan Gohman SCEVHandle getUMaxExpr(SmallVectorImpl<SCEVHandle> &Operands); 472246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getUnknown(Value *V); 473f4ccfcb70402b34ee55e0b5820cf287b95a8762fDan Gohman SCEVHandle getCouldNotCompute(); 474246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 475246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 476246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 477246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getNegativeSCEV(const SCEVHandle &V); 478246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4793e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 4803e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4813e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky SCEVHandle getNotSCEV(const SCEVHandle &V); 4823e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 483246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 484246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 485246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 486246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &RHS); 487246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4886f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 4896f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 4906f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 4916f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); 4926f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 493f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 494f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 495f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 496f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); 497f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 498467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 499467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 500467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 501467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty); 502467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 503467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 504467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 505467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 506467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty); 507467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 5082ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 5092ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// the input value to the specified type. If the type must be extended, 5102ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// it is extended with unspecified bits. The conversion must not be 5112ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// narrowing. 5122ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman SCEVHandle getNoopOrAnyExtend(const SCEVHandle &V, const Type *Ty); 5132ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman 514467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 515467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 516467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 517467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty); 518467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 519246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getIntegerSCEV - Given an integer or FP type, create a constant for the 520246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 521246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 522246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 52327631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// hasSCEV - Return true if the SCEV for this value has already been 52427631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// computed. 52527631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner bool hasSCEV(Value *V) const; 52627631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 52727631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 52827631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// the specified value. 52927631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner void setSCEV(Value *V, const SCEVHandle &H); 53027631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 53153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 53253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 53353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 53453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 53553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 53653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 53753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 53853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 539d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// In the case that a relevant loop exit value cannot be computed, the 540d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// original value V is returned. 54166a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L); 54266a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 54366a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 54466a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 545f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getSCEVAtScope(Value *V, const Loop *L); 54653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 547c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// isLoopGuardedByCond - Test whether entry to the loop is protected by 5483d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// a conditional between LHS and RHS. This is used to help avoid max 5493d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// expressions in loop trip counts. 550c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 55135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *LHS, const SCEV *RHS); 552c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 55346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 55446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 55546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 55646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 55746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 55846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 55946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 56046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 56146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 56246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 56346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 564f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman SCEVHandle getBackedgeTakenCount(const Loop *L); 56553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 566a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 567a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 568a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 569a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman SCEVHandle getMaxBackedgeTakenCount(const Loop *L); 570a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 57146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 57246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 573f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 57453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 57546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// forgetLoopBackedgeTakenCount - This method should be called by the 57660f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman /// client when it has changed a loop in a way that may effect 57746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// ScalarEvolution's ability to compute a trip count, or if the loop 57846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// is deleted. 57946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void forgetLoopBackedgeTakenCount(const Loop *L); 58060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 5812c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 5822c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to end in (at every loop iteration). It is, at the same time, 5832c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// the minimum number of times S is divisible by 2. For example, given {4,+,8} 5842c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 5852c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman uint32_t GetMinTrailingZeros(const SCEVHandle &S); 5862c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 5872c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is 5882c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to begin with (at every loop iteration). 5892c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman uint32_t GetMinLeadingZeros(const SCEVHandle &S); 5902c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 5912c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinSignBits - Determine the minimum number of sign bits that S is 5922c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to begin with. 5932c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman uint32_t GetMinSignBits(const SCEVHandle &S); 5942c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 59553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 59653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 59753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 598b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS, const Module* = 0) const; 599ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 6005c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 6015c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 6025c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 60353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 60453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 60553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 60653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 607