ScalarEvolutionExpressions.h revision a9e4d3f37590bb326e6c5a3ea02ee1aa3db681ea
19c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 29c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// 39c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// The LLVM Compiler Infrastructure 49c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// 59c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// This file is distributed under the University of Illinois Open Source 69c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// License. See LICENSE.TXT for details. 79c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// 89c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar//===----------------------------------------------------------------------===// 99c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// 109c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// This file defines the classes used to represent and build scalar expressions. 119c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar// 129c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar//===----------------------------------------------------------------------===// 139c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 1440f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 15b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 169c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 179c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar#include "llvm/ADT/SmallPtrSet.h" 189c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar#include "llvm/Analysis/ScalarEvolution.h" 199c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar#include "llvm/Support/ErrorHandling.h" 209c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 21df91ef3d6c55692a0236f67b6c6b134a3bf84098Douglas Gregornamespace llvm { 22df91ef3d6c55692a0236f67b6c6b134a3bf84098Douglas Gregor class ConstantInt; 2302633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar class ConstantRange; 2402633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar class DominatorTree; 2502633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 2602633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar enum SCEVTypes { 27985b825eea7387be10478de0430815ed6a673326Daniel Dunbar // These should be ordered in terms of increasing complexity to make the 289c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar // folders simpler. 29985b825eea7387be10478de0430815ed6a673326Daniel Dunbar scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 30df91ef3d6c55692a0236f67b6c6b134a3bf84098Douglas Gregor scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 31df91ef3d6c55692a0236f67b6c6b134a3bf84098Douglas Gregor scUnknown, scCouldNotCompute 32c21c485b4fb58ef5d55cf3e523263dd824a2ace4Daniel Dunbar }; 33c21c485b4fb58ef5d55cf3e523263dd824a2ace4Daniel Dunbar 34c21c485b4fb58ef5d55cf3e523263dd824a2ace4Daniel Dunbar //===--------------------------------------------------------------------===// 35c21c485b4fb58ef5d55cf3e523263dd824a2ace4Daniel Dunbar /// SCEVConstant - This class represents a constant integer value. 369c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// 3731b1e5437e7435879fc044afb77ff27096008e72Daniel Dunbar class SCEVConstant : public SCEV { 389c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar friend class ScalarEvolution; 399c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 409c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar ConstantInt *V; 419c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 4247ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar SCEV(ID, scConstant), V(v) {} 4347ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar public: 44871adcf4e41285e3f4c3b62eaa1b2e05b60b92daDaniel Dunbar ConstantInt *getValue() const { return V; } 4562cf601812e03dd9bc5df42b8ef06a0cdedc38bfDaniel Dunbar 4662cf601812e03dd9bc5df42b8ef06a0cdedc38bfDaniel Dunbar Type *getType() const { return V->getType(); } 4747ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar 4847ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 499c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar static inline bool classof(const SCEV *S) { 509c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar return S->getSCEVType() == scConstant; 5131b1e5437e7435879fc044afb77ff27096008e72Daniel Dunbar } 5231b1e5437e7435879fc044afb77ff27096008e72Daniel Dunbar }; 53b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 549c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar //===--------------------------------------------------------------------===// 55b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// SCEVCastExpr - This is the base class for unary cast operator classes. 5647ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar /// 5747ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar class SCEVCastExpr : public SCEV { 58871adcf4e41285e3f4c3b62eaa1b2e05b60b92daDaniel Dunbar protected: 5962cf601812e03dd9bc5df42b8ef06a0cdedc38bfDaniel Dunbar const SCEV *Op; 6062cf601812e03dd9bc5df42b8ef06a0cdedc38bfDaniel Dunbar Type *Ty; 6147ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar 6247ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar SCEVCastExpr(const FoldingSetNodeIDRef ID, 63b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar unsigned SCEVTy, const SCEV *op, Type *ty); 64b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 65b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar public: 66b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar const SCEV *getOperand() const { return Op; } 679c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar Type *getType() const { return Ty; } 689c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 69b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 70b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar static inline bool classof(const SCEV *S) { 719c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar return S->getSCEVType() == scTruncate || 72b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar S->getSCEVType() == scZeroExtend || 73b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar S->getSCEVType() == scSignExtend; 74b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar } 75b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar }; 76b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 77b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar //===--------------------------------------------------------------------===// 78b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// SCEVTruncateExpr - This class represents a truncation of an integer value 79b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// to a smaller integer value. 80b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// 81b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar class SCEVTruncateExpr : public SCEVCastExpr { 82b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar friend class ScalarEvolution; 83b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 849c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 859c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar const SCEV *op, Type *ty); 869c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 879c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar public: 8847ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 89b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar static inline bool classof(const SCEV *S) { 909c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar return S->getSCEVType() == scTruncate; 919c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar } 92b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar }; 939c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 94b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar //===--------------------------------------------------------------------===// 959c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// SCEVZeroExtendExpr - This class represents a zero extension of a small 969c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// integer value to a larger integer value. 979c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// 989c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar class SCEVZeroExtendExpr : public SCEVCastExpr { 9947ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar friend class ScalarEvolution; 100b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 1019c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 1029c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar const SCEV *op, Type *ty); 103b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar 1049c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar public: 105b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 1069c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar static inline bool classof(const SCEV *S) { 1079c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar return S->getSCEVType() == scZeroExtend; 1089c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar } 1099c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar }; 11047ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar 111b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar //===--------------------------------------------------------------------===// 1129c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// SCEVSignExtendExpr - This class represents a sign extension of a small 1139c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// integer value to a larger integer value. 114b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// 1159c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar class SCEVSignExtendExpr : public SCEVCastExpr { 116b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar friend class ScalarEvolution; 1179c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 1189c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 1199c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar const SCEV *op, Type *ty); 1209c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 12147ac7d27c44bd64a7d0fc03d4babc196cf2b8230Daniel Dunbar public: 122b488c1dac8e53206f07103d794a62a3f5012c0f4Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 1239c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar static inline bool classof(const SCEV *S) { 12431b1e5437e7435879fc044afb77ff27096008e72Daniel Dunbar return S->getSCEVType() == scSignExtend; 1259c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar } 126ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar }; 12740f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 128a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar 129a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar //===--------------------------------------------------------------------===// 130a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar /// SCEVNAryExpr - This node is a base class providing common 131a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar /// functionality for n'ary operators. 132a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar /// 133a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar class SCEVNAryExpr : public SCEV { 134a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar protected: 135a5a7bd0de7b6b80212095195a055a4a43f21d4b2Daniel Dunbar // Since SCEVs are immutable, ScalarEvolution allocates operand 13640f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar // arrays with its SCEVAllocator, so this class just needs a simple 13740f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar // pointer rather than a more elaborate vector-like data structure. 138a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar // This also avoids the need for a non-trivial destructor. 139a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar const SCEV *const *Operands; 14040f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar size_t NumOperands; 14140f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 142a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar SCEVNAryExpr(const FoldingSetNodeIDRef ID, 14340f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar enum SCEVTypes T, const SCEV *const *O, size_t N) 14440f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar : SCEV(ID, T), Operands(O), NumOperands(N) {} 145a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar 146a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar public: 147a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar size_t getNumOperands() const { return NumOperands; } 148a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar const SCEV *getOperand(unsigned i) const { 149a3ec60e0cf2a1916f479288998d31bd980b1a306Daniel Dunbar assert(i < NumOperands && "Operand index out of range!"); 15040f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar return Operands[i]; 15140f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar } 15240f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 15340f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar typedef const SCEV *const *op_iterator; 15440f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar op_iterator op_begin() const { return Operands; } 15540f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar op_iterator op_end() const { return Operands + NumOperands; } 15640f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 15740f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar Type *getType() const { return getOperand(0)->getType(); } 15840f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 15940f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 16040f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar return (NoWrapFlags)(SubclassData & Mask); 16140f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar } 16240f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 16340f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 16440f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar static inline bool classof(const SCEV *S) { 16540f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar return S->getSCEVType() == scAddExpr || 16640f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar S->getSCEVType() == scMulExpr || 16740f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar S->getSCEVType() == scSMaxExpr || 16840f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar S->getSCEVType() == scUMaxExpr || 16940f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar S->getSCEVType() == scAddRecExpr; 17040f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar } 17140f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar }; 17240f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 17340f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar //===--------------------------------------------------------------------===// 17440f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 17540f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar /// operators. 17640f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar /// 17740f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar class SCEVCommutativeExpr : public SCEVNAryExpr { 17840f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar protected: 17940f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 18040f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar enum SCEVTypes T, const SCEV *const *O, size_t N) 18140f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar : SCEVNAryExpr(ID, T, O, N) {} 18240f1265ebd42ece3e7f7917319b56012e8e2bce2Daniel Dunbar 1838cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar public: 1848cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 1858cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar static inline bool classof(const SCEV *S) { 1868cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar return S->getSCEVType() == scAddExpr || 1878cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar S->getSCEVType() == scMulExpr || 1888cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar S->getSCEVType() == scSMaxExpr || 1898cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar S->getSCEVType() == scUMaxExpr; 1908cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar } 1918cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar 19202633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar /// Set flags for a non-recurrence without clearing previously set flags. 19302633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar void setNoWrapFlags(NoWrapFlags Flags) { 19402633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar SubclassData |= Flags; 19502633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar } 19602633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar }; 19702633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 19802633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 19902633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar //===--------------------------------------------------------------------===// 20002633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 20102633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar /// 20202633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar class SCEVAddExpr : public SCEVCommutativeExpr { 20302633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar friend class ScalarEvolution; 20402633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 20502633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar SCEVAddExpr(const FoldingSetNodeIDRef ID, 20602633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar const SCEV *const *O, size_t N) 20702633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 20802633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar } 20902633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 21002633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar public: 21102633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar Type *getType() const { 21202633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar // Use the type of the last operand, which is likely to be a pointer 21302633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar // type, if there is one. This doesn't usually matter, but it can help 21402633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar // reduce casts when the expressions are expanded. 21502633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar return getOperand(getNumOperands() - 1)->getType(); 21602633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar } 21702633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar 21802633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 21902633b541b04ad5ffc1c70f4c2feeeb13e607057Daniel Dunbar static inline bool classof(const SCEV *S) { 2208cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar return S->getSCEVType() == scAddExpr; 2218cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar } 2228cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar }; 2238cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar 2248cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar //===--------------------------------------------------------------------===// 2258cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2268cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar /// 227ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar class SCEVMulExpr : public SCEVCommutativeExpr { 228ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar friend class ScalarEvolution; 2298cac5f7e1ce63dd77ee0fb4ef68f9fa804f41ea6Daniel Dunbar 230ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar SCEVMulExpr(const FoldingSetNodeIDRef ID, 231ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar const SCEV *const *O, size_t N) 232ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 233ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar } 234ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar 235ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar public: 236ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 237ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar static inline bool classof(const SCEV *S) { 238f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar return S->getSCEVType() == scMulExpr; 239f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar } 240f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar }; 241f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 242f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 243f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar //===--------------------------------------------------------------------===// 244f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar /// SCEVUDivExpr - This class represents a binary unsigned division operation. 245f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar /// 246f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar class SCEVUDivExpr : public SCEV { 247f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar friend class ScalarEvolution; 248f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 249f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar const SCEV *LHS; 250f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar const SCEV *RHS; 251f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 252f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 253f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 254f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar public: 255f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar const SCEV *getLHS() const { return LHS; } 256f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar const SCEV *getRHS() const { return RHS; } 257f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 258f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar Type *getType() const { 259f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar // In most cases the types of LHS and RHS will be the same, but in some 260f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 261f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar // depend on the type for correctness, but handling types carefully can 262f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar // avoid extra casts in the SCEVExpander. The LHS is more likely to be 263f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar // a pointer type than the RHS, so use the RHS' type here. 264f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar return getRHS()->getType(); 265f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar } 266f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar 267f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 268f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar static inline bool classof(const SCEV *S) { 269f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar return S->getSCEVType() == scUDivExpr; 270f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar } 271f7b8eec37c8c8012fa525c71fb29a58c9f29beefDaniel Dunbar }; 272ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar 273ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar 274ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar //===--------------------------------------------------------------------===// 275ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 276e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// count of the specified loop. This is the primary focus of the 277ff7488dc9a766f94daf54d81b03ab9160d0bfd88Daniel Dunbar /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 27868a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 27968a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// created and analyzed. 28068a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// 28168a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// All operands of an AddRec are required to be loop invariant. 28268a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// 28368a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar class SCEVAddRecExpr : public SCEVNAryExpr { 28468a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar friend class ScalarEvolution; 28568a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar 28668a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar const Loop *L; 28768a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar 28868a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 28968a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar const SCEV *const *O, size_t N, const Loop *l) 29068a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 29168a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar 29268a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar public: 29368a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar const SCEV *getStart() const { return Operands[0]; } 29468a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar const Loop *getLoop() const { return L; } 295008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar 296008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// getStepRecurrence - This method constructs and returns the recurrence 297008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// indicating how much this expression steps by. If this is a polynomial 298008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// of degree N, it returns a chrec of degree N-1. 299008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// We cannot determine whether the step recurrence has self-wraparound. 300008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 301008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar if (isAffine()) return getOperand(1); 302008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 303008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar op_end()), 304008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar getLoop(), FlagAnyWrap); 305008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar } 306008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar 307008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// isAffine - Return true if this is an affine AddRec (i.e., it represents 308008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar /// an expressions A+B*x where A and B are loop invariant values. 309008f54a54299eaafdaa940e2bdeaf55935ecd95aDaniel Dunbar bool isAffine() const { 310e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan // We know that the start value is invariant. This expression is thus 311e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan // affine iff the step is also invariant. 312e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan return getNumOperands() == 2; 313e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan } 314e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan 315e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 316e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 317e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 318e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan bool isQuadratic() const { 319e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan return getNumOperands() == 3; 320e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan } 321e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan 322e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// Set flags for a recurrence without clearing any previously set flags. 323e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 324e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// to make it easier to propagate flags. 325e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan void setNoWrapFlags(NoWrapFlags Flags) { 326e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan if (Flags & (FlagNUW | FlagNSW)) 327e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan Flags = ScalarEvolution::setFlags(Flags, FlagNW); 328e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan SubclassData |= Flags; 329e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan } 330e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan 331e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// evaluateAtIteration - Return the value of this chain of recurrences at 332e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// the specified iteration number. 333e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 334e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan 335e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// getNumIterationsInRange - Return the number of iterations of this loop 336e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// that produce values in the specified constant range. Another way of 337e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// looking at this is that it returns the first iteration number where the 338e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// value is not in the condition, thus computing the exit count. If the 339e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 340e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// returned. 341e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan const SCEV *getNumIterationsInRange(ConstantRange Range, 342e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan ScalarEvolution &SE) const; 343e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan 344e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan /// getPostIncExpr - Return an expression representing the value of 34568a31d406c6dc4382c700d1199b062de2aa7e1daDaniel Dunbar /// this expression one iteration of the loop ahead. 34611e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 34711e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 34811e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar } 34911e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 35011e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 35111e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar static inline bool classof(const SCEV *S) { 35211e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar return S->getSCEVType() == scAddRecExpr; 35311e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar } 35411e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar }; 35511e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 35611e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 35711e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar //===--------------------------------------------------------------------===// 35811e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar /// SCEVSMaxExpr - This class represents a signed maximum selection. 35911e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar /// 36011e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar class SCEVSMaxExpr : public SCEVCommutativeExpr { 36111e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar friend class ScalarEvolution; 36211e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 36311e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 36411e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar const SCEV *const *O, size_t N) 36511e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 36611e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar // Max never overflows. 36711e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 36811e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar } 36911e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 37011e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar public: 37111e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar /// Methods for support type inquiry through isa, cast, and dyn_cast: 37211e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar static inline bool classof(const SCEV *S) { 37311e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar return S->getSCEVType() == scSMaxExpr; 37411e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar } 37511e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar }; 37611e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 37711e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar 378e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan //===--------------------------------------------------------------------===// 37911e1b40d759a643086f590f6ffbd9d68360bad46Daniel Dunbar /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 3809c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar /// 3819c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar class SCEVUMaxExpr : public SCEVCommutativeExpr { 3829c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar friend class ScalarEvolution; 3839c073ff462eb75ccbb1c4446e21c148f3fc618e1Daniel Dunbar 384e7925a075f110ab21afeae084670a155dea568e3Edward O'Callaghan SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 385 const SCEV *const *O, size_t N) 386 : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 387 // Max never overflows. 388 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 389 } 390 391 public: 392 /// Methods for support type inquiry through isa, cast, and dyn_cast: 393 static inline bool classof(const SCEV *S) { 394 return S->getSCEVType() == scUMaxExpr; 395 } 396 }; 397 398 //===--------------------------------------------------------------------===// 399 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 400 /// value, and only represent it as its LLVM Value. This is the "bottom" 401 /// value for the analysis. 402 /// 403 class SCEVUnknown : public SCEV, private CallbackVH { 404 friend class ScalarEvolution; 405 406 // Implement CallbackVH. 407 virtual void deleted(); 408 virtual void allUsesReplacedWith(Value *New); 409 410 /// SE - The parent ScalarEvolution value. This is used to update 411 /// the parent's maps when the value associated with a SCEVUnknown 412 /// is deleted or RAUW'd. 413 ScalarEvolution *SE; 414 415 /// Next - The next pointer in the linked list of all 416 /// SCEVUnknown instances owned by a ScalarEvolution. 417 SCEVUnknown *Next; 418 419 SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 420 ScalarEvolution *se, SCEVUnknown *next) : 421 SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 422 423 public: 424 Value *getValue() const { return getValPtr(); } 425 426 /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 427 /// constant representing a type size, alignment, or field offset in 428 /// a target-independent manner, and hasn't happened to have been 429 /// folded with other operations into something unrecognizable. This 430 /// is mainly only useful for pretty-printing and other situations 431 /// where it isn't absolutely required for these to succeed. 432 bool isSizeOf(Type *&AllocTy) const; 433 bool isAlignOf(Type *&AllocTy) const; 434 bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 435 436 Type *getType() const { return getValPtr()->getType(); } 437 438 /// Methods for support type inquiry through isa, cast, and dyn_cast: 439 static inline bool classof(const SCEV *S) { 440 return S->getSCEVType() == scUnknown; 441 } 442 }; 443 444 /// SCEVVisitor - This class defines a simple visitor class that may be used 445 /// for various SCEV analysis purposes. 446 template<typename SC, typename RetVal=void> 447 struct SCEVVisitor { 448 RetVal visit(const SCEV *S) { 449 switch (S->getSCEVType()) { 450 case scConstant: 451 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 452 case scTruncate: 453 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 454 case scZeroExtend: 455 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 456 case scSignExtend: 457 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 458 case scAddExpr: 459 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 460 case scMulExpr: 461 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 462 case scUDivExpr: 463 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 464 case scAddRecExpr: 465 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 466 case scSMaxExpr: 467 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 468 case scUMaxExpr: 469 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 470 case scUnknown: 471 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 472 case scCouldNotCompute: 473 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 474 default: 475 llvm_unreachable("Unknown SCEV type!"); 476 } 477 } 478 479 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 480 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 481 } 482 }; 483 484 /// Visit all nodes in the expression tree using worklist traversal. 485 /// 486 /// Visitor implements: 487 /// // return true to follow this node. 488 /// bool follow(const SCEV *S); 489 /// // return true to terminate the search. 490 /// bool isDone(); 491 template<typename SV> 492 class SCEVTraversal { 493 SV &Visitor; 494 SmallVector<const SCEV *, 8> Worklist; 495 SmallPtrSet<const SCEV *, 8> Visited; 496 497 void push(const SCEV *S) { 498 if (Visited.insert(S) && Visitor.follow(S)) 499 Worklist.push_back(S); 500 } 501 public: 502 SCEVTraversal(SV& V): Visitor(V) {} 503 504 void visitAll(const SCEV *Root) { 505 push(Root); 506 while (!Worklist.empty() && !Visitor.isDone()) { 507 const SCEV *S = Worklist.pop_back_val(); 508 509 switch (S->getSCEVType()) { 510 case scConstant: 511 case scUnknown: 512 break; 513 case scTruncate: 514 case scZeroExtend: 515 case scSignExtend: 516 push(cast<SCEVCastExpr>(S)->getOperand()); 517 break; 518 case scAddExpr: 519 case scMulExpr: 520 case scSMaxExpr: 521 case scUMaxExpr: 522 case scAddRecExpr: { 523 const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 524 for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 525 E = NAry->op_end(); I != E; ++I) { 526 push(*I); 527 } 528 break; 529 } 530 case scUDivExpr: { 531 const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 532 push(UDiv->getLHS()); 533 push(UDiv->getRHS()); 534 break; 535 } 536 case scCouldNotCompute: 537 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 538 default: 539 llvm_unreachable("Unknown SCEV kind!"); 540 } 541 } 542 } 543 }; 544 545 /// Use SCEVTraversal to visit all nodes in the givien expression tree. 546 template<typename SV> 547 void visitAll(const SCEV *Root, SV& Visitor) { 548 SCEVTraversal<SV> T(Visitor); 549 T.visitAll(Root); 550 } 551 552 /// The ScevRewriter takes a scalar evolution expression and copies all its 553 /// components. The result after a rewrite is an identical SCEV. 554 struct ScevRewriter 555 : public SCEVVisitor<ScevRewriter, const SCEV*> { 556 public: 557 ScevRewriter(ScalarEvolution &S) : SE(S) {} 558 559 virtual const SCEV *visitConstant(const SCEVConstant *Constant) { 560 return Constant; 561 } 562 563 virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 564 const SCEV *Operand = visit(Expr->getOperand()); 565 return SE.getTruncateExpr(Operand, Expr->getType()); 566 } 567 568 virtual const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 569 const SCEV *Operand = visit(Expr->getOperand()); 570 return SE.getZeroExtendExpr(Operand, Expr->getType()); 571 } 572 573 virtual const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 574 const SCEV *Operand = visit(Expr->getOperand()); 575 return SE.getSignExtendExpr(Operand, Expr->getType()); 576 } 577 578 virtual const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 579 SmallVector<const SCEV *, 2> Operands; 580 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 581 Operands.push_back(visit(Expr->getOperand(i))); 582 return SE.getAddExpr(Operands); 583 } 584 585 virtual const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 586 SmallVector<const SCEV *, 2> Operands; 587 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 588 Operands.push_back(visit(Expr->getOperand(i))); 589 return SE.getMulExpr(Operands); 590 } 591 592 virtual const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 593 return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 594 } 595 596 virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 597 SmallVector<const SCEV *, 2> Operands; 598 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 599 Operands.push_back(visit(Expr->getOperand(i))); 600 return SE.getAddRecExpr(Operands, Expr->getLoop(), 601 Expr->getNoWrapFlags()); 602 } 603 604 virtual const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 605 SmallVector<const SCEV *, 2> Operands; 606 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 607 Operands.push_back(visit(Expr->getOperand(i))); 608 return SE.getSMaxExpr(Operands); 609 } 610 611 virtual const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 612 SmallVector<const SCEV *, 2> Operands; 613 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 614 Operands.push_back(visit(Expr->getOperand(i))); 615 return SE.getUMaxExpr(Operands); 616 } 617 618 virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { 619 return Expr; 620 } 621 622 virtual const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 623 return Expr; 624 } 625 626 protected: 627 ScalarEvolution &SE; 628 }; 629 630 typedef DenseMap<const Value*, Value*> ValueToValueMap; 631 632 /// The ScevParameterRewriter takes a scalar evolution expression and updates 633 /// the SCEVUnknown components following the Map (Value -> Value). 634 struct ScevParameterRewriter: public ScevRewriter { 635 public: 636 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 637 ValueToValueMap &Map) { 638 ScevParameterRewriter Rewriter(SE, Map); 639 return Rewriter.visit(Scev); 640 } 641 ScevParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) 642 : ScevRewriter(S), Map(M) {} 643 644 virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { 645 Value *V = Expr->getValue(); 646 if (Map.count(V)) 647 return SE.getUnknown(Map[V]); 648 return Expr; 649 } 650 651 private: 652 ValueToValueMap ⤅ 653 }; 654 655} 656 657#endif 658