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