ScalarEvolution.h revision b12a754cce0c1d5542af605203a47820edba454d
153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
29769ab22265b313171d201b5928688524a01bd87Misha Brukman//
353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//                     The LLVM Compiler Infrastructure
453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source
67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details.
79769ab22265b313171d201b5928688524a01bd87Misha Brukman//
853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===//
953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
1053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// The ScalarEvolution class is an LLVM pass which can be used to analyze and
113f46a3abeedba8d517b4182de34c821d752db058Dan Gohman// categorize scalar expressions in loops.  It specializes in recognizing
1253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// general induction variables, representing them with the abstract and opaque
1353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// SCEV class.  Given this analysis, trip counts of loops and other important
1453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// properties can be obtained.
1553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//
1653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// This analysis is primarily useful for induction variable substitution and
1753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// strength reduction.
189769ab22265b313171d201b5928688524a01bd87Misha Brukman//
1953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner//===----------------------------------------------------------------------===//
2053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
2153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
2253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#define LLVM_ANALYSIS_SCALAREVOLUTION_H
2353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
2453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#include "llvm/Pass.h"
2503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include "llvm/Instructions.h"
26ffef8acc3e3398bdd04e947c7949befdd52faf86Dan Gohman#include "llvm/Function.h"
271f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h"
2835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h"
291c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/Support/Allocator.h"
3085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman#include "llvm/Support/ConstantRange.h"
311c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/ADT/FoldingSet.h"
32444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.h"
3303ee68a145ab5394c070298049d93f305be93ec3Dan Gohman#include <map>
3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
3553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm {
36246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman  class APInt;
3703ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class Constant;
38246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman  class ConstantInt;
3903ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class DominatorTree;
4053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  class Type;
41246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman  class ScalarEvolution;
42f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman  class TargetData;
4312ddd409535b52a7fa5157ded9a4cedd161fedb6Benjamin Kramer  class LLVMContext;
4403ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class Loop;
4503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman  class LoopInfo;
46fc8deb971d2b4dff370ba93948975e33a038605dDan Gohman  class Operator;
47dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman  class SCEVUnknown;
48aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  class SCEV;
49081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman  template<> struct FoldingSetTrait<SCEV>;
5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
516c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman  /// SCEV - This class represents an analyzed expression in the program.  These
52650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman  /// are opaque objects that the client is not allowed to do much with
53650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman  /// directly.
5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  ///
55c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman  class SCEV : public FoldingSetNode {
56081ad68e687b24dd102ed890bae1e10d8d284cefDan Gohman    friend struct FoldingSetTrait<SCEV>;
57aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman
58c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    /// FastID - A reference to an Interned FoldingSetNodeID for this node.
59c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    /// The ScalarEvolution's BumpPtrAllocator holds the data.
60c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman    FoldingSetNodeIDRef FastID;
61c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman
622f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    // The SCEV baseclass this node corresponds to
632f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    const unsigned short SCEVType;
6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
652f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman  protected:
662f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    /// SubclassData - This field is initialized to zero and may be used in
673f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// subclasses to store miscellaneous information.
682f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman    unsigned short SubclassData;
692f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman
702f1b15386f84a607304fca7e26fa6b67b490df4dDan Gohman  private:
7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    SCEV(const SCEV &);            // DO NOT IMPLEMENT
7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    void operator=(const SCEV &);  // DO NOT IMPLEMENT
734ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman
7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  public:
753228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// NoWrapFlags are bitfield indices into SubclassData.
763228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
773228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
783228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// no-signed-wrap <NSW> properties, which are derived from the IR
793228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// operator. NSW is a misnomer that we use to mean no signed overflow or
803228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// underflow.
813228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
823228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// AddRec expression may have a no-self-wraparound <NW> property if the
833228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// result can never reach the start value. This property is independent of
843228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// the actual start value and step direction. Self-wraparound is defined
853228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// purely in terms of the recurrence's loop, step size, and
863228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// bitwidth. Formally, a recurrence with no self-wraparound satisfies:
873228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth).
883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    ///
893228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Note that NUW and NSW are also valid properties of a recurrence, and
903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// either implies NW. For convenience, NW will be set for a recurrence
913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// whenever either NUW or NSW are set.
923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    enum NoWrapFlags { FlagAnyWrap = 0,          // No guarantee.
933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNW      = (1 << 0),   // No self-wrap.
943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNUW     = (1 << 1),   // No unsigned wrap.
953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       FlagNSW     = (1 << 2),   // No signed wrap.
963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                       NoWrapMask  = (1 << 3) -1 };
973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
983bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
993bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}
1001c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman
10153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    unsigned getSCEVType() const { return SCEVType; }
10253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
10353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// getType - Return the LLVM type of this SCEV expression.
10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
1054ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    const Type *getType() const;
10653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
107cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    /// isZero - Return true if the expression is a constant zero.
108cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    ///
109cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman    bool isZero() const;
110cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman
11170a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    /// isOne - Return true if the expression is a constant one.
11270a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    ///
11370a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman    bool isOne() const;
11470a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman
1154d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    /// isAllOnesValue - Return true if the expression is a constant
1164d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    /// all-ones value.
1174d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    ///
1184d289bf4af88759be173a1a809bf8c092d729764Dan Gohman    bool isAllOnesValue() const;
1194d289bf4af88759be173a1a809bf8c092d729764Dan Gohman
12053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// print - Print out the internal representation of this scalar to the
12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified stream.  This should really only be used for debugging
12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// purposes.
1234ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    void print(raw_ostream &OS) const;
12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// dump - This method is used for debugging.
12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    void dump() const;
12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
1299769ab22265b313171d201b5928688524a01bd87Misha Brukman
130aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
131aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  // temporary FoldingSetNodeID values.
132aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
133aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static void Profile(const SCEV &X, FoldingSetNodeID& ID) {
134aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      ID = X.FastID;
135aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
136aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
137aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman                       FoldingSetNodeID &TempID) {
138aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      return ID == X.FastID;
139aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
140aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
141aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman      return X.FastID.ComputeHash();
142aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman    }
143aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman  };
144aadb5f5adbdb650c5cdc5ece939aaa30af91b3bcDan Gohman
145b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
146b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman    S.print(OS);
147b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman    return OS;
148b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman  }
149b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman
15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// SCEVCouldNotCompute - An object of this class is returned by queries that
15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// could not be answered.  For example, if you ask for the number of
15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// iterations of a linked-list traversal loop, you will get one of these.
15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// None of the standard SCEV operations are valid on this class, it is just a
15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// marker.
15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  struct SCEVCouldNotCompute : public SCEV {
156753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson    SCEVCouldNotCompute();
15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
15953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
16053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    static bool classof(const SCEV *S);
16153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
16253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
16353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
16453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// client code (intentionally) can't do much with the SCEV objects directly,
16553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  /// they must ask this class for services.
16653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  ///
16753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  class ScalarEvolution : public FunctionPass {
168714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman  public:
169714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// LoopDisposition - An enum describing the relationship between a
170714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// SCEV and a loop.
171714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    enum LoopDisposition {
172714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopVariant,    ///< The SCEV is loop-variant (unknown).
173714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopInvariant,  ///< The SCEV is loop-invariant.
174714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman      LoopComputable  ///< The SCEV varies predictably with the loop.
175714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    };
176714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
1779c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// BlockDisposition - An enum describing the relationship between a
1789c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// SCEV and a basic block.
1799c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    enum BlockDisposition {
1809c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      DoesNotDominateBlock,  ///< The SCEV does not dominate the block.
1819c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      DominatesBlock,        ///< The SCEV dominates the block.
1829c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman      ProperlyDominatesBlock ///< The SCEV properly dominates the block.
1839c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    };
1849c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
1853228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Convenient NoWrapFlags manipulation that hides enum casts and is
1863228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// visible in the ScalarEvolution name space.
1873228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) {
1883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags & Mask);
1893228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1903228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
1913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                                      SCEV::NoWrapFlags OnFlags) {
1923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags | OnFlags);
1933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags,
1953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                                        SCEV::NoWrapFlags OffFlags) {
1963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
1973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
1983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
199714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman  private:
2001959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
2011959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    /// notified whenever a Value is deleted.
2021959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    class SCEVCallbackVH : public CallbackVH {
2031959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      ScalarEvolution *SE;
2041959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      virtual void deleted();
2051959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      virtual void allUsesReplacedWith(Value *New);
2061959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    public:
2071959b7562e57f8394496e761486f23b187ac3f1bDan Gohman      SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
2081959b7562e57f8394496e761486f23b187ac3f1bDan Gohman    };
2091959b7562e57f8394496e761486f23b187ac3f1bDan Gohman
21035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman    friend class SCEVCallbackVH;
211629bff692ae96dea517dc854e27b57ee6c8729efBenjamin Kramer    friend class SCEVExpander;
212dc7a235363166a61e81986c534fe11ceb44109fcDan Gohman    friend class SCEVUnknown;
21335738ac150afafe2359268d4b2169498c6c98c5fDan Gohman
214f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// F - The function we are analyzing.
215f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
216f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    Function *F;
217f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
218f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// LI - The loop information for the function we are currently analyzing.
219f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
220f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    LoopInfo *LI;
221f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
2223f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// TD - The target data information for the target we are targeting.
223f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    TargetData *TD;
225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
2261cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    /// DT - The dominator tree.
2271cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    ///
2281cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman    DominatorTree *DT;
2291cd9275c8d612bd1c92fc7ba436b60aaead1efbfDan Gohman
23086fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute - This SCEV is used to represent unknown trip
23186fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// counts and things.
2321c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    SCEVCouldNotCompute CouldNotCompute;
233f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
234e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// ValueExprMapType - The typedef for ValueExprMap.
235f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ///
236e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
237e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman      ValueExprMapType;
238e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman
239e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// ValueExprMap - This is a cache of the values we have analyzed so far.
240e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    ///
241e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    ValueExprMapType ValueExprMap;
242f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
243a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// BackedgeTakenInfo - Information about the backedge-taken count
2443f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// of a loop. This currently includes an exact count and a maximum count.
245a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    ///
246a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    struct BackedgeTakenInfo {
247a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// Exact - An expression indicating the exact backedge-taken count of
248a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
2490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      const SCEV *Exact;
250a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2517b9547089f0363b803e55dcbde1d6b99710dfe69Andreas Bolka      /// Max - An expression indicating the least maximum backedge-taken
252a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// count of the loop that is known, or a SCEVCouldNotCompute.
2530bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      const SCEV *Max;
254a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2550bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
256a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        Exact(exact), Max(exact) {}
257a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
2580bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      BackedgeTakenInfo(const SCEV *exact, const SCEV *max) :
259a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        Exact(exact), Max(max) {}
260a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
261a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
262a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// computed information, or whether it's all SCEVCouldNotCompute
263a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      /// values.
264a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      bool hasAnyInfo() const {
265a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman        return !isa<SCEVCouldNotCompute>(Exact) ||
266a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman               !isa<SCEVCouldNotCompute>(Max);
267a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman      }
268a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    };
269a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
270f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
271f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// this function as they are computed.
272a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
273f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
274f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ConstantEvolutionLoopExitValue - This map contains entries for all of
275f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// the PHI instructions that we attempt to compute constant evolutions for.
276f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// This allows us to avoid potentially expensive recomputation of these
277f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// properties.  An instruction maps to null if we are unable to compute its
278f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// exit value.
279f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
280f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
28142214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// ValuesAtScopes - This map contains entries for all the expressions
28242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// that we attempt to compute getSCEVAtScope information for, which can
28342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// be expensive in extreme cases.
28442214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    std::map<const SCEV *,
28542214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman             std::map<const Loop *, const SCEV *> > ValuesAtScopes;
2866bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman
287714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// LoopDispositions - Memoized computeLoopDisposition results.
288714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    std::map<const SCEV *,
289714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman             std::map<const Loop *, LoopDisposition> > LoopDispositions;
290714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
291714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// computeLoopDisposition - Compute a LoopDisposition value.
292714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
293714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
2949c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// BlockDispositions - Memoized computeBlockDisposition results.
2959c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    std::map<const SCEV *,
2969c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman             std::map<const BasicBlock *, BlockDisposition> > BlockDispositions;
2979c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
2989c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// computeBlockDisposition - Compute a BlockDisposition value.
2999c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
3009c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
3016678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    /// UnsignedRanges - Memoized results from getUnsignedRange
3026678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
3036678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman
3046678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    /// SignedRanges - Memoized results from getSignedRange
3056678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman    DenseMap<const SCEV *, ConstantRange> SignedRanges;
3066678e7b6eb534b43b92105076e6d0553e5cf7defDan Gohman
3077c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    /// setUnsignedRange - Set the memoized unsigned range for the given SCEV.
3087c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    const ConstantRange &setUnsignedRange(const SCEV *S,
3097c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman                                          const ConstantRange &CR) {
3107c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
3117c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        UnsignedRanges.insert(std::make_pair(S, CR));
3127c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      if (!Pair.second)
3137c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        Pair.first->second = CR;
3147c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      return Pair.first->second;
3157c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    }
3167c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman
3177c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    /// setUnsignedRange - Set the memoized signed range for the given SCEV.
3187c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    const ConstantRange &setSignedRange(const SCEV *S,
3197c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman                                        const ConstantRange &CR) {
3207c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
3217c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        SignedRanges.insert(std::make_pair(S, CR));
3227c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      if (!Pair.second)
3237c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman        Pair.first->second = CR;
3247c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman      return Pair.first->second;
3257c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman    }
3267c0fd8eb724a7228a6cf7e3e5487614c25202a91Dan Gohman
327f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// createSCEV - We know that there is no SCEV for the specified value.
328f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// Analyze the expression.
3290bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *createSCEV(Value *V);
330f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
331f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// createNodeForPHI - Provide the special handling we need to analyze PHI
332f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// SCEVs.
3330bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *createNodeForPHI(PHINode *PN);
334f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
33526466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman    /// createNodeForGEP - Provide the special handling we need to analyze GEP
33626466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman    /// SCEVs.
337d281ed2d03654b9cdb290a2d7c73dfe7b826e554Dan Gohman    const SCEV *createNodeForGEP(GEPOperator *GEP);
33826466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman
33942214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called
34042214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    /// at most once for each SCEV+Loop pair.
34142214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    ///
34242214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman    const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
34342214899082bfb5b6f8c6a09d355fec9ef4a0e82Dan Gohman
344fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// ForgetSymbolicValue - This looks up computed SCEV values for all
345fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// instructions that depend on the given instruction and removes them from
346e8ac3f3be4b4df619368bf46aa4ed91557b5f76eDan Gohman    /// the ValueExprMap map if they reference SymName. This is used during PHI
347fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    /// resolution.
348fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
349f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
35051f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// getBECount - Subtract the end and start values and divide by the step,
35151f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// rounding up, to get the number of times the backedge is executed. Return
35251f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman    /// CouldNotCompute if an intermediate computation overflows.
3530bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getBECount(const SCEV *Start,
354a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman                           const SCEV *End,
3551f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman                           const SCEV *Step,
3561f96e67f78110d0ac5b30a32375097a28f869c63Dan Gohman                           bool NoWrap);
35751f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman
358a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
359a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// loop, lazily computing new values if the loop hasn't been analyzed
360a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// yet.
361a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
362a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
363f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ComputeBackedgeTakenCount - Compute the number of times the specified
364f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// loop will iterate.
365a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
366f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
367a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
368a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// backedge of the specified loop will execute if it exits via the
369a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// specified block.
370a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
371a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                      BasicBlock *ExitingBlock);
372a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
373a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
374a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// backedge of the specified loop will execute if its exit condition
375a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// were a conditional branch of ExitCond, TBB, and FBB.
376a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo
377a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
378a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            Value *ExitCond,
379a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            BasicBlock *TBB,
380a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                            BasicBlock *FBB);
381a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
382a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
383a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// times the backedge of the specified loop will execute if its exit
384a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
385a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// and FBB.
386a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    BackedgeTakenInfo
387a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
388a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                ICmpInst *ExitCond,
389a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                BasicBlock *TBB,
390a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman                                                BasicBlock *FBB);
391a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
392f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
3937e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// of 'icmp op load X, cst', try to see if we can compute the
3947e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// backedge-taken count.
395f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo
396f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
397f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   Constant *RHS,
398f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   const Loop *L,
399f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                   ICmpInst::Predicate p);
400f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
40107ad19b509530b43e6a9acc5c1285cb560dd7198Dan Gohman    /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute
402f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// a constant number of times (the condition evolves only from constants),
403f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// try to evaluate a few iterations of the loop until we get the exit
404f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// condition gets a value of ExitWhen (true or false).  If we cannot
4057e77f7959162a601291fd5400a88908d021033d3Dan Gohman    /// evaluate the backedge-taken count of the loop, return CouldNotCompute.
4060bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L,
407650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman                                                      Value *Cond,
408650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman                                                      bool ExitWhen);
409f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
410f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowFarToZero - Return the number of times a backedge comparing the
411f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified value to zero will execute.  If not computable, return
41286fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute.
413f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L);
414f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
415f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowFarToNonZero - Return the number of times a backedge checking the
416f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified value for nonzero will execute.  If not computable, return
41786fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute.
418f6d009fb6fc19d9f7ee7cdc528bf8e83a758faccDan Gohman    BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L);
419f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
420f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// HowManyLessThans - Return the number of times a backedge containing the
421f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// specified less-than comparison will execute.  If not computable, return
42286fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman    /// CouldNotCompute. isSigned specifies whether the less-than is signed.
42335738ac150afafe2359268d4b2169498c6c98c5fDan Gohman    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
42435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman                                       const Loop *L, bool isSigned);
425f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
426f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
427f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// (which may not be an immediate predecessor) which has exactly one
428f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// successor from which BB is reachable, or null if no such block is
429f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// found.
430005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman    std::pair<BasicBlock *, BasicBlock *>
431005752bbe72868b548bba93dbc1ea46ffe8e5b2cDan Gohman    getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
432f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
433af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    /// isImpliedCond - Test whether the condition described by Pred, LHS, and
434af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    /// RHS is true whenever the given FoundCondValue value evaluates to true.
435af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman    bool isImpliedCond(ICmpInst::Predicate Pred,
4360f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                       const SCEV *LHS, const SCEV *RHS,
437af08a36bd6b9d32a5ea993849d43094fecbd5bedDan Gohman                       Value *FoundCondValue,
4380f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                       bool Inverse);
4390f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman
4400f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// isImpliedCondOperands - Test whether the condition described by Pred,
4413f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
4420f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// and FoundRHS is true.
4430f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    bool isImpliedCondOperands(ICmpInst::Predicate Pred,
4440f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                               const SCEV *LHS, const SCEV *RHS,
4450f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                               const SCEV *FoundLHS, const SCEV *FoundRHS);
4460f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman
4470f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// isImpliedCondOperandsHelper - Test whether the condition described by
4483f46a3abeedba8d517b4182de34c821d752db058Dan Gohman    /// Pred, LHS, and RHS is true whenever the condition described by Pred,
4490f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    /// FoundLHS, and FoundRHS is true.
4500f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman    bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
4510f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                                     const SCEV *LHS, const SCEV *RHS,
4520f4b285a5b86b1e9c6e27bb46028dfbb77bb5db4Dan Gohman                                     const SCEV *FoundLHS, const SCEV *FoundRHS);
45385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
454f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
455f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// in the header of its containing loop, we know the loop executes a
456f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// constant number of times, and the PHI node is just a recurrence
457f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    /// involving constants, fold it.
458f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
459f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman                                                const Loop *L);
460f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman
46153c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// isKnownPredicateWithRanges - Test if the given expression is known to
46253c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// satisfy the condition described by Pred and the known constant ranges
46353c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    /// of LHS and RHS.
46453c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    ///
46553c66eacc417c0113fba7159487b90005dc8f91eDan Gohman    bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
46653c66eacc417c0113fba7159487b90005dc8f91eDan Gohman                                    const SCEV *LHS, const SCEV *RHS);
46753c66eacc417c0113fba7159487b90005dc8f91eDan Gohman
46856a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman    /// forgetMemoizedResults - Drop memoized information computed for S.
46956a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman    void forgetMemoizedResults(const SCEV *S);
47056a756821842678a96f2baa8c6a53bd28fc2b69eDan Gohman
47153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  public:
472ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky    static char ID; // Pass identification, replacement for typeid
473f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    ScalarEvolution();
4749769ab22265b313171d201b5928688524a01bd87Misha Brukman
475e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson    LLVMContext &getContext() const { return F->getContext(); }
476508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson
477af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// isSCEVable - Test if values of the given type are analyzable within
478af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// the SCEV framework. This primarily includes integer types, and it
479af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// can optionally include pointer types if the ScalarEvolution class
480af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// has access to target-specific information.
481af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    bool isSCEVable(const Type *Ty) const;
482af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman
483af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// getTypeSizeInBits - Return the size in bits of the specified type,
484af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// for which isSCEVable must return true.
485af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    uint64_t getTypeSizeInBits(const Type *Ty) const;
486af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman
487af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// getEffectiveSCEVType - Return a type with the same bitwidth as
488af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// the given type and which represents how SCEV will treat the given
489af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// type, for which isSCEVable must return true. For pointer types,
490af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    /// this is the pointer-sized integer type.
491af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman    const Type *getEffectiveSCEVType(const Type *Ty) const;
4922d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman
493e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman    /// getSCEV - Return a SCEV expression for the full generality of the
49453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified expression.
4950bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEV(Value *V);
4960bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman
4970bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getConstant(ConstantInt *V);
4980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getConstant(const APInt& Val);
4990bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false);
5000bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty);
5010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty);
5020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty);
5030bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty);
5043645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
5053228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
5063645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
5073228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
5080bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 2> Ops;
509246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(LHS);
510246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(RHS);
5113228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddExpr(Ops, Flags);
512246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5133228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
5143228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
5150bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 3> Ops;
516246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op0);
517246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op1);
518246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(Op2);
5193228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddExpr(Ops, Flags);
520246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5213645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
5223228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
5233645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
5243228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap)
5253228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    {
5260bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 2> Ops;
527246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(LHS);
528246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman      Ops.push_back(RHS);
5293228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getMulExpr(Ops, Flags);
530246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5310bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
5320bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
5333228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags);
5340bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
5353228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags);
5360bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
5373228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              const Loop *L, SCEV::NoWrapFlags Flags) {
5380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
5393228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return getAddRecExpr(NewOp, L, Flags);
540246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    }
5410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
5420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
5430bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
5440bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
5450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
5460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
5470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUnknown(Value *V);
5480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getCouldNotCompute();
549246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5504f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    /// getSizeOfExpr - Return an expression for sizeof on the given type.
5514f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
5524f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    const SCEV *getSizeOfExpr(const Type *AllocTy);
5534f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
554ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getAlignOfExpr - Return an expression for alignof on the given type.
5554f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
5564f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    const SCEV *getAlignOfExpr(const Type *AllocTy);
5574f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
558ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
5594f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
5604f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo);
5614f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
562ebdcbc26c77b97483afbcb906f988cc66d43606dDan Gohman    /// getOffsetOfExpr - Return an expression for offsetof on the given field.
5634f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    ///
5644f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman    const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo);
5654f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman
566246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
567246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    ///
5680bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNegativeSCEV(const SCEV *V);
569246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5703e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    /// getNotSCEV - Return the SCEV object corresponding to ~V.
5713e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    ///
5720bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNotSCEV(const SCEV *V);
5733e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky
5743228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// getMinusSCEV - Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
575992efb03785f2a368fbb63b09373be1d6a96ce5aChris Lattner    const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
5763228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                             SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
577246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
5786f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
5796f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// of the input value to the specified type.  If the type must be
5806f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky    /// extended, it is zero extended.
5810bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty);
5826f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky
583f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
584f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// of the input value to the specified type.  If the type must be
585f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman    /// extended, it is sign extended.
5860bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty);
587f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman
588467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
589467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// the input value to the specified type.  If the type must be extended,
590467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// it is zero extended.  The conversion must not be narrowing.
5910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty);
592467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
593467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
594467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// the input value to the specified type.  If the type must be extended,
595467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// it is sign extended.  The conversion must not be narrowing.
5960bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty);
597467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
5982ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
5992ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// the input value to the specified type. If the type must be extended,
6002ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// it is extended with unspecified bits. The conversion must not be
6012ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman    /// narrowing.
6020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty);
6032ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman
604467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
605467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// input value to the specified type.  The conversion must not be
606467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman    /// widening.
6070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty);
608467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman
609a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
610a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// the types using zero-extension, and then perform a umax operation
611a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman    /// with them.
6120bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS,
613a271d36d7ce96bce52fcb73ca1ef028d9a9d8d0fDan Gohman                                           const SCEV *RHS);
614a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman
615c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// getUMinFromMismatchedTypes - Promote the operands to the wider of
616c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// the types using zero-extension, and then perform a umin operation
617c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman    /// with them.
6180bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS,
6190bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman                                           const SCEV *RHS);
620c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman
621b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// getPointerBase - Transitively follow the chain of pointer-type operands
622b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// until reaching a SCEV that does not have a single pointer operand. This
623b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// returns a SCEVUnknown pointer for well-formed pointer-type expressions,
624b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    /// but corner cases do exist.
625b12a754cce0c1d5542af605203a47820edba454dAndrew Trick    const SCEV *getPointerBase(const SCEV *V);
626b12a754cce0c1d5542af605203a47820edba454dAndrew Trick
627e7125f4babb536df3a2573b6166954da7753c6b8Dan Gohman    /// getSCEVAtScope - Return a SCEV expression for the specified value
62853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// at the specified scope in the program.  The L value specifies a loop
62953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// nest to evaluate the expression at, where null is the top-level or a
63053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// specified loop is immediately inside of the loop.
63153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
63253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// This method can be used to compute the exit value for a variable defined
63353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    /// in a loop by querying what the value will hold in the parent loop.
63453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    ///
635d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman    /// In the case that a relevant loop exit value cannot be computed, the
636d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman    /// original value V is returned.
6370bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
63866a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman
63966a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman    /// getSCEVAtScope - This is a convenience function which does
64066a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman    /// getSCEVAtScope(getSCEV(V), L).
6410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getSCEVAtScope(Value *V, const Loop *L);
64253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
6433948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
6443948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    /// by a conditional between LHS and RHS.  This is used to help avoid max
64585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// expressions in loop trip counts, and to eliminate casts.
6463948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman    bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
6473948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman                                  const SCEV *LHS, const SCEV *RHS);
648c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman
64985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
65085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// protected by a conditional between LHS and RHS.  This is used to
65185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// to eliminate casts.
65285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
65385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman                                     const SCEV *LHS, const SCEV *RHS);
65485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
65546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// getBackedgeTakenCount - If the specified loop has a predictable
65646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
65746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// object. The backedge-taken count is the number of times the loop header
65846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// will be branched to from within the loop. This is one less than the
65946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// trip count of the loop, since it doesn't count the first iteration,
66046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// when the header is branched to from outside the loop.
66146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    ///
66246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// Note that it is not valid to call this method on a loop without a
66346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// loop-invariant backedge-taken count (see
66446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// hasLoopInvariantBackedgeTakenCount).
66546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    ///
6660bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getBackedgeTakenCount(const Loop *L);
66753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
668a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
669a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// return the least SCEV value that is known never to be less than the
670a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman    /// actual backedge taken count.
6710bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getMaxBackedgeTakenCount(const Loop *L);
672a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman
67346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
67446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman    /// has an analyzable loop-invariant backedge-taken count.
675f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman    bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
67653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
6774c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// forgetLoop - This method should be called by the client when it has
6784c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// changed a loop in a way that may effect ScalarEvolution's ability to
6794c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    /// compute a trip count, or if the loop is deleted.
6804c7279ac726e338400626fca5a09b5533426eb6aDan Gohman    void forgetLoop(const Loop *L);
68160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman
68245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// forgetValue - This method should be called by the client when it has
68345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// changed a value in a way that may effect its value, or which may
68445a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    /// disconnect it from a def-use chain linking it to a loop.
68545a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen    void forgetValue(Value *V);
68645a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen
687650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
688650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// is guaranteed to end in (at every loop iteration).  It is, at the same
689650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// time, the minimum number of times S is divisible by 2.  For example,
690650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// given {4,+,8} it returns 2.  If S is guaranteed to be 0, it returns the
691650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman    /// bitwidth of S.
6920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    uint32_t GetMinTrailingZeros(const SCEV *S);
6932c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
69485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
69585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
69685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ConstantRange getUnsignedRange(const SCEV *S);
69785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
69885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// getSignedRange - Determine the signed range for a particular SCEV.
69985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ConstantRange getSignedRange(const SCEV *S);
70185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
70285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNegative - Test if the given expression is known to be negative.
70385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNegative(const SCEV *S);
70585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
70685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownPositive - Test if the given expression is known to be positive.
70785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
70885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownPositive(const SCEV *S);
70985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
71085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonNegative - Test if the given expression is known to be
71185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-negative.
71285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
71385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonNegative(const SCEV *S);
71485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
71585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonPositive - Test if the given expression is known to be
71685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-positive.
71785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
71885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonPositive(const SCEV *S);
71985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman
72085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// isKnownNonZero - Test if the given expression is known to be
72185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// non-zero.
72285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
72385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownNonZero(const SCEV *S);
7242c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
725e48172710bf78ae210b2257d6ac3e0e8fb3ba792Dan Gohman    /// isKnownPredicate - Test if the given expression is known to satisfy
72685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    /// the condition described by Pred, LHS, and RHS.
72785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    ///
72885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman    bool isKnownPredicate(ICmpInst::Predicate Pred,
72985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman                          const SCEV *LHS, const SCEV *RHS);
7302c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman
731e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
7325cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// predicate Pred. Return true iff any changes were made. If the
7335cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// operands are provably equal or inequal, LHS and RHS are set to
7345cc6f9ba4777a460d7036edbbb3e8f01fb0a3d32Dan Gohman    /// the same value and Pred is set to either ICMP_EQ or ICMP_NE.
735e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    ///
736e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman    bool SimplifyICmpOperands(ICmpInst::Predicate &Pred,
737e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman                              const SCEV *&LHS,
738e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman                              const SCEV *&RHS);
739e979650fa5faf4b1253f623662a8d9c81a4a4fc3Dan Gohman
740714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// getLoopDisposition - Return the "disposition" of the given SCEV with
741714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    /// respect to the given loop.
742714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman    LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
743714b5290b04e08570dae4304c1c92d30c06d3c99Dan Gohman
74417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// isLoopInvariant - Return true if the value of the given SCEV is
74517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// unchanging in the specified loop.
74617ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    bool isLoopInvariant(const SCEV *S, const Loop *L);
74717ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman
74817ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// hasComputableLoopEvolution - Return true if the given SCEV changes value
74917ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// in a known way in the specified loop.  This property being true implies
75017ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// that the value is variant in the loop AND that we can emit an expression
75117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    /// to compute the value of the expression at any particular loop iteration.
75217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman    bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
75317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman
7549c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// getLoopDisposition - Return the "disposition" of the given SCEV with
7559c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    /// respect to the given block.
7569c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
7579c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman
758dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// dominates - Return true if elements that makes up the given SCEV
759dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// dominate the specified basic block.
7609c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    bool dominates(const SCEV *S, const BasicBlock *BB);
761dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman
762dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// properlyDominates - Return true if elements that makes up the given SCEV
763dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman    /// properly dominate the specified basic block.
7649c9fcfc719158a46cb2e41b66d7dc1a63cd48d74Dan Gohman    bool properlyDominates(const SCEV *S, const BasicBlock *BB);
765dc0e8fb9f9512622f55f73e1a434caa5c0915694Dan Gohman
7664ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    /// hasOperand - Test whether the given SCEV has Op as a direct or
7674ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    /// indirect operand.
7684ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman    bool hasOperand(const SCEV *S, const SCEV *Op) const;
7694ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman
77053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual bool runOnFunction(Function &F);
77153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual void releaseMemory();
77253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
77345cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner    virtual void print(raw_ostream &OS, const Module* = 0) const;
7741c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman
77508367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson  private:
7761c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    FoldingSet<SCEV> UniqueSCEVs;
7771c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman    BumpPtrAllocator SCEVAllocator;
778ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman
779ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// FirstUnknown - The head of a linked list of all SCEVUnknown
780ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// values that have been allocated. This is used by releaseMemory
781ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// to locate them all and call their destructors.
782ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    SCEVUnknown *FirstUnknown;
78353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner  };
78453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner}
78553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner
78653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif
787