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    ///
822