LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ScalarEvolutionExpressions.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 820 1042 78.7 %
Date: 2018-10-19 05:06:59 Functions: 161 237 67.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the classes used to represent and build scalar expressions.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
      15             : #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
      16             : 
      17             : #include "llvm/ADT/DenseMap.h"
      18             : #include "llvm/ADT/FoldingSet.h"
      19             : #include "llvm/ADT/SmallPtrSet.h"
      20             : #include "llvm/ADT/SmallVector.h"
      21             : #include "llvm/ADT/iterator_range.h"
      22             : #include "llvm/Analysis/ScalarEvolution.h"
      23             : #include "llvm/IR/Constants.h"
      24             : #include "llvm/IR/Value.h"
      25             : #include "llvm/IR/ValueHandle.h"
      26             : #include "llvm/Support/Casting.h"
      27             : #include "llvm/Support/ErrorHandling.h"
      28             : #include <cassert>
      29             : #include <cstddef>
      30             : 
      31             : namespace llvm {
      32             : 
      33             : class APInt;
      34             : class Constant;
      35             : class ConstantRange;
      36             : class Loop;
      37             : class Type;
      38             : 
      39             :   enum SCEVTypes {
      40             :     // These should be ordered in terms of increasing complexity to make the
      41             :     // folders simpler.
      42             :     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
      43             :     scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
      44             :     scUnknown, scCouldNotCompute
      45             :   };
      46             : 
      47             :   /// This class represents a constant integer value.
      48             :   class SCEVConstant : public SCEV {
      49             :     friend class ScalarEvolution;
      50             : 
      51             :     ConstantInt *V;
      52             : 
      53      413695 :     SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
      54      413695 :       SCEV(ID, scConstant), V(v) {}
      55             : 
      56             :   public:
      57           0 :     ConstantInt *getValue() const { return V; }
      58    13253317 :     const APInt &getAPInt() const { return getValue()->getValue(); }
      59             : 
      60           0 :     Type *getType() const { return V->getType(); }
      61             : 
      62             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
      63             :     static bool classof(const SCEV *S) {
      64    21490103 :       return S->getSCEVType() == scConstant;
      65             :     }
      66             :   };
      67             : 
      68             :   /// This is the base class for unary cast operator classes.
      69             :   class SCEVCastExpr : public SCEV {
      70             :   protected:
      71             :     const SCEV *Op;
      72             :     Type *Ty;
      73             : 
      74             :     SCEVCastExpr(const FoldingSetNodeIDRef ID,
      75             :                  unsigned SCEVTy, const SCEV *op, Type *ty);
      76             : 
      77             :   public:
      78           0 :     const SCEV *getOperand() const { return Op; }
      79           0 :     Type *getType() const { return Ty; }
      80             : 
      81             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
      82             :     static bool classof(const SCEV *S) {
      83      147165 :       return S->getSCEVType() == scTruncate ||
      84      290920 :              S->getSCEVType() == scZeroExtend ||
      85             :              S->getSCEVType() == scSignExtend;
      86             :     }
      87             :   };
      88             : 
      89             :   /// This class represents a truncation of an integer value to a
      90             :   /// smaller integer value.
      91             :   class SCEVTruncateExpr : public SCEVCastExpr {
      92             :     friend class ScalarEvolution;
      93             : 
      94             :     SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
      95             :                      const SCEV *op, Type *ty);
      96             : 
      97             :   public:
      98             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
      99             :     static bool classof(const SCEV *S) {
     100      142611 :       return S->getSCEVType() == scTruncate;
     101             :     }
     102             :   };
     103             : 
     104             :   /// This class represents a zero extension of a small integer value
     105             :   /// to a larger integer value.
     106             :   class SCEVZeroExtendExpr : public SCEVCastExpr {
     107             :     friend class ScalarEvolution;
     108             : 
     109             :     SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
     110             :                        const SCEV *op, Type *ty);
     111             : 
     112             :   public:
     113             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     114             :     static bool classof(const SCEV *S) {
     115       19197 :       return S->getSCEVType() == scZeroExtend;
     116             :     }
     117             :   };
     118             : 
     119             :   /// This class represents a sign extension of a small integer value
     120             :   /// to a larger integer value.
     121             :   class SCEVSignExtendExpr : public SCEVCastExpr {
     122             :     friend class ScalarEvolution;
     123             : 
     124             :     SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
     125             :                        const SCEV *op, Type *ty);
     126             : 
     127             :   public:
     128             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     129             :     static bool classof(const SCEV *S) {
     130       44239 :       return S->getSCEVType() == scSignExtend;
     131             :     }
     132             :   };
     133             : 
     134             :   /// This node is a base class providing common functionality for
     135             :   /// n'ary operators.
     136             :   class SCEVNAryExpr : public SCEV {
     137             :   protected:
     138             :     // Since SCEVs are immutable, ScalarEvolution allocates operand
     139             :     // arrays with its SCEVAllocator, so this class just needs a simple
     140             :     // pointer rather than a more elaborate vector-like data structure.
     141             :     // This also avoids the need for a non-trivial destructor.
     142             :     const SCEV *const *Operands;
     143             :     size_t NumOperands;
     144             : 
     145             :     SCEVNAryExpr(const FoldingSetNodeIDRef ID,
     146             :                  enum SCEVTypes T, const SCEV *const *O, size_t N)
     147      832819 :       : SCEV(ID, T), Operands(O), NumOperands(N) {}
     148             : 
     149             :   public:
     150           0 :     size_t getNumOperands() const { return NumOperands; }
     151             : 
     152           0 :     const SCEV *getOperand(unsigned i) const {
     153             :       assert(i < NumOperands && "Operand index out of range!");
     154    19875393 :       return Operands[i];
     155             :     }
     156             : 
     157             :     using op_iterator = const SCEV *const *;
     158             :     using op_range = iterator_range<op_iterator>;
     159             : 
     160           0 :     op_iterator op_begin() const { return Operands; }
     161     2326021 :     op_iterator op_end() const { return Operands + NumOperands; }
     162             :     op_range operands() const {
     163    14920228 :       return make_range(op_begin(), op_end());
     164             :     }
     165             : 
     166     2055436 :     Type *getType() const { return getOperand(0)->getType(); }
     167             : 
     168           0 :     NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
     169      585068 :       return (NoWrapFlags)(SubclassData & Mask);
     170             :     }
     171             : 
     172             :     bool hasNoUnsignedWrap() const {
     173      409524 :       return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
     174             :     }
     175             : 
     176             :     bool hasNoSignedWrap() const {
     177      408880 :       return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
     178             :     }
     179             : 
     180             :     bool hasNoSelfWrap() const {
     181        6492 :       return getNoWrapFlags(FlagNW) != FlagAnyWrap;
     182             :     }
     183             : 
     184             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     185             :     static bool classof(const SCEV *S) {
     186      346590 :       return S->getSCEVType() == scAddExpr ||
     187      295988 :              S->getSCEVType() == scMulExpr ||
     188      295011 :              S->getSCEVType() == scSMaxExpr ||
     189      662897 :              S->getSCEVType() == scUMaxExpr ||
     190             :              S->getSCEVType() == scAddRecExpr;
     191             :     }
     192             :   };
     193             : 
     194             :   /// This node is the base class for n'ary commutative operators.
     195             :   class SCEVCommutativeExpr : public SCEVNAryExpr {
     196             :   protected:
     197             :     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
     198             :                         enum SCEVTypes T, const SCEV *const *O, size_t N)
     199             :       : SCEVNAryExpr(ID, T, O, N) {}
     200             : 
     201             :   public:
     202             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     203             :     static bool classof(const SCEV *S) {
     204       93337 :       return S->getSCEVType() == scAddExpr ||
     205       63224 :              S->getSCEVType() == scMulExpr ||
     206      193945 :              S->getSCEVType() == scSMaxExpr ||
     207             :              S->getSCEVType() == scUMaxExpr;
     208             :     }
     209             : 
     210             :     /// Set flags for a non-recurrence without clearing previously set flags.
     211           0 :     void setNoWrapFlags(NoWrapFlags Flags) {
     212     1092847 :       SubclassData |= Flags;
     213           0 :     }
     214             :   };
     215             : 
     216             :   /// This node represents an addition of some number of SCEVs.
     217             :   class SCEVAddExpr : public SCEVCommutativeExpr {
     218             :     friend class ScalarEvolution;
     219             : 
     220             :     SCEVAddExpr(const FoldingSetNodeIDRef ID,
     221             :                 const SCEV *const *O, size_t N)
     222             :       : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}
     223             : 
     224             :   public:
     225     1041605 :     Type *getType() const {
     226             :       // Use the type of the last operand, which is likely to be a pointer
     227             :       // type, if there is one. This doesn't usually matter, but it can help
     228             :       // reduce casts when the expressions are expanded.
     229     1061168 :       return getOperand(getNumOperands() - 1)->getType();
     230             :     }
     231             : 
     232             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     233             :     static bool classof(const SCEV *S) {
     234     6990261 :       return S->getSCEVType() == scAddExpr;
     235             :     }
     236             :   };
     237             : 
     238             :   /// This node represents multiplication of some number of SCEVs.
     239             :   class SCEVMulExpr : public SCEVCommutativeExpr {
     240             :     friend class ScalarEvolution;
     241             : 
     242             :     SCEVMulExpr(const FoldingSetNodeIDRef ID,
     243             :                 const SCEV *const *O, size_t N)
     244             :       : SCEVCommutativeExpr(ID, scMulExpr, O, N) {}
     245             : 
     246             :   public:
     247             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     248             :     static bool classof(const SCEV *S) {
     249    11240417 :       return S->getSCEVType() == scMulExpr;
     250             :     }
     251             :   };
     252             : 
     253             :   /// This class represents a binary unsigned division operation.
     254             :   class SCEVUDivExpr : public SCEV {
     255             :     friend class ScalarEvolution;
     256             : 
     257             :     const SCEV *LHS;
     258             :     const SCEV *RHS;
     259             : 
     260             :     SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
     261       22942 :       : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
     262             : 
     263             :   public:
     264           0 :     const SCEV *getLHS() const { return LHS; }
     265           0 :     const SCEV *getRHS() const { return RHS; }
     266             : 
     267             :     Type *getType() const {
     268             :       // In most cases the types of LHS and RHS will be the same, but in some
     269             :       // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
     270             :       // depend on the type for correctness, but handling types carefully can
     271             :       // avoid extra casts in the SCEVExpander. The LHS is more likely to be
     272             :       // a pointer type than the RHS, so use the RHS' type here.
     273       78604 :       return getRHS()->getType();
     274             :     }
     275             : 
     276             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     277             :     static bool classof(const SCEV *S) {
     278       84155 :       return S->getSCEVType() == scUDivExpr;
     279             :     }
     280             :   };
     281             : 
     282             :   /// This node represents a polynomial recurrence on the trip count
     283             :   /// of the specified loop.  This is the primary focus of the
     284             :   /// ScalarEvolution framework; all the other SCEV subclasses are
     285             :   /// mostly just supporting infrastructure to allow SCEVAddRecExpr
     286             :   /// expressions to be created and analyzed.
     287             :   ///
     288             :   /// All operands of an AddRec are required to be loop invariant.
     289             :   ///
     290             :   class SCEVAddRecExpr : public SCEVNAryExpr {
     291             :     friend class ScalarEvolution;
     292             : 
     293             :     const Loop *L;
     294             : 
     295             :     SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
     296             :                    const SCEV *const *O, size_t N, const Loop *l)
     297      380620 :       : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
     298             : 
     299             :   public:
     300     1243070 :     const SCEV *getStart() const { return Operands[0]; }
     301           0 :     const Loop *getLoop() const { return L; }
     302             : 
     303             :     /// Constructs and returns the recurrence indicating how much this
     304             :     /// expression steps by.  If this is a polynomial of degree N, it
     305             :     /// returns a chrec of degree N-1.  We cannot determine whether
     306             :     /// the step recurrence has self-wraparound.
     307      807917 :     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
     308      807775 :       if (isAffine()) return getOperand(1);
     309         284 :       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
     310             :                                                            op_end()),
     311             :                               getLoop(), FlagAnyWrap);
     312             :     }
     313             : 
     314             :     /// Return true if this represents an expression A + B*x where A
     315             :     /// and B are loop invariant values.
     316             :     bool isAffine() const {
     317             :       // We know that the start value is invariant.  This expression is thus
     318             :       // affine iff the step is also invariant.
     319     1562115 :       return getNumOperands() == 2;
     320             :     }
     321             : 
     322             :     /// Return true if this represents an expression A + B*x + C*x^2
     323             :     /// where A, B and C are loop invariant values.  This corresponds
     324             :     /// to an addrec of the form {L,+,M,+,N}
     325             :     bool isQuadratic() const {
     326        7795 :       return getNumOperands() == 3;
     327             :     }
     328             : 
     329             :     /// Set flags for a recurrence without clearing any previously set flags.
     330             :     /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
     331             :     /// to make it easier to propagate flags.
     332           0 :     void setNoWrapFlags(NoWrapFlags Flags) {
     333      815275 :       if (Flags & (FlagNUW | FlagNSW))
     334             :         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
     335      828195 :       SubclassData |= Flags;
     336           0 :     }
     337             : 
     338             :     /// Return the value of this chain of recurrences at the specified
     339             :     /// iteration number.
     340             :     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
     341             : 
     342             :     /// Return the number of iterations of this loop that produce
     343             :     /// values in the specified constant range.  Another way of
     344             :     /// looking at this is that it returns the first iteration number
     345             :     /// where the value is not in the condition, thus computing the
     346             :     /// exit count.  If the iteration count can't be computed, an
     347             :     /// instance of SCEVCouldNotCompute is returned.
     348             :     const SCEV *getNumIterationsInRange(const ConstantRange &Range,
     349             :                                         ScalarEvolution &SE) const;
     350             : 
     351             :     /// Return an expression representing the value of this expression
     352             :     /// one iteration of the loop ahead.
     353             :     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
     354             : 
     355             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     356             :     static bool classof(const SCEV *S) {
     357     3738056 :       return S->getSCEVType() == scAddRecExpr;
     358             :     }
     359             :   };
     360             : 
     361             :   /// This class represents a signed maximum selection.
     362             :   class SCEVSMaxExpr : public SCEVCommutativeExpr {
     363             :     friend class ScalarEvolution;
     364             : 
     365             :     SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
     366             :                  const SCEV *const *O, size_t N)
     367             :       : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
     368             :       // Max never overflows.
     369             :       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     370             :     }
     371             : 
     372             :   public:
     373             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     374             :     static bool classof(const SCEV *S) {
     375       45409 :       return S->getSCEVType() == scSMaxExpr;
     376             :     }
     377             :   };
     378             : 
     379             :   /// This class represents an unsigned maximum selection.
     380             :   class SCEVUMaxExpr : public SCEVCommutativeExpr {
     381             :     friend class ScalarEvolution;
     382             : 
     383             :     SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
     384             :                  const SCEV *const *O, size_t N)
     385             :       : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
     386             :       // Max never overflows.
     387             :       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     388             :     }
     389             : 
     390             :   public:
     391             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     392             :     static bool classof(const SCEV *S) {
     393       57650 :       return S->getSCEVType() == scUMaxExpr;
     394             :     }
     395             :   };
     396             : 
     397             :   /// This means that we are dealing with an entirely unknown SCEV
     398             :   /// value, and only represent it as its LLVM Value.  This is the
     399             :   /// "bottom" value for the analysis.
     400      227071 :   class SCEVUnknown final : public SCEV, private CallbackVH {
     401             :     friend class ScalarEvolution;
     402             : 
     403             :     /// The parent ScalarEvolution value. This is used to update the
     404             :     /// parent's maps when the value associated with a SCEVUnknown is
     405             :     /// deleted or RAUW'd.
     406             :     ScalarEvolution *SE;
     407             : 
     408             :     /// The next pointer in the linked list of all SCEVUnknown
     409             :     /// instances owned by a ScalarEvolution.
     410             :     SCEVUnknown *Next;
     411             : 
     412      227285 :     SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
     413      227285 :                 ScalarEvolution *se, SCEVUnknown *next) :
     414      227285 :       SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
     415             : 
     416             :     // Implement CallbackVH.
     417             :     void deleted() override;
     418             :     void allUsesReplacedWith(Value *New) override;
     419             : 
     420             :   public:
     421     4312576 :     Value *getValue() const { return getValPtr(); }
     422             : 
     423             :     /// @{
     424             :     /// Test whether this is a special constant representing a type
     425             :     /// size, alignment, or field offset in a target-independent
     426             :     /// manner, and hasn't happened to have been folded with other
     427             :     /// operations into something unrecognizable. This is mainly only
     428             :     /// useful for pretty-printing and other situations where it isn't
     429             :     /// absolutely required for these to succeed.
     430             :     bool isSizeOf(Type *&AllocTy) const;
     431             :     bool isAlignOf(Type *&AllocTy) const;
     432             :     bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
     433             :     /// @}
     434             : 
     435     2371750 :     Type *getType() const { return getValPtr()->getType(); }
     436             : 
     437             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     438             :     static bool classof(const SCEV *S) {
     439     2110826 :       return S->getSCEVType() == scUnknown;
     440             :     }
     441             :   };
     442             : 
     443             :   /// This class defines a simple visitor class that may be used for
     444             :   /// various SCEV analysis purposes.
     445             :   template<typename SC, typename RetVal=void>
     446             :   struct SCEVVisitor {
     447     1000251 :     RetVal visit(const SCEV *S) {
     448     2000502 :       switch (S->getSCEVType()) {
     449       14216 :       case scConstant:
     450       31684 :         return ((SC*)this)->visitConstant((const SCEVConstant*)S);
     451        3396 :       case scTruncate:
     452        3396 :         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
     453        7189 :       case scZeroExtend:
     454        7189 :         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
     455        3974 :       case scSignExtend:
     456        3974 :         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
     457       88867 :       case scAddExpr:
     458       88867 :         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
     459       44268 :       case scMulExpr:
     460       44268 :         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
     461        6596 :       case scUDivExpr:
     462        6596 :         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
     463      215744 :       case scAddRecExpr:
     464      215744 :         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
     465        4840 :       case scSMaxExpr:
     466        4840 :         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
     467         725 :       case scUMaxExpr:
     468         725 :         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
     469       74862 :       case scUnknown:
     470      204947 :         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
     471           0 :       case scCouldNotCompute:
     472           0 :         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
     473           0 :       default:
     474           0 :         llvm_unreachable("Unknown SCEV type!");
     475             :       }
     476             :     }
     477       49350 : 
     478       98700 :     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
     479           0 :       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
     480             :     }
     481          98 :   };
     482          98 : 
     483         143 :   /// Visit all nodes in the expression tree using worklist traversal.
     484         143 :   ///
     485         271 :   /// Visitor implements:
     486         271 :   ///   // return true to follow this node.
     487        8679 :   ///   bool follow(const SCEV *S);
     488        8679 :   ///   // return true to terminate the search.
     489         798 :   ///   bool isDone();
     490         798 :   template<typename SV>
     491          78 :   class SCEVTraversal {
     492          78 :     SV &Visitor;
     493        6745 :     SmallVector<const SCEV *, 8> Worklist;
     494        6745 :     SmallPtrSet<const SCEV *, 8> Visited;
     495          14 : 
     496      561225 :     void push(const SCEV *S) {
     497      561240 :       if (Visited.insert(S).second && Visitor.follow(S))
     498      471680 :         Worklist.push_back(S);
     499      561211 :     }
     500      223820 : 
     501      207523 :   public:
     502      169218 :     SCEVTraversal(SV& V): Visitor(V) {}
     503      207509 : 
     504      151196 :     void visitAll(const SCEV *Root) {
     505      151196 :       push(Root);
     506      174477 :       while (!Worklist.empty() && !Visitor.isDone()) {
     507      116564 :         const SCEV *S = Worklist.pop_back_val();
     508      105138 : 
     509      164918 :         switch (S->getSCEVType()) {
     510      105268 :         case scConstant:
     511      105138 :         case scUnknown:
     512      116688 :           break;
     513      116688 :         case scTruncate:
     514      213032 :         case scZeroExtend:
     515       90178 :         case scSignExtend:
     516        1588 :           push(cast<SCEVCastExpr>(S)->getOperand());
     517      207720 :           break;
     518      143678 :         case scAddExpr:
     519           0 :         case scMulExpr:
     520      143910 :         case scSMaxExpr:
     521      143910 :         case scUMaxExpr:
     522      482176 :         case scAddRecExpr:
     523        7318 :           for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
     524        6727 :             push(Op);
     525      678309 :           break;
     526           0 :         case scUDivExpr: {
     527           0 :           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
     528         326 :           push(UDiv->getLHS());
     529         326 :           push(UDiv->getRHS());
     530         326 :           break;
     531      120046 :         }
     532       93444 :         case scCouldNotCompute:
     533       12506 :           llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
     534           0 :         default:
     535           0 :           llvm_unreachable("Unknown SCEV kind!");
     536        1319 :         }
     537       10527 :       }
     538       54367 :     }
     539      367988 :   };
     540      247374 : 
     541          49 :   /// Use SCEVTraversal to visit all nodes in the given expression tree.
     542          49 :   template<typename SV>
     543          88 :   void visitAll(const SCEV *Root, SV& Visitor) {
     544        1956 :     SCEVTraversal<SV> T(Visitor);
     545        1886 :     T.visitAll(Root);
     546       28396 :   }
     547       12230 : 
     548       12230 :   /// Return true if any node in \p Root satisfies the predicate \p Pred.
     549       59308 :   template <typename PredTy>
     550         328 :   bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
     551         136 :     struct FindClosure {
     552       93826 :       bool Found = false;
     553        1105 :       PredTy Pred;
     554      145015 : 
     555       49034 :       FindClosure(PredTy Pred) : Pred(Pred) {}
     556       49034 : 
     557      171421 :       bool follow(const SCEV *S) {
     558          33 :         if (!Pred(S))
     559         551 :           return true;
     560      252166 : 
     561             :         Found = true;
     562             :         return false;
     563           0 :       }
     564           0 : 
     565             :       bool isDone() const { return Found; }
     566       55008 :     };
     567       63166 : 
     568       46480 :     FindClosure FC(Pred);
     569             :     visitAll(Root, FC);
     570             :     return FC.Found;
     571         451 :   }
     572         451 : 
     573         632 :   /// This visitor recursively visits a SCEV expression and re-writes it.
     574      147740 :   /// The result from each visit is cached, so it will return the same
     575       99682 :   /// SCEV for the same input.
     576         112 :   template<typename SC>
     577        2840 :   class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
     578        2840 :   protected:
     579        4815 :     ScalarEvolution &SE;
     580        4815 :     // Memoize the result of each visit so that we only compute once for
     581       13456 :     // the same input SCEV. This is to avoid redundant computations when
     582       14422 :     // a SCEV is referenced by multiple SCEVs. Without memoization, this
     583       14463 :     // visit algorithm would have exponential time complexity in the worst
     584       70684 :     // case, causing the compiler to hang on certain tests.
     585          32 :     DenseMap<const SCEV *, const SCEV *> RewriteResults;
     586          32 : 
     587      112455 :   public:
     588      111087 :     SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}
     589       49022 : 
     590      468273 :     const SCEV *visit(const SCEV *S) {
     591      466158 :       auto It = RewriteResults.find(S);
     592      519844 :       if (It != RewriteResults.end())
     593       45495 :         return It->second;
     594      398409 :       auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
     595      505781 :       auto Result = RewriteResults.try_emplace(S, Visited);
     596             :       assert(Result.second && "Should insert a new entry");
     597      436390 :       return Result.first->second;
     598       78414 :     }
     599             : 
     600           0 :     const SCEV *visitConstant(const SCEVConstant *Constant) {
     601       65154 :       return Constant;
     602       45901 :     }
     603        2739 : 
     604        2805 :     const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     605        2297 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     606        3186 :       return Operand == Expr->getOperand()
     607        2797 :                  ? Expr
     608        4739 :                  : SE.getTruncateExpr(Operand, Expr->getType());
     609       45996 :     }
     610       31230 : 
     611        2845 :     const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
     612        2845 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     613       18518 :       return Operand == Expr->getOperand()
     614       16007 :                  ? Expr
     615        3098 :                  : SE.getZeroExtendExpr(Operand, Expr->getType());
     616       14832 :     }
     617          62 : 
     618        1944 :     const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
     619        1882 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     620        6990 :       return Operand == Expr->getOperand()
     621       26510 :                  ? Expr
     622       28392 :                  : SE.getSignExtendExpr(Operand, Expr->getType());
     623       26510 :     }
     624       49990 : 
     625       97370 :     const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
     626       51767 :       SmallVector<const SCEV *, 2> Operands;
     627      179650 :       bool Changed = false;
     628      252932 :       for (auto *Op : Expr->operands()) {
     629      111319 :         Operands.push_back(((SC*)this)->visit(Op));
     630      268835 :         Changed |= Op != Operands.back();
     631       14511 :       }
     632       60114 :       return !Changed ? Expr : SE.getAddExpr(Operands);
     633         936 :     }
     634         936 : 
     635       17887 :     const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
     636         363 :       SmallVector<const SCEV *, 2> Operands;
     637        4113 :       bool Changed = false;
     638       62982 :       for (auto *Op : Expr->operands()) {
     639       43015 :         Operands.push_back(((SC*)this)->visit(Op));
     640       43015 :         Changed |= Op != Operands.back();
     641       12393 :       }
     642       17782 :       return !Changed ? Expr : SE.getMulExpr(Operands);
     643       16877 :     }
     644      157897 : 
     645       67623 :     const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
     646        4705 :       auto *LHS = ((SC *)this)->visit(Expr->getLHS());
     647        4458 :       auto *RHS = ((SC *)this)->visit(Expr->getRHS());
     648        4444 :       bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
     649         320 :       return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
     650        6818 :     }
     651         286 : 
     652        6558 :     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
     653           0 :       SmallVector<const SCEV *, 2> Operands;
     654           0 :       bool Changed = false;
     655       31961 :       for (auto *Op : Expr->operands()) {
     656       25403 :         Operands.push_back(((SC*)this)->visit(Op));
     657       13428 :         Changed |= Op != Operands.back();
     658         320 :       }
     659       39632 :       return !Changed ? Expr
     660       31952 :                       : SE.getAddRecExpr(Operands, Expr->getLoop(),
     661       38334 :                                          Expr->getNoWrapFlags());
     662      115232 :     }
     663           0 : 
     664         655 :     const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
     665      166912 :       SmallVector<const SCEV *, 2> Operands;
     666           0 :       bool Changed = false;
     667        2031 :       for (auto *Op : Expr->operands()) {
     668        1376 :         Operands.push_back(((SC *)this)->visit(Op));
     669        1398 :         Changed |= Op != Operands.back();
     670          39 :       }
     671         667 :       return !Changed ? Expr : SE.getSMaxExpr(Operands);
     672        2832 :     }
     673        2820 : 
     674         347 :     const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
     675           0 :       SmallVector<const SCEV *, 2> Operands;
     676           0 :       bool Changed = false;
     677        1048 :       for (auto *Op : Expr->operands()) {
     678         701 :         Operands.push_back(((SC*)this)->visit(Op));
     679       82571 :         Changed |= Op != Operands.back();
     680       55274 :       }
     681         347 :       return !Changed ? Expr : SE.getUMaxExpr(Operands);
     682             :     }
     683           0 : 
     684         178 :     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     685       75040 :       return Expr;
     686         178 :     }
     687       24011 : 
     688       48022 :     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
     689        3560 :       return Expr;
     690        3560 :     }
     691           0 :   };
     692             : 
     693             :   using ValueToValueMap = DenseMap<const Value *, Value *>;
     694       31776 : 
     695             :   /// The SCEVParameterRewriter takes a scalar evolution expression and updates
     696             :   /// the SCEVUnknown components following the Map (Value -> Value).
     697        1079 :   class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
     698        1079 :   public:
     699        7486 :     static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
     700        6996 :                                ValueToValueMap &Map,
     701             :                                bool InterpretConsts = false) {
     702             :       SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
     703       10308 :       return Rewriter.visit(Scev);
     704        9328 :     }
     705             : 
     706             :     SCEVParameterRewriter(ScalarEvolution &SE, ValueToValueMap &M, bool C)
     707         490 :       : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
     708             : 
     709          32 :     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     710             :       Value *V = Expr->getValue();
     711          32 :       if (Map.count(V)) {
     712           4 :         Value *NV = Map[V];
     713           4 :         if (InterpretConsts && isa<ConstantInt>(NV))
     714           0 :           return SE.getConstant(cast<ConstantInt>(NV));
     715           4 :         return SE.getUnknown(NV);
     716             :       }
     717          28 :       return Expr;
     718             :     }
     719             : 
     720             :   private:
     721             :     ValueToValueMap &Map;
     722             :     bool InterpretConsts;
     723             :   };
     724             : 
     725             :   using LoopToScevMapT = DenseMap<const Loop *, const SCEV *>;
     726             : 
     727             :   /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
     728             :   /// the Map (Loop -> SCEV) to all AddRecExprs.
     729             :   class SCEVLoopAddRecRewriter
     730             :       : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
     731             :   public:
     732             :     SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
     733        2752 :         : SCEVRewriteVisitor(SE), Map(M) {}
     734             : 
     735        1376 :     static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
     736    41062723 :                                ScalarEvolution &SE) {
     737    42688072 :       SCEVLoopAddRecRewriter Rewriter(SE, Map);
     738    21503905 :       return Rewriter.visit(Scev);
     739    41062723 :     }
     740           0 : 
     741        1328 :     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
     742           0 :       SmallVector<const SCEV *, 2> Operands;
     743        3990 :       for (const SCEV *Op : Expr->operands())
     744      790339 :         Operands.push_back(visit(Op));
     745      804237 : 
     746      609346 :       const Loop *L = Expr->getLoop();
     747      789005 :       const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
     748        5498 : 
     749       12321 :       if (0 == Map.count(L))
     750        5485 :         return Res;
     751        5498 : 
     752      113737 :       const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
     753      124740 :       return Rec->evaluateAtIteration(Map[L], SE);
     754       96748 :     }
     755      113737 : 
     756     6091000 :   private:
     757     7496956 :     LoopToScevMapT &Map;
     758     5014791 :   };
     759     6091000 : 
     760       11975 : } // end namespace llvm
     761       11975 : 
     762        9696 : #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

Generated by: LCOV version 1.13