ScalarEvolution.h revision 03ee68a145ab5394c070298049d93f305be93ec3
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 1153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner// catagorize 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" 26ca5183d445954a9b2a570d6bbba1bc2b00ad6442Jeff Cohen#include "llvm/Support/DataTypes.h" 2735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h" 281c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/Support/Allocator.h" 2985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman#include "llvm/Support/ConstantRange.h" 301c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman#include "llvm/ADT/FoldingSet.h" 31444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.h" 321baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman#include <iosfwd> 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; 43508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson class LLVMContext; 4403ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class Loop; 4503ee68a145ab5394c070298049d93f305be93ec3Dan Gohman class LoopInfo; 4653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 476c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// SCEV - This class represents an analyzed expression in the program. These 48650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// are opaque objects that the client is not allowed to do much with 49650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// directly. 5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 51c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman class SCEV : public FastFoldingSetNode { 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const unsigned SCEVType; // The SCEV baseclass this node corresponds to 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 5753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 5853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 59c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman explicit SCEV(const FoldingSetNodeID &ID, unsigned SCEVTy) : 60c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman FastFoldingSetNode(ID), SCEVType(SCEVTy) {} 611c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 6353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the specified loop. 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const = 0; 6753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 6953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known way in the specified loop. This property being true implies that 7053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the value is variant in the loop AND that we can emit an expression to 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// compute the value of the expression at any particular loop iteration. 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 7553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 7653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const = 0; 7753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 78cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 79cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 80cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 81cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 8270a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// isOne - Return true if the expression is a constant one. 8370a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// 8470a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman bool isOne() const; 8570a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman 864d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// isAllOnesValue - Return true if the expression is a constant 874d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// all-ones value. 884d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// 894d289bf4af88759be173a1a809bf8c092d729764Dan Gohman bool isAllOnesValue() const; 904d289bf4af88759be173a1a809bf8c092d729764Dan Gohman 91afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 92afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 93afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 94afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 95afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 960bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman virtual const SCEV * 970bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman replaceSymbolicValuesWithConcrete(const SCEV *Sym, 980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Conc, 99246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 100afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1015a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// dominates - Return true if elements that makes up this SCEV dominates 1025a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// the specified basic block. 1035a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 1045a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 10653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 10753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 108b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const = 0; 109b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(std::ostream &OS) const; 1105c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 11553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1169769ab22265b313171d201b5928688524a01bd87Misha Brukman 117b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 118b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 119b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 120b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 121b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 12953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 13253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 133753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson SCEVCouldNotCompute(); 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 13653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 13853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 139b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1400bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman virtual const SCEV * 1410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman replaceSymbolicValuesWithConcrete(const SCEV *Sym, 1420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Conc, 143246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 14453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 1455a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 1465a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 1475a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 1485a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 14953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 15853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 1591959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 1601959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// notified whenever a Value is deleted. 1611959b7562e57f8394496e761486f23b187ac3f1bDan Gohman class SCEVCallbackVH : public CallbackVH { 1621959b7562e57f8394496e761486f23b187ac3f1bDan Gohman ScalarEvolution *SE; 1631959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void deleted(); 1641959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void allUsesReplacedWith(Value *New); 1651959b7562e57f8394496e761486f23b187ac3f1bDan Gohman public: 1661959b7562e57f8394496e761486f23b187ac3f1bDan Gohman SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 1671959b7562e57f8394496e761486f23b187ac3f1bDan Gohman }; 1681959b7562e57f8394496e761486f23b187ac3f1bDan Gohman 16935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 170deb052a3dd0227579f86d74b3c1d70384ea5c16bDaniel Dunbar friend struct SCEVExpander; 17135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 172f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 173f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 174f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 175f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 176f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 177f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 178f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 179f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 180f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// TD - The target data information for the target we are targetting. 181f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 182f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman TargetData *TD; 183f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 18486fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute - This SCEV is used to represent unknown trip 18586fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// counts and things. 1861c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman SCEVCouldNotCompute CouldNotCompute; 187f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 188f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Scalars - This is a cache of the scalars we have analyzed so far. 189f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 1900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman std::map<SCEVCallbackVH, const SCEV *> Scalars; 191f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 192a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 193a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// of a loop. This currently inclues an exact count and a maximum count. 194a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 195a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman struct BackedgeTakenInfo { 196a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the exact backedge-taken count of 197a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 1980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Exact; 199a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2007b9547089f0363b803e55dcbde1d6b99710dfe69Andreas Bolka /// Max - An expression indicating the least maximum backedge-taken 201a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 2020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Max; 203a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2040bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 205a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 206a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 2070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : 208a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(max) {} 209a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 210a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 211a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 212a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 213a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 214a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman return !isa<SCEVCouldNotCompute>(Exact) || 215a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman !isa<SCEVCouldNotCompute>(Max); 216a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 217a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 218a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 219f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 220f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 221a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 222f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 223f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 226f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 227f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 228f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 229f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 2306bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// ValuesAtScopes - This map contains entries for all the instructions 2316bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// that we attempt to compute getSCEVAtScope information for without 2326bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// using SCEV techniques, which can be expensive. 2336bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 2346bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 235f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 236f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 2370bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createSCEV(Value *V); 238f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 239f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 240f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 2410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createNodeForPHI(PHINode *PN); 242f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 24326466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 24426466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 2450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *createNodeForGEP(User *GEP); 24626466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 247f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 248f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// for the specified instruction and replaces any references to the 249f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// symbolic value SymName with the specified value. This is used during 250f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// PHI resolution. 251f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman void ReplaceSymbolicValueWithConcrete(Instruction *I, 2520bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *SymName, 2530bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *NewVal); 254f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 25551f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// getBECount - Subtract the end and start values and divide by the step, 25651f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// rounding up, to get the number of times the backedge is executed. Return 25751f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// CouldNotCompute if an intermediate computation overflows. 2580bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getBECount(const SCEV *Start, 2590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *End, 2600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Step); 26151f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman 262a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 263a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 264a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 265a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 266a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 267f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 268f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 269a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 270f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 271a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 272a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if it exits via the 273a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// specified block. 274a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 275a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *ExitingBlock); 276a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 277a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 278a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if its exit condition 279a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// were a conditional branch of ExitCond, TBB, and FBB. 280a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 281a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCond(const Loop *L, 282a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman Value *ExitCond, 283a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 284a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 285a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 286a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 287a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// times the backedge of the specified loop will execute if its exit 288a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 289a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// and FBB. 290a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 291a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 292a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ICmpInst *ExitCond, 293a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 294a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 295a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 296f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 297f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the trip count. 2980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV * 299f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 300f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *RHS, 301f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L, 302f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ICmpInst::Predicate p); 303f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 304f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 305f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// a constant number of times (the condition evolves only from constants), 306f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 307f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 30886fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// evaluate the trip count of the loop, return CouldNotCompute. 3090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, 310650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman Value *Cond, 311650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman bool ExitWhen); 312f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 313f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToZero - Return the number of times a backedge comparing the 314f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value to zero will execute. If not computable, return 31586fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 3160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *HowFarToZero(const SCEV *V, const Loop *L); 317f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 318f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToNonZero - Return the number of times a backedge checking the 319f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value for nonzero will execute. If not computable, return 32086fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 3210bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); 322f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 323f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowManyLessThans - Return the number of times a backedge containing the 324f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified less-than comparison will execute. If not computable, return 32586fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. isSigned specifies whether the less-than is signed. 32635738ac150afafe2359268d4b2169498c6c98c5fDan Gohman BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 32735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const Loop *L, bool isSigned); 328f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 329859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// getLoopPredecessor - If the given loop's header has exactly one unique 330859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// predecessor outside the loop, return it. Otherwise return null. 331859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman BasicBlock *getLoopPredecessor(const Loop *L); 332859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman 333f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 334f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 335f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 336f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 337f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 338f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 33985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isNecessaryCond - Test whether the condition described by Pred, LHS, 34085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// and RHS is a necessary condition for the given Cond value to evaluate 34185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// to true. 34240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman bool isNecessaryCond(Value *Cond, ICmpInst::Predicate Pred, 34340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman const SCEV *LHS, const SCEV *RHS, 34440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman bool Inverse); 34540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 34685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isNecessaryCondOperands - Test whether the condition described by Pred, 34785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// LHS, and RHS is a necessary condition for the condition described by 34885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// Pred, FoundLHS, and FoundRHS to evaluate to true. 34985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isNecessaryCondOperands(ICmpInst::Predicate Pred, 35085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS, 35185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *FoundLHS, const SCEV *FoundRHS); 35285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 353f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 354f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 355f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 356f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 357f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 358f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 359f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 36053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 361ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 362f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 3639769ab22265b313171d201b5928688524a01bd87Misha Brukman 36407cf79ef537caff6d39145f190a28a336e629b6fOwen Anderson LLVMContext *getContext() const { return Context; } 365508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 367af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 368af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 369af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 370af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman bool isSCEVable(const Type *Ty) const; 371af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 372af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 373af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 374af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman uint64_t getTypeSizeInBits(const Type *Ty) const; 375af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 376af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 377af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 378af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 379af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 380af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *getEffectiveSCEVType(const Type *Ty) const; 3812d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 38253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 38353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 3840bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEV(Value *V); 3850bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman 3860bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(ConstantInt *V); 3870bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(const APInt& Val); 3880bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 3890bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); 3900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); 3910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); 3920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); 3930bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops); 3940bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS) { 3950bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 396246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 397246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 398246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 399246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4000bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, 4010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Op2) { 4020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 3> Ops; 403246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 404246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 405246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 406246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 407246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4080bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops); 4090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS) { 4100bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 2> Ops; 411246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 412246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 413246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 414246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4150bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 4160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 417246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 4180bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 419246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 4200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 421246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 4220bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 423246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 424246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 4250bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 4260bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 4270bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 4280bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 4290bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 4300bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 4310bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUnknown(Value *V); 4320bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getCouldNotCompute(); 433246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 434246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 435246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 4360bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNegativeSCEV(const SCEV *V); 437246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4383e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 4393e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4400bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNotSCEV(const SCEV *V); 4413e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 442246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 443246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 4440bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMinusSCEV(const SCEV *LHS, 4450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS); 446246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4476f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 4486f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 4496f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 4500bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); 4516f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 452f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 453f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 454f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 4550bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); 456f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 457467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 458467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 459467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 4600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); 461467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 462467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 463467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 464467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 4650bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); 466467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 4672ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 4682ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// the input value to the specified type. If the type must be extended, 4692ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// it is extended with unspecified bits. The conversion must not be 4702ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// narrowing. 4710bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); 4722ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman 473467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 474467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 475467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 4760bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); 477467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 4786bbcba18db6d1f4bc0f0157df41cc02627bc4aa9Dan Gohman /// getIntegerSCEV - Given a SCEVable type, create a constant for the 479246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 4800bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getIntegerSCEV(int Val, const Type *Ty); 481246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 482a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 483a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// the types using zero-extension, and then perform a umax operation 484a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// with them. 4850bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 4860bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS); 487a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 488c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// getUMinFromMismatchedTypes - Promote the operands to the wider of 489c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// the types using zero-extension, and then perform a umin operation 490c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// with them. 4910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 4920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS); 493c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman 49453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 49553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 49653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 49753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 49853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 49953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 50053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 50153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 502d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// In the case that a relevant loop exit value cannot be computed, the 503d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// original value V is returned. 5040bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 50566a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 50666a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 50766a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 5080bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getSCEVAtScope(Value *V, const Loop *L); 50953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 510c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// isLoopGuardedByCond - Test whether entry to the loop is protected by 5113d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// a conditional between LHS and RHS. This is used to help avoid max 51285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// expressions in loop trip counts, and to eliminate casts. 513c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 51435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *LHS, const SCEV *RHS); 515c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 51685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 51785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// protected by a conditional between LHS and RHS. This is used to 51885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// to eliminate casts. 51985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 52085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 52185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 52246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 52346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 52446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 52546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 52646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 52746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 52846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 52946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 53046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 53146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 53246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 5330bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getBackedgeTakenCount(const Loop *L); 53453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 535a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 536a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 537a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 5380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getMaxBackedgeTakenCount(const Loop *L); 539a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 54046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 54146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 542f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 54353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 54446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// forgetLoopBackedgeTakenCount - This method should be called by the 54560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman /// client when it has changed a loop in a way that may effect 54646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// ScalarEvolution's ability to compute a trip count, or if the loop 54746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// is deleted. 54846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void forgetLoopBackedgeTakenCount(const Loop *L); 54960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 550650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// GetMinTrailingZeros - Determine the minimum number of zero bits that S 551650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// is guaranteed to end in (at every loop iteration). It is, at the same 552650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// time, the minimum number of times S is divisible by 2. For example, 553650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the 554650919e8b0aa28d20b8ff11f42ba81fea8b336ccDan Gohman /// bitwidth of S. 5550bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman uint32_t GetMinTrailingZeros(const SCEV *S); 5562c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 55785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 55885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 55985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getUnsignedRange(const SCEV *S); 56085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 56185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// getSignedRange - Determine the signed range for a particular SCEV. 56285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 56385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman ConstantRange getSignedRange(const SCEV *S); 56485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 56585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNegative - Test if the given expression is known to be negative. 56685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 56785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNegative(const SCEV *S); 56885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 56985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownPositive - Test if the given expression is known to be positive. 57085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 57185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPositive(const SCEV *S); 57285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 57385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonNegative - Test if the given expression is known to be 57485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-negative. 57585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 57685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonNegative(const SCEV *S); 57785b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 57885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonPositive - Test if the given expression is known to be 57985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-positive. 58085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 58185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonPositive(const SCEV *S); 58285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman 58385b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonZero - Test if the given expression is known to be 58485b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// non-zero. 58585b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 58685b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownNonZero(const SCEV *S); 5872c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 58885b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// isKnownNonZero - Test if the given expression is known to satisfy 58985b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// the condition described by Pred, LHS, and RHS. 59085b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman /// 59185b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman bool isKnownPredicate(ICmpInst::Predicate Pred, 59285b05a2e60e0e696739167b52cc7cc3e7cf390c0Dan Gohman const SCEV *LHS, const SCEV *RHS); 5932c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 59453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 59553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 59653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 597b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS, const Module* = 0) const; 598ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 5995c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 6005c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 6015c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 6021c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 60308367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson private: 6041c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman FoldingSet<SCEV> UniqueSCEVs; 6051c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman BumpPtrAllocator SCEVAllocator; 60653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 60753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 60853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 60953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 610