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 24255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/DenseSet.h" 25255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/FoldingSet.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ConstantRange.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 31255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Pass.h" 321c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/Support/Allocator.h" 33255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/DataTypes.h" 3403ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include <map> 3553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 37246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 3803ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class Constant; 39246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 4003ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class DominatorTree; 4153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 42246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 433574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow class DataLayout; 44618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier class TargetLibraryInfo; 4512ddd409535b52a7fa5157ded9a4cedd161fedb6Benjamin Kramer class LLVMContext; 4603ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class Loop; 4703ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class LoopInfo; 48fc8deb971d2b4dff370ba93948975e33a038605dDan Gohman class Operator; 49dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman class SCEVUnknown; 50aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman class SCEV; 51081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman template<> struct FoldingSetTrait<SCEV>; 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 536c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// SCEV - This class represents an analyzed expression in the program. These 54650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// are opaque objects that the client is not allowed to do much with 55650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// directly. 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 57c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman class SCEV : public FoldingSetNode { 58081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman friend struct FoldingSetTrait<SCEV>; 59aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman 60c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// FastID - A reference to an Interned FoldingSetNodeID for this node. 61c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// The ScalarEvolution's BumpPtrAllocator holds the data. 62c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman FoldingSetNodeIDRef FastID; 63c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman 642f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman // The SCEV baseclass this node corresponds to 652f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman const unsigned short SCEVType; 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 672f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman protected: 682f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman /// SubclassData - This field is initialized to zero and may be used in 693f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// subclasses to store miscellaneous information. 702f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman unsigned short SubclassData; 712f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman 722f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman private: 73de8091708f2d5ade958507aa6d37907a6277e9f2Craig Topper SCEV(const SCEV &) LLVM_DELETED_FUNCTION; 74de8091708f2d5ade958507aa6d37907a6277e9f2Craig Topper void operator=(const SCEV &) LLVM_DELETED_FUNCTION; 754ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman 7653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 773228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// NoWrapFlags are bitfield indices into SubclassData. 783228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// 793228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// Add and Mul expressions may have no-unsigned-wrap <NUW> or 803228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// no-signed-wrap <NSW> properties, which are derived from the IR 813228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// operator. NSW is a misnomer that we use to mean no signed overflow or 823228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// underflow. 833228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// 843228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// AddRec expression may have a no-self-wraparound <NW> property if the 853228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// result can never reach the start value. This property is independent of 863228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// the actual start value and step direction. Self-wraparound is defined 873228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// purely in terms of the recurrence's loop, step size, and 883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: 893228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). 903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// 913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// Note that NUW and NSW are also valid properties of a recurrence, and 923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// either implies NW. For convenience, NW will be set for a recurrence 933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// whenever either NUW or NSW are set. 943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. 953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick FlagNW = (1 << 0), // No self-wrap. 963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick FlagNUW = (1 << 1), // No unsigned wrap. 973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick FlagNSW = (1 << 2), // No signed wrap. 983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick NoWrapMask = (1 << 3) -1 }; 993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick 1003bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : 1013bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} 1021c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 10653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 107db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const; 10853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 109cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 110cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 111cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 112cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 11370a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// isOne - Return true if the expression is a constant one. 11470a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// 11570a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman bool isOne() const; 11670a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman 1174d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// isAllOnesValue - Return true if the expression is a constant 1184d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// all-ones value. 1194d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// 1204d289bf4af88759be173a1a809bf8c092d729764Dan Gohman bool isAllOnesValue() const; 1214d289bf4af88759be173a1a809bf8c092d729764Dan Gohman 122f8fd841a4bb7a59f81cf4642169e8251e039acfeAndrew Trick /// isNonConstantNegative - Return true if the specified scev is negated, 123f8fd841a4bb7a59f81cf4642169e8251e039acfeAndrew Trick /// but not a constant. 124f8fd841a4bb7a59f81cf4642169e8251e039acfeAndrew Trick bool isNonConstantNegative() const; 125f8fd841a4bb7a59f81cf4642169e8251e039acfeAndrew Trick 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 1294ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman void print(raw_ostream &OS) const; 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 13253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 13353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1359769ab22265b313171d201b5928688524a01bd87Misha Brukman 136aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman // Specialize FoldingSetTrait for SCEV to avoid needing to compute 137aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman // temporary FoldingSetNodeID values. 138aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { 139aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static void Profile(const SCEV &X, FoldingSetNodeID& ID) { 140aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman ID = X.FastID; 141aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 142aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, 143f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer unsigned IDHash, FoldingSetNodeID &TempID) { 144aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman return ID == X.FastID; 145aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 146aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { 147aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman return X.FastID.ComputeHash(); 148aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman } 149aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman }; 150aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman 151b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 152b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 153b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 154b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 155b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 16053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 162753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson SCEVCouldNotCompute(); 16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 16553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 16853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 16953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 17053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 17153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 17253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 173714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman public: 174714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// LoopDisposition - An enum describing the relationship between a 175714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// SCEV and a loop. 176714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman enum LoopDisposition { 177714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopVariant, ///< The SCEV is loop-variant (unknown). 178714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopInvariant, ///< The SCEV is loop-invariant. 179714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopComputable ///< The SCEV varies predictably with the loop. 180714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman }; 181714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 1829c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// BlockDisposition - An enum describing the relationship between a 1839c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// SCEV and a basic block. 1849c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman enum BlockDisposition { 1859c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman DoesNotDominateBlock, ///< The SCEV does not dominate the block. 1869c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman DominatesBlock, ///< The SCEV dominates the block. 1879c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman ProperlyDominatesBlock ///< The SCEV properly dominates the block. 1889c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman }; 1899c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 1903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// Convenient NoWrapFlags manipulation that hides enum casts and is 1913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// visible in the ScalarEvolution name space. 1922905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 1932905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer maskFlags(SCEV::NoWrapFlags Flags, int Mask) { 1943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return (SCEV::NoWrapFlags)(Flags & Mask); 1953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick } 1962905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 1972905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { 1983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return (SCEV::NoWrapFlags)(Flags | OnFlags); 1993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick } 2002905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 2012905440bdd9627f202398137aab5ded38f681fc9Benjamin Kramer clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { 2023228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return (SCEV::NoWrapFlags)(Flags & ~OffFlags); 2033228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick } 2043228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick 205714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman private: 2061959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 2071959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// notified whenever a Value is deleted. 2081959b7562e57f8394496e761486f23b187ac3f1bDan Gohman class SCEVCallbackVH : public CallbackVH { 2091959b7562e57f8394496e761486f23b187ac3f1bDan Gohman ScalarEvolution *SE; 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void deleted() override; 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void allUsesReplacedWith(Value *New) override; 2121959b7562e57f8394496e761486f23b187ac3f1bDan Gohman public: 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); 2141959b7562e57f8394496e761486f23b187ac3f1bDan Gohman }; 2151959b7562e57f8394496e761486f23b187ac3f1bDan Gohman 21635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 217629bff692ae96dea517dc854e27b57ee6c8729efBenjamin Kramer friend class SCEVExpander; 218dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman friend class SCEVUnknown; 21935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 220f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 221f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 222f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 223f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 226f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 227f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The DataLayout information for the target we are targeting. 229f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL; 231f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 232618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier /// TLI - The target library information for the target we are targeting. 233618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier /// 234618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier TargetLibraryInfo *TLI; 235618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier 2361cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman /// DT - The dominator tree. 2371cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman /// 2381cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman DominatorTree *DT; 2391cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman 24086fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute - This SCEV is used to represent unknown trip 24186fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// counts and things. 2421c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman SCEVCouldNotCompute CouldNotCompute; 243f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 244e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// ValueExprMapType - The typedef for ValueExprMap. 245f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 246e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> > 247e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman ValueExprMapType; 248e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman 249e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// ValueExprMap - This is a cache of the values we have analyzed so far. 250e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// 251e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman ValueExprMapType ValueExprMap; 252f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 2538aa22019ca5ef29a15058be905d782e7225aa206Andrew Trick /// Mark predicate values currently being processed by isImpliedCond. 2548aa22019ca5ef29a15058be905d782e7225aa206Andrew Trick DenseSet<Value*> PendingLoopPredicates; 2558aa22019ca5ef29a15058be905d782e7225aa206Andrew Trick 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// ExitLimit - Information about the number of loop iterations for which a 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// loop exit's branch condition evaluates to the not-taken path. This is a 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// temporary pair of exact and max expressions that are eventually 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// summarized in ExitNotTakenInfo and BackedgeTakenInfo. 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// If MustExit is true, then the exit must be taken when the BECount 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// reaches Exact (and before surpassing Max). If MustExit is false, then 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// BECount may exceed Exact or Max if the loop exits via another branch. In 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// either case, the loop may exit early via another branch. 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// MustExit is true for most cases. However, an exit guarded by an 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// (in)equality on a nonunit stride may be skipped. 2685116ff671f45d48594d11360e22991a7edb13862Andrew Trick struct ExitLimit { 2695116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *Exact; 2705116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *Max; 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool MustExit; 2725116ff671f45d48594d11360e22991a7edb13862Andrew Trick 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /*implicit*/ ExitLimit(const SCEV *E) 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Exact(E), Max(E), MustExit(true) {} 2755116ff671f45d48594d11360e22991a7edb13862Andrew Trick 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExitLimit(const SCEV *E, const SCEV *M, bool MustExit) 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Exact(E), Max(M), MustExit(MustExit) {} 2785116ff671f45d48594d11360e22991a7edb13862Andrew Trick 2795116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// hasAnyInfo - Test whether this ExitLimit contains any computed 2805116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// information, or whether it's all SCEVCouldNotCompute values. 2815116ff671f45d48594d11360e22991a7edb13862Andrew Trick bool hasAnyInfo() const { 2825116ff671f45d48594d11360e22991a7edb13862Andrew Trick return !isa<SCEVCouldNotCompute>(Exact) || 2835116ff671f45d48594d11360e22991a7edb13862Andrew Trick !isa<SCEVCouldNotCompute>(Max); 2845116ff671f45d48594d11360e22991a7edb13862Andrew Trick } 2855116ff671f45d48594d11360e22991a7edb13862Andrew Trick }; 2865116ff671f45d48594d11360e22991a7edb13862Andrew Trick 2875116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ExitNotTakenInfo - Information about the number of times a particular 2885116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// loop exit may be reached before exiting the loop. 2895116ff671f45d48594d11360e22991a7edb13862Andrew Trick struct ExitNotTakenInfo { 2901009c3299be8c147ecd3fbd2d75ba1bafb2c84b1Andrew Trick AssertingVH<BasicBlock> ExitingBlock; 2915116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *ExactNotTaken; 2925116ff671f45d48594d11360e22991a7edb13862Andrew Trick PointerIntPair<ExitNotTakenInfo*, 1> NextExit; 2935116ff671f45d48594d11360e22991a7edb13862Andrew Trick 294dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {} 2955116ff671f45d48594d11360e22991a7edb13862Andrew Trick 2965116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// isCompleteList - Return true if all loop exits are computable. 2975116ff671f45d48594d11360e22991a7edb13862Andrew Trick bool isCompleteList() const { 2985116ff671f45d48594d11360e22991a7edb13862Andrew Trick return NextExit.getInt() == 0; 2995116ff671f45d48594d11360e22991a7edb13862Andrew Trick } 3005116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3015116ff671f45d48594d11360e22991a7edb13862Andrew Trick void setIncomplete() { NextExit.setInt(1); } 3025116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3035116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// getNextExit - Return a pointer to the next exit's not-taken info. 3045116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitNotTakenInfo *getNextExit() const { 3055116ff671f45d48594d11360e22991a7edb13862Andrew Trick return NextExit.getPointer(); 3065116ff671f45d48594d11360e22991a7edb13862Andrew Trick } 3075116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3085116ff671f45d48594d11360e22991a7edb13862Andrew Trick void setNextExit(ExitNotTakenInfo *ENT) { NextExit.setPointer(ENT); } 3095116ff671f45d48594d11360e22991a7edb13862Andrew Trick }; 3105116ff671f45d48594d11360e22991a7edb13862Andrew Trick 311a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 3123f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// of a loop. This currently includes an exact count and a maximum count. 313a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 3145116ff671f45d48594d11360e22991a7edb13862Andrew Trick class BackedgeTakenInfo { 3155116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ExitNotTaken - A list of computable exits and their not-taken counts. 3165116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// Loops almost never have more than one computable exit. 3175116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitNotTakenInfo ExitNotTaken; 318a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 3197b9547089f0363b803e55dcbde1d6b99710dfe69Andreas Bolka /// Max - An expression indicating the least maximum backedge-taken 320a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 3210bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Max; 322a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 3235116ff671f45d48594d11360e22991a7edb13862Andrew Trick public: 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BackedgeTakenInfo() : Max(nullptr) {} 325a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 3265116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// Initialize BackedgeTakenInfo from a list of exact exit counts. 3275116ff671f45d48594d11360e22991a7edb13862Andrew Trick BackedgeTakenInfo( 3285116ff671f45d48594d11360e22991a7edb13862Andrew Trick SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts, 3295116ff671f45d48594d11360e22991a7edb13862Andrew Trick bool Complete, const SCEV *MaxCount); 330a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 331a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 332a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 333a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 334a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 335fcb4356dee96563def584fe38eeafb3eb63c5cd8Andrew Trick return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max); 336a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 3375116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3385116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// getExact - Return an expression indicating the exact backedge-taken 3395116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// count of the loop if it is known, or SCEVCouldNotCompute 3405116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// otherwise. This is the number of times the loop header can be 3415116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// guaranteed to execute, minus one. 3425116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *getExact(ScalarEvolution *SE) const; 3435116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3445116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// getExact - Return the number of times this loop exit may fall through 345252ef7a61a9455c1e5d7b8a5a5f7ec8b3a75e200Andrew Trick /// to the back edge, or SCEVCouldNotCompute. The loop is guaranteed not 346252ef7a61a9455c1e5d7b8a5a5f7ec8b3a75e200Andrew Trick /// to exit via this block before this number of iterations, but may exit 347252ef7a61a9455c1e5d7b8a5a5f7ec8b3a75e200Andrew Trick /// via another block. 348fcb4356dee96563def584fe38eeafb3eb63c5cd8Andrew Trick const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; 3495116ff671f45d48594d11360e22991a7edb13862Andrew Trick 3505116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// getMax - Get the max backedge taken count for the loop. 3515116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *getMax(ScalarEvolution *SE) const; 3525116ff671f45d48594d11360e22991a7edb13862Andrew Trick 353e74c2e86cb405963ba9c4043a1d0ca00b8f85fbeAndrew Trick /// Return true if any backedge taken count expressions refer to the given 354e74c2e86cb405963ba9c4043a1d0ca00b8f85fbeAndrew Trick /// subexpression. 355e74c2e86cb405963ba9c4043a1d0ca00b8f85fbeAndrew Trick bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; 356e74c2e86cb405963ba9c4043a1d0ca00b8f85fbeAndrew Trick 3575116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// clear - Invalidate this result and free associated memory. 3585116ff671f45d48594d11360e22991a7edb13862Andrew Trick void clear(); 359a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 360a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 361f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 362f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 36377a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman DenseMap<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 364f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 365f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 366f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 367f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 368f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 369f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 37077a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman DenseMap<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 371f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 37242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// ValuesAtScopes - This map contains entries for all the expressions 37342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// that we attempt to compute getSCEVAtScope information for, which can 37442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// be expensive in extreme cases. 37577a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman DenseMap<const SCEV *, 3763cda2d38851d73eec38d38a46462aaa65de4ef8eWan Xiaofei SmallVector<std::pair<const Loop *, const SCEV *>, 2> > ValuesAtScopes; 3776bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 378714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// LoopDispositions - Memoized computeLoopDisposition results. 37977a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman DenseMap<const SCEV *, 3803cda2d38851d73eec38d38a46462aaa65de4ef8eWan Xiaofei SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions; 381714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 382714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// computeLoopDisposition - Compute a LoopDisposition value. 383714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); 384714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 3859c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// BlockDispositions - Memoized computeBlockDisposition results. 38677a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman DenseMap<const SCEV *, 3873cda2d38851d73eec38d38a46462aaa65de4ef8eWan Xiaofei SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions; 3889c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 3899c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// computeBlockDisposition - Compute a BlockDisposition value. 3909c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); 3919c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 3926678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman /// UnsignedRanges - Memoized results from getUnsignedRange 3936678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman DenseMap<const SCEV *, ConstantRange> UnsignedRanges; 3946678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman 3956678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman /// SignedRanges - Memoized results from getSignedRange 3966678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman DenseMap<const SCEV *, ConstantRange> SignedRanges; 3976678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman 3987c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. 3997c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &setUnsignedRange(const SCEV *S, 4007c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &CR) { 4017c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = 4027c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman UnsignedRanges.insert(std::make_pair(S, CR)); 4037c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman if (!Pair.second) 4047c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman Pair.first->second = CR; 4057c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman return Pair.first->second; 4067c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman } 4077c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman 4087c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman /// setUnsignedRange - Set the memoized signed range for the given SCEV. 4097c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &setSignedRange(const SCEV *S, 4107c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman const ConstantRange &CR) { 4117c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = 4127c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman SignedRanges.insert(std::make_pair(S, CR)); 4137c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman if (!Pair.second) 4147c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman Pair.first->second = CR; 4157c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman return Pair.first->second; 4167c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman } 4177c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman 418f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 419f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 4200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createSCEV(Value *V); 421f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 422f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 423f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 4240bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createNodeForPHI(PHINode *PN); 425f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 42626466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 42726466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 428d281ed2d03654b9cdb290a2d7c73dfe7b826e554Dan Gohman const SCEV *createNodeForGEP(GEPOperator *GEP); 42926466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 43042214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called 43142214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// at most once for each SCEV+Loop pair. 43242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman /// 43342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); 43442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman 435fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// ForgetSymbolicValue - This looks up computed SCEV values for all 436fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// instructions that depend on the given instruction and removes them from 437e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman /// the ValueExprMap map if they reference SymName. This is used during PHI 438fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman /// resolution. 439fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman void ForgetSymbolicName(Instruction *I, const SCEV *SymName); 440f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 441a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 442a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 443a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 444a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 445a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 446f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 447f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 448a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 449f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 4505116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ComputeExitLimit - Compute the number of times the backedge of the 4515116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// specified loop will execute if it exits via the specified block. 4525116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock); 4535116ff671f45d48594d11360e22991a7edb13862Andrew Trick 4545116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ComputeExitLimitFromCond - Compute the number of times the backedge of 4555116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// the specified loop will execute if its exit condition were a conditional 4565116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// branch of ExitCond, TBB, and FBB. 4575116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit ComputeExitLimitFromCond(const Loop *L, 4585116ff671f45d48594d11360e22991a7edb13862Andrew Trick Value *ExitCond, 4595116ff671f45d48594d11360e22991a7edb13862Andrew Trick BasicBlock *TBB, 460616011418e7460f765469f6347417fa25b5b740bAndrew Trick BasicBlock *FBB, 461616011418e7460f765469f6347417fa25b5b740bAndrew Trick bool IsSubExpr); 4625116ff671f45d48594d11360e22991a7edb13862Andrew Trick 4635116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ComputeExitLimitFromICmp - Compute the number of times the backedge of 4645116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// the specified loop will execute if its exit condition were a conditional 4655116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// branch of the ICmpInst ExitCond, TBB, and FBB. 4665116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit ComputeExitLimitFromICmp(const Loop *L, 4675116ff671f45d48594d11360e22991a7edb13862Andrew Trick ICmpInst *ExitCond, 4685116ff671f45d48594d11360e22991a7edb13862Andrew Trick BasicBlock *TBB, 469616011418e7460f765469f6347417fa25b5b740bAndrew Trick BasicBlock *FBB, 470616011418e7460f765469f6347417fa25b5b740bAndrew Trick bool IsSubExpr); 4715116ff671f45d48594d11360e22991a7edb13862Andrew Trick 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// backedge of the specified loop will execute if its exit condition were a 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// switch with a single exiting case to ExitingBB. 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExitLimit 47636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch, 47736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *ExitingBB, bool IsSubExpr); 47836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4795116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ComputeLoadConstantCompareExitLimit - Given an exit condition 4807e77f7959162a601291fd5400a88908d021033d3Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the 4817e77f7959162a601291fd5400a88908d021033d3Dan Gohman /// backedge-taken count. 4825116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit ComputeLoadConstantCompareExitLimit(LoadInst *LI, 4835116ff671f45d48594d11360e22991a7edb13862Andrew Trick Constant *RHS, 4845116ff671f45d48594d11360e22991a7edb13862Andrew Trick const Loop *L, 4855116ff671f45d48594d11360e22991a7edb13862Andrew Trick ICmpInst::Predicate p); 4865116ff671f45d48594d11360e22991a7edb13862Andrew Trick 4875116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// ComputeExitCountExhaustively - If the loop is known to execute a 4885116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// constant number of times (the condition evolves only from constants), 489f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 490f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 4915116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// evaluate the exit count of the loop, return CouldNotCompute. 4925116ff671f45d48594d11360e22991a7edb13862Andrew Trick const SCEV *ComputeExitCountExhaustively(const Loop *L, 4935116ff671f45d48594d11360e22991a7edb13862Andrew Trick Value *Cond, 4945116ff671f45d48594d11360e22991a7edb13862Andrew Trick bool ExitWhen); 495f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 4965116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// HowFarToZero - Return the number of times an exit condition comparing 4975116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// the specified value to zero will execute. If not computable, return 49886fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 499616011418e7460f765469f6347417fa25b5b740bAndrew Trick ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); 500f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 5015116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// HowFarToNonZero - Return the number of times an exit condition checking 5025116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// the specified value for nonzero will execute. If not computable, return 50386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 5045116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L); 505f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 5065116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// HowManyLessThans - Return the number of times an exit condition 5075116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// containing the specified less-than comparison will execute. If not 5085116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// computable, return CouldNotCompute. isSigned specifies whether the 5095116ff671f45d48594d11360e22991a7edb13862Andrew Trick /// less-than is signed. 5105116ff671f45d48594d11360e22991a7edb13862Andrew Trick ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 511616011418e7460f765469f6347417fa25b5b740bAndrew Trick const Loop *L, bool isSigned, bool IsSubExpr); 51210bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS, 51310bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick const Loop *L, bool isSigned, bool IsSubExpr); 514f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 515f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 516f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 517f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 518f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 519005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman std::pair<BasicBlock *, BasicBlock *> 520005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 521f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 522af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman /// isImpliedCond - Test whether the condition described by Pred, LHS, and 523af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman /// RHS is true whenever the given FoundCondValue value evaluates to true. 524af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman bool isImpliedCond(ICmpInst::Predicate Pred, 5250f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 526af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman Value *FoundCondValue, 5270f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool Inverse); 5280f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman 5290f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// isImpliedCondOperands - Test whether the condition described by Pred, 5303f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, 5310f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// and FoundRHS is true. 5320f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool isImpliedCondOperands(ICmpInst::Predicate Pred, 5330f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 5340f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *FoundLHS, const SCEV *FoundRHS); 5350f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman 5360f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// isImpliedCondOperandsHelper - Test whether the condition described by 5373f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// Pred, LHS, and RHS is true whenever the condition described by Pred, 5380f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman /// FoundLHS, and FoundRHS is true. 5390f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, 5400f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman const SCEV *LHS, const SCEV *RHS, 541b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick const SCEV *FoundLHS, 542b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick const SCEV *FoundRHS); 54385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 544f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 545f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 546f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 547f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 548f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 549f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 550f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 55153c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// isKnownPredicateWithRanges - Test if the given expression is known to 55253c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// satisfy the condition described by Pred and the known constant ranges 55353c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// of LHS and RHS. 55453c66eacc417c0113fba7159487b90005dc8f91eDan Gohman /// 55553c66eacc417c0113fba7159487b90005dc8f91eDan Gohman bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, 55653c66eacc417c0113fba7159487b90005dc8f91eDan Gohman const SCEV *LHS, const SCEV *RHS); 55753c66eacc417c0113fba7159487b90005dc8f91eDan Gohman 55856a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman /// forgetMemoizedResults - Drop memoized information computed for S. 55956a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman void forgetMemoizedResults(const SCEV *S); 56056a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman 561a10369920fa86d8961495b71dbc00f5596d122d9Shuxin Yang /// Return false iff given SCEV contains a SCEVUnknown with NULL value- 5625e915e6e364532ed00b4c5508e59b42f608b5244Shuxin Yang /// pointer. 5635e915e6e364532ed00b4c5508e59b42f608b5244Shuxin Yang bool checkValidity(const SCEV *S) const; 5645e915e6e364532ed00b4c5508e59b42f608b5244Shuxin Yang 56553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 566ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 567f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 5689769ab22265b313171d201b5928688524a01bd87Misha Brukman 569e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &getContext() const { return F->getContext(); } 570508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson 571af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 572af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 573af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 574af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 575db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool isSCEVable(Type *Ty) const; 576af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 577af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 578af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 579db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner uint64_t getTypeSizeInBits(Type *Ty) const; 580af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 581af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 582af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 583af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 584af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 585db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getEffectiveSCEVType(Type *Ty) const; 5862d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 587e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman /// getSCEV - Return a SCEV expression for the full generality of the 58853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 5890bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEV(Value *V); 5900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman 5910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(ConstantInt *V); 5920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(const APInt& Val); 593db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); 594db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); 595db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty); 596db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty); 597db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); 5983645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, 5993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 6003645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, 6013228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 6020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 603246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 604246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 6053228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return getAddExpr(Ops, Flags); 606246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 6073228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 6083228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 6090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 3> Ops; 610246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 611246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 612246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 6133228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return getAddExpr(Ops, Flags); 614246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 6153645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 6163228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 6173645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, 6183228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) 6193228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick { 6200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 621246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 622246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 6233228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return getMulExpr(Ops, Flags); 624246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 625e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 626e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 627e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky SmallVector<const SCEV *, 3> Ops; 628e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky Ops.push_back(Op0); 629e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky Ops.push_back(Op1); 630e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky Ops.push_back(Op2); 631e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky return getMulExpr(Ops, Flags); 632e97728ecf8a0ee69562cc0e7880cfaa65200c624Nick Lewycky } 6330bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 63436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); 6350bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 6363228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick const Loop *L, SCEV::NoWrapFlags Flags); 6370bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 6383228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick const Loop *L, SCEV::NoWrapFlags Flags); 6390bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 6403228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick const Loop *L, SCEV::NoWrapFlags Flags) { 6410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 6423228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return getAddRecExpr(NewOp, L, Flags); 643246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 6440bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 6450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 6460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 6470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 6480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 6490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 6500bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUnknown(Value *V); 6510bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getCouldNotCompute(); 652246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 65314807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault /// getSizeOfExpr - Return an expression for sizeof AllocTy that is type 65414807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault /// IntTy 6554f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 65614807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); 6574f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 65814807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault /// getOffsetOfExpr - Return an expression for offsetof on the given field 65914807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault /// with type IntTy 6604f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman /// 66114807bd8c801f976c999e5a6699f31ee9642021aMatt Arsenault const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); 6624f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman 663246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 664246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 6650bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNegativeSCEV(const SCEV *V); 666246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 6673e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 6683e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 6690bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNotSCEV(const SCEV *V); 6703e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 6713228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. 672992efb03785f2a368fbb63b09373be1d6a96ce5aChris Lattner const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, 6733228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 674246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 6756f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 6766f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 6776f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 678db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); 6796f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 680f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 681f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 682f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 683db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); 684f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 685467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 686467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 687467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 688db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); 689467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 690467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 691467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 692467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 693db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); 694467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 6952ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 6962ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// the input value to the specified type. If the type must be extended, 6972ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// it is extended with unspecified bits. The conversion must not be 6982ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// narrowing. 699db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); 7002ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman 701467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 702467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 703467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 704db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); 705467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 706a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 707a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// the types using zero-extension, and then perform a umax operation 708a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// with them. 7090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 710a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman const SCEV *RHS); 711a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 712c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// getUMinFromMismatchedTypes - Promote the operands to the wider of 713c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// the types using zero-extension, and then perform a umin operation 714c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// with them. 7150bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 7160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS); 717c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman 718b12a754cce0c1d5542af605203a47820edba454dAndrew Trick /// getPointerBase - Transitively follow the chain of pointer-type operands 719b12a754cce0c1d5542af605203a47820edba454dAndrew Trick /// until reaching a SCEV that does not have a single pointer operand. This 720b12a754cce0c1d5542af605203a47820edba454dAndrew Trick /// returns a SCEVUnknown pointer for well-formed pointer-type expressions, 721b12a754cce0c1d5542af605203a47820edba454dAndrew Trick /// but corner cases do exist. 722b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *getPointerBase(const SCEV *V); 723b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 724e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman /// getSCEVAtScope - Return a SCEV expression for the specified value 72553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 72653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 72753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 72853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 72953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 73053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 73153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 732d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// In the case that a relevant loop exit value cannot be computed, the 733d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// original value V is returned. 7340bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 73566a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 73666a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 73766a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 7380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(Value *V, const Loop *L); 73953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7403948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected 7413948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman /// by a conditional between LHS and RHS. This is used to help avoid max 74285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// expressions in loop trip counts, and to eliminate casts. 7433948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 7443948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman const SCEV *LHS, const SCEV *RHS); 745c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 74685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 74785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// protected by a conditional between LHS and RHS. This is used to 74885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// to eliminate casts. 74985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 75085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 75185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 752b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick /// getSmallConstantTripCount - Returns the maximum trip count of this loop 7533eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// as a normal unsigned value. Returns 0 if the trip count is unknown or 7543eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// not constant. This "trip count" assumes that control exits via 7553eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// ExitingBlock. More precisely, it is the number of times that control may 7563eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// reach ExitingBlock before taking the branch. For loops with multiple 7573eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// exits, it may not be the number times that the loop header executes if 7583eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// the loop exits prematurely via another branch. 7593eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); 760b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick 761b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick /// getSmallConstantTripMultiple - Returns the largest constant divisor of 762b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick /// the trip count of this loop as a normal unsigned value, if 763b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick /// possible. This means that the actual trip count is always a multiple of 764b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick /// the returned value (don't forget the trip count could very well be zero 7653eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// as well!). As explained in the comments for getSmallConstantTripCount, 7663eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick /// this assumes that control exits the loop via ExitingBlock. 7673eada319fc21bca31a2bc7819e4c05f46e6f82e1Andrew Trick unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock); 768b1831c66403315a1d84593b7c198ddbd43a574cfAndrew Trick 7695116ff671f45d48594d11360e22991a7edb13862Andrew Trick // getExitCount - Get the expression for the number of loop iterations for 770fcb4356dee96563def584fe38eeafb3eb63c5cd8Andrew Trick // which this loop is guaranteed not to exit via ExitingBlock. Otherwise 771fcb4356dee96563def584fe38eeafb3eb63c5cd8Andrew Trick // return SCEVCouldNotCompute. 772fcb4356dee96563def584fe38eeafb3eb63c5cd8Andrew Trick const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock); 7735116ff671f45d48594d11360e22991a7edb13862Andrew Trick 77446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 77546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 77646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 77746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 77846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 77946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 78046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 78146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 78246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 78346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 78446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 7850bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getBackedgeTakenCount(const Loop *L); 78653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 787a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 788a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 789a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 7900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMaxBackedgeTakenCount(const Loop *L); 791a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 79246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 79346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 794f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 79553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7964c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// forgetLoop - This method should be called by the client when it has 7974c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// changed a loop in a way that may effect ScalarEvolution's ability to 7984c7279ac726e338400626fca5a09b5533426eb6aDan Gohman /// compute a trip count, or if the loop is deleted. 7994c7279ac726e338400626fca5a09b5533426eb6aDan Gohman void forgetLoop(const Loop *L); 80060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 80145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// forgetValue - This method should be called by the client when it has 80245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// changed a value in a way that may effect its value, or which may 80345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen /// disconnect it from a def-use chain linking it to a loop. 80445a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen void forgetValue(Value *V); 80545a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 80636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Called when the client has changed the disposition of values in 80736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// this loop. 80836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 80936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// We don't have a way to invalidate per-loop dispositions. Clear and 81036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// recompute is simpler. 81136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } 81236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 813650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// GetMinTrailingZeros - Determine the minimum number of zero bits that S 814650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// is guaranteed to end in (at every loop iteration). It is, at the same 815650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// time, the minimum number of times S is divisible by 2. For example, 816650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the 817650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// bitwidth of S. 8180bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman uint32_t GetMinTrailingZeros(const SCEV *S); 8192c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 82085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 82185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 82285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getUnsignedRange(const SCEV *S); 82385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 82485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getSignedRange - Determine the signed range for a particular SCEV. 82585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 82685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getSignedRange(const SCEV *S); 82785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 82885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNegative - Test if the given expression is known to be negative. 82985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 83085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNegative(const SCEV *S); 83185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 83285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownPositive - Test if the given expression is known to be positive. 83385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 83485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPositive(const SCEV *S); 83585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 83685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonNegative - Test if the given expression is known to be 83785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-negative. 83885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 83985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonNegative(const SCEV *S); 84085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 84185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonPositive - Test if the given expression is known to be 84285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-positive. 84385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 84485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonPositive(const SCEV *S); 84585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 84685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonZero - Test if the given expression is known to be 84785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-zero. 84885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 84985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonZero(const SCEV *S); 8502c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 851e48172710bf78ae210b2257d6ac3e0e8fb3ba792Dan Gohman /// isKnownPredicate - Test if the given expression is known to satisfy 85285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// the condition described by Pred, LHS, and RHS. 85385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 85485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPredicate(ICmpInst::Predicate Pred, 85585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 8562c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 857e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with 85894c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru /// predicate Pred. Return true iff any changes were made. If the 859f84606732c76899af54c295ec987c96c88452747Jakub Staszak /// operands are provably equal or unequal, LHS and RHS are set to 8605cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. 861e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman /// 862e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, 863e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman const SCEV *&LHS, 8646cf07a80ff5ee8ef7dc336f954aae17c7e8d83d4Benjamin Kramer const SCEV *&RHS, 8656cf07a80ff5ee8ef7dc336f954aae17c7e8d83d4Benjamin Kramer unsigned Depth = 0); 866e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman 867714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// getLoopDisposition - Return the "disposition" of the given SCEV with 868714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman /// respect to the given loop. 869714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); 870714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman 87117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// isLoopInvariant - Return true if the value of the given SCEV is 87217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// unchanging in the specified loop. 87317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman bool isLoopInvariant(const SCEV *S, const Loop *L); 87417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman 87517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// hasComputableLoopEvolution - Return true if the given SCEV changes value 87617ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// in a known way in the specified loop. This property being true implies 87717ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// that the value is variant in the loop AND that we can emit an expression 87817ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman /// to compute the value of the expression at any particular loop iteration. 87917ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); 88017ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman 8819c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// getLoopDisposition - Return the "disposition" of the given SCEV with 8829c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman /// respect to the given block. 8839c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); 8849c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman 885dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// dominates - Return true if elements that makes up the given SCEV 886dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// dominate the specified basic block. 8879c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman bool dominates(const SCEV *S, const BasicBlock *BB); 888dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman 889dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// properlyDominates - Return true if elements that makes up the given SCEV 890dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman /// properly dominate the specified basic block. 8919c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman bool properlyDominates(const SCEV *S, const BasicBlock *BB); 892dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman 8934ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman /// hasOperand - Test whether the given SCEV has Op as a direct or 8944ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman /// indirect operand. 8954ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman bool hasOperand(const SCEV *S, const SCEV *Op) const; 8964ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman 897dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Return the size of an element read or written by Inst. 898dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const SCEV *getElementSize(Instruction *Inst); 899dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 900dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Compute the array dimensions Sizes from the set of Terms extracted from 901dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// the memory access function of this SCEVAddRecExpr. 902dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, 903dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVectorImpl<const SCEV *> &Sizes, 904dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const SCEV *ElementSize) const; 905dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 90636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 90736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override; 90836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 909dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &OS, const Module* = nullptr) const override; 91036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void verifyAnalysis() const override; 9111c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 91208367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson private: 91310bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// Compute the backedge taken count knowing the interval difference, the 91410bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// stride and presence of the equality in the comparison. 91510bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, 91610bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick bool Equality); 91710bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick 91836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Verify if an linear IV with positive stride can overflow when in a 91910bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// less-than comparison, knowing the invariant term of the comparison, 92010bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// the stride and the knowledge of NSW/NUW flags on the recurrence. 92110bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, 92210bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick bool IsSigned, bool NoWrap); 92310bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick 92436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Verify if an linear IV with negative stride can overflow when in a 92510bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// greater-than comparison, knowing the invariant term of the comparison, 92610bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick /// the stride and the knowledge of NSW/NUW flags on the recurrence. 92710bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, 92810bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick bool IsSigned, bool NoWrap); 92910bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick 93010bb82e54fc0608e6220581bda0405af8f12d32fAndrew Trick private: 9311c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman FoldingSet<SCEV> UniqueSCEVs; 9321c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman BumpPtrAllocator SCEVAllocator; 933ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 934ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// FirstUnknown - The head of a linked list of all SCEVUnknown 935ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// values that have been allocated. This is used by releaseMemory 936ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// to locate them all and call their destructors. 937ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown *FirstUnknown; 93853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 93953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 94053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 94153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 942