ScalarEvolution.h revision 1f6efa3996dd1929fbc129203ce5009b620e6969
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 113f46a3abeedba8d517b4182de34c821d752db058Dan Gohman// categorize 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" 2503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include "llvm/Instructions.h" 26ffef8acc3e3398bdd04e947c7949befdd52faf86Dan Gohman#include "llvm/Function.h" 271f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 2835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h" 291c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/Support/Allocator.h" 3085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman#include "llvm/Support/ConstantRange.h" 311c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/ADT/FoldingSet.h" 32444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.h" 3303ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include <map> 3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 36246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 3703ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class Constant; 38246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3903ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class DominatorTree; 4053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 41246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 42f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman class TargetData; 4312ddd409535b52a7fa5157ded9a4cedd161fedb6Benjamin Kramer class LLVMContext; 4403ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class Loop; 4503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class LoopInfo; 46fc8deb971d2b4dff370ba93948975e33a038605dDan Gohman class Operator; 47dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman class SCEVUnknown; 48aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman class SCEV; 49081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman template<> struct FoldingSetTrait<SCEV>; 5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 516c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// SCEV - This class represents an analyzed expression in the program. These 52650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// are opaque objects that the client is not allowed to do much with 53650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// directly. 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 55c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman class SCEV : public FoldingSetNode { 56081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman friend struct FoldingSetTrait<SCEV>; 57aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman 58c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// FastID - A reference to an Interned FoldingSetNodeID for this node. 59c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// The ScalarEvolution's BumpPtrAllocator holds the data. 60c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman FoldingSetNodeIDRef FastID; 61c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman 622f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman // The SCEV baseclass this node corresponds to 632f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman const unsigned short SCEVType; 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 652f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman protected: 662f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman /// SubclassData - This field is initialized to zero and may be used in 673f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// subclasses to store miscellaneous information. 682f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman unsigned short SubclassData; 692f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman 702f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman private: 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 734ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 753bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : 763bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} 771c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 7853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 7953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 8053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 8153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 824ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman const Type *getType() const; 8353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 84cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 85cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 86cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 87cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 8870a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// isOne - Return true if the expression is a constant one. 8970a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// 9070a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman bool isOne() const; 9170a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman 924d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// isAllOnesValue - Return true if the expression is a constant 934d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// all-ones value. 944d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// 954d289bf4af88759be173a1a809bf8c092d729764Dan Gohman bool isAllOnesValue() const; 964d289bf4af88759be173a1a809bf8c092d729764Dan Gohman 9753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 9853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 9953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 1004ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman void print(raw_ostream &OS) const; 10153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1069769ab22265b313171d201b5928688524a01bd87Misha Brukman 107aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman // Specialize FoldingSetTrait for SCEV to avoid needing to compute 108aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman // temporary FoldingSetNodeID values. 109aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { 110aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static void Profile(const SCEV &X, FoldingSetNodeID& ID) { 111aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman ID = X.FastID; 112aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 113aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, 114aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman FoldingSetNodeID &TempID) { 115aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman return ID == X.FastID; 116aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 117aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { 118aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman return X.FastID.ComputeHash(); 119aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 120aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman }; 121aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman 122b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 123b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 124b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 125b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 126b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 12953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 13253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 133753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson SCEVCouldNotCompute(); 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 13653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 13853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 13953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 14053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 14153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 14253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 14353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 14453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 145714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman public: 146714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// LoopDisposition - An enum describing the relationship between a 147714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// SCEV and a loop. 148714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman enum LoopDisposition { 149714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopVariant, ///< The SCEV is loop-variant (unknown). 150714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopInvariant, ///< The SCEV is loop-invariant. 151714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopComputable ///< The SCEV varies predictably with the loop. 152714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman }; 153714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 1549c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// BlockDisposition - An enum describing the relationship between a 1559c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// SCEV and a basic block. 1569c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman enum BlockDisposition { 1579c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman DoesNotDominateBlock, ///< The SCEV does not dominate the block. 1589c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman DominatesBlock, ///< The SCEV dominates the block. 1599c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman ProperlyDominatesBlock ///< The SCEV properly dominates the block. 1609c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman }; 1619c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 162714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman private: 1631959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 1641959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// notified whenever a Value is deleted. 1651959b7562e57f8394496e761486f23b187ac3f1bDan Gohman class SCEVCallbackVH : public CallbackVH { 1661959b7562e57f8394496e761486f23b187ac3f1bDan Gohman ScalarEvolution *SE; 1671959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void deleted(); 1681959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void allUsesReplacedWith(Value *New); 1691959b7562e57f8394496e761486f23b187ac3f1bDan Gohman public: 1701959b7562e57f8394496e761486f23b187ac3f1bDan Gohman SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 1711959b7562e57f8394496e761486f23b187ac3f1bDan Gohman }; 1721959b7562e57f8394496e761486f23b187ac3f1bDan Gohman 17335738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 174629bff692ae96dea517dc854e27b57ee6c8729efBenjamin Kramer friend class SCEVExpander; 175dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman friend class SCEVUnknown; 17635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 177f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 178f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 179f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 180f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 181f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 182f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 183f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 184f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 1853f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// TD - The target data information for the target we are targeting. 186f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 187f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman TargetData *TD; 188f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 1891cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman /// DT - The dominator tree. 1901cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman /// 1911cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman DominatorTree *DT; 1921cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman 19386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute - This SCEV is used to represent unknown trip 19486fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// counts and things. 1951c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman SCEVCouldNotCompute CouldNotCompute; 196f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 197e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// ValueExprMapType - The typedef for ValueExprMap. 198f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 199e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> > 200e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman ValueExprMapType; 201e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman 202e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// ValueExprMap - This is a cache of the values we have analyzed so far. 203e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// 204e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman ValueExprMapType ValueExprMap; 205f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 206a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 2073f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// of a loop. This currently includes an exact count and a maximum count. 208a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 209a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman struct BackedgeTakenInfo { 210a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the exact backedge-taken count of 211a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 2120bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Exact; 213a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2147b9547089f0363b803e55dcbde1d6b99710dfe69Andreas Bolka /// Max - An expression indicating the least maximum backedge-taken 215a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 2160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Max; 217a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2180bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 219a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 220a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2210bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : 222a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(max) {} 223a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 224a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 225a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 226a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 227a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 228a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman return !isa<SCEVCouldNotCompute>(Exact) || 229a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman !isa<SCEVCouldNotCompute>(Max); 230a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 231a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 232a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 233f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 234f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 235a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 236f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 237f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 238f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 239f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 240f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 241f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 242f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 243f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 24442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// ValuesAtScopes - This map contains entries for all the expressions 24542214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// that we attempt to compute getSCEVAtScope information for, which can 24642214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// be expensive in extreme cases. 24742214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman std::map<const SCEV *, 24842214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman std::map<const Loop *, const SCEV *> > ValuesAtScopes; 2496bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 250714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// LoopDispositions - Memoized computeLoopDisposition results. 251714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman std::map<const SCEV *, 252714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman std::map<const Loop *, LoopDisposition> > LoopDispositions; 253714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 254714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// computeLoopDisposition - Compute a LoopDisposition value. 255714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); 256714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 2579c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// BlockDispositions - Memoized computeBlockDisposition results. 2589c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman std::map<const SCEV *, 2599c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman std::map<const BasicBlock *, BlockDisposition> > BlockDispositions; 2609c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 2619c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// computeBlockDisposition - Compute a BlockDisposition value. 2629c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); 2639c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 2646678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman /// UnsignedRanges - Memoized results from getUnsignedRange 2656678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman DenseMap<const SCEV *, ConstantRange> UnsignedRanges; 2666678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman 2676678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman /// SignedRanges - Memoized results from getSignedRange 2686678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman DenseMap<const SCEV *, ConstantRange> SignedRanges; 2696678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman 2707c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. 2717c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &setUnsignedRange(const SCEV *S, 2727c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &CR) { 2737c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = 2747c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman UnsignedRanges.insert(std::make_pair(S, CR)); 2757c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman if (!Pair.second) 2767c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman Pair.first->second = CR; 2777c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman return Pair.first->second; 2787c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman } 2797c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman 2807c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman /// setUnsignedRange - Set the memoized signed range for the given SCEV. 2817c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &setSignedRange(const SCEV *S, 2827c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &CR) { 2837c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = 2847c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman SignedRanges.insert(std::make_pair(S, CR)); 2857c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman if (!Pair.second) 2867c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman Pair.first->second = CR; 2877c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman return Pair.first->second; 2887c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman } 2897c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman 290f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 291f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 2920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createSCEV(Value *V); 293f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 294f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 295f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 2960bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createNodeForPHI(PHINode *PN); 297f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 29826466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 29926466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 300d281ed2d03654b9cdb290a2d7c73dfe7b826e554Dan Gohman const SCEV *createNodeForGEP(GEPOperator *GEP); 30126466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 30242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called 30342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// at most once for each SCEV+Loop pair. 30442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// 30542214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); 30642214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman 307fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// ForgetSymbolicValue - This looks up computed SCEV values for all 308fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// instructions that depend on the given instruction and removes them from 309e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// the ValueExprMap map if they reference SymName. This is used during PHI 310fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// resolution. 311fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman void ForgetSymbolicName(Instruction *I, const SCEV *SymName); 312f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 31351f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// getBECount - Subtract the end and start values and divide by the step, 31451f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// rounding up, to get the number of times the backedge is executed. Return 31551f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// CouldNotCompute if an intermediate computation overflows. 3160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getBECount(const SCEV *Start, 317a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman const SCEV *End, 3181f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman const SCEV *Step, 3191f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman bool NoWrap); 32051f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman 321a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 322a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 323a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 324a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 325a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 326f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 327f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 328a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 329f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 330a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 331a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if it exits via the 332a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// specified block. 333a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 334a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *ExitingBlock); 335a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 336a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 337a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if its exit condition 338a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// were a conditional branch of ExitCond, TBB, and FBB. 339a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 340a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCond(const Loop *L, 341a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman Value *ExitCond, 342a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 343a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 344a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 345a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 346a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// times the backedge of the specified loop will execute if its exit 347a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 348a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// and FBB. 349a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 350a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 351a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ICmpInst *ExitCond, 352a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 353a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 354a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 355f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 3567e77f7959162a601291fd5400a88908d021033d3Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the 3577e77f7959162a601291fd5400a88908d021033d3Dan Gohman /// backedge-taken count. 358f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman BackedgeTakenInfo 359f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 360f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *RHS, 361f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L, 362f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ICmpInst::Predicate p); 363f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 36407ad19b509530b43e6a9acc5c1285cb560dd7198Dan Gohman /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute 365f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// a constant number of times (the condition evolves only from constants), 366f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 367f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 3687e77f7959162a601291fd5400a88908d021033d3Dan Gohman /// evaluate the backedge-taken count of the loop, return CouldNotCompute. 3690bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, 370650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman Value *Cond, 371650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman bool ExitWhen); 372f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 373f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToZero - Return the number of times a backedge comparing the 374f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value to zero will execute. If not computable, return 37586fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 376f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L); 377f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 378f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToNonZero - Return the number of times a backedge checking the 379f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value for nonzero will execute. If not computable, return 38086fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 381f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L); 382f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 383f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowManyLessThans - Return the number of times a backedge containing the 384f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified less-than comparison will execute. If not computable, return 38586fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. isSigned specifies whether the less-than is signed. 38635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 38735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const Loop *L, bool isSigned); 388f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 389f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 390f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 391f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 392f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 393005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman std::pair<BasicBlock *, BasicBlock *> 394005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 395f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 396af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman /// isImpliedCond - Test whether the condition described by Pred, LHS, and 397af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman /// RHS is true whenever the given FoundCondValue value evaluates to true. 398af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman bool isImpliedCond(ICmpInst::Predicate Pred, 3990f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 400af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman Value *FoundCondValue, 4010f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool Inverse); 4020f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman 4030f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// isImpliedCondOperands - Test whether the condition described by Pred, 4043f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, 4050f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// and FoundRHS is true. 4060f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool isImpliedCondOperands(ICmpInst::Predicate Pred, 4070f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 4080f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *FoundLHS, const SCEV *FoundRHS); 4090f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman 4100f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// isImpliedCondOperandsHelper - Test whether the condition described by 4113f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// Pred, LHS, and RHS is true whenever the condition described by Pred, 4120f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// FoundLHS, and FoundRHS is true. 4130f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, 4140f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 4150f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *FoundLHS, const SCEV *FoundRHS); 41685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 417f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 418f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 419f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 420f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 421f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 422f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 423f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 42453c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// isKnownPredicateWithRanges - Test if the given expression is known to 42553c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// satisfy the condition described by Pred and the known constant ranges 42653c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// of LHS and RHS. 42753c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// 42853c66eacc417c0113fba7159487b90005dc8f91eDan Gohman bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, 42953c66eacc417c0113fba7159487b90005dc8f91eDan Gohman const SCEV *LHS, const SCEV *RHS); 43053c66eacc417c0113fba7159487b90005dc8f91eDan Gohman 43156a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman /// forgetMemoizedResults - Drop memoized information computed for S. 43256a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman void forgetMemoizedResults(const SCEV *S); 43356a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman 43453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 435ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 436f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 4379769ab22265b313171d201b5928688524a01bd87Misha Brukman 438e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &getContext() const { return F->getContext(); } 439508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson 440af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 441af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 442af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 443af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 444af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman bool isSCEVable(const Type *Ty) const; 445af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 446af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 447af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 448af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman uint64_t getTypeSizeInBits(const Type *Ty) const; 449af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 450af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 451af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 452af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 453af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 454af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *getEffectiveSCEVType(const Type *Ty) const; 4552d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 456e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman /// getSCEV - Return a SCEV expression for the full generality of the 45753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 4580bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEV(Value *V); 4590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman 4600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(ConstantInt *V); 4610bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(const APInt& Val); 4620bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 4630bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); 4640bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); 4650bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); 4660bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); 4673645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, 4683645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false); 4693645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, 4703645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false) { 4710bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 472246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 473246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 4743645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman return getAddExpr(Ops, HasNUW, HasNSW); 475246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4760bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, 4773645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *Op2, 4783645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false) { 4790bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 3> Ops; 480246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 481246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 482246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 4833645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman return getAddExpr(Ops, HasNUW, HasNSW); 484246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4853645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 4863645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false); 4873645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, 4883645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false) { 4890bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 490246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 491246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 4923645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman return getMulExpr(Ops, HasNUW, HasNSW); 493246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4940bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 4950bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 4963645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const Loop *L, 4973645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false); 4980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 4993645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const Loop *L, 5003645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false); 5010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 5023645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const Loop *L, 5033645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool HasNUW = false, bool HasNSW = false) { 5040bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 5053645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman return getAddRecExpr(NewOp, L, HasNUW, HasNSW); 506246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 5070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 5080bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 5090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 5100bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 5110bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 5120bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 5130bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUnknown(Value *V); 5140bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getCouldNotCompute(); 515246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 5164f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// getSizeOfExpr - Return an expression for sizeof on the given type. 5174f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 5184f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman const SCEV *getSizeOfExpr(const Type *AllocTy); 5194f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 520ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman /// getAlignOfExpr - Return an expression for alignof on the given type. 5214f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 5224f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman const SCEV *getAlignOfExpr(const Type *AllocTy); 5234f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 524ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman /// getOffsetOfExpr - Return an expression for offsetof on the given field. 5254f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 5264f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo); 5274f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 528ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman /// getOffsetOfExpr - Return an expression for offsetof on the given field. 5294f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 5304f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo); 5314f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 532246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 533246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 5340bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNegativeSCEV(const SCEV *V); 535246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 5363e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 5373e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 5380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNotSCEV(const SCEV *V); 5393e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 540246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 541246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 5420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMinusSCEV(const SCEV *LHS, 543a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman const SCEV *RHS); 544246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 5456f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 5466f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 5476f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 5480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); 5496f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 550f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 551f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 552f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 5530bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); 554f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 555467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 556467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 557467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 5580bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); 559467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 560467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 561467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 562467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 5630bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); 564467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 5652ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 5662ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// the input value to the specified type. If the type must be extended, 5672ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// it is extended with unspecified bits. The conversion must not be 5682ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// narrowing. 5690bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); 5702ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman 571467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 572467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 573467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 5740bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); 575467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 576a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 577a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// the types using zero-extension, and then perform a umax operation 578a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// with them. 5790bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 580a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman const SCEV *RHS); 581a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 582c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// getUMinFromMismatchedTypes - Promote the operands to the wider of 583c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// the types using zero-extension, and then perform a umin operation 584c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// with them. 5850bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 5860bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS); 587c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman 588e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman /// getSCEVAtScope - Return a SCEV expression for the specified value 58953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 59053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 59153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 59253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 59353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 59453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 59553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 596d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// In the case that a relevant loop exit value cannot be computed, the 597d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// original value V is returned. 5980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 59966a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 60066a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 60166a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 6020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(Value *V, const Loop *L); 60353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6043948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected 6053948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman /// by a conditional between LHS and RHS. This is used to help avoid max 60685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// expressions in loop trip counts, and to eliminate casts. 6073948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 6083948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman const SCEV *LHS, const SCEV *RHS); 609c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 61085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 61185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// protected by a conditional between LHS and RHS. This is used to 61285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// to eliminate casts. 61385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 61485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 61585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 61646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 61746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 61846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 61946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 62046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 62146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 62246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 62346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 62446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 62546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 62646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 6270bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getBackedgeTakenCount(const Loop *L); 62853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 629a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 630a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 631a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 6320bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMaxBackedgeTakenCount(const Loop *L); 633a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 63446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 63546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 636f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 63753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6384c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// forgetLoop - This method should be called by the client when it has 6394c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// changed a loop in a way that may effect ScalarEvolution's ability to 6404c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// compute a trip count, or if the loop is deleted. 6414c7279ac726e338400626fca5a09b5533426eb6aDan Gohman void forgetLoop(const Loop *L); 64260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 64345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// forgetValue - This method should be called by the client when it has 64445a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// changed a value in a way that may effect its value, or which may 64545a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// disconnect it from a def-use chain linking it to a loop. 64645a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen void forgetValue(Value *V); 64745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 648650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// GetMinTrailingZeros - Determine the minimum number of zero bits that S 649650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// is guaranteed to end in (at every loop iteration). It is, at the same 650650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// time, the minimum number of times S is divisible by 2. For example, 651650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the 652650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// bitwidth of S. 6530bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman uint32_t GetMinTrailingZeros(const SCEV *S); 6542c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 65585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 65685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 65785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getUnsignedRange(const SCEV *S); 65885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 65985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getSignedRange - Determine the signed range for a particular SCEV. 66085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 66185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getSignedRange(const SCEV *S); 66285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 66385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNegative - Test if the given expression is known to be negative. 66485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 66585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNegative(const SCEV *S); 66685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 66785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownPositive - Test if the given expression is known to be positive. 66885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 66985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPositive(const SCEV *S); 67085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 67185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonNegative - Test if the given expression is known to be 67285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-negative. 67385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 67485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonNegative(const SCEV *S); 67585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 67685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonPositive - Test if the given expression is known to be 67785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-positive. 67885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 67985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonPositive(const SCEV *S); 68085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 68185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonZero - Test if the given expression is known to be 68285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-zero. 68385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 68485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonZero(const SCEV *S); 6852c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 686e48172710bf78ae210b2257d6ac3e0e8fb3ba792Dan Gohman /// isKnownPredicate - Test if the given expression is known to satisfy 68785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// the condition described by Pred, LHS, and RHS. 68885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 68985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPredicate(ICmpInst::Predicate Pred, 69085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 6912c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 692e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with 6935cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman /// predicate Pred. Return true iff any changes were made. If the 6945cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman /// operands are provably equal or inequal, LHS and RHS are set to 6955cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. 696e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman /// 697e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, 698e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman const SCEV *&LHS, 699e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman const SCEV *&RHS); 700e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman 701714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// getLoopDisposition - Return the "disposition" of the given SCEV with 702714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// respect to the given loop. 703714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); 704714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 70517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// isLoopInvariant - Return true if the value of the given SCEV is 70617ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// unchanging in the specified loop. 70717ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman bool isLoopInvariant(const SCEV *S, const Loop *L); 70817ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman 70917ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// hasComputableLoopEvolution - Return true if the given SCEV changes value 71017ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// in a known way in the specified loop. This property being true implies 71117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// that the value is variant in the loop AND that we can emit an expression 71217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// to compute the value of the expression at any particular loop iteration. 71317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); 71417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman 7159c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// getLoopDisposition - Return the "disposition" of the given SCEV with 7169c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// respect to the given block. 7179c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); 7189c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 719dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// dominates - Return true if elements that makes up the given SCEV 720dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// dominate the specified basic block. 7219c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman bool dominates(const SCEV *S, const BasicBlock *BB); 722dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman 723dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// properlyDominates - Return true if elements that makes up the given SCEV 724dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// properly dominate the specified basic block. 7259c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman bool properlyDominates(const SCEV *S, const BasicBlock *BB); 726dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman 7274ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman /// hasOperand - Test whether the given SCEV has Op as a direct or 7284ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman /// indirect operand. 7294ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman bool hasOperand(const SCEV *S, const SCEV *Op) const; 7304ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman 73153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 73253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 73353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 73445cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner virtual void print(raw_ostream &OS, const Module* = 0) const; 7351c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 73608367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson private: 7371c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman FoldingSet<SCEV> UniqueSCEVs; 7381c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman BumpPtrAllocator SCEVAllocator; 739ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 740ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// FirstUnknown - The head of a linked list of all SCEVUnknown 741ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// values that have been allocated. This is used by releaseMemory 742ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// to locate them all and call their destructors. 743ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown *FirstUnknown; 74453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 74553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 74653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 74753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 748