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
17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/ADT/iterator_range.h"
1818a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick#include "llvm/ADT/SmallPtrSet.h"
19255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Analysis/ScalarEvolution.h"
20c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h"
214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattnernamespace llvm {
234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  class ConstantInt;
244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  class ConstantRange;
255a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng  class DominatorTree;
264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  enum SCEVTypes {
284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    // These should be ordered in terms of increasing complexity to make the
294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    // folders simpler.
30d19534add90a2a894af61523b830887097bb780bDan Gohman    scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
31c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
320f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    scUnknown, scCouldNotCompute
334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVConstant - This class represents a constant integer value.
374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  class SCEVConstant : public SCEV {
39246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
40246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    ConstantInt *V;
423bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
433bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      SCEV(ID, scConstant), V(v) {}
444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    ConstantInt *getValue() const { return V; }
464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
47db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const { return V->getType(); }
484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scConstant;
524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
5684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  /// SCEVCastExpr - This is the base class for unary cast operator classes.
574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
5884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  class SCEVCastExpr : public SCEV {
5984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  protected:
600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *Op;
61db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *Ty;
6284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman
633bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVCastExpr(const FoldingSetNodeIDRef ID,
64db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner                 unsigned SCEVTy, const SCEV *op, Type *ty);
6584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman
664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
670bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getOperand() const { return Op; }
68db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const { return Ty; }
69fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman
7084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman    /// Methods for support type inquiry through isa, cast, and dyn_cast:
7184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman    static inline bool classof(const SCEV *S) {
7284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman      return S->getSCEVType() == scTruncate ||
7384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman             S->getSCEVType() == scZeroExtend ||
7484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman             S->getSCEVType() == scSignExtend;
7584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman    }
7684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  };
7784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman
7884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  //===--------------------------------------------------------------------===//
7984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  /// SCEVTruncateExpr - This class represents a truncation of an integer value
8084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  /// to a smaller integer value.
8184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  ///
8284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  class SCEVTruncateExpr : public SCEVCastExpr {
8384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman    friend class ScalarEvolution;
8484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman
853bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
86db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner                     const SCEV *op, Type *ty);
8784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman
8884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  public:
894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scTruncate;
924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVZeroExtendExpr - This class represents a zero extension of a small
974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// integer value to a larger integer value.
984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
9984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  class SCEVZeroExtendExpr : public SCEVCastExpr {
100246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
101246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
1023bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
103db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner                       const SCEV *op, Type *ty);
1044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
10584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  public:
1064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
1074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
1084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scZeroExtend;
1094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
1114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
112d19534add90a2a894af61523b830887097bb780bDan Gohman  //===--------------------------------------------------------------------===//
113d19534add90a2a894af61523b830887097bb780bDan Gohman  /// SCEVSignExtendExpr - This class represents a sign extension of a small
114d19534add90a2a894af61523b830887097bb780bDan Gohman  /// integer value to a larger integer value.
115d19534add90a2a894af61523b830887097bb780bDan Gohman  ///
11684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  class SCEVSignExtendExpr : public SCEVCastExpr {
117246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
118246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
1193bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
120db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner                       const SCEV *op, Type *ty);
121d19534add90a2a894af61523b830887097bb780bDan Gohman
12284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman  public:
123d19534add90a2a894af61523b830887097bb780bDan Gohman    /// Methods for support type inquiry through isa, cast, and dyn_cast:
124d19534add90a2a894af61523b830887097bb780bDan Gohman    static inline bool classof(const SCEV *S) {
125d19534add90a2a894af61523b830887097bb780bDan Gohman      return S->getSCEVType() == scSignExtend;
126d19534add90a2a894af61523b830887097bb780bDan Gohman    }
127d19534add90a2a894af61523b830887097bb780bDan Gohman  };
128d19534add90a2a894af61523b830887097bb780bDan Gohman
1294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
130d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman  //===--------------------------------------------------------------------===//
131d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman  /// SCEVNAryExpr - This node is a base class providing common
132d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman  /// functionality for n'ary operators.
133d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman  ///
134ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  class SCEVNAryExpr : public SCEV {
135ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  protected:
136f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    // Since SCEVs are immutable, ScalarEvolution allocates operand
137f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    // arrays with its SCEVAllocator, so this class just needs a simple
138f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    // pointer rather than a more elaborate vector-like data structure.
139f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    // This also avoids the need for a non-trivial destructor.
140f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    const SCEV *const *Operands;
141f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    size_t NumOperands;
1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
1433bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVNAryExpr(const FoldingSetNodeIDRef ID,
144f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                 enum SCEVTypes T, const SCEV *const *O, size_t N)
1453bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEV(ID, T), Operands(O), NumOperands(N) {}
1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
1474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
148f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    size_t getNumOperands() const { return NumOperands; }
1490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getOperand(unsigned i) const {
150f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman      assert(i < NumOperands && "Operand index out of range!");
1514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return Operands[i];
1524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
1534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
154f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    typedef const SCEV *const *op_iterator;
155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    typedef iterator_range<op_iterator> op_range;
156f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    op_iterator op_begin() const { return Operands; }
157f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman    op_iterator op_end() const { return Operands + NumOperands; }
158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    op_range operands() const {
159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      return make_range(op_begin(), op_end());
160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    }
1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
162db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const { return getOperand(0)->getType(); }
163ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman
1643228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
1653228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      return (NoWrapFlags)(SubclassData & Mask);
1663645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman    }
1673645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman
168ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman    /// Methods for support type inquiry through isa, cast, and dyn_cast:
169ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman    static inline bool classof(const SCEV *S) {
170ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman      return S->getSCEVType() == scAddExpr ||
171ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman             S->getSCEVType() == scMulExpr ||
172ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman             S->getSCEVType() == scSMaxExpr ||
173ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman             S->getSCEVType() == scUMaxExpr ||
174ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman             S->getSCEVType() == scAddRecExpr;
175ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman    }
176ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  };
177ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman
178ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  //===--------------------------------------------------------------------===//
179ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
180ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  /// operators.
181ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  ///
182ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  class SCEVCommutativeExpr : public SCEVNAryExpr {
183ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  protected:
1843bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
185c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman                        enum SCEVTypes T, const SCEV *const *O, size_t N)
1863bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEVNAryExpr(ID, T, O, N) {}
187ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman
188ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  public:
1894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
1904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
1914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scAddExpr ||
192c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky             S->getSCEVType() == scMulExpr ||
1933e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky             S->getSCEVType() == scSMaxExpr ||
1943e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky             S->getSCEVType() == scUMaxExpr;
1954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
1963228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
1973228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Set flags for a non-recurrence without clearing previously set flags.
1983228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    void setNoWrapFlags(NoWrapFlags Flags) {
1993228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      SubclassData |= Flags;
2003228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
2014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
2024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
2054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
2064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
2074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  class SCEVAddExpr : public SCEVCommutativeExpr {
208246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
209246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
2103bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVAddExpr(const FoldingSetNodeIDRef ID,
211f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                const SCEV *const *O, size_t N)
2123bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
2134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
2144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
216db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const {
2172b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman      // Use the type of the last operand, which is likely to be a pointer
2182b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman      // type, if there is one. This doesn't usually matter, but it can help
2192b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman      // reduce casts when the expressions are expanded.
2202b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman      return getOperand(getNumOperands() - 1)->getType();
2212b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman    }
2222b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman
2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
2244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scAddExpr;
2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
2274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
2284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
2304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
2314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
2324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  class SCEVMulExpr : public SCEVCommutativeExpr {
233246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
234246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
2353bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVMulExpr(const FoldingSetNodeIDRef ID,
236f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                const SCEV *const *O, size_t N)
2373bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scMulExpr;
2444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
2454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
2464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
249e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
2504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
251e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz  class SCEVUDivExpr : public SCEV {
252246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
253246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
2540bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *LHS;
2550bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *RHS;
2563bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
2573bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  public:
2600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getLHS() const { return LHS; }
2610bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getRHS() const { return RHS; }
2624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
263db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const {
2644ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      // In most cases the types of LHS and RHS will be the same, but in some
2654ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
2664ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      // depend on the type for correctness, but handling types carefully can
2674ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      // avoid extra casts in the SCEVExpander. The LHS is more likely to be
2684ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      // a pointer type than the RHS, so use the RHS' type here.
2694ce32db913beb6ae27df2fa0a9db5d68fd4889d2Dan Gohman      return getRHS()->getType();
270afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner    }
271afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner
2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
274e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz      return S->getSCEVType() == scUDivExpr;
2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
2764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
2774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
2811e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman  /// count of the specified loop.  This is the primary focus of the
2821e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman  /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
2831e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman  /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
2841e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman  /// created and analyzed.
2854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// All operands of an AddRec are required to be loop invariant.
2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
288ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  class SCEVAddRecExpr : public SCEVNAryExpr {
289246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
290246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    const Loop *L;
2924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
2933bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
294f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                   const SCEV *const *O, size_t N, const Loop *l)
295203a7239ae928568fe7a34c03ead4b1b3133870eDan Gohman      : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
297ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman  public:
2980bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getStart() const { return Operands[0]; }
2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    const Loop *getLoop() const { return L; }
3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// getStepRecurrence - This method constructs and returns the recurrence
3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// indicating how much this expression steps by.  If this is a polynomial
3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// of degree N, it returns a chrec of degree N-1.
3043228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// We cannot determine whether the step recurrence has self-wraparound.
3050bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
30617f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman      if (isAffine()) return getOperand(1);
3070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman      return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
3080bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman                                                           op_end()),
3093228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick                              getLoop(), FlagAnyWrap);
3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
3114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// isAffine - Return true if this is an affine AddRec (i.e., it represents
3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// an expressions A+B*x where A and B are loop invariant values.
3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    bool isAffine() const {
3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      // We know that the start value is invariant.  This expression is thus
31694c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru      // affine iff the step is also invariant.
3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return getNumOperands() == 2;
3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
3224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
3234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    bool isQuadratic() const {
3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return getNumOperands() == 3;
3254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
3273228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// Set flags for a recurrence without clearing any previously set flags.
3283228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
3293228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    /// to make it easier to propagate flags.
3303228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    void setNoWrapFlags(NoWrapFlags Flags) {
3313228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      if (Flags & (FlagNUW | FlagNSW))
3323228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick        Flags = ScalarEvolution::setFlags(Flags, FlagNW);
3333228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      SubclassData |= Flags;
3343228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick    }
3353228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick
3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// evaluateAtIteration - Return the value of this chain of recurrences at
3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// the specified iteration number.
3380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
3394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// getNumIterationsInRange - Return the number of iterations of this loop
3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// that produce values in the specified constant range.  Another way of
3424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// looking at this is that it returns the first iteration number where the
3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// value is not in the condition, thus computing the exit count.  If the
3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
345eefdebe002ede066bf80859e72aec831cfd1d92dNick Lewycky    /// returned.
3460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman    const SCEV *getNumIterationsInRange(ConstantRange Range,
347246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman                                       ScalarEvolution &SE) const;
3484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
349c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman    /// getPostIncExpr - Return an expression representing the value of
350c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman    /// this expression one iteration of the loop ahead.
351fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
352fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman      return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
353c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman    }
354c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman
3554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
3564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
3574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scAddRecExpr;
3584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
3594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
360dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Collect parametric terms occurring in step expressions.
361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    void collectParametricTerms(ScalarEvolution &SE,
362dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                                SmallVectorImpl<const SCEV *> &Terms) const;
363dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines
364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Return in Subscripts the access functions for each dimension in Sizes.
365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    void computeAccessFunctions(ScalarEvolution &SE,
366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                                SmallVectorImpl<const SCEV *> &Subscripts,
367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                                SmallVectorImpl<const SCEV *> &Sizes) const;
368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines
369dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
370dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// subscripts and sizes of an array access.
371dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// The delinearization is a 3 step process: the first two steps compute the
373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// sizes of each subscript and the third step computes the access functions
374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// for the delinearized array:
375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 1. Find the terms in the step functions
377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 2. Compute the array size
378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 3. Compute the access function: divide the SCEV by the array size
379dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///    starting with the innermost dimensions found in step 2. The Quotient
380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///    is the SCEV to be divided in the next step of the recursion. The
381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///    Remainder is the subscript of the innermost dimension. Loop over all
382dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///    array dimensions computed in step 2.
383dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
384dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// To compute a uniform array size for several memory accesses to the same
385dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// object, one can collect in step 1 all the step terms for all the memory
386dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// accesses, and compute in step 2 a unique array shape. This guarantees
387dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// that the array shape will be the same across all memory accesses.
388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
389dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// FIXME: We could derive the result of steps 1 and 2 from a description of
390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// the array shape given in metadata.
391dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
392dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Example:
393dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
394dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// A[][n][m]
395dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
396dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// for i
397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///   for j
398dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///     for k
399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///       A[j+k][2i][5i] =
400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// The initial SCEV:
402dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
404dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
405dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 1. Find the different terms in the step functions:
406dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// -> [2*m, 5, n*m, n*m]
407dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
408dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 2. Compute the array size: sort and unique them
409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// -> [n*m, 2*m, 5]
410dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// find the GCD of all the terms = 1
411dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// divide by the GCD and erase constant terms
412dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// -> [n*m, 2*m]
413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// GCD = m
414dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// divide by GCD -> [n, 2]
415dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// remove constant terms
416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// -> [n]
417dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// size of the array is A[unknown][n][m]
418dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// 3. Compute the access function
420dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
422dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
423dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// The remainder is the subscript of the innermost array dimension: [5i].
424dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
425dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
426dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
427dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// The Remainder is the subscript of the next array dimension: [2i].
429dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
430dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// The subscript of the outermost dimension is the Quotient: [j+k].
431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    ///
432dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
433dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    void delinearize(ScalarEvolution &SE,
434dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                     SmallVectorImpl<const SCEV *> &Subscripts,
435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                     SmallVectorImpl<const SCEV *> &Sizes,
436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines                     const SCEV *ElementSize) const;
4375230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop  };
438c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky
439c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  //===--------------------------------------------------------------------===//
440c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  /// SCEVSMaxExpr - This class represents a signed maximum selection.
441c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  ///
442c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  class SCEVSMaxExpr : public SCEVCommutativeExpr {
443c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky    friend class ScalarEvolution;
444c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky
4453bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
446f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                 const SCEV *const *O, size_t N)
4473bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
4483645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman      // Max never overflows.
4493228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
450c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky    }
451c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky
452c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  public:
453c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky    /// Methods for support type inquiry through isa, cast, and dyn_cast:
454c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky    static inline bool classof(const SCEV *S) {
455c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky      return S->getSCEVType() == scSMaxExpr;
456c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky    }
457c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky  };
458c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky
459c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky
4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  //===--------------------------------------------------------------------===//
4613e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky  /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
4623e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky  ///
4633e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky  class SCEVUMaxExpr : public SCEVCommutativeExpr {
4643e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    friend class ScalarEvolution;
4653e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky
4663bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman    SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
467f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman                 const SCEV *const *O, size_t N)
4683bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
4693645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman      // Max never overflows.
4703228cc259b5ca00e46af36da369a451f5736cbf4Andrew Trick      setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
4713e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    }
4723e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky
4733e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky  public:
4743e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    /// Methods for support type inquiry through isa, cast, and dyn_cast:
4753e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    static inline bool classof(const SCEV *S) {
4763e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky      return S->getSCEVType() == scUMaxExpr;
4773e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky    }
4783e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky  };
4793e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky
480c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman  //===--------------------------------------------------------------------===//
4814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
48275144f93eb7e4dbf22d308d21581ae255dd520c6Dan Gohman  /// value, and only represent it as its LLVM Value.  This is the "bottom"
4834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  /// value for the analysis.
4844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  ///
485ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman  class SCEVUnknown : public SCEV, private CallbackVH {
486246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman    friend class ScalarEvolution;
487246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman
488ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    // Implement CallbackVH.
48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    void deleted() override;
49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    void allUsesReplacedWith(Value *New) override;
491ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman
492ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// SE - The parent ScalarEvolution value. This is used to update
493ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// the parent's maps when the value associated with a SCEVUnknown
494ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// is deleted or RAUW'd.
495ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    ScalarEvolution *SE;
496ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman
497ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// Next - The next pointer in the linked list of all
498ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    /// SCEVUnknown instances owned by a ScalarEvolution.
499ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    SCEVUnknown *Next;
500ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman
501ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
502ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman                ScalarEvolution *se, SCEVUnknown *next) :
503ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
5041c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman
505c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman  public:
506ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman    Value *getValue() const { return getValPtr(); }
5074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
5080f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
5090f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// constant representing a type size, alignment, or field offset in
5100f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// a target-independent manner, and hasn't happened to have been
5110f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// folded with other operations into something unrecognizable. This
5120f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// is mainly only useful for pretty-printing and other situations
5130f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman    /// where it isn't absolutely required for these to succeed.
514db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    bool isSizeOf(Type *&AllocTy) const;
515db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    bool isAlignOf(Type *&AllocTy) const;
516db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
5170f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman
518db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner    Type *getType() const { return getValPtr()->getType(); }
5194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
5204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    /// Methods for support type inquiry through isa, cast, and dyn_cast:
5214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    static inline bool classof(const SCEV *S) {
5224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner      return S->getSCEVType() == scUnknown;
5234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner    }
5244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner  };
5252cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner
5262cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner  /// SCEVVisitor - This class defines a simple visitor class that may be used
5272cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner  /// for various SCEV analysis purposes.
5282cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner  template<typename SC, typename RetVal=void>
5292cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner  struct SCEVVisitor {
530890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman    RetVal visit(const SCEV *S) {
5312cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      switch (S->getSCEVType()) {
5322cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scConstant:
533890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitConstant((const SCEVConstant*)S);
5342cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scTruncate:
535890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
5362cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scZeroExtend:
537890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
538d19534add90a2a894af61523b830887097bb780bDan Gohman      case scSignExtend:
539890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
5402cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scAddExpr:
541890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
5422cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scMulExpr:
543890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
544e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz      case scUDivExpr:
545890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
5462cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scAddRecExpr:
547890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
548c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky      case scSMaxExpr:
549890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
5503e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky      case scUMaxExpr:
551890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
5522cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scUnknown:
553890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
5542cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      case scCouldNotCompute:
555890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman        return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
5562cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      default:
557c23197a26f34f559ea9797de51e187087c039c42Torok Edwin        llvm_unreachable("Unknown SCEV type!");
5582cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner      }
5592cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner    }
5602cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner
561890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman    RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
562c23197a26f34f559ea9797de51e187087c039c42Torok Edwin      llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
5632cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner    }
5642cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner  };
5658b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick
5668b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  /// Visit all nodes in the expression tree using worklist traversal.
5678b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  ///
5688b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  /// Visitor implements:
5698b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  ///   // return true to follow this node.
5708b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  ///   bool follow(const SCEV *S);
5718b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  ///   // return true to terminate the search.
5728b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  ///   bool isDone();
5738b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  template<typename SV>
5748b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  class SCEVTraversal {
5758b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    SV &Visitor;
5768b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    SmallVector<const SCEV *, 8> Worklist;
57718a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick    SmallPtrSet<const SCEV *, 8> Visited;
5788b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick
5798b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    void push(const SCEV *S) {
58018a1b616ea123548b61a037c4f4fea4133aac1b5Andrew Trick      if (Visited.insert(S) && Visitor.follow(S))
5818b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        Worklist.push_back(S);
5828b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    }
5838b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  public:
5848b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    SCEVTraversal(SV& V): Visitor(V) {}
5858b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick
5868b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    void visitAll(const SCEV *Root) {
5878b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick      push(Root);
5888b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick      while (!Worklist.empty() && !Visitor.isDone()) {
5898b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        const SCEV *S = Worklist.pop_back_val();
5908b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick
5918b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        switch (S->getSCEVType()) {
5928b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scConstant:
5938b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scUnknown:
5948b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          break;
5958b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scTruncate:
5968b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scZeroExtend:
5978b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scSignExtend:
5988b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          push(cast<SCEVCastExpr>(S)->getOperand());
5998b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          break;
6008b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scAddExpr:
6018b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scMulExpr:
6028b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scSMaxExpr:
6038b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scUMaxExpr:
6048b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scAddRecExpr: {
6058b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
6068b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          for (SCEVNAryExpr::op_iterator I = NAry->op_begin(),
6078b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick                 E = NAry->op_end(); I != E; ++I) {
6088b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick            push(*I);
6098b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          }
6108b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          break;
6118b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        }
6128b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scUDivExpr: {
6138b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
6148b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          push(UDiv->getLHS());
6158b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          push(UDiv->getRHS());
6168b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          break;
6178b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        }
6188b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        case scCouldNotCompute:
6198b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
6208b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        default:
6218b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick          llvm_unreachable("Unknown SCEV kind!");
6228b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick        }
6238b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick      }
6248b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    }
6258b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  };
6268b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick
6278b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  /// Use SCEVTraversal to visit all nodes in the givien expression tree.
6288b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  template<typename SV>
6298b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  void visitAll(const SCEV *Root, SV& Visitor) {
6308b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    SCEVTraversal<SV> T(Visitor);
6318b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick    T.visitAll(Root);
6328b7036b0f4ae3f76ad24a6b9bc2d874620406306Andrew Trick  }
633a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
634b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop  typedef DenseMap<const Value*, Value*> ValueToValueMap;
635b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
636b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
637b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop  /// the SCEVUnknown components following the Map (Value -> Value).
638b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop  struct SCEVParameterRewriter
639b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> {
640a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop  public:
641b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines                               ValueToValueMap &Map,
64336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines                               bool InterpretConsts = false) {
64436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
645b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return Rewriter.visit(Scev);
646b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
647a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
64836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C)
64936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      : SE(S), Map(M), InterpretConsts(C) {}
650b075ed3b90fa2a520aeb15802fddf3460d865f91Matt Beaumont-Gay
651b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitConstant(const SCEVConstant *Constant) {
652a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return Constant;
653a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
654a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
655b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
656a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
657a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getTruncateExpr(Operand, Expr->getType());
658a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
659a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
660b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
661a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
662a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getZeroExtendExpr(Operand, Expr->getType());
663a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
664a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
665b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
666a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
667a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getSignExtendExpr(Operand, Expr->getType());
668a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
669a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
670b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
671a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      SmallVector<const SCEV *, 2> Operands;
672a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
673a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
674a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getAddExpr(Operands);
675a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
676a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
677b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
678a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      SmallVector<const SCEV *, 2> Operands;
679a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
680a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
681a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getMulExpr(Operands);
682a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
683a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
684b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
685a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS()));
686a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
687a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
688b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
689a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      SmallVector<const SCEV *, 2> Operands;
690a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
691a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
692a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getAddRecExpr(Operands, Expr->getLoop(),
693a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop                              Expr->getNoWrapFlags());
694a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
695a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
696b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
697a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      SmallVector<const SCEV *, 2> Operands;
698a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
699a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
700a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getSMaxExpr(Operands);
701a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
702a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
703b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
704a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      SmallVector<const SCEV *, 2> Operands;
705a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
706a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
707a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return SE.getUMaxExpr(Operands);
708a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
709a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
710b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUnknown(const SCEVUnknown *Expr) {
711a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      Value *V = Expr->getValue();
71236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      if (Map.count(V)) {
71336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines        Value *NV = Map[V];
71436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines        if (InterpretConsts && isa<ConstantInt>(NV))
71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines          return SE.getConstant(cast<ConstantInt>(NV));
71636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines        return SE.getUnknown(NV);
71736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      }
718a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop      return Expr;
719a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    }
720a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
721b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
722b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return Expr;
723b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
724b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
725a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop  private:
726b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    ScalarEvolution &SE;
727a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop    ValueToValueMap &Map;
72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    bool InterpretConsts;
729a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop  };
730a9e4d3f37590bb326e6c5a3ea02ee1aa3db681eaSebastian Pop
7315661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop  typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT;
7325661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
7330deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop  /// The SCEVApplyRewriter takes a scalar evolution expression and applies
7345661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop  /// the Map (Loop -> SCEV) to all AddRecExprs.
735b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop  struct SCEVApplyRewriter
736b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> {
7375661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop  public:
7385661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop    static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
7395661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop                               ScalarEvolution &SE) {
7400deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop      SCEVApplyRewriter Rewriter(SE, Map);
7415661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      return Rewriter.visit(Scev);
7425661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop    }
743b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
7440deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop    SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M)
745b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      : SE(S), Map(M) {}
746b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
747b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitConstant(const SCEVConstant *Constant) {
748b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return Constant;
749b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
750b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
751b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
752b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
753b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getTruncateExpr(Operand, Expr->getType());
754b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
755b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
756b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
757b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
758b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getZeroExtendExpr(Operand, Expr->getType());
759b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
760b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
761b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
762b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      const SCEV *Operand = visit(Expr->getOperand());
763b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getSignExtendExpr(Operand, Expr->getType());
764b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
765b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
766b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
767b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      SmallVector<const SCEV *, 2> Operands;
768b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
769b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
770b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getAddExpr(Operands);
771b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
7725661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
773b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
774b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      SmallVector<const SCEV *, 2> Operands;
775b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
776b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
777b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getMulExpr(Operands);
778b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
779b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
780b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
781b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS()));
782b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
783b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
784b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
7855661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      SmallVector<const SCEV *, 2> Operands;
7865661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
7875661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
7885661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
7895661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      const Loop *L = Expr->getLoop();
7905661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
7915661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
7925661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      if (0 == Map.count(L))
7935661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop        return Res;
7945661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
7955661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res;
7965661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop      return Rec->evaluateAtIteration(Map[L], SE);
7975661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop    }
7985661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
799b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
800b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      SmallVector<const SCEV *, 2> Operands;
801b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
802b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
803b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getSMaxExpr(Operands);
804b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
805b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
806b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
807b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      SmallVector<const SCEV *, 2> Operands;
808b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
809b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop        Operands.push_back(visit(Expr->getOperand(i)));
810b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return SE.getUMaxExpr(Operands);
811b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
812b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
813b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitUnknown(const SCEVUnknown *Expr) {
814b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return Expr;
815b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
816b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
817b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
818b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop      return Expr;
819b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    }
820b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop
8215661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop  private:
822b8fc659c8eb36796531d55fa78cbb1957895aa9bSebastian Pop    ScalarEvolution &SE;
8235661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop    LoopToScevMapT &Map;
8245661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop  };
8255661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
8265661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop/// Applies the Map (Loop -> SCEV) to the given Scev.
8275661fcdde295645e5c6f982a25225e682727b5b1Sebastian Popstatic inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map,
8285661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop                                ScalarEvolution &SE) {
8290deff9fbeb3a6a68f224282f8c6bd277d4c0c78cSebastian Pop  return SCEVApplyRewriter::rewrite(Scev, Map, SE);
8305661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop}
8315661fcdde295645e5c6f982a25225e682727b5b1Sebastian Pop
8324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner}
8334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner
8344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif
835