ScalarEvolution.h revision f9a9a9928cc977970d9852292b1c139074ecf055
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 91320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The ScalarEvolution class is an LLVM pass which can be used to analyze and 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// catagorize scalar expressions in loops. It specializes in recognizing 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// general induction variables, representing them with the abstract and opaque 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SCEV class. Given this analysis, trip counts of loops and other important 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// properties can be obtained. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This analysis is primarily useful for induction variable substitution and 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// strength reduction. 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LLVM_ANALYSIS_SCALAREVOLUTION_H 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Pass.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Analysis/LoopInfo.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/DataTypes.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/ValueHandle.h" 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/DenseMap.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <iosfwd> 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace llvm { 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class APInt; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class ConstantInt; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class Type; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVHandle; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class ScalarEvolution; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class TargetData; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<> struct DenseMapInfo<SCEVHandle>; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEV - This class represents an analyzed expression in the program. These 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// are reference-counted opaque objects that the client is not allowed to 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// do much with directly. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEV { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const unsigned SCEVType; // The SCEV baseclass this node corresponds to 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mutable unsigned RefCount; 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class SCEVHandle; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class DenseMapInfo<SCEVHandle>; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addRef() const { ++RefCount; } 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void dropRef() const { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (--RefCount == 0) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete this; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ScalarEvolution* parent; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEV(const SCEV &); // DO NOT IMPLEMENT 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void operator=(const SCEV &); // DO NOT IMPLEMENT 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) protected: 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~SCEV(); 6223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) public: 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit SCEV(unsigned SCEVTy, const ScalarEvolution* p) : 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVType(SCEVTy), RefCount(0), parent(p) {} 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned getSCEVType() const { return SCEVType; } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 68effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 69effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch /// the specified loop. 70effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch virtual bool isLoopInvariant(const Loop *L) const = 0; 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// known way in the specified loop. This property being true implies that 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the value is variant in the loop AND that we can emit an expression to 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// compute the value of the expression at any particular loop iteration. 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getType - Return the LLVM type of this SCEV expression. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual const Type *getType() const = 0; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 82cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// isZero - Return true if the expression is a constant zero. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isZero() const; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isOne - Return true if the expression is a constant one. 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isOne() const; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 9146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// the symbolic value "Sym", construct and return a new SCEV that produces 921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// the same value, but which uses the concrete value Conc instead of the 9346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) /// symbolic value. If this SCEV does not use the symbolic value, it 941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// returns itself. 951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci virtual SCEVHandle 961320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 971320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const SCEVHandle &Conc, 981320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ScalarEvolution &SE) const = 0; 9946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// dominates - Return true if elements that makes up this SCEV dominates 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the specified basic block. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// print - Print out the internal representation of this scalar to the 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// specified stream. This should really only be used for debugging 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// purposes. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void print(raw_ostream &OS) const = 0; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void print(std::ostream &OS) const; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void print(std::ostream *OS) const { if (OS) print(*OS); } 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// dump - This method is used for debugging. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void dump() const; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S.print(OS); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OS; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S.print(OS); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OS; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVCouldNotCompute - An object of this class is returned by queries that 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// could not be answered. For example, if you ask for the number of 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// iterations of a linked-list traversal loop, you will get one of these. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// None of the standard SCEV operations are valid on this class, it is just a 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// marker. 13158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) struct SCEVCouldNotCompute : public SCEV { 13258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) SCEVCouldNotCompute(const ScalarEvolution* p); 13358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) ~SCEVCouldNotCompute(); 134f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 135f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // None of these methods are valid for this object. 136f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) virtual bool isLoopInvariant(const Loop *L) const; 137f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) virtual const Type *getType() const; 138f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) virtual bool hasComputableLoopEvolution(const Loop *L) const; 1391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci virtual void print(raw_ostream &OS) const; 1401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci virtual SCEVHandle 1411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 142f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) const SCEVHandle &Conc, 143f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) ScalarEvolution &SE) const; 144f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 145f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 146f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return true; 147a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 148f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 149f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 150f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 1511320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci static bool classof(const SCEV *S); 1521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci }; 1531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 1551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// freeing the objects when the last reference is dropped. 1561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci class SCEVHandle { 157f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) const SCEV *S; 158f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) SCEVHandle(); // DO NOT IMPLEMENT 159a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) public: 160f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) SCEVHandle(const SCEV *s) : S(s) { 161a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) assert(S && "Cannot create a handle to a null SCEV!"); 162f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) S->addRef(); 163f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 164f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 165f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) S->addRef(); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SCEVHandle() { S->dropRef(); } 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) operator const SCEV*() const { return S; } 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV &operator*() const { return *S; } 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *operator->() const { return S; } 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator==(const SCEV *RHS) const { return S == RHS; } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator!=(const SCEV *RHS) const { return S != RHS; } 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &operator=(SCEV *RHS) { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (S != RHS) { 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->dropRef(); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S = RHS; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->addRef(); 1821e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) } 1831e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) return *this; 1841e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) } 1851e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &operator=(const SCEVHandle &RHS) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (S != RHS.S) { 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->dropRef(); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S = RHS.S; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->addRef(); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return *this; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<typename From> struct simplify_type; 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) template<> struct simplify_type<const SCEVHandle> { 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef const SCEV* SimpleType; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Node; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<> struct simplify_type<SCEVHandle> 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : public simplify_type<const SCEVHandle> {}; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Specialize DenseMapInfo for SCEVHandle so that SCEVHandle may be used 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // as a key in DenseMaps. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<> 20923730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) struct DenseMapInfo<SCEVHandle> { 21023730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) static inline SCEVHandle getEmptyKey() { 21123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) static SCEVCouldNotCompute Empty(0); 21223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) if (Empty.RefCount == 0) 21323730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) Empty.addRef(); 21423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) return &Empty; 215effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch } 216effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch static inline SCEVHandle getTombstoneKey() { 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static SCEVCouldNotCompute Tombstone(0); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Tombstone.RefCount == 0) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tombstone.addRef(); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &Tombstone; 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static unsigned getHashValue(const SCEVHandle &Val) { 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return DenseMapInfo<const SCEV *>::getHashValue(Val); 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool isEqual(const SCEVHandle &LHS, const SCEVHandle &RHS) { 226cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return LHS == RHS; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool isPod() { return false; } 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ScalarEvolution - This class is the main scalar evolution driver. Because 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// client code (intentionally) can't do much with the SCEV objects directly, 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// they must ask this class for services. 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class ScalarEvolution : public FunctionPass { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// notified whenever a Value is deleted. 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVCallbackVH : public CallbackVH { 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ScalarEvolution *SE; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void deleted(); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void allUsesReplacedWith(Value *New); 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class SCEVCallbackVH; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class SCEVExpander; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// F - The function we are analyzing. 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Function *F; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// LI - The loop information for the function we are currently analyzing. 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LoopInfo *LI; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// TD - The target data information for the target we are targetting. 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TargetData *TD; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// CouldNotCompute - This SCEV is used to represent unknown trip 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// counts and things. 26358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) SCEVHandle CouldNotCompute; 26458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 265f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// Scalars - This is a cache of the scalars we have analyzed so far. 266f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// 267f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) std::map<SCEVCallbackVH, SCEVHandle> Scalars; 268f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 269a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) /// BackedgeTakenInfo - Information about the backedge-taken count 270f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// of a loop. This currently inclues an exact count and a maximum count. 271a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) /// 2721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci struct BackedgeTakenInfo { 2731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// Exact - An expression indicating the exact backedge-taken count of 2741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 2751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci SCEVHandle Exact; 276f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 277f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// Exact - An expression indicating the least maximum backedge-taken 278f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// count of the loop that is known, or a SCEVCouldNotCompute. 279f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) SCEVHandle Max; 280f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 281f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : 282a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Exact(exact), Max(exact) {} 283a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 284f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 285a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Exact(exact), Max(exact) {} 286a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 2871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : 2881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci Exact(exact), Max(max) {} 2891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 2901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 2911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// computed information, or whether it's all SCEVCouldNotCompute 2921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// values. 2931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool hasAnyInfo() const { 294f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return !isa<SCEVCouldNotCompute>(Exact) || 295f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) !isa<SCEVCouldNotCompute>(Max); 296a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 297f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) }; 298f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 299f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 300f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// this function as they are computed. 301f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 302f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 303f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /// ConstantEvolutionLoopExitValue - This map contains entries for all of 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the PHI instructions that we attempt to compute constant evolutions for. 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// This allows us to avoid potentially expensive recomputation of these 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// properties. An instruction maps to null if we are unable to compute its 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// exit value. 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ValuesAtScopes - This map contains entries for all the instructions 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// that we attempt to compute getSCEVAtScope information for without 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// using SCEV techniques, which can be expensive. 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// createSCEV - We know that there is no SCEV for the specified value. 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Analyze the expression. 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVHandle createSCEV(Value *V); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// createNodeForPHI - Provide the special handling we need to analyze PHI 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVs. 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVHandle createNodeForPHI(PHINode *PN); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// createNodeForGEP - Provide the special handling we need to analyze GEP 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVs. 3251e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) SCEVHandle createNodeForGEP(User *GEP); 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// for the specified instruction and replaces any references to the 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// symbolic value SymName with the specified value. This is used during 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// PHI resolution. 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ReplaceSymbolicValueWithConcrete(Instruction *I, 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &SymName, 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &NewVal); 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getBECount - Subtract the end and start values and divide by the step, 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// rounding up, to get the number of times the backedge is executed. Return 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// CouldNotCompute if an intermediate computation overflows. 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVHandle getBECount(const SCEVHandle &Start, 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &End, 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEVHandle &Step); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 343 /// loop, lazily computing new values if the loop hasn't been analyzed 344 /// yet. 345 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 346 347 /// ComputeBackedgeTakenCount - Compute the number of times the specified 348 /// loop will iterate. 349 BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 350 351 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 352 /// backedge of the specified loop will execute if it exits via the 353 /// specified block. 354 BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 355 BasicBlock *ExitingBlock); 356 357 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 358 /// backedge of the specified loop will execute if its exit condition 359 /// were a conditional branch of ExitCond, TBB, and FBB. 360 BackedgeTakenInfo 361 ComputeBackedgeTakenCountFromExitCond(const Loop *L, 362 Value *ExitCond, 363 BasicBlock *TBB, 364 BasicBlock *FBB); 365 366 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 367 /// times the backedge of the specified loop will execute if its exit 368 /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 369 /// and FBB. 370 BackedgeTakenInfo 371 ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 372 ICmpInst *ExitCond, 373 BasicBlock *TBB, 374 BasicBlock *FBB); 375 376 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 377 /// of 'icmp op load X, cst', try to see if we can compute the trip count. 378 SCEVHandle 379 ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 380 Constant *RHS, 381 const Loop *L, 382 ICmpInst::Predicate p); 383 384 /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 385 /// a constant number of times (the condition evolves only from constants), 386 /// try to evaluate a few iterations of the loop until we get the exit 387 /// condition gets a value of ExitWhen (true or false). If we cannot 388 /// evaluate the trip count of the loop, return CouldNotCompute. 389 SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, 390 bool ExitWhen); 391 392 /// HowFarToZero - Return the number of times a backedge comparing the 393 /// specified value to zero will execute. If not computable, return 394 /// CouldNotCompute. 395 SCEVHandle HowFarToZero(const SCEV *V, const Loop *L); 396 397 /// HowFarToNonZero - Return the number of times a backedge checking the 398 /// specified value for nonzero will execute. If not computable, return 399 /// CouldNotCompute. 400 SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L); 401 402 /// HowManyLessThans - Return the number of times a backedge containing the 403 /// specified less-than comparison will execute. If not computable, return 404 /// CouldNotCompute. isSigned specifies whether the less-than is signed. 405 BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 406 const Loop *L, bool isSigned); 407 408 /// getLoopPredecessor - If the given loop's header has exactly one unique 409 /// predecessor outside the loop, return it. Otherwise return null. 410 BasicBlock *getLoopPredecessor(const Loop *L); 411 412 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 413 /// (which may not be an immediate predecessor) which has exactly one 414 /// successor from which BB is reachable, or null if no such block is 415 /// found. 416 BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 417 418 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 419 /// in the header of its containing loop, we know the loop executes a 420 /// constant number of times, and the PHI node is just a recurrence 421 /// involving constants, fold it. 422 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 423 const Loop *L); 424 425 /// forgetLoopPHIs - Delete the memoized SCEVs associated with the 426 /// PHI nodes in the given loop. This is used when the trip count of 427 /// the loop may have changed. 428 void forgetLoopPHIs(const Loop *L); 429 430 public: 431 static char ID; // Pass identification, replacement for typeid 432 ScalarEvolution(); 433 434 /// isSCEVable - Test if values of the given type are analyzable within 435 /// the SCEV framework. This primarily includes integer types, and it 436 /// can optionally include pointer types if the ScalarEvolution class 437 /// has access to target-specific information. 438 bool isSCEVable(const Type *Ty) const; 439 440 /// getTypeSizeInBits - Return the size in bits of the specified type, 441 /// for which isSCEVable must return true. 442 uint64_t getTypeSizeInBits(const Type *Ty) const; 443 444 /// getEffectiveSCEVType - Return a type with the same bitwidth as 445 /// the given type and which represents how SCEV will treat the given 446 /// type, for which isSCEVable must return true. For pointer types, 447 /// this is the pointer-sized integer type. 448 const Type *getEffectiveSCEVType(const Type *Ty) const; 449 450 /// getSCEV - Return a SCEV expression handle for the full generality of the 451 /// specified expression. 452 SCEVHandle getSCEV(Value *V); 453 454 SCEVHandle getConstant(ConstantInt *V); 455 SCEVHandle getConstant(const APInt& Val); 456 SCEVHandle getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 457 SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 458 SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 459 SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 460 SCEVHandle getAnyExtendExpr(const SCEVHandle &Op, const Type *Ty); 461 SCEVHandle getAddExpr(SmallVectorImpl<SCEVHandle> &Ops); 462 SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 463 SmallVector<SCEVHandle, 2> Ops; 464 Ops.push_back(LHS); 465 Ops.push_back(RHS); 466 return getAddExpr(Ops); 467 } 468 SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 469 const SCEVHandle &Op2) { 470 SmallVector<SCEVHandle, 3> Ops; 471 Ops.push_back(Op0); 472 Ops.push_back(Op1); 473 Ops.push_back(Op2); 474 return getAddExpr(Ops); 475 } 476 SCEVHandle getMulExpr(SmallVectorImpl<SCEVHandle> &Ops); 477 SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 478 SmallVector<SCEVHandle, 2> Ops; 479 Ops.push_back(LHS); 480 Ops.push_back(RHS); 481 return getMulExpr(Ops); 482 } 483 SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 484 SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 485 const Loop *L); 486 SCEVHandle getAddRecExpr(SmallVectorImpl<SCEVHandle> &Operands, 487 const Loop *L); 488 SCEVHandle getAddRecExpr(const SmallVectorImpl<SCEVHandle> &Operands, 489 const Loop *L) { 490 SmallVector<SCEVHandle, 4> NewOp(Operands.begin(), Operands.end()); 491 return getAddRecExpr(NewOp, L); 492 } 493 SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 494 SCEVHandle getSMaxExpr(SmallVectorImpl<SCEVHandle> &Operands); 495 SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 496 SCEVHandle getUMaxExpr(SmallVectorImpl<SCEVHandle> &Operands); 497 SCEVHandle getSMinExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 498 SCEVHandle getUMinExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 499 SCEVHandle getUnknown(Value *V); 500 SCEVHandle getCouldNotCompute(); 501 502 /// getNegativeSCEV - Return the SCEV object corresponding to -V. 503 /// 504 SCEVHandle getNegativeSCEV(const SCEVHandle &V); 505 506 /// getNotSCEV - Return the SCEV object corresponding to ~V. 507 /// 508 SCEVHandle getNotSCEV(const SCEVHandle &V); 509 510 /// getMinusSCEV - Return LHS-RHS. 511 /// 512 SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 513 const SCEVHandle &RHS); 514 515 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 516 /// of the input value to the specified type. If the type must be 517 /// extended, it is zero extended. 518 SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); 519 520 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 521 /// of the input value to the specified type. If the type must be 522 /// extended, it is sign extended. 523 SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); 524 525 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 526 /// the input value to the specified type. If the type must be extended, 527 /// it is zero extended. The conversion must not be narrowing. 528 SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty); 529 530 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 531 /// the input value to the specified type. If the type must be extended, 532 /// it is sign extended. The conversion must not be narrowing. 533 SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty); 534 535 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 536 /// the input value to the specified type. If the type must be extended, 537 /// it is extended with unspecified bits. The conversion must not be 538 /// narrowing. 539 SCEVHandle getNoopOrAnyExtend(const SCEVHandle &V, const Type *Ty); 540 541 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 542 /// input value to the specified type. The conversion must not be 543 /// widening. 544 SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty); 545 546 /// getIntegerSCEV - Given an integer or FP type, create a constant for the 547 /// specified signed integer value and return a SCEV for the constant. 548 SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 549 550 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 551 /// the types using zero-extension, and then perform a umax operation 552 /// with them. 553 SCEVHandle getUMaxFromMismatchedTypes(const SCEVHandle &LHS, 554 const SCEVHandle &RHS); 555 556 /// hasSCEV - Return true if the SCEV for this value has already been 557 /// computed. 558 bool hasSCEV(Value *V) const; 559 560 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 561 /// the specified value. 562 void setSCEV(Value *V, const SCEVHandle &H); 563 564 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 565 /// at the specified scope in the program. The L value specifies a loop 566 /// nest to evaluate the expression at, where null is the top-level or a 567 /// specified loop is immediately inside of the loop. 568 /// 569 /// This method can be used to compute the exit value for a variable defined 570 /// in a loop by querying what the value will hold in the parent loop. 571 /// 572 /// In the case that a relevant loop exit value cannot be computed, the 573 /// original value V is returned. 574 SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L); 575 576 /// getSCEVAtScope - This is a convenience function which does 577 /// getSCEVAtScope(getSCEV(V), L). 578 SCEVHandle getSCEVAtScope(Value *V, const Loop *L); 579 580 /// isLoopGuardedByCond - Test whether entry to the loop is protected by 581 /// a conditional between LHS and RHS. This is used to help avoid max 582 /// expressions in loop trip counts. 583 bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 584 const SCEV *LHS, const SCEV *RHS); 585 586 /// getBackedgeTakenCount - If the specified loop has a predictable 587 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 588 /// object. The backedge-taken count is the number of times the loop header 589 /// will be branched to from within the loop. This is one less than the 590 /// trip count of the loop, since it doesn't count the first iteration, 591 /// when the header is branched to from outside the loop. 592 /// 593 /// Note that it is not valid to call this method on a loop without a 594 /// loop-invariant backedge-taken count (see 595 /// hasLoopInvariantBackedgeTakenCount). 596 /// 597 SCEVHandle getBackedgeTakenCount(const Loop *L); 598 599 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 600 /// return the least SCEV value that is known never to be less than the 601 /// actual backedge taken count. 602 SCEVHandle getMaxBackedgeTakenCount(const Loop *L); 603 604 /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 605 /// has an analyzable loop-invariant backedge-taken count. 606 bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 607 608 /// forgetLoopBackedgeTakenCount - This method should be called by the 609 /// client when it has changed a loop in a way that may effect 610 /// ScalarEvolution's ability to compute a trip count, or if the loop 611 /// is deleted. 612 void forgetLoopBackedgeTakenCount(const Loop *L); 613 614 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 615 /// guaranteed to end in (at every loop iteration). It is, at the same time, 616 /// the minimum number of times S is divisible by 2. For example, given {4,+,8} 617 /// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 618 uint32_t GetMinTrailingZeros(const SCEVHandle &S); 619 620 /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is 621 /// guaranteed to begin with (at every loop iteration). 622 uint32_t GetMinLeadingZeros(const SCEVHandle &S); 623 624 /// GetMinSignBits - Determine the minimum number of sign bits that S is 625 /// guaranteed to begin with. 626 uint32_t GetMinSignBits(const SCEVHandle &S); 627 628 virtual bool runOnFunction(Function &F); 629 virtual void releaseMemory(); 630 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 631 void print(raw_ostream &OS, const Module* = 0) const; 632 virtual void print(std::ostream &OS, const Module* = 0) const; 633 void print(std::ostream *OS, const Module* M = 0) const { 634 if (OS) print(*OS, M); 635 } 636 }; 637} 638 639#endif 640