ScalarEvolutionExpressions.h revision 2b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1a
1cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 2cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// 3cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// The LLVM Compiler Infrastructure 4cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// 5cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// This file is distributed under the University of Illinois Open Source 6cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// License. See LICENSE.TXT for details. 7cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// 8cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com//===----------------------------------------------------------------------===// 9cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com// 108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com// This file defines the classes used to represent and build scalar expressions. 118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com// 128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com//===----------------------------------------------------------------------===// 138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com#include "llvm/Analysis/ScalarEvolution.h" 188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com#include "llvm/Support/ErrorHandling.h" 198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.comnamespace llvm { 218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class ConstantInt; 228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class ConstantRange; 238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class DominatorTree; 248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com enum SCEVTypes { 268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // These should be ordered in terms of increasing complexity to make the 278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // folders simpler. 288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com scFieldOffset, scAllocSize, scUnknown, scCouldNotCompute 318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVConstant - This class represents a constant integer value. 358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVConstant : public SCEV { 378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com ConstantInt *V; 408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) : 418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEV(ID, scConstant), V(v) {} 428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 438cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com ConstantInt *getValue() const { return V; } 448cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 458cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *L) const { 468cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 478cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 488cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 498cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *L) const { 508cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; // Not loop variant 518cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 528cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 538cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const Type *getType() const; 548cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 558cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasOperand(const SCEV *) const { 568cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; 578cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 588cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 598cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool dominates(BasicBlock *BB, DominatorTree *DT) const { 608cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 618cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 628cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 638cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { 648cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 658cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 668cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 678cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 688cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 698cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 708cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVConstant *S) { return true; } 718cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 728cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scConstant; 738cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 748cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 758cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 768cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 778cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVCastExpr - This is the base class for unary cast operator classes. 788cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 798cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVCastExpr : public SCEV { 808cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com protected: 818cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *Op; 828cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const Type *Ty; 838cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 848cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVCastExpr(const FoldingSetNodeID &ID, 858cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com unsigned SCEVTy, const SCEV *op, const Type *ty); 868cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 878cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 888cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getOperand() const { return Op; } 898cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const Type *getType() const { return Ty; } 908cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 918cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *L) const { 928cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return Op->isLoopInvariant(L); 938cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 948cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 958cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *L) const { 968cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return Op->hasComputableLoopEvolution(L); 978cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 988cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 998cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasOperand(const SCEV *O) const { 1008cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return Op == O || Op->hasOperand(O); 1018cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1028cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1038cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; 1048cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1058cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 1068cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1078cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 1088cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVCastExpr *S) { return true; } 1098cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 1108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scTruncate || 1118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scZeroExtend || 1128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scSignExtend; 1138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 1158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 1178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVTruncateExpr - This class represents a truncation of an integer value 1188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// to a smaller integer value. 1198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 1208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVTruncateExpr : public SCEVCastExpr { 1218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 1228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVTruncateExpr(const FoldingSetNodeID &ID, 1248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *op, const Type *ty); 1258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 1278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 1288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 1308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 1328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scTruncate; 1338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 1358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 1378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// integer value to a larger integer value. 1398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 1408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVZeroExtendExpr : public SCEVCastExpr { 1418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 1428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1438cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVZeroExtendExpr(const FoldingSetNodeID &ID, 1448cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *op, const Type *ty); 1458cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1468cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 1478cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 1488cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1498cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 1508cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1518cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 1528cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scZeroExtend; 1538cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1548cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 1558cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1568cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 1578cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVSignExtendExpr - This class represents a sign extension of a small 1588cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// integer value to a larger integer value. 1598cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 1608cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVSignExtendExpr : public SCEVCastExpr { 1618cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 1628cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1638cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVSignExtendExpr(const FoldingSetNodeID &ID, 1648cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *op, const Type *ty); 1658cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1668cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 1678cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 1688cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1698cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 1708cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 1718cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 1728cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scSignExtend; 1738cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1748cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 1758cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1768cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1778cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 1788cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVNAryExpr - This node is a base class providing common 1798cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// functionality for n'ary operators. 1808cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 1818cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVNAryExpr : public SCEV { 1828cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com protected: 1838cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SmallVector<const SCEV *, 8> Operands; 1848cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1858cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVNAryExpr(const FoldingSetNodeID &ID, 1868cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops) 1878cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEV(ID, T), Operands(ops.begin(), ops.end()) {} 1888cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1898cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 1908cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com unsigned getNumOperands() const { return (unsigned)Operands.size(); } 1918cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getOperand(unsigned i) const { 1928cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com assert(i < Operands.size() && "Operand index out of range!"); 1938cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return Operands[i]; 1948cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1958cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 1968cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &getOperands() const { 1978cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return Operands; 1988cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 1998cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator; 2008cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com op_iterator op_begin() const { return Operands.begin(); } 2018cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com op_iterator op_end() const { return Operands.end(); } 2028cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2038cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *L) const { 2048cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2058cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (!getOperand(i)->isLoopInvariant(L)) return false; 2068cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 2078cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2088cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2098cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // hasComputableLoopEvolution - N-ary expressions have computable loop 2108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // evolutions iff they have at least one operand that varies with the loop, 2118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // but that all varying operands are computable. 2128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *L) const { 2138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool HasVarying = false; 2148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (!getOperand(i)->isLoopInvariant(L)) { 2168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (getOperand(i)->hasComputableLoopEvolution(L)) 2178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com HasVarying = true; 2188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com else 2198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; 2208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return HasVarying; 2228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasOperand(const SCEV *O) const { 2258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (O == getOperand(i) || getOperand(i)->hasOperand(O)) 2278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 2288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; 2298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool dominates(BasicBlock *BB, DominatorTree *DT) const; 2328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 2348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const Type *getType() const { return getOperand(0)->getType(); } 2368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } 2388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com void setHasNoUnsignedWrap(bool B) { 2398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); 2408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } 2428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com void setHasNoSignedWrap(bool B) { 2438cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); 2448cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2458cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2468cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 2478cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVNAryExpr *S) { return true; } 2488cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 2498cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scAddExpr || 2508cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scMulExpr || 2518cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scSMaxExpr || 2528cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scUMaxExpr || 2538cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scAddRecExpr; 2548cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2558cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 2568cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2578cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 2588cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 2598cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// operators. 2608cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 2618cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVCommutativeExpr : public SCEVNAryExpr { 2628cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com protected: 2638cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVCommutativeExpr(const FoldingSetNodeID &ID, 2648cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com enum SCEVTypes T, 2658cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops) 2668cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVNAryExpr(ID, T, ops) {} 2678cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2688cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 2698cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const char *getOperationStr() const = 0; 2708cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2718cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 2728cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2738cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 2748cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2758cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 2768cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scAddExpr || 2778cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scMulExpr || 2788cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scSMaxExpr || 2798cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com S->getSCEVType() == scUMaxExpr; 2808cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2818cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 2828cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2838cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2848cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 2858cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2868cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 2878cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVAddExpr : public SCEVCommutativeExpr { 2888cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 2898cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2908cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVAddExpr(const FoldingSetNodeID &ID, 2918cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops) 2928cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVCommutativeExpr(ID, scAddExpr, ops) { 2938cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 2948cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2958cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 2968cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const char *getOperationStr() const { return " + "; } 2978cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 2988cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const Type *getType() const { 2998cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // Use the type of the last operand, which is likely to be a pointer 3008cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // type, if there is one. This doesn't usually matter, but it can help 3018cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // reduce casts when the expressions are expanded. 3028cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return getOperand(getNumOperands() - 1)->getType(); 3038cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3048cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3058cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 3068cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVAddExpr *S) { return true; } 3078cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 3088cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scAddExpr; 3098cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 3118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 3138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 3148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 3158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVMulExpr : public SCEVCommutativeExpr { 3168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 3178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVMulExpr(const FoldingSetNodeID &ID, 3198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops) 3208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVCommutativeExpr(ID, scMulExpr, ops) { 3218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 3248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const char *getOperationStr() const { return " * "; } 3258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 3278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVMulExpr *S) { return true; } 3288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 3298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scMulExpr; 3308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 3328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 3358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVUDivExpr - This class represents a binary unsigned division operation. 3368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 3378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVUDivExpr : public SCEV { 3388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 3398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *LHS; 3418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *RHS; 3428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs) 3438cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 3448cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3458cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 3468cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getLHS() const { return LHS; } 3478cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getRHS() const { return RHS; } 3488cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3498cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *L) const { 3508cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3518cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3528cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3538cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *L) const { 3548cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return LHS->hasComputableLoopEvolution(L) && 3558cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com RHS->hasComputableLoopEvolution(L); 3568cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3578cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3588cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasOperand(const SCEV *O) const { 3598cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); 3608cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3618cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3628cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool dominates(BasicBlock *BB, DominatorTree *DT) const; 3638cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3648cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 3658cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3668cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const Type *getType() const; 3678cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3688cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com void print(raw_ostream &OS) const; 3698cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3708cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 3718cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVUDivExpr *S) { return true; } 3728cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 3738cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scUDivExpr; 3748cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3758cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 3768cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3778cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3788cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 3798cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3808cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// count of the specified loop. This is the primary focus of the 3818cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 3828cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 3838cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// created and analyzed. 3848cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 3858cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// All operands of an AddRec are required to be loop invariant. 3868cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 3878cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVAddRecExpr : public SCEVNAryExpr { 3888cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 3898cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3908cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const Loop *L; 3918cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 3928cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVAddRecExpr(const FoldingSetNodeID &ID, 3938cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops, const Loop *l) 3948cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) { 3958cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com for (size_t i = 0, e = Operands.size(); i != e; ++i) 3968cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com assert(Operands[i]->isLoopInvariant(l) && 3978cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com "Operands of AddRec must be loop-invariant!"); 3988cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 3998cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4008cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 4018cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getStart() const { return Operands[0]; } 4028cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const Loop *getLoop() const { return L; } 4038cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4048cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// getStepRecurrence - This method constructs and returns the recurrence 4058cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// indicating how much this expression steps by. If this is a polynomial 4068cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// of degree N, it returns a chrec of degree N-1. 4078cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 4088cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (isAffine()) return getOperand(1); 4098cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 4108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com op_end()), 4118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com getLoop()); 4128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *QL) const { 4158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com if (L == QL) return true; 4168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; 4178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *QueryLoop) const; 4208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// isAffine - Return true if this is an affine AddRec (i.e., it represents 4228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// an expressions A+B*x where A and B are loop invariant values. 4238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool isAffine() const { 4248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // We know that the start value is invariant. This expression is thus 4258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // affine iff the step is also invariant. 4268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return getNumOperands() == 2; 4278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool isQuadratic() const { 4338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return getNumOperands() == 3; 4348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// evaluateAtIteration - Return the value of this chain of recurrences at 4378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// the specified iteration number. 4388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 4398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// getNumIterationsInRange - Return the number of iterations of this loop 4418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// that produce values in the specified constant range. Another way of 4428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// looking at this is that it returns the first iteration number where the 4438cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// value is not in the condition, thus computing the exit count. If the 4448cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 4458cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// returned. 4468cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEV *getNumIterationsInRange(ConstantRange Range, 4478cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com ScalarEvolution &SE) const; 4488cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4498cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// getPostIncExpr - Return an expression representing the value of 4508cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// this expression one iteration of the loop ahead. 4518cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 4528cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 4538cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4548cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4558cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual void print(raw_ostream &OS) const; 4568cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4578cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 4588cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4598cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 4608cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scAddRecExpr; 4618cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4628cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 4638cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4648cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4658cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 4668cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVSMaxExpr - This class represents a signed maximum selection. 4678cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 4688cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVSMaxExpr : public SCEVCommutativeExpr { 4698cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 4708cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4718cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVSMaxExpr(const FoldingSetNodeID &ID, 4728cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops) 4738cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVCommutativeExpr(ID, scSMaxExpr, ops) { 4748cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // Max never overflows. 4758cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com setHasNoUnsignedWrap(true); 4768cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com setHasNoSignedWrap(true); 4778cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4788cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4798cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 4808cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const char *getOperationStr() const { return " smax "; } 4818cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4828cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 4838cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVSMaxExpr *S) { return true; } 4848cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 4858cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scSMaxExpr; 4868cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 4878cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 4888cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4898cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4908cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 4918cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 4928cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 4938cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVUMaxExpr : public SCEVCommutativeExpr { 4948cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com friend class ScalarEvolution; 4958cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 4968cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVUMaxExpr(const FoldingSetNodeID &ID, 4978cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const SmallVectorImpl<const SCEV *> &ops) 4988cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com : SCEVCommutativeExpr(ID, scUMaxExpr, ops) { 4998cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com // Max never overflows. 5008cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com setHasNoUnsignedWrap(true); 5018cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com setHasNoSignedWrap(true); 5028cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5038cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5048cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 5058cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual const char *getOperationStr() const { return " umax "; } 5068cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5078cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 5088cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEVUMaxExpr *S) { return true; } 5098cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com static inline bool classof(const SCEV *S) { 5108cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return S->getSCEVType() == scUMaxExpr; 5118cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5128cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com }; 5138cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5148cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com //===--------------------------------------------------------------------===// 5158cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// SCEVTargetDataConstant - This node is the base class for representing 5168cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// target-dependent values in a target-independent way. 5178cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com /// 5188cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com class SCEVTargetDataConstant : public SCEV { 5198cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com protected: 5208cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const Type *Ty; 5218cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEVTargetDataConstant(const FoldingSetNodeID &ID, enum SCEVTypes T, 5228cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com const Type *ty) : 5238cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com SCEV(ID, T), Ty(ty) {} 5248cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5258cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com public: 5268cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool isLoopInvariant(const Loop *) const { return true; } 5278cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasComputableLoopEvolution(const Loop *) const { 5288cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; // not computable 5298cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5308cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5318cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com virtual bool hasOperand(const SCEV *) const { 5328cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return false; 5338cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5348cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5358cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool dominates(BasicBlock *, DominatorTree *) const { 5368cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 5378cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5388cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 5398cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com bool properlyDominates(BasicBlock *, DominatorTree *) const { 5408cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com return true; 5418cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com } 5428cee797901763ab0922eb9ef484cfdcbc94bee54edisonn@google.com 543cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com virtual const Type *getType() const { return Ty; } 544 545 /// Methods for support type inquiry through isa, cast, and dyn_cast: 546 static inline bool classof(const SCEVTargetDataConstant *S) { return true; } 547 static inline bool classof(const SCEV *S) { 548 return S->getSCEVType() == scFieldOffset || 549 S->getSCEVType() == scAllocSize; 550 } 551 }; 552 553 //===--------------------------------------------------------------------===// 554 /// SCEVFieldOffsetExpr - This node represents an offsetof expression. 555 /// 556 class SCEVFieldOffsetExpr : public SCEVTargetDataConstant { 557 friend class ScalarEvolution; 558 559 const StructType *STy; 560 unsigned FieldNo; 561 SCEVFieldOffsetExpr(const FoldingSetNodeID &ID, const Type *ty, 562 const StructType *sty, unsigned fieldno) : 563 SCEVTargetDataConstant(ID, scFieldOffset, ty), 564 STy(sty), FieldNo(fieldno) {} 565 566 public: 567 const StructType *getStructType() const { return STy; } 568 unsigned getFieldNo() const { return FieldNo; } 569 570 virtual void print(raw_ostream &OS) const; 571 572 /// Methods for support type inquiry through isa, cast, and dyn_cast: 573 static inline bool classof(const SCEVFieldOffsetExpr *S) { return true; } 574 static inline bool classof(const SCEV *S) { 575 return S->getSCEVType() == scFieldOffset; 576 } 577 }; 578 579 //===--------------------------------------------------------------------===// 580 /// SCEVAllocSize - This node represents a sizeof expression. 581 /// 582 class SCEVAllocSizeExpr : public SCEVTargetDataConstant { 583 friend class ScalarEvolution; 584 585 const Type *AllocTy; 586 SCEVAllocSizeExpr(const FoldingSetNodeID &ID, 587 const Type *ty, const Type *allocty) : 588 SCEVTargetDataConstant(ID, scAllocSize, ty), 589 AllocTy(allocty) {} 590 591 public: 592 const Type *getAllocType() const { return AllocTy; } 593 594 virtual void print(raw_ostream &OS) const; 595 596 /// Methods for support type inquiry through isa, cast, and dyn_cast: 597 static inline bool classof(const SCEVAllocSizeExpr *S) { return true; } 598 static inline bool classof(const SCEV *S) { 599 return S->getSCEVType() == scAllocSize; 600 } 601 }; 602 603 //===--------------------------------------------------------------------===// 604 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 605 /// value, and only represent it as its LLVM Value. This is the "bottom" 606 /// value for the analysis. 607 /// 608 class SCEVUnknown : public SCEV { 609 friend class ScalarEvolution; 610 611 Value *V; 612 SCEVUnknown(const FoldingSetNodeID &ID, Value *v) : 613 SCEV(ID, scUnknown), V(v) {} 614 615 public: 616 Value *getValue() const { return V; } 617 618 virtual bool isLoopInvariant(const Loop *L) const; 619 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 620 return false; // not computable 621 } 622 623 virtual bool hasOperand(const SCEV *) const { 624 return false; 625 } 626 627 bool dominates(BasicBlock *BB, DominatorTree *DT) const; 628 629 bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 630 631 virtual const Type *getType() const; 632 633 virtual void print(raw_ostream &OS) const; 634 635 /// Methods for support type inquiry through isa, cast, and dyn_cast: 636 static inline bool classof(const SCEVUnknown *S) { return true; } 637 static inline bool classof(const SCEV *S) { 638 return S->getSCEVType() == scUnknown; 639 } 640 }; 641 642 /// SCEVVisitor - This class defines a simple visitor class that may be used 643 /// for various SCEV analysis purposes. 644 template<typename SC, typename RetVal=void> 645 struct SCEVVisitor { 646 RetVal visit(const SCEV *S) { 647 switch (S->getSCEVType()) { 648 case scConstant: 649 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 650 case scTruncate: 651 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 652 case scZeroExtend: 653 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 654 case scSignExtend: 655 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 656 case scAddExpr: 657 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 658 case scMulExpr: 659 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 660 case scUDivExpr: 661 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 662 case scAddRecExpr: 663 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 664 case scSMaxExpr: 665 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 666 case scUMaxExpr: 667 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 668 case scFieldOffset: 669 return ((SC*)this)->visitFieldOffsetExpr((const SCEVFieldOffsetExpr*)S); 670 case scAllocSize: 671 return ((SC*)this)->visitAllocSizeExpr((const SCEVAllocSizeExpr*)S); 672 case scUnknown: 673 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 674 case scCouldNotCompute: 675 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 676 default: 677 llvm_unreachable("Unknown SCEV type!"); 678 } 679 } 680 681 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 682 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 683 return RetVal(); 684 } 685 }; 686} 687 688#endif 689