ScalarEvolutionExpressions.h revision 4950e88e0fa7c44c0b54e2f64ddf57415ed83d40
14950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 24950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 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. 74950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 84950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 94950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file defines the classes used to represent and build scalar expressions. 114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 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. 264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr, 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) {} 364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 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 594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt) { 614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return (Value*)getValue(); 624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVTruncateExpr - This class represents a truncation of an integer value 754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// to a smaller integer value. 764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVTruncateExpr : public SCEV { 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVTruncateExpr(); 824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVTruncate object 844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 1034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 1044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVZeroExtendExpr : public SCEV { 1194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 1204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 1214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); 1224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVZeroExtendExpr(); 1234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 1244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVZeroExtend object 1254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 1274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 1294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 1304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 1334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 1364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 1374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 1404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 1444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 1584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// operators. 1594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVCommutativeExpr : public SCEV { 1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 1624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 1644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 1654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(T) { 1664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.reserve(ops.size()); 1674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.insert(Operands.end(), ops.begin(), ops.end()); 1684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVCommutativeExpr(); 1704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 1724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 1734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { 1744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(i < Operands.size() && "Operand index out of range!"); 1754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 1764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const std::vector<SCEVHandle> &getOperands() const { return Operands; } 1794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 1804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 1814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 1824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 1864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (!getOperand(i)->isLoopInvariant(L)) return false; 1874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 1884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 1914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 1924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (getOperand(i)->hasComputableLoopEvolution(L)) return true; 1934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 1944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 1974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return getOperand(0)->getType(); } 1994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 2004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 2054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner S->getSCEVType() == scMulExpr; 2064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 2144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddExpr(const std::vector<SCEVHandle> &ops) 2154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scAddExpr, ops) { 2164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 2204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 2224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 2244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, 2294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &Op2) { 2304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op0); 2324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op1); 2334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op2); 2344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 2444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 2464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 2534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVMulExpr(const std::vector<SCEVHandle> &ops) 2544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scMulExpr, ops) { 2554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 2594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 2614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 2634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 2644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 2764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUDivExpr - This class represents a binary unsigned division operation. 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUDivExpr : public SCEV { 2844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle LHS, RHS; 2854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} 2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVUDivExpr(); 2894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVUDiv object. 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); 2934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getLHS() const { return LHS; } 2954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getRHS() const { return RHS; } 2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 3094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner void print(std::ostream &OS) const; 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUDivExpr *S) { return true; } 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUDivExpr; 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// count of the specified loop. 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddRecExpr : public SCEV { 3284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 3294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 3304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 3324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(scAddRecExpr), Operands(ops), L(l) { 3334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 3344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 3354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVAddRecExpr(); 3384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, 3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Operands, 3424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const std::vector<SCEVHandle> &Operands, 3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L) { 3454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> NewOp(Operands); 3464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(NewOp, L); 3474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 3504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 3524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 3544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 3554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getStart() const { return Operands[0]; } 3564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 3574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 3604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 3614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 3624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle getStepRecurrence() const { 3634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (getNumOperands() == 2) return getOperand(1); 3644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), 3654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner getLoop()); 3664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 3694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (L == QL) return true; 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// FIXME: What if the start or step value a recurrence for the specified 3714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// loop? 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 3734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 3764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Operands[0]->getType(); } 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 3804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt); 3814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 3844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 3854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 3874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 3884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 3894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 3924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 3934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 3944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 3954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 4004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle evaluateAtIteration(SCEVHandle It) const; 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 4074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// returned. 4084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle getNumIterationsInRange(ConstantRange Range) const; 4094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 4224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value, and only represent it as it's LLVM Value. This is the "bottom" 4234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 4244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUnknown : public SCEV { 4264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *V; 4274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 4284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 4304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVUnknown(); 4314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 4324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - For SCEVUnknown, this just gets and returns a new 4334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown. 4344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(Value *V); 4354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *getValue() const { return V; } 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *expandCodeFor(ScalarEvolutionRewriter &SER, 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Instruction *InsertPt) { 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return V; 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 4464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 4494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 4544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 4564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 4594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 4614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 462