ScalarEvolutionExpressions.h revision b075ed3b90fa2a520aeb15802fddf3460d865f91
14950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 34950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// The LLVM Compiler Infrastructure 44950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 84950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 94950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file defines the classes used to represent and build scalar expressions. 119769ab22265b313171d201b5928688524a01bd87Misha Brukman// 124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1718a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick#include "llvm/ADT/SmallPtrSet.h" 18255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Analysis/ScalarEvolution.h" 19c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattnernamespace llvm { 224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantInt; 234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantRange; 245a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng class DominatorTree; 254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner enum SCEVTypes { 274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // These should be ordered in terms of increasing complexity to make the 284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // folders simpler. 29d19534add90a2a894af61523b830887097bb780bDan Gohman scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 30c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 310f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman scUnknown, scCouldNotCompute 324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVConstant - This class represents a constant integer value. 364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVConstant : public SCEV { 38246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 39246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *V; 413bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 423bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEV(ID, scConstant), V(v) {} 434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *getValue() const { return V; } 454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 46db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { return V->getType(); } 474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 5584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVCastExpr - This is the base class for unary cast operator classes. 564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 5784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVCastExpr : public SCEV { 5884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman protected: 590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Op; 60db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty; 6184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 623bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVCastExpr(const FoldingSetNodeIDRef ID, 63db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner unsigned SCEVTy, const SCEV *op, Type *ty); 6484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 660bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand() const { return Op; } 67db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { return Ty; } 68fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman 6984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 7084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman static inline bool classof(const SCEV *S) { 7184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman return S->getSCEVType() == scTruncate || 7284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scZeroExtend || 7384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scSignExtend; 7484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman } 7584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman }; 7684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 7784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman //===--------------------------------------------------------------------===// 7884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVTruncateExpr - This class represents a truncation of an integer value 7984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// to a smaller integer value. 8084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// 8184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVTruncateExpr : public SCEVCastExpr { 8284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman friend class ScalarEvolution; 8384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 843bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 85db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *op, Type *ty); 8684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 8784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 9884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVZeroExtendExpr : public SCEVCastExpr { 99246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 100246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 1013bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 102db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *op, Type *ty); 1034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 10484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 1054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 111d19534add90a2a894af61523b830887097bb780bDan Gohman //===--------------------------------------------------------------------===// 112d19534add90a2a894af61523b830887097bb780bDan Gohman /// SCEVSignExtendExpr - This class represents a sign extension of a small 113d19534add90a2a894af61523b830887097bb780bDan Gohman /// integer value to a larger integer value. 114d19534add90a2a894af61523b830887097bb780bDan Gohman /// 11584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVSignExtendExpr : public SCEVCastExpr { 116246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 117246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 1183bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 119db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const SCEV *op, Type *ty); 120d19534add90a2a894af61523b830887097bb780bDan Gohman 12184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 122d19534add90a2a894af61523b830887097bb780bDan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 123d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEV *S) { 124d19534add90a2a894af61523b830887097bb780bDan Gohman return S->getSCEVType() == scSignExtend; 125d19534add90a2a894af61523b830887097bb780bDan Gohman } 126d19534add90a2a894af61523b830887097bb780bDan Gohman }; 127d19534add90a2a894af61523b830887097bb780bDan Gohman 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 129d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman //===--------------------------------------------------------------------===// 130d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// SCEVNAryExpr - This node is a base class providing common 131d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// functionality for n'ary operators. 132d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// 133ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVNAryExpr : public SCEV { 134ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 135f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // Since SCEVs are immutable, ScalarEvolution allocates operand 136f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // arrays with its SCEVAllocator, so this class just needs a simple 137f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // pointer rather than a more elaborate vector-like data structure. 138f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // This also avoids the need for a non-trivial destructor. 139f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *Operands; 140f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman size_t NumOperands; 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1423bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVNAryExpr(const FoldingSetNodeIDRef ID, 143f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman enum SCEVTypes T, const SCEV *const *O, size_t N) 1443bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEV(ID, T), Operands(O), NumOperands(N) {} 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 147f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman size_t getNumOperands() const { return NumOperands; } 1480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand(unsigned i) const { 149f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman assert(i < NumOperands && "Operand index out of range!"); 1504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 1514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 153f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman typedef const SCEV *const *op_iterator; 154f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman op_iterator op_begin() const { return Operands; } 155f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman op_iterator op_end() const { return Operands + NumOperands; } 1564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 157db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { return getOperand(0)->getType(); } 158ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 1593228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 1603228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick return (NoWrapFlags)(SubclassData & Mask); 1613645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman } 1623645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman 163ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 164ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman static inline bool classof(const SCEV *S) { 165ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman return S->getSCEVType() == scAddExpr || 166ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scMulExpr || 167ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scSMaxExpr || 168ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scUMaxExpr || 169ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scAddRecExpr; 170ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman } 171ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman }; 172ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 173ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman //===--------------------------------------------------------------------===// 174ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 175ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// operators. 176ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// 177ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVCommutativeExpr : public SCEVNAryExpr { 178ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 1793bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 180c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman enum SCEVTypes T, const SCEV *const *O, size_t N) 1813bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVNAryExpr(ID, T, O, N) {} 182ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 183ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 1844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 187c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky S->getSCEVType() == scMulExpr || 1883e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scSMaxExpr || 1893e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scUMaxExpr; 1904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1913228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick 1923228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// Set flags for a non-recurrence without clearing previously set flags. 1933228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick void setNoWrapFlags(NoWrapFlags Flags) { 1943228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SubclassData |= Flags; 1953228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick } 1964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 203246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 204246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2053bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVAddExpr(const FoldingSetNodeIDRef ID, 206f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 2073bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 2084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 211db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { 2122b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // Use the type of the last operand, which is likely to be a pointer 2132b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // type, if there is one. This doesn't usually matter, but it can help 2142b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // reduce casts when the expressions are expanded. 2152b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman return getOperand(getNumOperands() - 1)->getType(); 2162b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman } 2172b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman 2184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 2214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 228246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 229246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2303bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVMulExpr(const FoldingSetNodeIDRef ID, 231f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 2323bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 2334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 244e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz /// SCEVUDivExpr - This class represents a binary unsigned division operation. 2454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 246e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz class SCEVUDivExpr : public SCEV { 247246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 248246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *LHS; 2500bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS; 2513bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 2523bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 2534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2550bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getLHS() const { return LHS; } 2560bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getRHS() const { return RHS; } 2574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 258db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { 2594ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman // In most cases the types of LHS and RHS will be the same, but in some 2604ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 2614ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman // depend on the type for correctness, but handling types carefully can 2624ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman // avoid extra casts in the SCEVExpander. The LHS is more likely to be 2634ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman // a pointer type than the RHS, so use the RHS' type here. 2644ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman return getRHS()->getType(); 265afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 266afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 2674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 269e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz return S->getSCEVType() == scUDivExpr; 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 2761e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// count of the specified loop. This is the primary focus of the 2771e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 2781e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 2791e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// created and analyzed. 2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 283ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVAddRecExpr : public SCEVNAryExpr { 284246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 285246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2883bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 289f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N, const Loop *l) 290203a7239ae928568fe7a34c03ead4b1b3133870eDan Gohman : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 292ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 2930bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStart() const { return Operands[0]; } 2944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 2954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 2993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// We cannot determine whether the step recurrence has self-wraparound. 3000bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 30117f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (isAffine()) return getOperand(1); 3020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 3030bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman op_end()), 3043228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick getLoop(), FlagAnyWrap); 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 3094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 31194c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // affine iff the step is also invariant. 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3223228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// Set flags for a recurrence without clearing any previously set flags. 3233228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 3243228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick /// to make it easier to propagate flags. 3253228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick void setNoWrapFlags(NoWrapFlags Flags) { 3263228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick if (Flags & (FlagNUW | FlagNSW)) 3273228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick Flags = ScalarEvolution::setFlags(Flags, FlagNW); 3283228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick SubclassData |= Flags; 3293228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick } 3303228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick 3314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 3324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 3330bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 3344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 3384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 3394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 340eefdebe002ede066bf80859e72aec831cfd1d92dNick Lewycky /// returned. 3410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNumIterationsInRange(ConstantRange Range, 342246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 344c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// getPostIncExpr - Return an expression representing the value of 345c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// this expression one iteration of the loop ahead. 346fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 347fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 348c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman } 349c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman 3504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 3534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 356c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 357c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky //===--------------------------------------------------------------------===// 358c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// SCEVSMaxExpr - This class represents a signed maximum selection. 359c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// 360c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky class SCEVSMaxExpr : public SCEVCommutativeExpr { 361c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky friend class ScalarEvolution; 362c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 3633bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 364f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 3653bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 3663645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman // Max never overflows. 3673228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 368c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 369c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 370c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky public: 371c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 372c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEV *S) { 373c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return S->getSCEVType() == scSMaxExpr; 374c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 375c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky }; 376c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 377c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3793e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 3803e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 3813e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky class SCEVUMaxExpr : public SCEVCommutativeExpr { 3823e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky friend class ScalarEvolution; 3833e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 3843bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 385f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 3863bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 3873645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman // Max never overflows. 3883228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 3893e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 3903e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 3913e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky public: 3923e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 3933e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEV *S) { 3943e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return S->getSCEVType() == scUMaxExpr; 3953e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 3963e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky }; 3973e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 398c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman //===--------------------------------------------------------------------===// 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 40075144f93eb7e4dbf22d308d21581ae255dd520c6Dan Gohman /// value, and only represent it as its LLVM Value. This is the "bottom" 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 403ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman class SCEVUnknown : public SCEV, private CallbackVH { 404246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 405246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 406ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman // Implement CallbackVH. 407ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman virtual void deleted(); 408ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman virtual void allUsesReplacedWith(Value *New); 409ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 410ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// SE - The parent ScalarEvolution value. This is used to update 411ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// the parent's maps when the value associated with a SCEVUnknown 412ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// is deleted or RAUW'd. 413ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman ScalarEvolution *SE; 414ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 415ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// Next - The next pointer in the linked list of all 416ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// SCEVUnknown instances owned by a ScalarEvolution. 417ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown *Next; 418ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 419ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 420ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman ScalarEvolution *se, SCEVUnknown *next) : 421ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 4221c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 423c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman public: 424ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman Value *getValue() const { return getValPtr(); } 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4260f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 4270f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// constant representing a type size, alignment, or field offset in 4280f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// a target-independent manner, and hasn't happened to have been 4290f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// folded with other operations into something unrecognizable. This 4300f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// is mainly only useful for pretty-printing and other situations 4310f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// where it isn't absolutely required for these to succeed. 432db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool isSizeOf(Type *&AllocTy) const; 433db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool isAlignOf(Type *&AllocTy) const; 434db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 4350f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman 436db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *getType() const { return getValPtr()->getType(); } 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4432cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 4442cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 4452cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 4462cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 4472cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 448890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visit(const SCEV *S) { 4492cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 4502cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 451890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitConstant((const SCEVConstant*)S); 4522cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 453890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 4542cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 455890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 456d19534add90a2a894af61523b830887097bb780bDan Gohman case scSignExtend: 457890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 4582cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 459890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 4602cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 461890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 462e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz case scUDivExpr: 463890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 4642cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 465890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 466c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky case scSMaxExpr: 467890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 4683e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky case scUMaxExpr: 469890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 4702cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 471890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 4722cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 473890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 4742cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 475c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unknown SCEV type!"); 4762cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 4772cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 4782cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 479890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 480c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 4812cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 4822cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 4838b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick 4848b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// Visit all nodes in the expression tree using worklist traversal. 4858b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// 4868b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// Visitor implements: 4878b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// // return true to follow this node. 4888b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// bool follow(const SCEV *S); 4898b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// // return true to terminate the search. 4908b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// bool isDone(); 4918b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick template<typename SV> 4928b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick class SCEVTraversal { 4938b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick SV &Visitor; 4948b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick SmallVector<const SCEV *, 8> Worklist; 49518a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick SmallPtrSet<const SCEV *, 8> Visited; 4968b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick 4978b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick void push(const SCEV *S) { 49818a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick if (Visited.insert(S) && Visitor.follow(S)) 4998b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick Worklist.push_back(S); 5008b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5018b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick public: 5028b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick SCEVTraversal(SV& V): Visitor(V) {} 5038b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick 5048b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick void visitAll(const SCEV *Root) { 5058b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick push(Root); 5068b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick while (!Worklist.empty() && !Visitor.isDone()) { 5078b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick const SCEV *S = Worklist.pop_back_val(); 5088b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick 5098b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick switch (S->getSCEVType()) { 5108b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scConstant: 5118b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scUnknown: 5128b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick break; 5138b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scTruncate: 5148b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scZeroExtend: 5158b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scSignExtend: 5168b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick push(cast<SCEVCastExpr>(S)->getOperand()); 5178b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick break; 5188b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scAddExpr: 5198b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scMulExpr: 5208b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scSMaxExpr: 5218b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scUMaxExpr: 5228b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scAddRecExpr: { 5238b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 5248b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 5258b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick E = NAry->op_end(); I != E; ++I) { 5268b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick push(*I); 5278b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5288b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick break; 5298b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5308b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scUDivExpr: { 5318b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 5328b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick push(UDiv->getLHS()); 5338b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick push(UDiv->getRHS()); 5348b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick break; 5358b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5368b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick case scCouldNotCompute: 5378b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 5388b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick default: 5398b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick llvm_unreachable("Unknown SCEV kind!"); 5408b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5418b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5428b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 5438b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick }; 5448b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick 5458b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick /// Use SCEVTraversal to visit all nodes in the givien expression tree. 5468b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick template<typename SV> 5478b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick void visitAll(const SCEV *Root, SV& Visitor) { 5488b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick SCEVTraversal<SV> T(Visitor); 5498b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick T.visitAll(Root); 5508b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick } 551a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 5520deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop /// The SCEVRewriter takes a scalar evolution expression and copies all its 553a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop /// components. The result after a rewrite is an identical SCEV. 5540deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop struct SCEVRewriter 5550deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop : public SCEVVisitor<SCEVRewriter, const SCEV*> { 556a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop public: 5570deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop SCEVRewriter(ScalarEvolution &S) : SE(S) {} 558a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 559b075ed3b90fa2a520aeb15802fddf3460d865f91Matt Beaumont-Gay virtual ~SCEVRewriter() {} 560b075ed3b90fa2a520aeb15802fddf3460d865f91Matt Beaumont-Gay 561a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitConstant(const SCEVConstant *Constant) { 562a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return Constant; 563a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 564a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 565a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 566a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop const SCEV *Operand = visit(Expr->getOperand()); 567a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getTruncateExpr(Operand, Expr->getType()); 568a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 569a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 570a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 571a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop const SCEV *Operand = visit(Expr->getOperand()); 572a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getZeroExtendExpr(Operand, Expr->getType()); 573a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 574a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 575a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 576a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop const SCEV *Operand = visit(Expr->getOperand()); 577a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getSignExtendExpr(Operand, Expr->getType()); 578a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 579a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 580a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 581a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop SmallVector<const SCEV *, 2> Operands; 582a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 583a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 584a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getAddExpr(Operands); 585a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 586a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 587a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 588a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop SmallVector<const SCEV *, 2> Operands; 589a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 590a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 591a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getMulExpr(Operands); 592a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 593a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 594a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 595a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 596a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 597a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 598a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 599a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop SmallVector<const SCEV *, 2> Operands; 600a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 601a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 602a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getAddRecExpr(Operands, Expr->getLoop(), 603a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Expr->getNoWrapFlags()); 604a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 605a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 606a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 607a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop SmallVector<const SCEV *, 2> Operands; 608a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 609a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 610a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getSMaxExpr(Operands); 611a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 612a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 613a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 614a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop SmallVector<const SCEV *, 2> Operands; 615a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 616a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 617a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getUMaxExpr(Operands); 618a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 619a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 620a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { 621a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return Expr; 622a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 623a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 624a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 625a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return Expr; 626a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 627a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 628a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop protected: 629a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop ScalarEvolution &SE; 630a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop }; 631a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 632a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop typedef DenseMap<const Value*, Value*> ValueToValueMap; 633a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 6340deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop /// The SCEVParameterRewriter takes a scalar evolution expression and updates 635a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop /// the SCEVUnknown components following the Map (Value -> Value). 6360deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop struct SCEVParameterRewriter: public SCEVRewriter { 637a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop public: 638a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 639a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop ValueToValueMap &Map) { 6400deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop SCEVParameterRewriter Rewriter(SE, Map); 641a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return Rewriter.visit(Scev); 642a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 6430deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) 6440deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop : SCEVRewriter(S), Map(M) {} 645a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 646a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { 647a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop Value *V = Expr->getValue(); 648a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop if (Map.count(V)) 649a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return SE.getUnknown(Map[V]); 650a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop return Expr; 651a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop } 652a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 653a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop private: 654a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop ValueToValueMap ⤅ 655a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop }; 656a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop 6575661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; 6585661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6590deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop /// The SCEVApplyRewriter takes a scalar evolution expression and applies 6605661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop /// the Map (Loop -> SCEV) to all AddRecExprs. 6610deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop struct SCEVApplyRewriter: public SCEVRewriter { 6625661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop public: 6635661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, 6645661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop ScalarEvolution &SE) { 6650deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop SCEVApplyRewriter Rewriter(SE, Map); 6665661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop return Rewriter.visit(Scev); 6675661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop } 6680deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) 6690deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop : SCEVRewriter(S), Map(M) {} 6705661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6715661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 6725661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop SmallVector<const SCEV *, 2> Operands; 6735661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 6745661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop Operands.push_back(visit(Expr->getOperand(i))); 6755661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6765661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop const Loop *L = Expr->getLoop(); 6775661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); 6785661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6795661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop if (0 == Map.count(L)) 6805661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop return Res; 6815661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6825661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; 6835661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop return Rec->evaluateAtIteration(Map[L], SE); 6845661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop } 6855661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6865661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop private: 6875661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop LoopToScevMapT ⤅ 6885661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop }; 6895661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6905661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop/// Applies the Map (Loop -> SCEV) to the given Scev. 6915661fcdde295645e5c6f982a25225e682727b5b1Sebastian Popstatic inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, 6925661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop ScalarEvolution &SE) { 6930deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop return SCEVApplyRewriter::rewrite(Scev, Map, SE); 6945661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop} 6955661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop 6964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 6974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 6984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 699