ScalarEvolution.h revision 6bbcba18db6d1f4bc0f0157df41cc02627bc4aa9
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" 25019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Analysis/LoopInfo.h" 26ca5183d445954a9b2a570d6bbba1bc2b00ad6442Jeff Cohen#include "llvm/Support/DataTypes.h" 2735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman#include "llvm/Support/ValueHandle.h" 28444f49150df8a4280ccea20fc2839cd899fc7558Dan Gohman#include "llvm/ADT/DenseMap.h" 291baa88e3de8947b02d9ef4caa73e5860f048ec6eDan Gohman#include <iosfwd> 3053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 3153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattnernamespace llvm { 32246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class APInt; 33246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ConstantInt; 3453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class Type; 35246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman class ScalarEvolution; 36f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman class TargetData; 3708367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVConstant; 3808367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVTruncateExpr; 3908367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVZeroExtendExpr; 4008367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVCommutativeExpr; 4108367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVUDivExpr; 4208367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVSignExtendExpr; 4308367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVAddRecExpr; 4408367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson class SCEVUnknown; 4553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 466c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// SCEV - This class represents an analyzed expression in the program. These 476c0866ca8373da318741cc90ad7afd1bda22bb1bDan Gohman /// are reference-counted opaque objects that the client is not allowed to 4853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// do much with directly. 4953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 5053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class SCEV { 5153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner const unsigned SCEVType; // The SCEV baseclass this node corresponds to 5253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 5353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner SCEV(const SCEV &); // DO NOT IMPLEMENT 5453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void operator=(const SCEV &); // DO NOT IMPLEMENT 5553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner protected: 5653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual ~SCEV(); 5753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 58753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson explicit SCEV(unsigned SCEVTy) : 59753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson SCEVType(SCEVTy) {} 6053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner unsigned getSCEVType() const { return SCEVType; } 6253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the specified loop. 6553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const = 0; 6653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 6753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 6853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// known way in the specified loop. This property being true implies that 6953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// the value is variant in the loop AND that we can emit an expression to 7053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// compute the value of the expression at any particular loop iteration. 7153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 7253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 7353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getType - Return the LLVM type of this SCEV expression. 7453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 7553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const = 0; 7653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 77cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// isZero - Return true if the expression is a constant zero. 78cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman /// 79cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman bool isZero() const; 80cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman 8170a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// isOne - Return true if the expression is a constant one. 8270a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman /// 8370a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman bool isOne() const; 8470a1fe704831f9b842be0b2a2af5f7082b0e540cDan Gohman 854d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// isAllOnesValue - Return true if the expression is a constant 864d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// all-ones value. 874d289bf4af88759be173a1a809bf8c092d729764Dan Gohman /// 884d289bf4af88759be173a1a809bf8c092d729764Dan Gohman bool isAllOnesValue() const; 894d289bf4af88759be173a1a809bf8c092d729764Dan Gohman 90afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 91afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the symbolic value "Sym", construct and return a new SCEV that produces 92afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// the same value, but which uses the concrete value Conc instead of the 93afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// symbolic value. If this SCEV does not use the symbolic value, it 94afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner /// returns itself. 95372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson virtual const SCEV* 96372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson replaceSymbolicValuesWithConcrete(const SCEV* Sym, 97372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Conc, 98246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const = 0; 99afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1005a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// dominates - Return true if elements that makes up this SCEV dominates 1015a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng /// the specified basic block. 1025a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 1035a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 10453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// print - Print out the internal representation of this scalar to the 10553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified stream. This should really only be used for debugging 10653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// purposes. 107b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const = 0; 108b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(std::ostream &OS) const; 1095c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 11053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 11153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// dump - This method is used for debugging. 11253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 11353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner void dump() const; 11453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 1159769ab22265b313171d201b5928688524a01bd87Misha Brukman 116b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 117b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman S.print(OS); 118b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman return OS; 119b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman } 120b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman 12153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 12253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner S.print(OS); 12353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner return OS; 12453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner } 12553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 12653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// SCEVCouldNotCompute - An object of this class is returned by queries that 12753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// could not be answered. For example, if you ask for the number of 12853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// iterations of a linked-list traversal loop, you will get one of these. 12953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// None of the standard SCEV operations are valid on this class, it is just a 13053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// marker. 13153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner struct SCEVCouldNotCompute : public SCEV { 132753ad615f96c3d56d6f17983bdba88012e88677cOwen Anderson SCEVCouldNotCompute(); 13353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 13453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner // None of these methods are valid for this object. 13553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool isLoopInvariant(const Loop *L) const; 13653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual const Type *getType() const; 13753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const; 138b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 139372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson virtual const SCEV* 140372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson replaceSymbolicValuesWithConcrete(const SCEV* Sym, 141372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Conc, 142246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 14353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 1445a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 1455a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 1465a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 1475a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 14853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 14953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 15053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner static bool classof(const SCEV *S); 15153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 15253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 15353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// ScalarEvolution - This class is the main scalar evolution driver. Because 15453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// client code (intentionally) can't do much with the SCEV objects directly, 15553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// they must ask this class for services. 15653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 15753e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner class ScalarEvolution : public FunctionPass { 1581959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 1591959b7562e57f8394496e761486f23b187ac3f1bDan Gohman /// notified whenever a Value is deleted. 1601959b7562e57f8394496e761486f23b187ac3f1bDan Gohman class SCEVCallbackVH : public CallbackVH { 1611959b7562e57f8394496e761486f23b187ac3f1bDan Gohman ScalarEvolution *SE; 1621959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void deleted(); 1631959b7562e57f8394496e761486f23b187ac3f1bDan Gohman virtual void allUsesReplacedWith(Value *New); 1641959b7562e57f8394496e761486f23b187ac3f1bDan Gohman public: 1651959b7562e57f8394496e761486f23b187ac3f1bDan Gohman SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 1661959b7562e57f8394496e761486f23b187ac3f1bDan Gohman }; 1671959b7562e57f8394496e761486f23b187ac3f1bDan Gohman 16835738ac150afafe2359268d4b2169498c6c98c5fDan Gohman friend class SCEVCallbackVH; 1695be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman friend class SCEVExpander; 17035738ac150afafe2359268d4b2169498c6c98c5fDan Gohman 171f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// F - The function we are analyzing. 172f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 173f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Function *F; 174f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 175f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// LI - The loop information for the function we are currently analyzing. 176f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 177f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman LoopInfo *LI; 178f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 179f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// TD - The target data information for the target we are targetting. 180f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 181f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman TargetData *TD; 182f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 18386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute - This SCEV is used to represent unknown trip 18486fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// counts and things. 185372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* CouldNotCompute; 186f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 187f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Scalars - This is a cache of the scalars we have analyzed so far. 188f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// 189372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson std::map<SCEVCallbackVH, const SCEV*> Scalars; 190f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 191a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// BackedgeTakenInfo - Information about the backedge-taken count 192a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// of a loop. This currently inclues an exact count and a maximum count. 193a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// 194a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman struct BackedgeTakenInfo { 195a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the exact backedge-taken count of 196a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 197372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Exact; 198a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 199a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// Exact - An expression indicating the least maximum backedge-taken 200a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// count of the loop that is known, or a SCEVCouldNotCompute. 201372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Max; 202a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 203372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson /*implicit*/ BackedgeTakenInfo(const SCEV* exact) : 204a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(exact) {} 205a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 206372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson BackedgeTakenInfo(const SCEV* exact, const SCEV* max) : 207a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman Exact(exact), Max(max) {} 208a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 209a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 210a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// computed information, or whether it's all SCEVCouldNotCompute 211a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// values. 212a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman bool hasAnyInfo() const { 213a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman return !isa<SCEVCouldNotCompute>(Exact) || 214a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman !isa<SCEVCouldNotCompute>(Max); 215a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman } 216a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman }; 217a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 218f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 219f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// this function as they are computed. 220a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 221f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 222f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ConstantEvolutionLoopExitValue - This map contains entries for all of 223f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// the PHI instructions that we attempt to compute constant evolutions for. 224f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// This allows us to avoid potentially expensive recomputation of these 225f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// properties. An instruction maps to null if we are unable to compute its 226f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// exit value. 227f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 228f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 2296bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// ValuesAtScopes - This map contains entries for all the instructions 2306bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// that we attempt to compute getSCEVAtScope information for without 2316bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman /// using SCEV techniques, which can be expensive. 2326bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 2336bce643c36e7263aada5058f08cd242b4ce6b87dDan Gohman 234f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createSCEV - We know that there is no SCEV for the specified value. 235f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// Analyze the expression. 236372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* createSCEV(Value *V); 237f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 238f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// createNodeForPHI - Provide the special handling we need to analyze PHI 239f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// SCEVs. 240372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* createNodeForPHI(PHINode *PN); 241f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 24226466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// createNodeForGEP - Provide the special handling we need to analyze GEP 24326466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman /// SCEVs. 244372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* createNodeForGEP(User *GEP); 24526466c0eb3451c5c953b3cca8940359152c4f8e3Dan Gohman 246f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 247f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// for the specified instruction and replaces any references to the 248f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// symbolic value SymName with the specified value. This is used during 249f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// PHI resolution. 250f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman void ReplaceSymbolicValueWithConcrete(Instruction *I, 251372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* SymName, 252372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* NewVal); 253f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 25451f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// getBECount - Subtract the end and start values and divide by the step, 25551f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// rounding up, to get the number of times the backedge is executed. Return 25651f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman /// CouldNotCompute if an intermediate computation overflows. 257372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getBECount(const SCEV* Start, 258372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* End, 259372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Step); 26051f53b7f5a0e859ceef995c61667905166b96f1bDan Gohman 261a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 262a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// loop, lazily computing new values if the loop hasn't been analyzed 263a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// yet. 264a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 265a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 266f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCount - Compute the number of times the specified 267f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// loop will iterate. 268a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 269f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 270a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 271a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if it exits via the 272a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// specified block. 273a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 274a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *ExitingBlock); 275a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 276a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 277a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// backedge of the specified loop will execute if its exit condition 278a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// were a conditional branch of ExitCond, TBB, and FBB. 279a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 280a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCond(const Loop *L, 281a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman Value *ExitCond, 282a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 283a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 284a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 285a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 286a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// times the backedge of the specified loop will execute if its exit 287a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 288a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// and FBB. 289a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BackedgeTakenInfo 290a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 291a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman ICmpInst *ExitCond, 292a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *TBB, 293a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman BasicBlock *FBB); 294a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 295f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 296f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// of 'icmp op load X, cst', try to see if we can compute the trip count. 297372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* 298f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 299f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *RHS, 300f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L, 301f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ICmpInst::Predicate p); 302f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 303f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 304f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// a constant number of times (the condition evolves only from constants), 305f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// try to evaluate a few iterations of the loop until we get the exit 306f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// condition gets a value of ExitWhen (true or false). If we cannot 30786fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// evaluate the trip count of the loop, return CouldNotCompute. 308372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, 309f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool ExitWhen); 310f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 311f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToZero - Return the number of times a backedge comparing the 312f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value to zero will execute. If not computable, return 31386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 314372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* HowFarToZero(const SCEV *V, const Loop *L); 315f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 316f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowFarToNonZero - Return the number of times a backedge checking the 317f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified value for nonzero will execute. If not computable, return 31886fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. 319372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* HowFarToNonZero(const SCEV *V, const Loop *L); 320f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 321f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// HowManyLessThans - Return the number of times a backedge containing the 322f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// specified less-than comparison will execute. If not computable, return 32386fbf2fe4cae21febffa4bb2f64cd0c2ee834694Dan Gohman /// CouldNotCompute. isSigned specifies whether the less-than is signed. 32435738ac150afafe2359268d4b2169498c6c98c5fDan Gohman BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 32535738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const Loop *L, bool isSigned); 326f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 327859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// getLoopPredecessor - If the given loop's header has exactly one unique 328859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman /// predecessor outside the loop, return it. Otherwise return null. 329859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman BasicBlock *getLoopPredecessor(const Loop *L); 330859b4824eeb2d88c441e855afe3dd7827dfd62a4Dan Gohman 331f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 332f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// (which may not be an immediate predecessor) which has exactly one 333f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// successor from which BB is reachable, or null if no such block is 334f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// found. 335f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 336f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 337f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 338f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// in the header of its containing loop, we know the loop executes a 339f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// constant number of times, and the PHI node is just a recurrence 340f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman /// involving constants, fold it. 341f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 342f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman const Loop *L); 343f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman 344fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// forgetLoopPHIs - Delete the memoized SCEVs associated with the 345fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// PHI nodes in the given loop. This is used when the trip count of 346fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman /// the loop may have changed. 347fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman void forgetLoopPHIs(const Loop *L); 348fb7d35f22a958747dd3ae8861ae3ce018146131cDan Gohman 34953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner public: 350ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 351f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman ScalarEvolution(); 3529769ab22265b313171d201b5928688524a01bd87Misha Brukman 353af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// isSCEVable - Test if values of the given type are analyzable within 354af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the SCEV framework. This primarily includes integer types, and it 355af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// can optionally include pointer types if the ScalarEvolution class 356af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// has access to target-specific information. 357af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman bool isSCEVable(const Type *Ty) const; 358af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 359af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getTypeSizeInBits - Return the size in bits of the specified type, 360af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// for which isSCEVable must return true. 361af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman uint64_t getTypeSizeInBits(const Type *Ty) const; 362af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 363af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// getEffectiveSCEVType - Return a type with the same bitwidth as 364af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// the given type and which represents how SCEV will treat the given 365af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// type, for which isSCEVable must return true. For pointer types, 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// this is the pointer-sized integer type. 367af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *getEffectiveSCEVType(const Type *Ty) const; 3682d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 36953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEV - Return a SCEV expression handle for the full generality of the 37053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified expression. 371372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSCEV(Value *V); 372372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson 373372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getConstant(ConstantInt *V); 374372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getConstant(const APInt& Val); 375372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 376372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getTruncateExpr(const SCEV* Op, const Type *Ty); 377372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getZeroExtendExpr(const SCEV* Op, const Type *Ty); 378372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSignExtendExpr(const SCEV* Op, const Type *Ty); 379372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAnyExtendExpr(const SCEV* Op, const Type *Ty); 380372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddExpr(SmallVectorImpl<const SCEV*> &Ops); 381372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddExpr(const SCEV* LHS, const SCEV* RHS) { 382372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 2> Ops; 383246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 384246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 385246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 386246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 387372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddExpr(const SCEV* Op0, const SCEV* Op1, 388372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Op2) { 389372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 3> Ops; 390246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op0); 391246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op1); 392246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(Op2); 393246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddExpr(Ops); 394246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 395372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getMulExpr(SmallVectorImpl<const SCEV*> &Ops); 396372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getMulExpr(const SCEV* LHS, const SCEV* RHS) { 397372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 2> Ops; 398246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(LHS); 399246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Ops.push_back(RHS); 400246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getMulExpr(Ops); 401246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 402372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUDivExpr(const SCEV* LHS, const SCEV* RHS); 403372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddRecExpr(const SCEV* Start, const SCEV* Step, 404246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 405372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands, 406246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L); 407372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getAddRecExpr(const SmallVectorImpl<const SCEV*> &Operands, 408246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const Loop *L) { 409372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 4> NewOp(Operands.begin(), Operands.end()); 410246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return getAddRecExpr(NewOp, L); 411246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman } 412372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSMaxExpr(const SCEV* LHS, const SCEV* RHS); 413372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSMaxExpr(SmallVectorImpl<const SCEV*> &Operands); 414372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUMaxExpr(const SCEV* LHS, const SCEV* RHS); 415372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUMaxExpr(SmallVectorImpl<const SCEV*> &Operands); 416372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSMinExpr(const SCEV* LHS, const SCEV* RHS); 417372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUMinExpr(const SCEV* LHS, const SCEV* RHS); 418372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUnknown(Value *V); 419372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getCouldNotCompute(); 420246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 421246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getNegativeSCEV - Return the SCEV object corresponding to -V. 422246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 423372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getNegativeSCEV(const SCEV* V); 424246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4253e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// getNotSCEV - Return the SCEV object corresponding to ~V. 4263e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 427372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getNotSCEV(const SCEV* V); 4283e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 429246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// getMinusSCEV - Return LHS-RHS. 430246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// 431372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getMinusSCEV(const SCEV* LHS, 432372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* RHS); 433246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 4346f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 4356f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// of the input value to the specified type. If the type must be 4366f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky /// extended, it is zero extended. 437372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getTruncateOrZeroExtend(const SCEV* V, const Type *Ty); 4386f8abf929ac173872cc50aff767bc25f2a07a523Nick Lewycky 439f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 440f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// of the input value to the specified type. If the type must be 441f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman /// extended, it is sign extended. 442372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getTruncateOrSignExtend(const SCEV* V, const Type *Ty); 443f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman 444467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 445467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 446467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is zero extended. The conversion must not be narrowing. 447372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getNoopOrZeroExtend(const SCEV* V, const Type *Ty); 448467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 449467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 450467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// the input value to the specified type. If the type must be extended, 451467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// it is sign extended. The conversion must not be narrowing. 452372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getNoopOrSignExtend(const SCEV* V, const Type *Ty); 453467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 4542ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 4552ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// the input value to the specified type. If the type must be extended, 4562ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// it is extended with unspecified bits. The conversion must not be 4572ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman /// narrowing. 458372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getNoopOrAnyExtend(const SCEV* V, const Type *Ty); 4592ce84c8d4784dfd24458a63db8d531917d2f8ba5Dan Gohman 460467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 461467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// input value to the specified type. The conversion must not be 462467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman /// widening. 463372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getTruncateOrNoop(const SCEV* V, const Type *Ty); 464467c430316b7a5b6fa8069531ca8d603b1e1197fDan Gohman 4656bbcba18db6d1f4bc0f0157df41cc02627bc4aa9Dan Gohman /// getIntegerSCEV - Given a SCEVable type, create a constant for the 466246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman /// specified signed integer value and return a SCEV for the constant. 467372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getIntegerSCEV(int Val, const Type *Ty); 468246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 469a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 470a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// the types using zero-extension, and then perform a umax operation 471a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman /// with them. 472372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUMaxFromMismatchedTypes(const SCEV* LHS, 473372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* RHS); 474a334aa7a106d5ebb971862f25daaadad48d96235Dan Gohman 475c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// getUMinFromMismatchedTypes - Promote the operands to the wider of 476c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// the types using zero-extension, and then perform a umin operation 477c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman /// with them. 478372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getUMinFromMismatchedTypes(const SCEV* LHS, 479372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* RHS); 480c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9cDan Gohman 48127631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// hasSCEV - Return true if the SCEV for this value has already been 48227631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// computed. 48327631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner bool hasSCEV(Value *V) const; 48427631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 48527631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 48627631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner /// the specified value. 487372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson void setSCEV(Value *V, const SCEV* H); 48827631a30eb1c5cb1c5190531b10a147f058d6ff1Chris Lattner 48953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// getSCEVAtScope - Return a SCEV expression handle for the specified value 49053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// at the specified scope in the program. The L value specifies a loop 49153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// nest to evaluate the expression at, where null is the top-level or a 49253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// specified loop is immediately inside of the loop. 49353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 49453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// This method can be used to compute the exit value for a variable defined 49553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// in a loop by querying what the value will hold in the parent loop. 49653e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner /// 497d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// In the case that a relevant loop exit value cannot be computed, the 498d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman /// original value V is returned. 499372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSCEVAtScope(const SCEV *S, const Loop *L); 50066a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman 50166a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope - This is a convenience function which does 50266a7e857aa5843da3a7d0f52aa09a5935cf565dcDan Gohman /// getSCEVAtScope(getSCEV(V), L). 503372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getSCEVAtScope(Value *V, const Loop *L); 50453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 505c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// isLoopGuardedByCond - Test whether entry to the loop is protected by 5063d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// a conditional between LHS and RHS. This is used to help avoid max 5073d739fe3756bf67be23c2ca54ec7b04bef89bfe0Dan Gohman /// expressions in loop trip counts. 508c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 50935738ac150afafe2359268d4b2169498c6c98c5fDan Gohman const SCEV *LHS, const SCEV *RHS); 510c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 51146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// getBackedgeTakenCount - If the specified loop has a predictable 51246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 51346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// object. The backedge-taken count is the number of times the loop header 51446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// will be branched to from within the loop. This is one less than the 51546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// trip count of the loop, since it doesn't count the first iteration, 51646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// when the header is branched to from outside the loop. 51746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 51846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// Note that it is not valid to call this method on a loop without a 51946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// loop-invariant backedge-taken count (see 52046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount). 52146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// 522372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getBackedgeTakenCount(const Loop *L); 52353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 524a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 525a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// return the least SCEV value that is known never to be less than the 526a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman /// actual backedge taken count. 527372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* getMaxBackedgeTakenCount(const Loop *L); 528a1af757e0af9c2fb5ade4b06408e1adfa0425c6cDan Gohman 52946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 53046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// has an analyzable loop-invariant backedge-taken count. 531f8a8be86e3972608741c1e1ecb89ec3c6f570552Dan Gohman bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 53253e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 53346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// forgetLoopBackedgeTakenCount - This method should be called by the 53460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman /// client when it has changed a loop in a way that may effect 53546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// ScalarEvolution's ability to compute a trip count, or if the loop 53646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman /// is deleted. 53746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void forgetLoopBackedgeTakenCount(const Loop *L); 53860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 5392c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 5402c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to end in (at every loop iteration). It is, at the same time, 5412c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// the minimum number of times S is divisible by 2. For example, given {4,+,8} 5422c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 543372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson uint32_t GetMinTrailingZeros(const SCEV* S); 5442c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 5452c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is 5462c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to begin with (at every loop iteration). 547372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson uint32_t GetMinLeadingZeros(const SCEV* S); 5482c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 5492c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// GetMinSignBits - Determine the minimum number of sign bits that S is 5502c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman /// guaranteed to begin with. 551372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson uint32_t GetMinSignBits(const SCEV* S); 5522c364ad4a65737f3bda876f86eba0061ecbd5470Dan Gohman 55353e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual bool runOnFunction(Function &F); 55453e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void releaseMemory(); 55553e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 556b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS, const Module* = 0) const; 557ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer virtual void print(std::ostream &OS, const Module* = 0) const; 5585c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS, const Module* M = 0) const { 5595c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (OS) print(*OS, M); 5605c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 56108367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson 56208367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson private: 56308367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson // Uniquing tables. 56408367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<ConstantInt*, SCEVConstant*> SCEVConstants; 56508367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<const SCEV*, const Type*>, 56608367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVTruncateExpr*> SCEVTruncates; 56708367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<const SCEV*, const Type*>, 56808367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVZeroExtendExpr*> SCEVZeroExtends; 56908367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<unsigned, std::vector<const SCEV*> >, 57008367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVCommutativeExpr*> SCEVCommExprs; 57108367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<const SCEV*, const SCEV*>, 57208367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVUDivExpr*> SCEVUDivs; 57308367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<const SCEV*, const Type*>, 57408367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVSignExtendExpr*> SCEVSignExtends; 57508367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<std::pair<const Loop *, std::vector<const SCEV*> >, 57608367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson SCEVAddRecExpr*> SCEVAddRecExprs; 57708367b61638b4d446ebab69e2aad6431daa77ba7Owen Anderson std::map<Value*, SCEVUnknown*> SCEVUnknowns; 57853e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner }; 57953e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner} 58053e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner 58153e677abadadf71ef33f2f69533a32c1fa3d168fChris Lattner#endif 582