ScalarEvolution.h revision db125cfaf57cc83e7dd7453de2d509bc8efd0e5e
153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
29769ab22265b313171d201b5928688524a01bd87Misha Brukman//
353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//                     The LLVM Compiler Infrastructure
453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source
67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details.
79769ab22265b313171d201b5928688524a01bd87Misha Brukman//
853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===//
953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
1053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// The ScalarEvolution class is an LLVM pass which can be used to analyze and
113f46a3abeedba8d517b4182de34c821d752db058Dan Gohman// categorize scalar expressions in loops.  It specializes in recognizing
1253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// general induction variables, representing them with the abstract and opaque
1353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// SCEV class.  Given this analysis, trip counts of loops and other important
1453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// properties can be obtained.
1553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
1653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// This analysis is primarily useful for induction variable substitution and
1753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// strength reduction.
189769ab22265b313171d201b5928688524a01bd87Misha Brukman//
1953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===//
2053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
2153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
2253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#define LLVM_ANALYSIS_SCALAREVOLUTION_H
2353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
2453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#include "llvm/Pass.h"
2503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include "llvm/Instructions.h"
26ffef8acc3e3398bdd04e947c7949befdd52faf86Dan Gohman#include "llvm/Function.h"
27562b84b3aea359d1f918184e355da82bf05eb290Jay Foad#include "llvm/Operator.h"
281f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h"
2935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h"
301c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/Support/Allocator.h"
3185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman#include "llvm/Support/ConstantRange.h"
321c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/ADT/FoldingSet.h"
33444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.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;
43f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman  class TargetData;
4412ddd409535b52a7fa5157ded9a4cedd161fedb6Benjamin Kramer  class LLVMContext;
4503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class Loop;
4603ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class LoopInfo;
47fc8deb971d2b4dff370ba93948975e33a038605dDan Gohman  class Operator;
48dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman  class SCEVUnknown;
49aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  class SCEV;
50081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman  template<> struct FoldingSetTrait<SCEV>;
5153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
526c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman  /// SCEV - This class represents an analyzed expression in the program.  These
53650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman  /// are opaque objects that the client is not allowed to do much with
54650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman  /// directly.
5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  ///
56c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman  class SCEV : public FoldingSetNode {
57081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman    friend struct FoldingSetTrait<SCEV>;
58aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman
59c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    /// FastID - A reference to an Interned FoldingSetNodeID for this node.
60c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    /// The ScalarEvolution's BumpPtrAllocator holds the data.
61c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    FoldingSetNodeIDRef FastID;
62c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman
632f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    // The SCEV baseclass this node corresponds to
642f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    const unsigned short SCEVType;
6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
662f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman  protected:
672f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    /// SubclassData - This field is initialized to zero and may be used in
683f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// subclasses to store miscellaneous information.
692f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    unsigned short SubclassData;
702f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman
712f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman  private:
7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    SCEV(const SCEV &);            // DO NOT IMPLEMENT
7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    void operator=(const SCEV &);  // DO NOT IMPLEMENT
744ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman
7553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  public:
763228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// NoWrapFlags are bitfield indices into SubclassData.
773228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
783228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
793228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// no-signed-wrap <NSW> properties, which are derived from the IR
803228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// operator. NSW is a misnomer that we use to mean no signed overflow or
813228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// underflow.
823228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
833228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// AddRec expression may have a no-self-wraparound <NW> property if the
843228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// result can never reach the start value. This property is independent of
853228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// the actual start value and step direction. Self-wraparound is defined
863228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// purely in terms of the recurrence's loop, step size, and
873228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// bitwidth. Formally, a recurrence with no self-wraparound satisfies:
883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth).
893228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Note that NUW and NSW are also valid properties of a recurrence, and
913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// either implies NW. For convenience, NW will be set for a recurrence
923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// whenever either NUW or NSW are set.
933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    enum NoWrapFlags { FlagAnyWrap = 0,          // No guarantee.
943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNW      = (1 << 0),   // No self-wrap.
953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNUW     = (1 << 1),   // No unsigned wrap.
963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNSW     = (1 << 2),   // No signed wrap.
973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       NoWrapMask  = (1 << 3) -1 };
983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
993bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
1003bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}
1011c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman
10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    unsigned getSCEVType() const { return SCEVType; }
10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// getType - Return the LLVM type of this SCEV expression.
10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
106db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const;
10753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
108cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    /// isZero - Return true if the expression is a constant zero.
109cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    ///
110cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    bool isZero() const;
111cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman
11270a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    /// isOne - Return true if the expression is a constant one.
11370a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    ///
11470a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    bool isOne() const;
11570a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman
1164d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    /// isAllOnesValue - Return true if the expression is a constant
1174d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    /// all-ones value.
1184d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    ///
1194d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    bool isAllOnesValue() const;
1204d289bf4af88759be173a1a809bf8c092d729764Dan Gohman
12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// print - Print out the internal representation of this scalar to the
12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified stream.  This should really only be used for debugging
12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// purposes.
1244ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    void print(raw_ostream &OS) const;
12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// dump - This method is used for debugging.
12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    void dump() const;
12953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
1309769ab22265b313171d201b5928688524a01bd87Misha Brukman
131aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
132aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  // temporary FoldingSetNodeID values.
133aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
134aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static void Profile(const SCEV &X, FoldingSetNodeID& ID) {
135aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      ID = X.FastID;
136aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
137aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
138aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman                       FoldingSetNodeID &TempID) {
139aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      return ID == X.FastID;
140aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
141aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
142aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      return X.FastID.ComputeHash();
143aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
144aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  };
145aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman
146b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
147b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman    S.print(OS);
148b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman    return OS;
149b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman  }
150b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman
15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// SCEVCouldNotCompute - An object of this class is returned by queries that
15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// could not be answered.  For example, if you ask for the number of
15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// iterations of a linked-list traversal loop, you will get one of these.
15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// None of the standard SCEV operations are valid on this class, it is just a
15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// marker.
15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  struct SCEVCouldNotCompute : public SCEV {
157753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson    SCEVCouldNotCompute();
15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
16053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    static bool classof(const SCEV *S);
16253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
16553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// client code (intentionally) can't do much with the SCEV objects directly,
16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// they must ask this class for services.
16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  ///
16853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  class ScalarEvolution : public FunctionPass {
169714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman  public:
170714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// LoopDisposition - An enum describing the relationship between a
171714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// SCEV and a loop.
172714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    enum LoopDisposition {
173714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopVariant,    ///< The SCEV is loop-variant (unknown).
174714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopInvariant,  ///< The SCEV is loop-invariant.
175714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopComputable  ///< The SCEV varies predictably with the loop.
176714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    };
177714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
1789c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// BlockDisposition - An enum describing the relationship between a
1799c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// SCEV and a basic block.
1809c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    enum BlockDisposition {
1819c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      DoesNotDominateBlock,  ///< The SCEV does not dominate the block.
1829c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      DominatesBlock,        ///< The SCEV dominates the block.
1839c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      ProperlyDominatesBlock ///< The SCEV properly dominates the block.
1849c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    };
1859c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
1863228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Convenient NoWrapFlags manipulation that hides enum casts and is
1873228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// visible in the ScalarEvolution name space.
1883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) {
1893228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags & Mask);
1903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
1923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                                      SCEV::NoWrapFlags OnFlags) {
1933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags | OnFlags);
1943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags,
1963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                                        SCEV::NoWrapFlags OffFlags) {
1973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
1983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
200714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman  private:
2011959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
2021959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    /// notified whenever a Value is deleted.
2031959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    class SCEVCallbackVH : public CallbackVH {
2041959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      ScalarEvolution *SE;
2051959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      virtual void deleted();
2061959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      virtual void allUsesReplacedWith(Value *New);
2071959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    public:
2081959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
2091959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    };
2101959b7562e57f8394496e761486f23b187ac3f1bDan Gohman
21135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman    friend class SCEVCallbackVH;
212629bff692ae96dea517dc854e27b57ee6c8729efBenjamin Kramer    friend class SCEVExpander;
213dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman    friend class SCEVUnknown;
21435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman
215f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// F - The function we are analyzing.
216f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
217f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    Function *F;
218f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
219f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// LI - The loop information for the function we are currently analyzing.
220f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
221f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    LoopInfo *LI;
222f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
2233f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// TD - The target data information for the target we are targeting.
224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    TargetData *TD;
226f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
2271cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    /// DT - The dominator tree.
2281cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    ///
2291cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    DominatorTree *DT;
2301cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman
23186fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute - This SCEV is used to represent unknown trip
23286fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// counts and things.
2331c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    SCEVCouldNotCompute CouldNotCompute;
234f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
235e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// ValueExprMapType - The typedef for ValueExprMap.
236f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
237e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
238e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman      ValueExprMapType;
239e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman
240e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// ValueExprMap - This is a cache of the values we have analyzed so far.
241e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    ///
242e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    ValueExprMapType ValueExprMap;
243f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
244a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// BackedgeTakenInfo - Information about the backedge-taken count
2453f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// of a loop. This currently includes an exact count and a maximum count.
246a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    ///
247a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    struct BackedgeTakenInfo {
248a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// Exact - An expression indicating the exact backedge-taken count of
249a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
2500bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      const SCEV *Exact;
251a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2527b9547089f0363b803e55dcbde1d6b99710dfe69Andreas Bolka      /// Max - An expression indicating the least maximum backedge-taken
253a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// count of the loop that is known, or a SCEVCouldNotCompute.
2540bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      const SCEV *Max;
255a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2560bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
257a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        Exact(exact), Max(exact) {}
258a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      BackedgeTakenInfo(const SCEV *exact, const SCEV *max) :
260a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        Exact(exact), Max(max) {}
261a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
262a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
263a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// computed information, or whether it's all SCEVCouldNotCompute
264a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// values.
265a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      bool hasAnyInfo() const {
266a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        return !isa<SCEVCouldNotCompute>(Exact) ||
267a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman               !isa<SCEVCouldNotCompute>(Max);
268a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      }
269a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    };
270a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
271f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
272f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// this function as they are computed.
27377a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman    DenseMap<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
274f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
275f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ConstantEvolutionLoopExitValue - This map contains entries for all of
276f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// the PHI instructions that we attempt to compute constant evolutions for.
277f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// This allows us to avoid potentially expensive recomputation of these
278f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// properties.  An instruction maps to null if we are unable to compute its
279f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// exit value.
28077a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman    DenseMap<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
281f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
28242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// ValuesAtScopes - This map contains entries for all the expressions
28342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// that we attempt to compute getSCEVAtScope information for, which can
28442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// be expensive in extreme cases.
28577a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman    DenseMap<const SCEV *,
28642214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman             std::map<const Loop *, const SCEV *> > ValuesAtScopes;
2876bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman
288714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// LoopDispositions - Memoized computeLoopDisposition results.
28977a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman    DenseMap<const SCEV *,
290714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman             std::map<const Loop *, LoopDisposition> > LoopDispositions;
291714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
292714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// computeLoopDisposition - Compute a LoopDisposition value.
293714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
294714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
2959c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// BlockDispositions - Memoized computeBlockDisposition results.
29677a2c4c1e54b7e3c4815b276eb6a2d99a7621460Dan Gohman    DenseMap<const SCEV *,
2979c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman             std::map<const BasicBlock *, BlockDisposition> > BlockDispositions;
2989c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
2999c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// computeBlockDisposition - Compute a BlockDisposition value.
3009c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
3019c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
3026678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    /// UnsignedRanges - Memoized results from getUnsignedRange
3036678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
3046678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman
3056678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    /// SignedRanges - Memoized results from getSignedRange
3066678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    DenseMap<const SCEV *, ConstantRange> SignedRanges;
3076678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman
3087c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    /// setUnsignedRange - Set the memoized unsigned range for the given SCEV.
3097c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    const ConstantRange &setUnsignedRange(const SCEV *S,
3107c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman                                          const ConstantRange &CR) {
3117c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
3127c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        UnsignedRanges.insert(std::make_pair(S, CR));
3137c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      if (!Pair.second)
3147c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        Pair.first->second = CR;
3157c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      return Pair.first->second;
3167c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    }
3177c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman
3187c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    /// setUnsignedRange - Set the memoized signed range for the given SCEV.
3197c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    const ConstantRange &setSignedRange(const SCEV *S,
3207c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman                                        const ConstantRange &CR) {
3217c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
3227c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        SignedRanges.insert(std::make_pair(S, CR));
3237c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      if (!Pair.second)
3247c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        Pair.first->second = CR;
3257c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      return Pair.first->second;
3267c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    }
3277c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman
328f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// createSCEV - We know that there is no SCEV for the specified value.
329f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// Analyze the expression.
3300bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *createSCEV(Value *V);
331f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
332f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// createNodeForPHI - Provide the special handling we need to analyze PHI
333f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// SCEVs.
3340bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *createNodeForPHI(PHINode *PN);
335f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
33626466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman    /// createNodeForGEP - Provide the special handling we need to analyze GEP
33726466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman    /// SCEVs.
338d281ed2d03654b9cdb290a2d7c73dfe7b826e554Dan Gohman    const SCEV *createNodeForGEP(GEPOperator *GEP);
33926466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman
34042214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called
34142214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// at most once for each SCEV+Loop pair.
34242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    ///
34342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
34442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman
345fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// ForgetSymbolicValue - This looks up computed SCEV values for all
346fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// instructions that depend on the given instruction and removes them from
347e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// the ValueExprMap map if they reference SymName. This is used during PHI
348fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// resolution.
349fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
350f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
35151f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// getBECount - Subtract the end and start values and divide by the step,
35251f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// rounding up, to get the number of times the backedge is executed. Return
35351f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// CouldNotCompute if an intermediate computation overflows.
3540bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getBECount(const SCEV *Start,
355a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman                           const SCEV *End,
3561f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman                           const SCEV *Step,
3571f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman                           bool NoWrap);
35851f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman
359a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
360a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// loop, lazily computing new values if the loop hasn't been analyzed
361a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// yet.
362a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
363a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
364f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ComputeBackedgeTakenCount - Compute the number of times the specified
365f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// loop will iterate.
366a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
367f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
368a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
369a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// backedge of the specified loop will execute if it exits via the
370a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// specified block.
371a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
372a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                      BasicBlock *ExitingBlock);
373a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
374a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
375a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// backedge of the specified loop will execute if its exit condition
376a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// were a conditional branch of ExitCond, TBB, and FBB.
377a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo
378a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
379a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            Value *ExitCond,
380a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            BasicBlock *TBB,
381a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            BasicBlock *FBB);
382a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
383a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
384a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// times the backedge of the specified loop will execute if its exit
385a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
386a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// and FBB.
387a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo
388a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
389a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                ICmpInst *ExitCond,
390a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                BasicBlock *TBB,
391a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                BasicBlock *FBB);
392a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
393f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
3947e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// of 'icmp op load X, cst', try to see if we can compute the
3957e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// backedge-taken count.
396f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo
397f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
398f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   Constant *RHS,
399f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   const Loop *L,
400f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   ICmpInst::Predicate p);
401f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
40207ad19b509530b43e6a9acc5c1285cb560dd7198Dan Gohman    /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute
403f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// a constant number of times (the condition evolves only from constants),
404f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// try to evaluate a few iterations of the loop until we get the exit
405f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// condition gets a value of ExitWhen (true or false).  If we cannot
4067e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// evaluate the backedge-taken count of the loop, return CouldNotCompute.
4070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
408650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman                                                      Value *Cond,
409650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman                                                      bool ExitWhen);
410f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
411f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowFarToZero - Return the number of times a backedge comparing the
412f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified value to zero will execute.  If not computable, return
41386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute.
414f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L);
415f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
416f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowFarToNonZero - Return the number of times a backedge checking the
417f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified value for nonzero will execute.  If not computable, return
41886fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute.
419f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L);
420f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
421f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowManyLessThans - Return the number of times a backedge containing the
422f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified less-than comparison will execute.  If not computable, return
42386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute. isSigned specifies whether the less-than is signed.
42435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
42535738ac150afafe2359268d4b2169498c6c98c5fDan Gohman                                       const Loop *L, bool isSigned);
426f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
427f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
428f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// (which may not be an immediate predecessor) which has exactly one
429f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// successor from which BB is reachable, or null if no such block is
430f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// found.
431005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman    std::pair<BasicBlock *, BasicBlock *>
432005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman    getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
433f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
434af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    /// isImpliedCond - Test whether the condition described by Pred, LHS, and
435af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    /// RHS is true whenever the given FoundCondValue value evaluates to true.
436af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    bool isImpliedCond(ICmpInst::Predicate Pred,
4370f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                       const SCEV *LHS, const SCEV *RHS,
438af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman                       Value *FoundCondValue,
4390f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                       bool Inverse);
4400f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman
4410f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// isImpliedCondOperands - Test whether the condition described by Pred,
4423f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
4430f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// and FoundRHS is true.
4440f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    bool isImpliedCondOperands(ICmpInst::Predicate Pred,
4450f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                               const SCEV *LHS, const SCEV *RHS,
4460f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                               const SCEV *FoundLHS, const SCEV *FoundRHS);
4470f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman
4480f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// isImpliedCondOperandsHelper - Test whether the condition described by
4493f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// Pred, LHS, and RHS is true whenever the condition described by Pred,
4500f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// FoundLHS, and FoundRHS is true.
4510f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
4520f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                                     const SCEV *LHS, const SCEV *RHS,
4530f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                                     const SCEV *FoundLHS, const SCEV *FoundRHS);
45485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
455f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
456f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// in the header of its containing loop, we know the loop executes a
457f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// constant number of times, and the PHI node is just a recurrence
458f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// involving constants, fold it.
459f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
460f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                const Loop *L);
461f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
46253c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// isKnownPredicateWithRanges - Test if the given expression is known to
46353c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// satisfy the condition described by Pred and the known constant ranges
46453c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// of LHS and RHS.
46553c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    ///
46653c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
46753c66eacc417c0113fba7159487b90005dc8f91eDan Gohman                                    const SCEV *LHS, const SCEV *RHS);
46853c66eacc417c0113fba7159487b90005dc8f91eDan Gohman
46956a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman    /// forgetMemoizedResults - Drop memoized information computed for S.
47056a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman    void forgetMemoizedResults(const SCEV *S);
47156a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman
47253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  public:
473ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky    static char ID; // Pass identification, replacement for typeid
474f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ScalarEvolution();
4759769ab22265b313171d201b5928688524a01bd87Misha Brukman
476e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson    LLVMContext &getContext() const { return F->getContext(); }
477508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson
478af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// isSCEVable - Test if values of the given type are analyzable within
479af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// the SCEV framework. This primarily includes integer types, and it
480af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// can optionally include pointer types if the ScalarEvolution class
481af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// has access to target-specific information.
482db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    bool isSCEVable(Type *Ty) const;
483af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman
484af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// getTypeSizeInBits - Return the size in bits of the specified type,
485af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// for which isSCEVable must return true.
486db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    uint64_t getTypeSizeInBits(Type *Ty) const;
487af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman
488af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// getEffectiveSCEVType - Return a type with the same bitwidth as
489af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// the given type and which represents how SCEV will treat the given
490af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// type, for which isSCEVable must return true. For pointer types,
491af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// this is the pointer-sized integer type.
492db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getEffectiveSCEVType(Type *Ty) const;
4932d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman
494e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman    /// getSCEV - Return a SCEV expression for the full generality of the
49553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified expression.
4960bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEV(Value *V);
4970bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman
4980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getConstant(ConstantInt *V);
4990bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getConstant(const APInt& Val);
500db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
501db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
502db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty);
503db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty);
504db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
5053645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
5063228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
5073645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
5083228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
5090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 2> Ops;
510246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(LHS);
511246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(RHS);
5123228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddExpr(Ops, Flags);
513246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5143228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
5153228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
5160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 3> Ops;
517246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op0);
518246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op1);
519246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op2);
5203228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddExpr(Ops, Flags);
521246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5223645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
5233228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
5243645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
5253228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap)
5263228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    {
5270bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 2> Ops;
528246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(LHS);
529246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(RHS);
5303228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getMulExpr(Ops, Flags);
531246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5320bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
5330bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
5343228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags);
5350bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
5363228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags);
5370bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
5383228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags) {
5390bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
5403228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddRecExpr(NewOp, L, Flags);
541246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
5430bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
5440bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
5450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
5460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
5470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
5480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUnknown(Value *V);
5490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getCouldNotCompute();
550246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5514f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    /// getSizeOfExpr - Return an expression for sizeof on the given type.
5524f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
553db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getSizeOfExpr(Type *AllocTy);
5544f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
555ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getAlignOfExpr - Return an expression for alignof on the given type.
5564f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
557db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getAlignOfExpr(Type *AllocTy);
5584f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
559ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
5604f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
561db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getOffsetOfExpr(StructType *STy, unsigned FieldNo);
5624f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
563ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
5644f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
565db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getOffsetOfExpr(Type *CTy, Constant *FieldNo);
5664f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
567246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
568246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    ///
5690bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNegativeSCEV(const SCEV *V);
570246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5713e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    /// getNotSCEV - Return the SCEV object corresponding to ~V.
5723e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    ///
5730bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNotSCEV(const SCEV *V);
5743e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky
5753228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// getMinusSCEV - Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
576992efb03785f2a368fbb63b09373be1d6a96ce5aChris Lattner    const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
5773228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                             SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
578246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5796f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
5806f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// of the input value to the specified type.  If the type must be
5816f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// extended, it is zero extended.
582db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
5836f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky
584f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
585f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// of the input value to the specified type.  If the type must be
586f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// extended, it is sign extended.
587db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);
588f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman
589467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
590467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// the input value to the specified type.  If the type must be extended,
591467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// it is zero extended.  The conversion must not be narrowing.
592db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
593467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
594467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
595467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// the input value to the specified type.  If the type must be extended,
596467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// it is sign extended.  The conversion must not be narrowing.
597db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
598467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
5992ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
6002ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// the input value to the specified type. If the type must be extended,
6012ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// it is extended with unspecified bits. The conversion must not be
6022ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// narrowing.
603db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
6042ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman
605467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
606467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// input value to the specified type.  The conversion must not be
607467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// widening.
608db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
609467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
610a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
611a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// the types using zero-extension, and then perform a umax operation
612a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// with them.
6130bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS,
614a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman                                           const SCEV *RHS);
615a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
616c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// getUMinFromMismatchedTypes - Promote the operands to the wider of
617c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// the types using zero-extension, and then perform a umin operation
618c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// with them.
6190bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS,
6200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman                                           const SCEV *RHS);
621c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman
622b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// getPointerBase - Transitively follow the chain of pointer-type operands
623b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// until reaching a SCEV that does not have a single pointer operand. This
624b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// returns a SCEVUnknown pointer for well-formed pointer-type expressions,
625b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// but corner cases do exist.
626b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    const SCEV *getPointerBase(const SCEV *V);
627b12a754cce0c1d5542af605203a47820edba454dAndrew Trick
628e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman    /// getSCEVAtScope - Return a SCEV expression for the specified value
62953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// at the specified scope in the program.  The L value specifies a loop
63053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// nest to evaluate the expression at, where null is the top-level or a
63153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified loop is immediately inside of the loop.
63253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
63353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// This method can be used to compute the exit value for a variable defined
63453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// in a loop by querying what the value will hold in the parent loop.
63553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
636d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman    /// In the case that a relevant loop exit value cannot be computed, the
637d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman    /// original value V is returned.
6380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
63966a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman
64066a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman    /// getSCEVAtScope - This is a convenience function which does
64166a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman    /// getSCEVAtScope(getSCEV(V), L).
6420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEVAtScope(Value *V, const Loop *L);
64353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
6443948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
6453948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    /// by a conditional between LHS and RHS.  This is used to help avoid max
64685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// expressions in loop trip counts, and to eliminate casts.
6473948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
6483948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman                                  const SCEV *LHS, const SCEV *RHS);
649c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman
65085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
65185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// protected by a conditional between LHS and RHS.  This is used to
65285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// to eliminate casts.
65385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
65485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman                                     const SCEV *LHS, const SCEV *RHS);
65585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
65646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// getBackedgeTakenCount - If the specified loop has a predictable
65746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
65846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// object. The backedge-taken count is the number of times the loop header
65946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// will be branched to from within the loop. This is one less than the
66046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// trip count of the loop, since it doesn't count the first iteration,
66146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// when the header is branched to from outside the loop.
66246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    ///
66346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// Note that it is not valid to call this method on a loop without a
66446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// loop-invariant backedge-taken count (see
66546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// hasLoopInvariantBackedgeTakenCount).
66646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    ///
6670bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getBackedgeTakenCount(const Loop *L);
66853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
669a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
670a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// return the least SCEV value that is known never to be less than the
671a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// actual backedge taken count.
6720bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getMaxBackedgeTakenCount(const Loop *L);
673a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
67446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
67546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// has an analyzable loop-invariant backedge-taken count.
676f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
67753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
6784c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// forgetLoop - This method should be called by the client when it has
6794c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// changed a loop in a way that may effect ScalarEvolution's ability to
6804c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// compute a trip count, or if the loop is deleted.
6814c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    void forgetLoop(const Loop *L);
68260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman
68345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// forgetValue - This method should be called by the client when it has
68445a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// changed a value in a way that may effect its value, or which may
68545a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// disconnect it from a def-use chain linking it to a loop.
68645a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    void forgetValue(Value *V);
68745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen
688650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
689650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// is guaranteed to end in (at every loop iteration).  It is, at the same
690650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// time, the minimum number of times S is divisible by 2.  For example,
691650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// given {4,+,8} it returns 2.  If S is guaranteed to be 0, it returns the
692650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// bitwidth of S.
6930bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    uint32_t GetMinTrailingZeros(const SCEV *S);
6942c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
69585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
69685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
69785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ConstantRange getUnsignedRange(const SCEV *S);
69885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
69985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// getSignedRange - Determine the signed range for a particular SCEV.
70085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ConstantRange getSignedRange(const SCEV *S);
70285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
70385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNegative - Test if the given expression is known to be negative.
70485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNegative(const SCEV *S);
70685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
70785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownPositive - Test if the given expression is known to be positive.
70885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownPositive(const SCEV *S);
71085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
71185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonNegative - Test if the given expression is known to be
71285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-negative.
71385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
71485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonNegative(const SCEV *S);
71585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
71685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonPositive - Test if the given expression is known to be
71785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-positive.
71885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
71985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonPositive(const SCEV *S);
72085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
72185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonZero - Test if the given expression is known to be
72285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-zero.
72385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
72485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonZero(const SCEV *S);
7252c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
726e48172710bf78ae210b2257d6ac3e0e8fb3ba792Dan Gohman    /// isKnownPredicate - Test if the given expression is known to satisfy
72785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// the condition described by Pred, LHS, and RHS.
72885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
72985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownPredicate(ICmpInst::Predicate Pred,
73085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman                          const SCEV *LHS, const SCEV *RHS);
7312c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
732e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
7335cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// predicate Pred. Return true iff any changes were made. If the
7345cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// operands are provably equal or inequal, LHS and RHS are set to
7355cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// the same value and Pred is set to either ICMP_EQ or ICMP_NE.
736e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    ///
737e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    bool SimplifyICmpOperands(ICmpInst::Predicate &Pred,
738e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman                              const SCEV *&LHS,
739e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman                              const SCEV *&RHS);
740e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman
741714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// getLoopDisposition - Return the "disposition" of the given SCEV with
742714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// respect to the given loop.
743714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
744714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
74517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// isLoopInvariant - Return true if the value of the given SCEV is
74617ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// unchanging in the specified loop.
74717ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    bool isLoopInvariant(const SCEV *S, const Loop *L);
74817ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman
74917ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// hasComputableLoopEvolution - Return true if the given SCEV changes value
75017ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// in a known way in the specified loop.  This property being true implies
75117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// that the value is variant in the loop AND that we can emit an expression
75217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// to compute the value of the expression at any particular loop iteration.
75317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
75417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman
7559c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// getLoopDisposition - Return the "disposition" of the given SCEV with
7569c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// respect to the given block.
7579c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
7589c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
759dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// dominates - Return true if elements that makes up the given SCEV
760dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// dominate the specified basic block.
7619c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    bool dominates(const SCEV *S, const BasicBlock *BB);
762dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman
763dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// properlyDominates - Return true if elements that makes up the given SCEV
764dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// properly dominate the specified basic block.
7659c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    bool properlyDominates(const SCEV *S, const BasicBlock *BB);
766dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman
7674ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    /// hasOperand - Test whether the given SCEV has Op as a direct or
7684ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    /// indirect operand.
7694ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    bool hasOperand(const SCEV *S, const SCEV *Op) const;
7704ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman
77153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual bool runOnFunction(Function &F);
77253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual void releaseMemory();
77353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
77445cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner    virtual void print(raw_ostream &OS, const Module* = 0) const;
7751c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman
77608367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson  private:
7771c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    FoldingSet<SCEV> UniqueSCEVs;
7781c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    BumpPtrAllocator SCEVAllocator;
779ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman
780ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// FirstUnknown - The head of a linked list of all SCEVUnknown
781ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// values that have been allocated. This is used by releaseMemory
782ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// to locate them all and call their destructors.
783ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    SCEVUnknown *FirstUnknown;
78453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
78553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner}
78653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
78753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif
788