ScalarEvolutionExpressions.h revision 5c7e326585f3a543388ba871c3425f7664cd9143
14950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 34950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// The LLVM Compiler Infrastructure 44950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 54950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file was developed by the LLVM research group and is distributed under 64950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 84950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 94950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file defines the classes used to represent and build scalar expressions. 119769ab22265b313171d201b5928688524a01bd87Misha Brukman// 124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#include "llvm/Analysis/ScalarEvolution.h" 184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattnernamespace llvm { 204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantInt; 214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantRange; 224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner enum SCEVTypes { 244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // These should be ordered in terms of increasing complexity to make the 254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // folders simpler. 2660a05cc118763c680834a61280f48530482a1f86Chris Lattner scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr, 274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner scAddRecExpr, scUnknown, scCouldNotCompute 284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVConstant - This class represents a constant integer value. 324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVConstant : public SCEV { 344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *V; 354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 369769ab22265b313171d201b5928688524a01bd87Misha Brukman 374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVConstant(); 384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVConstant object. 404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(ConstantInt *V); 424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *getValue() const { return V; } 444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // Not loop variant 554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 59afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 60afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 61afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 62afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 63afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 655c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVTruncateExpr - This class represents a truncation of an integer value 764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// to a smaller integer value. 774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVTruncateExpr : public SCEV { 794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVTruncateExpr(); 834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVTruncate object 854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 909769ab22265b313171d201b5928688524a01bd87Misha Brukman 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 99afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 100afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 101afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 102afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 103afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 104afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(H, Ty); 105afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 106afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 1084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1125c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVZeroExtendExpr : public SCEV { 1264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 1274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); 1294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVZeroExtendExpr(); 1304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 1314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVZeroExtend object 1324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 1344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 1364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 1379769ab22265b313171d201b5928688524a01bd87Misha Brukman 1384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 1404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 1434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 1444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 1474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 150afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 151afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 152afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 153afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 154afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 155afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(H, Ty); 156afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 157afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1595c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 1714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// operators. 1724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVCommutativeExpr : public SCEV { 1744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 1754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 1774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 1784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(T) { 1794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.reserve(ops.size()); 1804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.insert(Operands.end(), ops.begin(), ops.end()); 1814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVCommutativeExpr(); 1834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 1854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 1864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { 1874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(i < Operands.size() && "Operand index out of range!"); 1884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 1894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const std::vector<SCEVHandle> &getOperands() const { return Operands; } 1924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 1934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 1944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 1954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 1994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (!getOperand(i)->isLoopInvariant(L)) return false; 2004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 2014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 203803513b364e27d303285d396fd8ee5b32149962aChris Lattner // hasComputableLoopEvolution - Commutative expressions have computable loop 204803513b364e27d303285d396fd8ee5b32149962aChris Lattner // evolutions iff they have at least one operand that varies with the loop, 205803513b364e27d303285d396fd8ee5b32149962aChris Lattner // but that all varying operands are computable. 2064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 207803513b364e27d303285d396fd8ee5b32149962aChris Lattner bool HasVarying = false; 2084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 209803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (!getOperand(i)->isLoopInvariant(L)) 210803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (getOperand(i)->hasComputableLoopEvolution(L)) 211803513b364e27d303285d396fd8ee5b32149962aChris Lattner HasVarying = true; 212803513b364e27d303285d396fd8ee5b32149962aChris Lattner else 213803513b364e27d303285d396fd8ee5b32149962aChris Lattner return false; 214803513b364e27d303285d396fd8ee5b32149962aChris Lattner return HasVarying; 2154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 217afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 218afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const; 219afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 2204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 2214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return getOperand(0)->getType(); } 2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 2245c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 2304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner S->getSCEVType() == scMulExpr; 2314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddExpr(const std::vector<SCEVHandle> &ops) 2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scAddExpr, ops) { 2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 2454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 2474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 2494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 2504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, 2544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &Op2) { 2554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op0); 2574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op1); 2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op2); 2594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 2634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 2664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVMulExpr(const std::vector<SCEVHandle> &ops) 2764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scMulExpr, ops) { 2774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 2834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 2854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 2934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 2954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3001628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer /// SCEVSDivExpr - This class represents a binary signed division operation. 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 30260a05cc118763c680834a61280f48530482a1f86Chris Lattner class SCEVSDivExpr : public SCEV { 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle LHS, RHS; 30460a05cc118763c680834a61280f48530482a1f86Chris Lattner SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 30560a05cc118763c680834a61280f48530482a1f86Chris Lattner : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {} 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 30760a05cc118763c680834a61280f48530482a1f86Chris Lattner virtual ~SCEVSDivExpr(); 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 30960a05cc118763c680834a61280f48530482a1f86Chris Lattner /// get method - This just gets and returns a new SCEVSDiv object. 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getLHS() const { return LHS; } 3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getRHS() const { return RHS; } 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 325afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 326afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 327afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 328afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 329afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (L == LHS && R == RHS) 330afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 331afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner else 332afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(L, R); 333afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 334afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 335afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner void print(std::ostream &OS) const; 3395c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 34260a05cc118763c680834a61280f48530482a1f86Chris Lattner static inline bool classof(const SCEVSDivExpr *S) { return true; } 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 34460a05cc118763c680834a61280f48530482a1f86Chris Lattner return S->getSCEVType() == scSDivExpr; 3454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// count of the specified loop. 3524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 3544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddRecExpr : public SCEV { 3564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 3574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 3584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 3604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(scAddRecExpr), Operands(ops), L(l) { 3614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 3624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 3634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 3644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVAddRecExpr(); 3664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, 3684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 3694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Operands, 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 3714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const std::vector<SCEVHandle> &Operands, 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L) { 3734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> NewOp(Operands); 3744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(NewOp, L); 3754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 3794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 3804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 3824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 3834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getStart() const { return Operands[0]; } 3844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 3854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 3884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 3894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 3904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle getStepRecurrence() const { 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (getNumOperands() == 2) return getOperand(1); 3924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), 3934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner getLoop()); 3944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (L == QL) return true; 3984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Operands[0]->getType(); } 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 4074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 4084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 4094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 4104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 4114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 4214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 4224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle evaluateAtIteration(SCEVHandle It) const; 4234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 4294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// returned. 4304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle getNumIterationsInRange(ConstantRange Range) const; 4314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 432afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 433afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const; 4344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4365c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 4474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value, and only represent it as it's LLVM Value. This is the "bottom" 4484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 4494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 4504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUnknown : public SCEV { 4514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *V; 4524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 4534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 4554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVUnknown(); 4564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 4574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - For SCEVUnknown, this just gets and returns a new 4584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown. 4594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(Value *V); 4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4612cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// getIntegerSCEV - Given an integer or FP type, create a constant for the 4622cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// specified signed integer value and return a SCEV for the constant. 4632cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner static SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 4644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4652cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner Value *getValue() const { return V; } 4664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 4684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 4694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 4704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 472afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 473afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 474afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (&*Sym == this) return Conc; 475afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 476afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 477afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 4784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 4794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4815c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 4824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 4854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 4874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4892cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 4902cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 4912cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 4922cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 4932cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 4942cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner RetVal visit(SCEV *S) { 4952cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 4962cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 4972cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitConstant((SCEVConstant*)S); 4982cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 4992cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S); 5002cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 5012cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S); 5022cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 5032cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S); 5042cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 5052cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S); 50660a05cc118763c680834a61280f48530482a1f86Chris Lattner case scSDivExpr: 50760a05cc118763c680834a61280f48530482a1f86Chris Lattner return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S); 5082cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 5092cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S); 5102cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 5112cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitUnknown((SCEVUnknown*)S); 5122cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 5132cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S); 5142cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 5152cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Unknown SCEV type!"); 5160ebf428e48ab258012d94d8efa05a4ae5932e2dbChris Lattner abort(); 5172cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5182cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5192cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5202cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) { 5212cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Invalid use of SCEVCouldNotCompute!"); 5222cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner abort(); 5232cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return RetVal(); 5242cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5252cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 5264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 5274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 5294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 530