ScalarEvolutionExpressions.h revision 7e2c793a2b5c746344652b6579e958ee42fafdcc
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 80f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file defines the classes used to represent and build scalar expressions. 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Analysis/ScalarEvolution.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallPtrSet.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/ErrorHandling.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace llvm { 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class ConstantInt; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class ConstantRange; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class DominatorTree; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum SCEVTypes { 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These should be ordered in terms of increasing complexity to make the 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // folders simpler. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scUnknown, scCouldNotCompute 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVConstant - This class represents a constant integer value. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVConstant : public SCEV { 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) friend class ScalarEvolution; 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ConstantInt *V; 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEV(ID, scConstant), V(v) {} 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ConstantInt *getValue() const { return V; } 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Type *getType() const { return V->getType(); } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVConstant *S) { return true; } 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scConstant; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) }; 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVCastExpr - This is the base class for unary cast operator classes. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVCastExpr : public SCEV { 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) protected: 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const SCEV *Op; 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Type *Ty; 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SCEVCastExpr(const FoldingSetNodeIDRef ID, 64c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned SCEVTy, const SCEV *op, Type *ty); 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *getOperand() const { return Op; } 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Type *getType() const { return Ty; } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static inline bool classof(const SCEVCastExpr *S) { return true; } 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static inline bool classof(const SCEV *S) { 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return S->getSCEVType() == scTruncate || 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scZeroExtend || 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) S->getSCEVType() == scSignExtend; 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) }; 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 79c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) //===--------------------------------------------------------------------===// 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVTruncateExpr - This class represents a truncation of an integer value 81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// to a smaller integer value. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVTruncateExpr : public SCEVCastExpr { 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 860f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *op, Type *ty); 880f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) 890f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) public: 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVTruncateExpr *S) { return true; } 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scTruncate; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVZeroExtendExpr - This class represents a zero extension of a small 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// integer value to a larger integer value. 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVZeroExtendExpr : public SCEVCastExpr { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *op, Type *ty); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scZeroExtend; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVSignExtendExpr - This class represents a sign extension of a small 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// integer value to a larger integer value. 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class SCEVSignExtendExpr : public SCEVCastExpr { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *op, Type *ty); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scSignExtend; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1320f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) 1330f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVNAryExpr - This node is a base class providing common 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// functionality for n'ary operators. 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVNAryExpr : public SCEV { 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) protected: 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Since SCEVs are immutable, ScalarEvolution allocates operand 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // arrays with its SCEVAllocator, so this class just needs a simple 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // pointer rather than a more elaborate vector-like data structure. 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This also avoids the need for a non-trivial destructor. 1440f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) const SCEV *const *Operands; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t NumOperands; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVNAryExpr(const FoldingSetNodeIDRef ID, 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum SCEVTypes T, const SCEV *const *O, size_t N) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEV(ID, T), Operands(O), NumOperands(N) {} 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t getNumOperands() const { return NumOperands; } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *getOperand(unsigned i) const { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(i < NumOperands && "Operand index out of range!"); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Operands[i]; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef const SCEV *const *op_iterator; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) op_iterator op_begin() const { return Operands; } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) op_iterator op_end() const { return Operands + NumOperands; } 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Type *getType() const { return getOperand(0)->getType(); } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (NoWrapFlags)(SubclassData & Mask); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVNAryExpr *S) { return true; } 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scAddExpr || 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scMulExpr || 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scSMaxExpr || 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scUMaxExpr || 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scAddRecExpr; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// operators. 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVCommutativeExpr : public SCEVNAryExpr { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) protected: 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum SCEVTypes T, const SCEV *const *O, size_t N) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEVNAryExpr(ID, T, O, N) {} 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scAddExpr || 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scMulExpr || 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scSMaxExpr || 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) S->getSCEVType() == scUMaxExpr; 1970f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) } 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Set flags for a non-recurrence without clearing previously set flags. 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setNoWrapFlags(NoWrapFlags Flags) { 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubclassData |= Flags; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVAddExpr : public SCEVCommutativeExpr { 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVAddExpr(const FoldingSetNodeIDRef ID, 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *const *O, size_t N) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Type *getType() const { 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Use the type of the last operand, which is likely to be a pointer 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // type, if there is one. This doesn't usually matter, but it can help 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // reduce casts when the expressions are expanded. 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getOperand(getNumOperands() - 1)->getType(); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVAddExpr *S) { return true; } 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return S->getSCEVType() == scAddExpr; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //===--------------------------------------------------------------------===// 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCEVMulExpr : public SCEVCommutativeExpr { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVMulExpr(const FoldingSetNodeIDRef ID, 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *const *O, size_t N) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 245c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static inline bool classof(const SCEVMulExpr *S) { return true; } 246c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static inline bool classof(const SCEV *S) { 247c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return S->getSCEVType() == scMulExpr; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 250c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 251c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 252c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) //===--------------------------------------------------------------------===// 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SCEVUDivExpr - This class represents a binary unsigned division operation. 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 255c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) class SCEVUDivExpr : public SCEV { 256c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) friend class ScalarEvolution; 257c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *LHS; 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *RHS; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *getLHS() const { return LHS; } 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *getRHS() const { return RHS; } 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Type *getType() const { 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In most cases the types of LHS and RHS will be the same, but in some 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // depend on the type for correctness, but handling types carefully can 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // avoid extra casts in the SCEVExpander. The LHS is more likely to be 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a pointer type than the RHS, so use the RHS' type here. 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getRHS()->getType(); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Methods for support type inquiry through isa, cast, and dyn_cast: 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEVUDivExpr *S) { return true; } 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline bool classof(const SCEV *S) { 2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return S->getSCEVType() == scUDivExpr; 2802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) //===--------------------------------------------------------------------===// 2852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// count of the specified loop. This is the primary focus of the 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 288c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 289c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// created and analyzed. 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// All operands of an AddRec are required to be loop invariant. 292c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// 293c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) class SCEVAddRecExpr : public SCEVNAryExpr { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class ScalarEvolution; 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 296c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const Loop *L; 297c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *const *O, size_t N, const Loop *l) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SCEV *getStart() const { return Operands[0]; } 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Loop *getLoop() const { return L; } 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getStepRecurrence - This method constructs and returns the recurrence 3077dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch /// indicating how much this expression steps by. If this is a polynomial 3087dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch /// of degree N, it returns a chrec of degree N-1. 3097dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch /// We cannot determine whether the step recurrence has self-wraparound. 3107dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 3117dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch if (isAffine()) return getOperand(1); 3127dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 3137dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch op_end()), 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getLoop(), FlagAnyWrap); 3157dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 3167dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isAffine - Return true if this is an affine AddRec (i.e., it represents 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// an expressions A+B*x where A and B are loop invariant values. 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isAffine() const { 3207dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // We know that the start value is invariant. This expression is thus 3217dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // affine if the step is also invariant. 3227dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch return getNumOperands() == 2; 3237dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 3247dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 327c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 328c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool isQuadratic() const { 329c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return getNumOperands() == 3; 330c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 331c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 332c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// Set flags for a recurrence without clearing any previously set flags. 333c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 334c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// to make it easier to propagate flags. 335c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void setNoWrapFlags(NoWrapFlags Flags) { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Flags & (FlagNUW | FlagNSW)) 337 Flags = ScalarEvolution::setFlags(Flags, FlagNW); 338 SubclassData |= Flags; 339 } 340 341 /// evaluateAtIteration - Return the value of this chain of recurrences at 342 /// the specified iteration number. 343 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 344 345 /// getNumIterationsInRange - Return the number of iterations of this loop 346 /// that produce values in the specified constant range. Another way of 347 /// looking at this is that it returns the first iteration number where the 348 /// value is not in the condition, thus computing the exit count. If the 349 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 350 /// returned. 351 const SCEV *getNumIterationsInRange(ConstantRange Range, 352 ScalarEvolution &SE) const; 353 354 /// getPostIncExpr - Return an expression representing the value of 355 /// this expression one iteration of the loop ahead. 356 const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 357 return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 358 } 359 360 /// Methods for support type inquiry through isa, cast, and dyn_cast: 361 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 362 static inline bool classof(const SCEV *S) { 363 return S->getSCEVType() == scAddRecExpr; 364 } 365 }; 366 367 368 //===--------------------------------------------------------------------===// 369 /// SCEVSMaxExpr - This class represents a signed maximum selection. 370 /// 371 class SCEVSMaxExpr : public SCEVCommutativeExpr { 372 friend class ScalarEvolution; 373 374 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 375 const SCEV *const *O, size_t N) 376 : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 377 // Max never overflows. 378 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 379 } 380 381 public: 382 /// Methods for support type inquiry through isa, cast, and dyn_cast: 383 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 384 static inline bool classof(const SCEV *S) { 385 return S->getSCEVType() == scSMaxExpr; 386 } 387 }; 388 389 390 //===--------------------------------------------------------------------===// 391 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 392 /// 393 class SCEVUMaxExpr : public SCEVCommutativeExpr { 394 friend class ScalarEvolution; 395 396 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 397 const SCEV *const *O, size_t N) 398 : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 399 // Max never overflows. 400 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 401 } 402 403 public: 404 /// Methods for support type inquiry through isa, cast, and dyn_cast: 405 static inline bool classof(const SCEVUMaxExpr *S) { return true; } 406 static inline bool classof(const SCEV *S) { 407 return S->getSCEVType() == scUMaxExpr; 408 } 409 }; 410 411 //===--------------------------------------------------------------------===// 412 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 413 /// value, and only represent it as its LLVM Value. This is the "bottom" 414 /// value for the analysis. 415 /// 416 class SCEVUnknown : public SCEV, private CallbackVH { 417 friend class ScalarEvolution; 418 419 // Implement CallbackVH. 420 virtual void deleted(); 421 virtual void allUsesReplacedWith(Value *New); 422 423 /// SE - The parent ScalarEvolution value. This is used to update 424 /// the parent's maps when the value associated with a SCEVUnknown 425 /// is deleted or RAUW'd. 426 ScalarEvolution *SE; 427 428 /// Next - The next pointer in the linked list of all 429 /// SCEVUnknown instances owned by a ScalarEvolution. 430 SCEVUnknown *Next; 431 432 SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 433 ScalarEvolution *se, SCEVUnknown *next) : 434 SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 435 436 public: 437 Value *getValue() const { return getValPtr(); } 438 439 /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 440 /// constant representing a type size, alignment, or field offset in 441 /// a target-independent manner, and hasn't happened to have been 442 /// folded with other operations into something unrecognizable. This 443 /// is mainly only useful for pretty-printing and other situations 444 /// where it isn't absolutely required for these to succeed. 445 bool isSizeOf(Type *&AllocTy) const; 446 bool isAlignOf(Type *&AllocTy) const; 447 bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 448 449 Type *getType() const { return getValPtr()->getType(); } 450 451 /// Methods for support type inquiry through isa, cast, and dyn_cast: 452 static inline bool classof(const SCEVUnknown *S) { return true; } 453 static inline bool classof(const SCEV *S) { 454 return S->getSCEVType() == scUnknown; 455 } 456 }; 457 458 /// SCEVVisitor - This class defines a simple visitor class that may be used 459 /// for various SCEV analysis purposes. 460 template<typename SC, typename RetVal=void> 461 struct SCEVVisitor { 462 RetVal visit(const SCEV *S) { 463 switch (S->getSCEVType()) { 464 case scConstant: 465 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 466 case scTruncate: 467 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 468 case scZeroExtend: 469 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 470 case scSignExtend: 471 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 472 case scAddExpr: 473 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 474 case scMulExpr: 475 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 476 case scUDivExpr: 477 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 478 case scAddRecExpr: 479 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 480 case scSMaxExpr: 481 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 482 case scUMaxExpr: 483 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 484 case scUnknown: 485 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 486 case scCouldNotCompute: 487 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 488 default: 489 llvm_unreachable("Unknown SCEV type!"); 490 } 491 } 492 493 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 494 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 495 } 496 }; 497 498 /// Visit all nodes in the expression tree using worklist traversal. 499 /// 500 /// Visitor implements: 501 /// // return true to follow this node. 502 /// bool follow(const SCEV *S); 503 /// // return true to terminate the search. 504 /// bool isDone(); 505 template<typename SV> 506 class SCEVTraversal { 507 SV &Visitor; 508 SmallVector<const SCEV *, 8> Worklist; 509 SmallPtrSet<const SCEV *, 8> Visited; 510 511 void push(const SCEV *S) { 512 if (Visited.insert(S) && Visitor.follow(S)) 513 Worklist.push_back(S); 514 } 515 public: 516 SCEVTraversal(SV& V): Visitor(V) {} 517 518 void visitAll(const SCEV *Root) { 519 push(Root); 520 while (!Worklist.empty() && !Visitor.isDone()) { 521 const SCEV *S = Worklist.pop_back_val(); 522 523 switch (S->getSCEVType()) { 524 case scConstant: 525 case scUnknown: 526 break; 527 case scTruncate: 528 case scZeroExtend: 529 case scSignExtend: 530 push(cast<SCEVCastExpr>(S)->getOperand()); 531 break; 532 case scAddExpr: 533 case scMulExpr: 534 case scSMaxExpr: 535 case scUMaxExpr: 536 case scAddRecExpr: { 537 const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 538 for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 539 E = NAry->op_end(); I != E; ++I) { 540 push(*I); 541 } 542 break; 543 } 544 case scUDivExpr: { 545 const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 546 push(UDiv->getLHS()); 547 push(UDiv->getRHS()); 548 break; 549 } 550 case scCouldNotCompute: 551 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 552 default: 553 llvm_unreachable("Unknown SCEV kind!"); 554 } 555 } 556 } 557 }; 558 559 /// Use SCEVTraversal to visit all nodes in the givien expression tree. 560 template<typename SV> 561 void visitAll(const SCEV *Root, SV& Visitor) { 562 SCEVTraversal<SV> T(Visitor); 563 T.visitAll(Root); 564 } 565} 566 567#endif 568