ScalarEvolutionExpressions.h revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
11ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 2b9056914e2627627ffdd615e078a9b6020ab1cf2philip.liard@gmail.com// 31ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// The LLVM Compiler Infrastructure 41ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// 51ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// This file is distributed under the University of Illinois Open Source 61ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// License. See LICENSE.TXT for details. 71ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// 81ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com//===----------------------------------------------------------------------===// 91ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// 101ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// This file defines the classes used to represent and build scalar expressions. 111ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com// 121ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com//===----------------------------------------------------------------------===// 131ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com 141ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 151ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 164784d0d0f3a84cdac8d7a6b99b72fbb6b1a98ca5philip.liard@gmail.com 171ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#include "llvm/ADT/iterator_range.h" 181ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#include "llvm/ADT/SmallPtrSet.h" 191ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#include "llvm/Analysis/ScalarEvolution.h" 201ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com#include "llvm/Support/ErrorHandling.h" 211ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com 221ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.comnamespace llvm { 231ad5e5bc944bfb46689d87ace2773109cb54f5ephilip.liard@gmail.com class ConstantInt; 24f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class ConstantRange; 253c98f629715fe49ee237cc9f3d9d5292478559afphilip.liard@gmail.com class DominatorTree; 2694dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com 2794dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com enum SCEVTypes { 2894dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com // These should be ordered in terms of increasing complexity to make the 2994dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com // folders simpler. 3094dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 3194dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 323c98f629715fe49ee237cc9f3d9d5292478559afphilip.liard@gmail.com scUnknown, scCouldNotCompute 333c98f629715fe49ee237cc9f3d9d5292478559afphilip.liard@gmail.com }; 3494dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com 3594dde5dd9944ad7fb16c1a45ddc79893b08dfa20philip.liard@gmail.com //===--------------------------------------------------------------------===// 3680b803ff192366d6bae636f40502131dace9abb5philip.liard@gmail.com /// SCEVConstant - This class represents a constant integer value. 37f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 38f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVConstant : public SCEV { 39f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 40f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 41f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com ConstantInt *V; 42f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 43f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEV(ID, scConstant), V(v) {} 44f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 45f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com ConstantInt *getValue() const { return V; } 46f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 47f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Type *getType() const { return V->getType(); } 48f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 49f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 50f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 51f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scConstant; 52f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 53f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 54f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 55f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 56f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVCastExpr - This is the base class for unary cast operator classes. 57f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 58f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVCastExpr : public SCEV { 59f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com protected: 60f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *Op; 61f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Type *Ty; 62f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 63f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVCastExpr(const FoldingSetNodeIDRef ID, 64f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com unsigned SCEVTy, const SCEV *op, Type *ty); 65b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com 66f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 67f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *getOperand() const { return Op; } 68f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Type *getType() const { return Ty; } 69f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 70f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 71f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 72f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scTruncate || 73f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scZeroExtend || 74f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scSignExtend; 75f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 76f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 77f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 78f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 79f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVTruncateExpr - This class represents a truncation of an integer value 80f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// to a smaller integer value. 81f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 82f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVTruncateExpr : public SCEVCastExpr { 83f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 84f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 85f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 86f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *op, Type *ty); 87f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 88f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 89f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 90f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 91f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scTruncate; 92f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 93f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 94f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 95f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 96f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVZeroExtendExpr - This class represents a zero extension of a small 97f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// integer value to a larger integer value. 98f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 99f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVZeroExtendExpr : public SCEVCastExpr { 100f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 101f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 102f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 103f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *op, Type *ty); 104f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 105f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 106f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 107f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 108f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scZeroExtend; 109f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 110f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 111f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 112f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 113f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVSignExtendExpr - This class represents a sign extension of a small 114f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// integer value to a larger integer value. 115f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 116f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVSignExtendExpr : public SCEVCastExpr { 117f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 118f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 119f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 120f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *op, Type *ty); 121f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 122f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 123f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 124f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 125f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scSignExtend; 126f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 127f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 128f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 129f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 130f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 131f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVNAryExpr - This node is a base class providing common 132f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// functionality for n'ary operators. 133f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 134f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVNAryExpr : public SCEV { 135f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com protected: 136f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // Since SCEVs are immutable, ScalarEvolution allocates operand 137f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // arrays with its SCEVAllocator, so this class just needs a simple 138f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // pointer rather than a more elaborate vector-like data structure. 139f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // This also avoids the need for a non-trivial destructor. 140f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *const *Operands; 141f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com size_t NumOperands; 142f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 143f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVNAryExpr(const FoldingSetNodeIDRef ID, 144f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com enum SCEVTypes T, const SCEV *const *O, size_t N) 145f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com : SCEV(ID, T), Operands(O), NumOperands(N) {} 146f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 147f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 148f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com size_t getNumOperands() const { return NumOperands; } 149f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *getOperand(unsigned i) const { 150f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com assert(i < NumOperands && "Operand index out of range!"); 151f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return Operands[i]; 152f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 153f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 154f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com typedef const SCEV *const *op_iterator; 155f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com typedef iterator_range<op_iterator> op_range; 156f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com op_iterator op_begin() const { return Operands; } 157f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com op_iterator op_end() const { return Operands + NumOperands; } 158f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com op_range operands() const { 159f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return make_range(op_begin(), op_end()); 160f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 161f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 162f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Type *getType() const { return getOperand(0)->getType(); } 163f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 164f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 165f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return (NoWrapFlags)(SubclassData & Mask); 166f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 16720b634ab760e0ae3f02079325f16ebfabda2dacalararennie@google.com 168f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 169f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 170f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scAddExpr || 171f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scMulExpr || 172f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scSMaxExpr || 173f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scUMaxExpr || 174f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scAddRecExpr; 175f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 176f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 177f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 178f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 179f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 180f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// operators. 181f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 182f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVCommutativeExpr : public SCEVNAryExpr { 183f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com protected: 18420b634ab760e0ae3f02079325f16ebfabda2dacalararennie@google.com SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 185f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com enum SCEVTypes T, const SCEV *const *O, size_t N) 186f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com : SCEVNAryExpr(ID, T, O, N) {} 187f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 188f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 189f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 190f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 191f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scAddExpr || 19218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com S->getSCEVType() == scMulExpr || 193f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scSMaxExpr || 194f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com S->getSCEVType() == scUMaxExpr; 195f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 196f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 197f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Set flags for a non-recurrence without clearing previously set flags. 198f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com void setNoWrapFlags(NoWrapFlags Flags) { 199f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SubclassData |= Flags; 200f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 201f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 202f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 203f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 204f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 205f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 206f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 207f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVAddExpr : public SCEVCommutativeExpr { 208f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 209f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 210f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVAddExpr(const FoldingSetNodeIDRef ID, 211f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *const *O, size_t N) 212f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 213f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 214f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 215f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 216f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Type *getType() const { 217b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com // Use the type of the last operand, which is likely to be a pointer 218f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // type, if there is one. This doesn't usually matter, but it can help 219f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com // reduce casts when the expressions are expanded. 220f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return getOperand(getNumOperands() - 1)->getType(); 221f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 222f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 223f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 224f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 225f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scAddExpr; 226f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 227f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 228f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 229f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com //===--------------------------------------------------------------------===// 230f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 231f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// 232f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com class SCEVMulExpr : public SCEVCommutativeExpr { 233f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com friend class ScalarEvolution; 234f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 235f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com SCEVMulExpr(const FoldingSetNodeIDRef ID, 236f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com const SCEV *const *O, size_t N) 237f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 238f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 239f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 240f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com public: 241f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 242f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com static inline bool classof(const SCEV *S) { 24318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return S->getSCEVType() == scMulExpr; 24418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 24518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 24618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 24718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 24818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com //===--------------------------------------------------------------------===// 24918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVUDivExpr - This class represents a binary unsigned division operation. 25018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 25118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVUDivExpr : public SCEV { 25218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com friend class ScalarEvolution; 25318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 25418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *LHS; 25518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *RHS; 25618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 25718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 25818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 25918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 26018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *getLHS() const { return LHS; } 26118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *getRHS() const { return RHS; } 26218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 26318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Type *getType() const { 26418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // In most cases the types of LHS and RHS will be the same, but in some 26518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 26618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // depend on the type for correctness, but handling types carefully can 26718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // avoid extra casts in the SCEVExpander. The LHS is more likely to be 26818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // a pointer type than the RHS, so use the RHS' type here. 26918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return getRHS()->getType(); 27018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 27118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 27218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 27318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static inline bool classof(const SCEV *S) { 27418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return S->getSCEVType() == scUDivExpr; 27518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 27618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 27718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 27818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 27918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com //===--------------------------------------------------------------------===// 28018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 28118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// count of the specified loop. This is the primary focus of the 28218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 28318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 28418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// created and analyzed. 28518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 28618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// All operands of an AddRec are required to be loop invariant. 28718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 28818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVAddRecExpr : public SCEVNAryExpr { 28918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com friend class ScalarEvolution; 29018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 29118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const Loop *L; 29218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 29318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 29418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *const *O, size_t N, const Loop *l) 29518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 29618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 29718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 29818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *getStart() const { return Operands[0]; } 29918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const Loop *getLoop() const { return L; } 30018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 30118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// getStepRecurrence - This method constructs and returns the recurrence 30218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// indicating how much this expression steps by. If this is a polynomial 30318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// of degree N, it returns a chrec of degree N-1. 30418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// We cannot determine whether the step recurrence has self-wraparound. 30518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 30618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (isAffine()) return getOperand(1); 30718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 30818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com op_end()), 30918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com getLoop(), FlagAnyWrap); 31018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 31118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 31218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// isAffine - Return true if this is an affine AddRec (i.e., it represents 31318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// an expressions A+B*x where A and B are loop invariant values. 31418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool isAffine() const { 31518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // We know that the start value is invariant. This expression is thus 31618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // affine iff the step is also invariant. 31718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return getNumOperands() == 2; 31818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 31918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 32018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 32118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 32218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 32318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool isQuadratic() const { 32418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return getNumOperands() == 3; 32518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 32618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 32718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Set flags for a recurrence without clearing any previously set flags. 32818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 32918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// to make it easier to propagate flags. 33018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void setNoWrapFlags(NoWrapFlags Flags) { 33118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (Flags & (FlagNUW | FlagNSW)) 33218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Flags = ScalarEvolution::setFlags(Flags, FlagNW); 33318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SubclassData |= Flags; 33418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 33518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 33618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// evaluateAtIteration - Return the value of this chain of recurrences at 33718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// the specified iteration number. 33818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 33918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 34018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// getNumIterationsInRange - Return the number of iterations of this loop 34118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// that produce values in the specified constant range. Another way of 34218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// looking at this is that it returns the first iteration number where the 34318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// value is not in the condition, thus computing the exit count. If the 34418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 34518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// returned. 34618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *getNumIterationsInRange(ConstantRange Range, 34718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution &SE) const; 34818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 34918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// getPostIncExpr - Return an expression representing the value of 35018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// this expression one iteration of the loop ahead. 35118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 35218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 35318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 35418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 35518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 35618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static inline bool classof(const SCEV *S) { 35718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return S->getSCEVType() == scAddRecExpr; 35818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 35918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 36018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Collect parametric terms occurring in step expressions. 36118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void collectParametricTerms(ScalarEvolution &SE, 36218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVectorImpl<const SCEV *> &Terms) const; 36318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 36418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Return in Subscripts the access functions for each dimension in Sizes. 36518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void computeAccessFunctions(ScalarEvolution &SE, 36618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVectorImpl<const SCEV *> &Subscripts, 36718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVectorImpl<const SCEV *> &Sizes) const; 36818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 36918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the 37018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// subscripts and sizes of an array access. 37118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 37218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The delinearization is a 3 step process: the first two steps compute the 37318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// sizes of each subscript and the third step computes the access functions 37418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// for the delinearized array: 37518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 37618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 1. Find the terms in the step functions 37718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 2. Compute the array size 37818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 3. Compute the access function: divide the SCEV by the array size 37918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// starting with the innermost dimensions found in step 2. The Quotient 38018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// is the SCEV to be divided in the next step of the recursion. The 38118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Remainder is the subscript of the innermost dimension. Loop over all 38218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// array dimensions computed in step 2. 38318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 38418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// To compute a uniform array size for several memory accesses to the same 38518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// object, one can collect in step 1 all the step terms for all the memory 38618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// accesses, and compute in step 2 a unique array shape. This guarantees 38718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// that the array shape will be the same across all memory accesses. 38818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 38918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// FIXME: We could derive the result of steps 1 and 2 from a description of 39018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// the array shape given in metadata. 39118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 39218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Example: 39318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 39418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// A[][n][m] 39518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 39618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// for i 39718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// for j 39818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// for k 39918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// A[j+k][2i][5i] = 40018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 40118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The initial SCEV: 40218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 40318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] 40418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 40518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 1. Find the different terms in the step functions: 40618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// -> [2*m, 5, n*m, n*m] 40718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 40818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 2. Compute the array size: sort and unique them 40918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// -> [n*m, 2*m, 5] 41018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// find the GCD of all the terms = 1 41118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// divide by the GCD and erase constant terms 41218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// -> [n*m, 2*m] 41318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// GCD = m 41418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// divide by GCD -> [n, 2] 41518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// remove constant terms 41618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// -> [n] 41718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// size of the array is A[unknown][n][m] 41818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 41918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 3. Compute the access function 42018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m 42118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k 42218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k 42318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The remainder is the subscript of the innermost array dimension: [5i]. 42418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 42518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n 42618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k 42718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k 42818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The Remainder is the subscript of the next array dimension: [2i]. 42918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 43018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The subscript of the outermost dimension is the Quotient: [j+k]. 43118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 43218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. 43318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void delinearize(ScalarEvolution &SE, 43418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVectorImpl<const SCEV *> &Subscripts, 43518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVectorImpl<const SCEV *> &Sizes, 43618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *ElementSize) const; 43718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 43818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 43918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com //===--------------------------------------------------------------------===// 44018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVSMaxExpr - This class represents a signed maximum selection. 44118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 44218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVSMaxExpr : public SCEVCommutativeExpr { 44318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com friend class ScalarEvolution; 44418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 44518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 44618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *const *O, size_t N) 44718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 44818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // Max never overflows. 44918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 45018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 45118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 45218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 45318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 45418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static inline bool classof(const SCEV *S) { 45518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return S->getSCEVType() == scSMaxExpr; 45618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 45718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 45818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 45918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 46018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com //===--------------------------------------------------------------------===// 46118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 46218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 46318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVUMaxExpr : public SCEVCommutativeExpr { 46418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com friend class ScalarEvolution; 46518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 46618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 46718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *const *O, size_t N) 46818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 46918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // Max never overflows. 47018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 47118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 47218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 47318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 47418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 47518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static inline bool classof(const SCEV *S) { 47618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return S->getSCEVType() == scUMaxExpr; 47718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 47818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 47918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 48018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com //===--------------------------------------------------------------------===// 48118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 48218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// value, and only represent it as its LLVM Value. This is the "bottom" 48318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// value for the analysis. 48418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// 48518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVUnknown : public SCEV, private CallbackVH { 48618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com friend class ScalarEvolution; 48718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 48818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com // Implement CallbackVH. 48918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void deleted() override; 49018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void allUsesReplacedWith(Value *New) override; 49118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 49218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SE - The parent ScalarEvolution value. This is used to update 49318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// the parent's maps when the value associated with a SCEVUnknown 49418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// is deleted or RAUW'd. 49518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution *SE; 49618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 49718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Next - The next pointer in the linked list of all 49818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVUnknown instances owned by a ScalarEvolution. 49918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVUnknown *Next; 50018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 50118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 50218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution *se, SCEVUnknown *next) : 50318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 50418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 50518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 50618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Value *getValue() const { return getValPtr(); } 50718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 50818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 50918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// constant representing a type size, alignment, or field offset in 51018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// a target-independent manner, and hasn't happened to have been 51118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// folded with other operations into something unrecognizable. This 51218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// is mainly only useful for pretty-printing and other situations 51318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// where it isn't absolutely required for these to succeed. 51418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool isSizeOf(Type *&AllocTy) const; 51518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool isAlignOf(Type *&AllocTy) const; 51618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 51718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 51818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Type *getType() const { return getValPtr()->getType(); } 51918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 52018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Methods for support type inquiry through isa, cast, and dyn_cast: 52118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static inline bool classof(const SCEV *S) { 522f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return S->getSCEVType() == scUnknown; 523f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 52418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 52518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 52618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// SCEVVisitor - This class defines a simple visitor class that may be used 52718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// for various SCEV analysis purposes. 52818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com template<typename SC, typename RetVal=void> 529f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com struct SCEVVisitor { 53018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com RetVal visit(const SCEV *S) { 53118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com switch (S->getSCEVType()) { 53218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scConstant: 53318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitConstant((const SCEVConstant*)S); 53418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scTruncate: 53518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 53618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scZeroExtend: 53718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 53818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scSignExtend: 53918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 54018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scAddExpr: 54118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 54218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scMulExpr: 54318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 54418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scUDivExpr: 54518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 54618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scAddRecExpr: 54718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 54818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scSMaxExpr: 549f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 550f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com case scUMaxExpr: 551f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 552f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com case scUnknown: 553f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 554f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com case scCouldNotCompute: 555f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 556f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com default: 557f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com llvm_unreachable("Unknown SCEV type!"); 558f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 559f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 560f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com 561f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 562f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 563f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com } 564f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com }; 565b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com 566b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com /// Visit all nodes in the expression tree using worklist traversal. 567b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com /// 568b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com /// Visitor implements: 569b3bfbbcb458043ddaaa1099b776014ba0968704dlararennie@google.com /// // return true to follow this node. 57018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// bool follow(const SCEV *S); 571f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com /// // return true to terminate the search. 57218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// bool isDone(); 57318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com template<typename SV> 57418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com class SCEVTraversal { 57518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SV &Visitor; 57618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 8> Worklist; 57718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallPtrSet<const SCEV *, 8> Visited; 57818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 57918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void push(const SCEV *S) { 58018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (Visited.insert(S) && Visitor.follow(S)) 58118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Worklist.push_back(S); 58218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 58318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 58418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVTraversal(SV& V): Visitor(V) {} 58518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 58618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void visitAll(const SCEV *Root) { 58718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com push(Root); 58818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com while (!Worklist.empty() && !Visitor.isDone()) { 58918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *S = Worklist.pop_back_val(); 59018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 59118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com switch (S->getSCEVType()) { 59218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scConstant: 59318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scUnknown: 59418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com break; 59518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scTruncate: 59618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scZeroExtend: 59718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scSignExtend: 59818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com push(cast<SCEVCastExpr>(S)->getOperand()); 59918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com break; 60018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scAddExpr: 60118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scMulExpr: 60218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scSMaxExpr: 60318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scUMaxExpr: 60418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scAddRecExpr: { 60518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 60618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 60718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com E = NAry->op_end(); I != E; ++I) { 60818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com push(*I); 60918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 61018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com break; 61118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 61218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scUDivExpr: { 61318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 61418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com push(UDiv->getLHS()); 61518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com push(UDiv->getRHS()); 61618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com break; 61718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 61818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com case scCouldNotCompute: 61918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 62018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com default: 62118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com llvm_unreachable("Unknown SCEV kind!"); 62218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 62318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 62418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 62518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 62618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 62718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// Use SCEVTraversal to visit all nodes in the givien expression tree. 62818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com template<typename SV> 62918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com void visitAll(const SCEV *Root, SV& Visitor) { 63018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVTraversal<SV> T(Visitor); 63118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com T.visitAll(Root); 63218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 63318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 63418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com typedef DenseMap<const Value*, Value*> ValueToValueMap; 63518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 63618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The SCEVParameterRewriter takes a scalar evolution expression and updates 63718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// the SCEVUnknown components following the Map (Value -> Value). 63818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com struct SCEVParameterRewriter 63918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { 64018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 64118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 64218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ValueToValueMap &Map, 64318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool InterpretConsts = false) { 64418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts); 64518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Rewriter.visit(Scev); 64618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 64718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 64818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C) 64918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SE(S), Map(M), InterpretConsts(C) {} 65018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 65118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitConstant(const SCEVConstant *Constant) { 65218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Constant; 65318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 65418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 65518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 65618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 65718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getTruncateExpr(Operand, Expr->getType()); 65818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 65918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 66018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 66118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 66218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getZeroExtendExpr(Operand, Expr->getType()); 66318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 66418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 66518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 66618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 66718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getSignExtendExpr(Operand, Expr->getType()); 66818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 66918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 67018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 67118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 67218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 67318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 67418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getAddExpr(Operands); 67518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 67618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 67718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 67818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 67918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 68018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 68118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getMulExpr(Operands); 68218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 68318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 68418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 68518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 68618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 68718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 68818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 68918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 69018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 69118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 69218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getAddRecExpr(Operands, Expr->getLoop(), 69318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Expr->getNoWrapFlags()); 69418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 69518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 69618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 69718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 69818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 69918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 70018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getSMaxExpr(Operands); 70118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 70218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 70318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 70418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 70518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 706f7b0d3f0da91816c0b3263a640de0c06e7e807d9lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 70718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getUMaxExpr(Operands); 70818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 70918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 71018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUnknown(const SCEVUnknown *Expr) { 71118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Value *V = Expr->getValue(); 71218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (Map.count(V)) { 71318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Value *NV = Map[V]; 71418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (InterpretConsts && isa<ConstantInt>(NV)) 71518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getConstant(cast<ConstantInt>(NV)); 71618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getUnknown(NV); 71718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 71818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Expr; 71918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 72018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 72118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 72218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Expr; 72318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 72418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 72518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com private: 72618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution &SE; 72718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ValueToValueMap ⤅ 72818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com bool InterpretConsts; 72918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 73018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 73118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; 73218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 73318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// The SCEVApplyRewriter takes a scalar evolution expression and applies 73418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com /// the Map (Loop -> SCEV) to all AddRecExprs. 73518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com struct SCEVApplyRewriter 73618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> { 73718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com public: 73818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, 73918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution &SE) { 74018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVApplyRewriter Rewriter(SE, Map); 74118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Rewriter.visit(Scev); 74218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 74318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 74418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) 74518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com : SE(S), Map(M) {} 74618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 74718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitConstant(const SCEVConstant *Constant) { 74818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Constant; 74918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 75018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 75118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 75218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 75318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getTruncateExpr(Operand, Expr->getType()); 75418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 75518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 75618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 75718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 75818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getZeroExtendExpr(Operand, Expr->getType()); 75918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 76018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 76118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 76218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Operand = visit(Expr->getOperand()); 76318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getSignExtendExpr(Operand, Expr->getType()); 76418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 76518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 76618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 76718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 76818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 76918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 77018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getAddExpr(Operands); 77118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 77218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 77318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 77418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 77518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 77618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 77718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getMulExpr(Operands); 77818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 77918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 78018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 78118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 78218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 78318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 78418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 78518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 78618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 78718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 78818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 78918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const Loop *L = Expr->getLoop(); 79018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); 79118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 79218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com if (0 == Map.count(L)) 79318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Res; 79418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 79518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; 79618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Rec->evaluateAtIteration(Map[L], SE); 79718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 79818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 79918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 80018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 80118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 80218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 80318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getSMaxExpr(Operands); 80418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 80518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 80618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 80718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com SmallVector<const SCEV *, 2> Operands; 80818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 80918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com Operands.push_back(visit(Expr->getOperand(i))); 81018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SE.getUMaxExpr(Operands); 81118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 81218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 81318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitUnknown(const SCEVUnknown *Expr) { 81418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Expr; 81518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 81618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 81718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 81818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return Expr; 81918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com } 82018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 82118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com private: 82218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution &SE; 82318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com LoopToScevMapT ⤅ 82418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com }; 82518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 82618404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com/// Applies the Map (Loop -> SCEV) to the given Scev. 82718404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.comstatic inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, 82818404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com ScalarEvolution &SE) { 82918404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com return SCEVApplyRewriter::rewrite(Scev, Map, SE); 83018404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com} 83118404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 83218404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com} 83318404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com 83418404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com#endif 83518404d8ed386420aabe8027d3c1da1d06a03f696lararennie@google.com