ScalarEvolutionExpressions.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
125b3c049e70834cf33790a28643ab058b507b35cBen Cheng//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 225b3c049e70834cf33790a28643ab058b507b35cBen Cheng// 325b3c049e70834cf33790a28643ab058b507b35cBen Cheng// The LLVM Compiler Infrastructure 425b3c049e70834cf33790a28643ab058b507b35cBen Cheng// 525b3c049e70834cf33790a28643ab058b507b35cBen Cheng// This file is distributed under the University of Illinois Open Source 625b3c049e70834cf33790a28643ab058b507b35cBen Cheng// License. See LICENSE.TXT for details. 725b3c049e70834cf33790a28643ab058b507b35cBen Cheng// 825b3c049e70834cf33790a28643ab058b507b35cBen Cheng//===----------------------------------------------------------------------===// 925b3c049e70834cf33790a28643ab058b507b35cBen Cheng// 1025b3c049e70834cf33790a28643ab058b507b35cBen Cheng// This file defines the classes used to represent and build scalar expressions. 1125b3c049e70834cf33790a28643ab058b507b35cBen Cheng// 1225b3c049e70834cf33790a28643ab058b507b35cBen Cheng//===----------------------------------------------------------------------===// 1325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 1425b3c049e70834cf33790a28643ab058b507b35cBen Cheng#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 1525b3c049e70834cf33790a28643ab058b507b35cBen Cheng#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 1625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 1725b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include "llvm/ADT/SmallPtrSet.h" 1825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include "llvm/Analysis/ScalarEvolution.h" 1925b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include "llvm/Support/ErrorHandling.h" 2025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 2125b3c049e70834cf33790a28643ab058b507b35cBen Chengnamespace llvm { 2225b3c049e70834cf33790a28643ab058b507b35cBen Cheng class ConstantInt; 2325b3c049e70834cf33790a28643ab058b507b35cBen Cheng class ConstantRange; 2425b3c049e70834cf33790a28643ab058b507b35cBen Cheng class DominatorTree; 2525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 2625b3c049e70834cf33790a28643ab058b507b35cBen Cheng enum SCEVTypes { 2725b3c049e70834cf33790a28643ab058b507b35cBen Cheng // These should be ordered in terms of increasing complexity to make the 2825b3c049e70834cf33790a28643ab058b507b35cBen Cheng // folders simpler. 2925b3c049e70834cf33790a28643ab058b507b35cBen Cheng scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 3025b3c049e70834cf33790a28643ab058b507b35cBen Cheng scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 3125b3c049e70834cf33790a28643ab058b507b35cBen Cheng scUnknown, scCouldNotCompute 3225b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 3325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 3525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVConstant - This class represents a constant integer value. 3625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 3725b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVConstant : public SCEV { 3825b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 3925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4025b3c049e70834cf33790a28643ab058b507b35cBen Cheng ConstantInt *V; 4125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 4225b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEV(ID, scConstant), V(v) {} 4325b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 4425b3c049e70834cf33790a28643ab058b507b35cBen Cheng ConstantInt *getValue() const { return V; } 4525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4625b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { return V->getType(); } 4725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 4925b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 5025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scConstant; 5125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 5225b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 5325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 5525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVCastExpr - This is the base class for unary cast operator classes. 5625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 5725b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVCastExpr : public SCEV { 5825b3c049e70834cf33790a28643ab058b507b35cBen Cheng protected: 5925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Op; 6025b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *Ty; 6125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6225b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVCastExpr(const FoldingSetNodeIDRef ID, 6325b3c049e70834cf33790a28643ab058b507b35cBen Cheng unsigned SCEVTy, const SCEV *op, Type *ty); 6425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6525b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 6625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getOperand() const { return Op; } 6725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { return Ty; } 6825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 7025b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 7125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scTruncate || 7225b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scZeroExtend || 7325b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scSignExtend; 7425b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 7525b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 7625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 7725b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 7825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVTruncateExpr - This class represents a truncation of an integer value 7925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// to a smaller integer value. 8025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 8125b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVTruncateExpr : public SCEVCastExpr { 8225b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 8325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8425b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 8525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *op, Type *ty); 8625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 8725b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 8825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 8925b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 9025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scTruncate; 9125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 9225b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 9325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 9425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 9525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVZeroExtendExpr - This class represents a zero extension of a small 9625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// integer value to a larger integer value. 9725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 9825b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVZeroExtendExpr : public SCEVCastExpr { 9925b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 10025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 10225b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *op, Type *ty); 10325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 10425b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 10525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 10625b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 10725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scZeroExtend; 10825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 10925b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 11025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11125b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 11225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVSignExtendExpr - This class represents a sign extension of a small 11325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// integer value to a larger integer value. 11425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 11525b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVSignExtendExpr : public SCEVCastExpr { 11625b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 11725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 11825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 11925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *op, Type *ty); 12025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12125b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 12225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 12325b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 12425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scSignExtend; 12525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 12625b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 12725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 12925b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 13025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVNAryExpr - This node is a base class providing common 13125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// functionality for n'ary operators. 13225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 13325b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVNAryExpr : public SCEV { 13425b3c049e70834cf33790a28643ab058b507b35cBen Cheng protected: 13525b3c049e70834cf33790a28643ab058b507b35cBen Cheng // Since SCEVs are immutable, ScalarEvolution allocates operand 13625b3c049e70834cf33790a28643ab058b507b35cBen Cheng // arrays with its SCEVAllocator, so this class just needs a simple 13725b3c049e70834cf33790a28643ab058b507b35cBen Cheng // pointer rather than a more elaborate vector-like data structure. 13825b3c049e70834cf33790a28643ab058b507b35cBen Cheng // This also avoids the need for a non-trivial destructor. 13925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *Operands; 14025b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t NumOperands; 14125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14225b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVNAryExpr(const FoldingSetNodeIDRef ID, 14325b3c049e70834cf33790a28643ab058b507b35cBen Cheng enum SCEVTypes T, const SCEV *const *O, size_t N) 14425b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEV(ID, T), Operands(O), NumOperands(N) {} 14525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 14625b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 14725b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t getNumOperands() const { return NumOperands; } 14825b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getOperand(unsigned i) const { 14925b3c049e70834cf33790a28643ab058b507b35cBen Cheng assert(i < NumOperands && "Operand index out of range!"); 15025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Operands[i]; 15125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 15225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15325b3c049e70834cf33790a28643ab058b507b35cBen Cheng typedef const SCEV *const *op_iterator; 15425b3c049e70834cf33790a28643ab058b507b35cBen Cheng op_iterator op_begin() const { return Operands; } 15525b3c049e70834cf33790a28643ab058b507b35cBen Cheng op_iterator op_end() const { return Operands + NumOperands; } 15625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { return getOperand(0)->getType(); } 15825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 15925b3c049e70834cf33790a28643ab058b507b35cBen Cheng NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 16025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return (NoWrapFlags)(SubclassData & Mask); 16125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 16225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 16325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 16425b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 16525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scAddExpr || 16625b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scMulExpr || 16725b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scSMaxExpr || 16825b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scUMaxExpr || 16925b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scAddRecExpr; 17025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 17125b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 17225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 17325b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 17425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 17525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// operators. 17625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 17725b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVCommutativeExpr : public SCEVNAryExpr { 17825b3c049e70834cf33790a28643ab058b507b35cBen Cheng protected: 17925b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 18025b3c049e70834cf33790a28643ab058b507b35cBen Cheng enum SCEVTypes T, const SCEV *const *O, size_t N) 18125b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVNAryExpr(ID, T, O, N) {} 18225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 18325b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 18425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 18525b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 18625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scAddExpr || 18725b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scMulExpr || 18825b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scSMaxExpr || 18925b3c049e70834cf33790a28643ab058b507b35cBen Cheng S->getSCEVType() == scUMaxExpr; 19025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 19125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Set flags for a non-recurrence without clearing previously set flags. 19325b3c049e70834cf33790a28643ab058b507b35cBen Cheng void setNoWrapFlags(NoWrapFlags Flags) { 19425b3c049e70834cf33790a28643ab058b507b35cBen Cheng SubclassData |= Flags; 19525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 19625b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 19725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 19925b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 20025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 20125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 20225b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVAddExpr : public SCEVCommutativeExpr { 20325b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 20425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 20525b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVAddExpr(const FoldingSetNodeIDRef ID, 20625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *O, size_t N) 20725b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 20825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 20925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21025b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 21125b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { 21225b3c049e70834cf33790a28643ab058b507b35cBen Cheng // Use the type of the last operand, which is likely to be a pointer 21325b3c049e70834cf33790a28643ab058b507b35cBen Cheng // type, if there is one. This doesn't usually matter, but it can help 21425b3c049e70834cf33790a28643ab058b507b35cBen Cheng // reduce casts when the expressions are expanded. 21525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return getOperand(getNumOperands() - 1)->getType(); 21625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 21725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 21825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 21925b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 22025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scAddExpr; 22125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 22225b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 22325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 22425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 22525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 22625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 22725b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVMulExpr : public SCEVCommutativeExpr { 22825b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 22925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23025b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVMulExpr(const FoldingSetNodeIDRef ID, 23125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *O, size_t N) 23225b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 23325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 23425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 23525b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 23625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 23725b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 23825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scMulExpr; 23925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 24025b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 24125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24325b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 24425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVUDivExpr - This class represents a binary unsigned division operation. 24525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 24625b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVUDivExpr : public SCEV { 24725b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 24825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 24925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *LHS; 25025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *RHS; 25125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 25225b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 25325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25425b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 25525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getLHS() const { return LHS; } 25625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getRHS() const { return RHS; } 25725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 25825b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { 25925b3c049e70834cf33790a28643ab058b507b35cBen Cheng // In most cases the types of LHS and RHS will be the same, but in some 26025b3c049e70834cf33790a28643ab058b507b35cBen Cheng // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 26125b3c049e70834cf33790a28643ab058b507b35cBen Cheng // depend on the type for correctness, but handling types carefully can 26225b3c049e70834cf33790a28643ab058b507b35cBen Cheng // avoid extra casts in the SCEVExpander. The LHS is more likely to be 26325b3c049e70834cf33790a28643ab058b507b35cBen Cheng // a pointer type than the RHS, so use the RHS' type here. 26425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return getRHS()->getType(); 26525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 26625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 26725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 26825b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 26925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scUDivExpr; 27025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 27125b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 27225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 27325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 27425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 27525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 27625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// count of the specified loop. This is the primary focus of the 27725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 27825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 27925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// created and analyzed. 28025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 28125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// All operands of an AddRec are required to be loop invariant. 28225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 28325b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVAddRecExpr : public SCEVNAryExpr { 28425b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 28525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 28625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const Loop *L; 28725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 28825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 28925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *O, size_t N, const Loop *l) 29025b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 29125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29225b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 29325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getStart() const { return Operands[0]; } 29425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const Loop *getLoop() const { return L; } 29525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 29625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// getStepRecurrence - This method constructs and returns the recurrence 29725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// indicating how much this expression steps by. If this is a polynomial 29825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// of degree N, it returns a chrec of degree N-1. 29925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// We cannot determine whether the step recurrence has self-wraparound. 30025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 30125b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (isAffine()) return getOperand(1); 30225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 30325b3c049e70834cf33790a28643ab058b507b35cBen Cheng op_end()), 30425b3c049e70834cf33790a28643ab058b507b35cBen Cheng getLoop(), FlagAnyWrap); 30525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 30625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 30725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// isAffine - Return true if this is an affine AddRec (i.e., it represents 30825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// an expressions A+B*x where A and B are loop invariant values. 30925b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool isAffine() const { 31025b3c049e70834cf33790a28643ab058b507b35cBen Cheng // We know that the start value is invariant. This expression is thus 31125b3c049e70834cf33790a28643ab058b507b35cBen Cheng // affine iff the step is also invariant. 31225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return getNumOperands() == 2; 31325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 31425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 31525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 31625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 31725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 31825b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool isQuadratic() const { 31925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return getNumOperands() == 3; 32025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 32125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 32225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Set flags for a recurrence without clearing any previously set flags. 32325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 32425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// to make it easier to propagate flags. 32525b3c049e70834cf33790a28643ab058b507b35cBen Cheng void setNoWrapFlags(NoWrapFlags Flags) { 32625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (Flags & (FlagNUW | FlagNSW)) 32725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Flags = ScalarEvolution::setFlags(Flags, FlagNW); 32825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SubclassData |= Flags; 32925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 33025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// evaluateAtIteration - Return the value of this chain of recurrences at 33225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// the specified iteration number. 33325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 33425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 33525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// getNumIterationsInRange - Return the number of iterations of this loop 33625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// that produce values in the specified constant range. Another way of 33725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// looking at this is that it returns the first iteration number where the 33825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// value is not in the condition, thus computing the exit count. If the 33925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 34025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// returned. 34125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *getNumIterationsInRange(ConstantRange Range, 34225b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution &SE) const; 34325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 34425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// getPostIncExpr - Return an expression representing the value of 34525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// this expression one iteration of the loop ahead. 34625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 34725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 34825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 34925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 35125b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 35225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scAddRecExpr; 35325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 35425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 35525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Splits the SCEV into two vectors of SCEVs representing the subscripts 35625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// and sizes of an array access. Returns the remainder of the 35725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// delinearization that is the offset start of the array. 35825b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *delinearize(ScalarEvolution &SE, 35925b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVectorImpl<const SCEV *> &Subscripts, 36025b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVectorImpl<const SCEV *> &Sizes) const; 36125b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 36225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36325b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 36425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVSMaxExpr - This class represents a signed maximum selection. 36525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 36625b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVSMaxExpr : public SCEVCommutativeExpr { 36725b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 36825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 36925b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 37025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *O, size_t N) 37125b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 37225b3c049e70834cf33790a28643ab058b507b35cBen Cheng // Max never overflows. 37325b3c049e70834cf33790a28643ab058b507b35cBen Cheng setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 37425b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 37525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 37625b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 37725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 37825b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 37925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scSMaxExpr; 38025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 38125b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 38225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 38325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 38425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 38525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 38625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 38725b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVUMaxExpr : public SCEVCommutativeExpr { 38825b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 38925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 39025b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 39125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *const *O, size_t N) 39225b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 39325b3c049e70834cf33790a28643ab058b507b35cBen Cheng // Max never overflows. 39425b3c049e70834cf33790a28643ab058b507b35cBen Cheng setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 39525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 39625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 39725b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 39825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 39925b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 40025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scUMaxExpr; 40125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 40225b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 40325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 40425b3c049e70834cf33790a28643ab058b507b35cBen Cheng //===--------------------------------------------------------------------===// 40525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 40625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// value, and only represent it as its LLVM Value. This is the "bottom" 40725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// value for the analysis. 40825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 40925b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVUnknown : public SCEV, private CallbackVH { 41025b3c049e70834cf33790a28643ab058b507b35cBen Cheng friend class ScalarEvolution; 41125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 41225b3c049e70834cf33790a28643ab058b507b35cBen Cheng // Implement CallbackVH. 41325b3c049e70834cf33790a28643ab058b507b35cBen Cheng void deleted() override; 41425b3c049e70834cf33790a28643ab058b507b35cBen Cheng void allUsesReplacedWith(Value *New) override; 41525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 41625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SE - The parent ScalarEvolution value. This is used to update 41725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// the parent's maps when the value associated with a SCEVUnknown 41825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// is deleted or RAUW'd. 41925b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution *SE; 42025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 42125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Next - The next pointer in the linked list of all 42225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVUnknown instances owned by a ScalarEvolution. 42325b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVUnknown *Next; 42425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 42525b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 42625b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution *se, SCEVUnknown *next) : 42725b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 42825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 42925b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 43025b3c049e70834cf33790a28643ab058b507b35cBen Cheng Value *getValue() const { return getValPtr(); } 43125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 43225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 43325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// constant representing a type size, alignment, or field offset in 43425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// a target-independent manner, and hasn't happened to have been 43525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// folded with other operations into something unrecognizable. This 43625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// is mainly only useful for pretty-printing and other situations 43725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// where it isn't absolutely required for these to succeed. 43825b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool isSizeOf(Type *&AllocTy) const; 43925b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool isAlignOf(Type *&AllocTy) const; 44025b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 44125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 44225b3c049e70834cf33790a28643ab058b507b35cBen Cheng Type *getType() const { return getValPtr()->getType(); } 44325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 44425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Methods for support type inquiry through isa, cast, and dyn_cast: 44525b3c049e70834cf33790a28643ab058b507b35cBen Cheng static inline bool classof(const SCEV *S) { 44625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return S->getSCEVType() == scUnknown; 44725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 44825b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 44925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 45025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// SCEVVisitor - This class defines a simple visitor class that may be used 45125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// for various SCEV analysis purposes. 45225b3c049e70834cf33790a28643ab058b507b35cBen Cheng template<typename SC, typename RetVal=void> 45325b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct SCEVVisitor { 45425b3c049e70834cf33790a28643ab058b507b35cBen Cheng RetVal visit(const SCEV *S) { 45525b3c049e70834cf33790a28643ab058b507b35cBen Cheng switch (S->getSCEVType()) { 45625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scConstant: 45725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitConstant((const SCEVConstant*)S); 45825b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scTruncate: 45925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 46025b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scZeroExtend: 46125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 46225b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scSignExtend: 46325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 46425b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scAddExpr: 46525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 46625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scMulExpr: 46725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 46825b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUDivExpr: 46925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 47025b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scAddRecExpr: 47125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 47225b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scSMaxExpr: 47325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 47425b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUMaxExpr: 47525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 47625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUnknown: 47725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 47825b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scCouldNotCompute: 47925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 48025b3c049e70834cf33790a28643ab058b507b35cBen Cheng default: 48125b3c049e70834cf33790a28643ab058b507b35cBen Cheng llvm_unreachable("Unknown SCEV type!"); 48225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 48325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 48425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 48525b3c049e70834cf33790a28643ab058b507b35cBen Cheng RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 48625b3c049e70834cf33790a28643ab058b507b35cBen Cheng llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 48725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 48825b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 48925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 49025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Visit all nodes in the expression tree using worklist traversal. 49125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// 49225b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Visitor implements: 49325b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// // return true to follow this node. 49425b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// bool follow(const SCEV *S); 49525b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// // return true to terminate the search. 49625b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// bool isDone(); 49725b3c049e70834cf33790a28643ab058b507b35cBen Cheng template<typename SV> 49825b3c049e70834cf33790a28643ab058b507b35cBen Cheng class SCEVTraversal { 49925b3c049e70834cf33790a28643ab058b507b35cBen Cheng SV &Visitor; 50025b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 8> Worklist; 50125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallPtrSet<const SCEV *, 8> Visited; 50225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 50325b3c049e70834cf33790a28643ab058b507b35cBen Cheng void push(const SCEV *S) { 50425b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (Visited.insert(S) && Visitor.follow(S)) 50525b3c049e70834cf33790a28643ab058b507b35cBen Cheng Worklist.push_back(S); 50625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 50725b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 50825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVTraversal(SV& V): Visitor(V) {} 50925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 51025b3c049e70834cf33790a28643ab058b507b35cBen Cheng void visitAll(const SCEV *Root) { 51125b3c049e70834cf33790a28643ab058b507b35cBen Cheng push(Root); 51225b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (!Worklist.empty() && !Visitor.isDone()) { 51325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *S = Worklist.pop_back_val(); 51425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 51525b3c049e70834cf33790a28643ab058b507b35cBen Cheng switch (S->getSCEVType()) { 51625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scConstant: 51725b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUnknown: 51825b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 51925b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scTruncate: 52025b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scZeroExtend: 52125b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scSignExtend: 52225b3c049e70834cf33790a28643ab058b507b35cBen Cheng push(cast<SCEVCastExpr>(S)->getOperand()); 52325b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 52425b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scAddExpr: 52525b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scMulExpr: 52625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scSMaxExpr: 52725b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUMaxExpr: 52825b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scAddRecExpr: { 52925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 53025b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 53125b3c049e70834cf33790a28643ab058b507b35cBen Cheng E = NAry->op_end(); I != E; ++I) { 53225b3c049e70834cf33790a28643ab058b507b35cBen Cheng push(*I); 53325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 53425b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 53525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 53625b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scUDivExpr: { 53725b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 53825b3c049e70834cf33790a28643ab058b507b35cBen Cheng push(UDiv->getLHS()); 53925b3c049e70834cf33790a28643ab058b507b35cBen Cheng push(UDiv->getRHS()); 54025b3c049e70834cf33790a28643ab058b507b35cBen Cheng break; 54125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 54225b3c049e70834cf33790a28643ab058b507b35cBen Cheng case scCouldNotCompute: 54325b3c049e70834cf33790a28643ab058b507b35cBen Cheng llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 54425b3c049e70834cf33790a28643ab058b507b35cBen Cheng default: 54525b3c049e70834cf33790a28643ab058b507b35cBen Cheng llvm_unreachable("Unknown SCEV kind!"); 54625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 54725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 54825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 54925b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 55025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 55125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// Use SCEVTraversal to visit all nodes in the givien expression tree. 55225b3c049e70834cf33790a28643ab058b507b35cBen Cheng template<typename SV> 55325b3c049e70834cf33790a28643ab058b507b35cBen Cheng void visitAll(const SCEV *Root, SV& Visitor) { 55425b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVTraversal<SV> T(Visitor); 55525b3c049e70834cf33790a28643ab058b507b35cBen Cheng T.visitAll(Root); 55625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 55725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 55825b3c049e70834cf33790a28643ab058b507b35cBen Cheng typedef DenseMap<const Value*, Value*> ValueToValueMap; 55925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 56025b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// The SCEVParameterRewriter takes a scalar evolution expression and updates 56125b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// the SCEVUnknown components following the Map (Value -> Value). 56225b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct SCEVParameterRewriter 56325b3c049e70834cf33790a28643ab058b507b35cBen Cheng : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { 56425b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 56525b3c049e70834cf33790a28643ab058b507b35cBen Cheng static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 56625b3c049e70834cf33790a28643ab058b507b35cBen Cheng ValueToValueMap &Map, 56725b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool InterpretConsts = false) { 56825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts); 56925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Rewriter.visit(Scev); 57025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 57125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 57225b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C) 57325b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SE(S), Map(M), InterpretConsts(C) {} 57425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 57525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitConstant(const SCEVConstant *Constant) { 57625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Constant; 57725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 57825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 57925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 58025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 58125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getTruncateExpr(Operand, Expr->getType()); 58225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 58325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 58425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 58525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 58625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getZeroExtendExpr(Operand, Expr->getType()); 58725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 58825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 58925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 59025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 59125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getSignExtendExpr(Operand, Expr->getType()); 59225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 59325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 59425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 59525b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 59625b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 59725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 59825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getAddExpr(Operands); 59925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 60025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 60125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 60225b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 60325b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 60425b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 60525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getMulExpr(Operands); 60625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 60725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 60825b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 60925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 61025b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 61125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 61225b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 61325b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 61425b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 61525b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 61625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getAddRecExpr(Operands, Expr->getLoop(), 61725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Expr->getNoWrapFlags()); 61825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 61925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 62025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 62125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 62225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 62325b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 62425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getSMaxExpr(Operands); 62525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 62625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 62725b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 62825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 62925b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 63025b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 63125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getUMaxExpr(Operands); 63225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 63325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 63425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUnknown(const SCEVUnknown *Expr) { 63525b3c049e70834cf33790a28643ab058b507b35cBen Cheng Value *V = Expr->getValue(); 63625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (Map.count(V)) { 63725b3c049e70834cf33790a28643ab058b507b35cBen Cheng Value *NV = Map[V]; 63825b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (InterpretConsts && isa<ConstantInt>(NV)) 63925b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getConstant(cast<ConstantInt>(NV)); 64025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getUnknown(NV); 64125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 64225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Expr; 64325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 64425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 64525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 64625b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Expr; 64725b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 64825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 64925b3c049e70834cf33790a28643ab058b507b35cBen Cheng private: 65025b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution &SE; 65125b3c049e70834cf33790a28643ab058b507b35cBen Cheng ValueToValueMap ⤅ 65225b3c049e70834cf33790a28643ab058b507b35cBen Cheng bool InterpretConsts; 65325b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 65425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 65525b3c049e70834cf33790a28643ab058b507b35cBen Cheng typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; 65625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 65725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// The SCEVApplyRewriter takes a scalar evolution expression and applies 65825b3c049e70834cf33790a28643ab058b507b35cBen Cheng /// the Map (Loop -> SCEV) to all AddRecExprs. 65925b3c049e70834cf33790a28643ab058b507b35cBen Cheng struct SCEVApplyRewriter 66025b3c049e70834cf33790a28643ab058b507b35cBen Cheng : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> { 66125b3c049e70834cf33790a28643ab058b507b35cBen Cheng public: 66225b3c049e70834cf33790a28643ab058b507b35cBen Cheng static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, 66325b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution &SE) { 66425b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVApplyRewriter Rewriter(SE, Map); 66525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Rewriter.visit(Scev); 66625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 66725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 66825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) 66925b3c049e70834cf33790a28643ab058b507b35cBen Cheng : SE(S), Map(M) {} 67025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 67125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitConstant(const SCEVConstant *Constant) { 67225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Constant; 67325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 67425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 67525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 67625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 67725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getTruncateExpr(Operand, Expr->getType()); 67825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 67925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 68025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 68125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 68225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getZeroExtendExpr(Operand, Expr->getType()); 68325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 68425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 68525b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 68625b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Operand = visit(Expr->getOperand()); 68725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getSignExtendExpr(Operand, Expr->getType()); 68825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 68925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 69025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 69125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 69225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 69325b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 69425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getAddExpr(Operands); 69525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 69625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 69725b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 69825b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 69925b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 70025b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 70125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getMulExpr(Operands); 70225b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 70325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 70425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 70525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 70625b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 70725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 70825b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 70925b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 71025b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 71125b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 71225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 71325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const Loop *L = Expr->getLoop(); 71425b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); 71525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 71625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (0 == Map.count(L)) 71725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Res; 71825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 71925b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; 72025b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Rec->evaluateAtIteration(Map[L], SE); 72125b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 72225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 72325b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 72425b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 72525b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 72625b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 72725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getSMaxExpr(Operands); 72825b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 72925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 73025b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 73125b3c049e70834cf33790a28643ab058b507b35cBen Cheng SmallVector<const SCEV *, 2> Operands; 73225b3c049e70834cf33790a28643ab058b507b35cBen Cheng for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 73325b3c049e70834cf33790a28643ab058b507b35cBen Cheng Operands.push_back(visit(Expr->getOperand(i))); 73425b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SE.getUMaxExpr(Operands); 73525b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 73625b3c049e70834cf33790a28643ab058b507b35cBen Cheng 73725b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitUnknown(const SCEVUnknown *Expr) { 73825b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Expr; 73925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 74025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 74125b3c049e70834cf33790a28643ab058b507b35cBen Cheng const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 74225b3c049e70834cf33790a28643ab058b507b35cBen Cheng return Expr; 74325b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 74425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 74525b3c049e70834cf33790a28643ab058b507b35cBen Cheng private: 74625b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution &SE; 74725b3c049e70834cf33790a28643ab058b507b35cBen Cheng LoopToScevMapT ⤅ 74825b3c049e70834cf33790a28643ab058b507b35cBen Cheng }; 74925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 75025b3c049e70834cf33790a28643ab058b507b35cBen Cheng/// Applies the Map (Loop -> SCEV) to the given Scev. 75125b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, 75225b3c049e70834cf33790a28643ab058b507b35cBen Cheng ScalarEvolution &SE) { 75325b3c049e70834cf33790a28643ab058b507b35cBen Cheng return SCEVApplyRewriter::rewrite(Scev, Map, SE); 75425b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 75525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 75625b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 75725b3c049e70834cf33790a28643ab058b507b35cBen Cheng 75825b3c049e70834cf33790a28643ab058b507b35cBen Cheng#endif 75925b3c049e70834cf33790a28643ab058b507b35cBen Cheng