LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ScalarEvolutionExpressions.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 216 225 96.0 %
Date: 2017-09-14 15:23:50 Functions: 158 185 85.4 %
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      295267 :     SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
      54      590534 :       SCEV(ID, scConstant), V(v) {}
      55             : 
      56             :   public:
      57             :     ConstantInt *getValue() const { return V; }
      58    13950061 :     const APInt &getAPInt() const { return getValue()->getValue(); }
      59             : 
      60     4592730 :     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    12447178 :       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        5376 :     const SCEV *getOperand() const { return Op; }
      79             :     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      481922 :       return S->getSCEVType() == scTruncate ||
      84      480306 :              S->getSCEVType() == scZeroExtend ||
      85      239160 :              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     1393932 :       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      796039 :       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      700237 :       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      692018 :       : SCEV(ID, T), Operands(O), NumOperands(N) {}
     148             : 
     149             :   public:
     150             :     size_t getNumOperands() const { return NumOperands; }
     151             : 
     152             :     const SCEV *getOperand(unsigned i) const {
     153             :       assert(i < NumOperands && "Operand index out of range!");
     154     6533764 :       return Operands[i];
     155             :     }
     156             : 
     157             :     using op_iterator = const SCEV *const *;
     158             :     using op_range = iterator_range<op_iterator>;
     159             : 
     160             :     op_iterator op_begin() const { return Operands; }
     161     2869841 :     op_iterator op_end() const { return Operands + NumOperands; }
     162             :     op_range operands() const {
     163     4342384 :       return make_range(op_begin(), op_end());
     164             :     }
     165             : 
     166     2901607 :     Type *getType() const { return getOperand(0)->getType(); }
     167             : 
     168             :     NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
     169      493523 :       return (NoWrapFlags)(SubclassData & Mask);
     170             :     }
     171             : 
     172             :     bool hasNoUnsignedWrap() const {
     173      258293 :       return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
     174             :     }
     175             : 
     176             :     bool hasNoSignedWrap() const {
     177      240014 :       return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
     178             :     }
     179             : 
     180             :     bool hasNoSelfWrap() const {
     181        3158 :       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      484843 :       return S->getSCEVType() == scAddExpr ||
     187      455859 :              S->getSCEVType() == scMulExpr ||
     188      448970 :              S->getSCEVType() == scSMaxExpr ||
     189      702062 :              S->getSCEVType() == scUMaxExpr ||
     190      224108 :              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      430838 :       : 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      164491 :       return S->getSCEVType() == scAddExpr ||
     205      118336 :              S->getSCEVType() == scMulExpr ||
     206      190142 :              S->getSCEVType() == scSMaxExpr ||
     207       47801 :              S->getSCEVType() == scUMaxExpr;
     208             :     }
     209             : 
     210             :     /// Set flags for a non-recurrence without clearing previously set flags.
     211             :     void setNoWrapFlags(NoWrapFlags Flags) {
     212      546052 :       SubclassData |= Flags;
     213             :     }
     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      307952 :       : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}
     223             : 
     224             :   public:
     225      398584 :     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      817212 :       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     3717494 :       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      118564 :       : 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     3372853 :       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        5786 :       : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
     262             : 
     263             :   public:
     264             :     const SCEV *getLHS() const { return LHS; }
     265       28124 :     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       28439 :       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      453690 :       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      261180 :       : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
     298             : 
     299             :   public:
     300     1054126 :     const SCEV *getStart() const { return Operands[0]; }
     301             :     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      592197 :     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
     308     1184277 :       if (isAffine()) return getOperand(1);
     309         468 :       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
     310             :                                                            op_end()),
     311         117 :                               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     1129399 :       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        4248 :       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             :     void setNoWrapFlags(NoWrapFlags Flags) {
     333      604877 :       if (Flags & (FlagNUW | FlagNSW))
     334      163719 :         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
     335      616843 :       SubclassData |= Flags;
     336             :     }
     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        8591 :     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
     354       17182 :       return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
     355             :     }
     356             : 
     357             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     358             :     static bool classof(const SCEV *S) {
     359     3844373 :       return S->getSCEVType() == scAddRecExpr;
     360             :     }
     361             :   };
     362             : 
     363             :   /// This class represents a signed maximum selection.
     364             :   class SCEVSMaxExpr : public SCEVCommutativeExpr {
     365             :     friend class ScalarEvolution;
     366             : 
     367             :     SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
     368             :                  const SCEV *const *O, size_t N)
     369        3390 :       : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
     370             :       // Max never overflows.
     371        3390 :       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     372             :     }
     373             : 
     374             :   public:
     375             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     376             :     static bool classof(const SCEV *S) {
     377      467745 :       return S->getSCEVType() == scSMaxExpr;
     378             :     }
     379             :   };
     380             : 
     381             :   /// This class represents an unsigned maximum selection.
     382             :   class SCEVUMaxExpr : public SCEVCommutativeExpr {
     383             :     friend class ScalarEvolution;
     384             : 
     385             :     SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
     386             :                  const SCEV *const *O, size_t N)
     387         932 :       : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
     388             :       // Max never overflows.
     389         932 :       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     390             :     }
     391             : 
     392             :   public:
     393             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     394             :     static bool classof(const SCEV *S) {
     395      476714 :       return S->getSCEVType() == scUMaxExpr;
     396             :     }
     397             :   };
     398             : 
     399             :   /// This means that we are dealing with an entirely unknown SCEV
     400             :   /// value, and only represent it as its LLVM Value.  This is the
     401             :   /// "bottom" value for the analysis.
     402      263918 :   class SCEVUnknown final : public SCEV, private CallbackVH {
     403             :     friend class ScalarEvolution;
     404             : 
     405             :     /// The parent ScalarEvolution value. This is used to update the
     406             :     /// parent's maps when the value associated with a SCEVUnknown is
     407             :     /// deleted or RAUW'd.
     408             :     ScalarEvolution *SE;
     409             : 
     410             :     /// The next pointer in the linked list of all SCEVUnknown
     411             :     /// instances owned by a ScalarEvolution.
     412             :     SCEVUnknown *Next;
     413             : 
     414      132173 :     SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
     415      132173 :                 ScalarEvolution *se, SCEVUnknown *next) :
     416      396519 :       SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
     417             : 
     418             :     // Implement CallbackVH.
     419             :     void deleted() override;
     420             :     void allUsesReplacedWith(Value *New) override;
     421             : 
     422             :   public:
     423     1655813 :     Value *getValue() const { return getValPtr(); }
     424             : 
     425             :     /// @{
     426             :     /// Test whether this is a special constant representing a type
     427             :     /// size, alignment, or field offset in a target-independent
     428             :     /// manner, and hasn't happened to have been folded with other
     429             :     /// operations into something unrecognizable. This is mainly only
     430             :     /// useful for pretty-printing and other situations where it isn't
     431             :     /// absolutely required for these to succeed.
     432             :     bool isSizeOf(Type *&AllocTy) const;
     433             :     bool isAlignOf(Type *&AllocTy) const;
     434             :     bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
     435             :     /// @}
     436             : 
     437     1060589 :     Type *getType() const { return getValPtr()->getType(); }
     438             : 
     439             :     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     440             :     static bool classof(const SCEV *S) {
     441     4306463 :       return S->getSCEVType() == scUnknown;
     442             :     }
     443             :   };
     444             : 
     445             :   /// This class defines a simple visitor class that may be used for
     446             :   /// various SCEV analysis purposes.
     447             :   template<typename SC, typename RetVal=void>
     448             :   struct SCEVVisitor {
     449      640176 :     RetVal visit(const SCEV *S) {
     450     1280352 :       switch (S->getSCEVType()) {
     451       13353 :       case scConstant:
     452      196379 :         return ((SC*)this)->visitConstant((const SCEVConstant*)S);
     453        1579 :       case scTruncate:
     454        1579 :         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
     455        3189 :       case scZeroExtend:
     456        3189 :         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
     457        8410 :       case scSignExtend:
     458        3034 :         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
     459       40133 :       case scAddExpr:
     460       40133 :         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
     461       28932 :       case scMulExpr:
     462       28932 :         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
     463        1925 :       case scUDivExpr:
     464        1925 :         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
     465      139886 :       case scAddRecExpr:
     466      139886 :         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
     467        2833 :       case scSMaxExpr:
     468        2833 :         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
     469         345 :       case scUMaxExpr:
     470         345 :         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
     471       38897 :       case scUnknown:
     472      148153 :         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
     473           0 :       case scCouldNotCompute:
     474           0 :         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
     475           0 :       default:
     476           0 :         llvm_unreachable("Unknown SCEV type!");
     477             :       }
     478             :     }
     479             : 
     480             :     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
     481           0 :       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
     482             :     }
     483             :   };
     484             : 
     485             :   /// Visit all nodes in the expression tree using worklist traversal.
     486             :   ///
     487             :   /// Visitor implements:
     488             :   ///   // return true to follow this node.
     489             :   ///   bool follow(const SCEV *S);
     490             :   ///   // return true to terminate the search.
     491             :   ///   bool isDone();
     492             :   template<typename SV>
     493     5109708 :   class SCEVTraversal {
     494             :     SV &Visitor;
     495             :     SmallVector<const SCEV *, 8> Worklist;
     496             :     SmallPtrSet<const SCEV *, 8> Visited;
     497             : 
     498     6272829 :     void push(const SCEV *S) {
     499     9820490 :       if (Visited.insert(S).second && Visitor.follow(S))
     500     4049503 :         Worklist.push_back(S);
     501     6272829 :     }
     502             : 
     503             :   public:
     504     5109708 :     SCEVTraversal(SV& V): Visitor(V) {}
     505             : 
     506     1703398 :     void visitAll(const SCEV *Root) {
     507     1703398 :       push(Root);
     508     5822002 :       while (!Worklist.empty() && !Visitor.isDone()) {
     509     8029816 :         const SCEV *S = Worklist.pop_back_val();
     510             : 
     511     4014908 :         switch (S->getSCEVType()) {
     512             :         case scConstant:
     513             :         case scUnknown:
     514             :           break;
     515      118937 :         case scTruncate:
     516             :         case scZeroExtend:
     517             :         case scSignExtend:
     518      118937 :           push(cast<SCEVCastExpr>(S)->getOperand());
     519      118937 :           break;
     520     1765911 :         case scAddExpr:
     521             :         case scMulExpr:
     522             :         case scSMaxExpr:
     523             :         case scUMaxExpr:
     524             :         case scAddRecExpr:
     525     7880726 :           for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
     526     4348904 :             push(Op);
     527             :           break;
     528       50795 :         case scUDivExpr: {
     529       50795 :           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
     530       50795 :           push(UDiv->getLHS());
     531       50795 :           push(UDiv->getRHS());
     532       50795 :           break;
     533             :         }
     534           0 :         case scCouldNotCompute:
     535           0 :           llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
     536           0 :         default:
     537           0 :           llvm_unreachable("Unknown SCEV kind!");
     538             :         }
     539             :       }
     540     1703398 :     }
     541             :   };
     542             : 
     543             :   /// Use SCEVTraversal to visit all nodes in the given expression tree.
     544             :   template<typename SV>
     545     1146761 :   void visitAll(const SCEV *Root, SV& Visitor) {
     546     2293522 :     SCEVTraversal<SV> T(Visitor);
     547     1146761 :     T.visitAll(Root);
     548     1146761 :   }
     549             : 
     550             :   /// Return true if any node in \p Root satisfies the predicate \p Pred.
     551             :   template <typename PredTy>
     552             :   bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
     553             :     struct FindClosure {
     554             :       bool Found = false;
     555             :       PredTy Pred;
     556             : 
     557     1130095 :       FindClosure(PredTy Pred) : Pred(Pred) {}
     558             : 
     559             :       bool follow(const SCEV *S) {
     560     4440306 :         if (!Pred(S))
     561             :           return true;
     562             : 
     563       13396 :         Found = true;
     564             :         return false;
     565             :       }
     566             : 
     567             :       bool isDone() const { return Found; }
     568             :     };
     569             : 
     570     2052935 :     FindClosure FC(Pred);
     571     1130095 :     visitAll(Root, FC);
     572     1130095 :     return FC.Found;
     573             :   }
     574             : 
     575             :   /// This visitor recursively visits a SCEV expression and re-writes it.
     576             :   /// The result from each visit is cached, so it will return the same
     577             :   /// SCEV for the same input.
     578             :   template<typename SC>
     579      179646 :   class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
     580             :   protected:
     581             :     ScalarEvolution &SE;
     582             :     // Memoize the result of each visit so that we only compute once for
     583             :     // the same input SCEV. This is to avoid redundant computations when
     584             :     // a SCEV is referenced by multiple SCEVs. Without memoization, this
     585             :     // visit algorithm would have exponential time complexity in the worst
     586             :     // case, causing the compiler to hang on certain tests.
     587             :     DenseMap<const SCEV *, const SCEV *> RewriteResults;
     588             : 
     589             :   public:
     590      179646 :     SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}
     591             : 
     592      293762 :     const SCEV *visit(const SCEV *S) {
     593      293762 :       auto It = RewriteResults.find(S);
     594      881286 :       if (It != RewriteResults.end())
     595       34847 :         return It->second;
     596      258915 :       auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
     597      258915 :       auto Result = RewriteResults.try_emplace(S, Visited);
     598             :       assert(Result.second && "Should insert a new entry");
     599      258915 :       return Result.first->second;
     600             :     }
     601             : 
     602             :     const SCEV *visitConstant(const SCEVConstant *Constant) {
     603             :       return Constant;
     604             :     }
     605             : 
     606         587 :     const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     607         587 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     608         587 :       return Operand == Expr->getOperand()
     609             :                  ? Expr
     610         587 :                  : SE.getTruncateExpr(Operand, Expr->getType());
     611             :     }
     612             : 
     613         980 :     const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
     614         980 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     615         980 :       return Operand == Expr->getOperand()
     616             :                  ? Expr
     617         980 :                  : SE.getZeroExtendExpr(Operand, Expr->getType());
     618             :     }
     619             : 
     620        1855 :     const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
     621        1855 :       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
     622        1855 :       return Operand == Expr->getOperand()
     623             :                  ? Expr
     624        1855 :                  : SE.getSignExtendExpr(Operand, Expr->getType());
     625             :     }
     626             : 
     627       21728 :     const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
     628       43456 :       SmallVector<const SCEV *, 2> Operands;
     629       21728 :       bool Changed = false;
     630       88710 :       for (auto *Op : Expr->operands()) {
     631       45254 :         Operands.push_back(((SC*)this)->visit(Op));
     632       90508 :         Changed |= Op != Operands.back();
     633             :       }
     634       43456 :       return !Changed ? Expr : SE.getAddExpr(Operands);
     635             :     }
     636             : 
     637       11968 :     const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
     638       23936 :       SmallVector<const SCEV *, 2> Operands;
     639       11968 :       bool Changed = false;
     640       58158 :       for (auto *Op : Expr->operands()) {
     641       34222 :         Operands.push_back(((SC*)this)->visit(Op));
     642       68444 :         Changed |= Op != Operands.back();
     643             :       }
     644       23936 :       return !Changed ? Expr : SE.getMulExpr(Operands);
     645             :     }
     646             : 
     647        1088 :     const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
     648        1088 :       auto *LHS = ((SC *)this)->visit(Expr->getLHS());
     649        1088 :       auto *RHS = ((SC *)this)->visit(Expr->getRHS());
     650        1088 :       bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
     651          16 :       return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
     652             :     }
     653             : 
     654       11296 :     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
     655       22592 :       SmallVector<const SCEV *, 2> Operands;
     656       11296 :       bool Changed = false;
     657       45339 :       for (auto *Op : Expr->operands()) {
     658       22747 :         Operands.push_back(((SC*)this)->visit(Op));
     659       45494 :         Changed |= Op != Operands.back();
     660             :       }
     661             :       return !Changed ? Expr
     662         300 :                       : SE.getAddRecExpr(Operands, Expr->getLoop(),
     663       22742 :                                          Expr->getNoWrapFlags());
     664             :     }
     665             : 
     666         133 :     const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
     667         266 :       SmallVector<const SCEV *, 2> Operands;
     668         133 :       bool Changed = false;
     669         548 :       for (auto *Op : Expr->operands()) {
     670         282 :         Operands.push_back(((SC *)this)->visit(Op));
     671         564 :         Changed |= Op != Operands.back();
     672             :       }
     673         266 :       return !Changed ? Expr : SE.getSMaxExpr(Operands);
     674             :     }
     675             : 
     676         217 :     const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
     677         434 :       SmallVector<const SCEV *, 2> Operands;
     678         217 :       bool Changed = false;
     679         887 :       for (auto *Op : Expr->operands()) {
     680         453 :         Operands.push_back(((SC*)this)->visit(Op));
     681         906 :         Changed |= Op != Operands.back();
     682             :       }
     683         434 :       return !Changed ? Expr : SE.getUMaxExpr(Operands);
     684             :     }
     685             : 
     686             :     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     687       38897 :       return Expr;
     688             :     }
     689             : 
     690             :     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
     691             :       return Expr;
     692             :     }
     693             :   };
     694             : 
     695             :   using ValueToValueMap = DenseMap<const Value *, Value *>;
     696             : 
     697             :   /// The SCEVParameterRewriter takes a scalar evolution expression and updates
     698             :   /// the SCEVUnknown components following the Map (Value -> Value).
     699        1080 :   class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
     700             :   public:
     701         540 :     static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
     702             :                                ValueToValueMap &Map,
     703             :                                bool InterpretConsts = false) {
     704        1620 :       SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
     705        1080 :       return Rewriter.visit(Scev);
     706             :     }
     707             : 
     708             :     SCEVParameterRewriter(ScalarEvolution &SE, ValueToValueMap &M, bool C)
     709        1080 :       : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
     710             : 
     711          94 :     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     712          94 :       Value *V = Expr->getValue();
     713         188 :       if (Map.count(V)) {
     714          80 :         Value *NV = Map[V];
     715          48 :         if (InterpretConsts && isa<ConstantInt>(NV))
     716           8 :           return SE.getConstant(cast<ConstantInt>(NV));
     717          36 :         return SE.getUnknown(NV);
     718             :       }
     719          54 :       return Expr;
     720             :     }
     721             : 
     722             :   private:
     723             :     ValueToValueMap &Map;
     724             :     bool InterpretConsts;
     725             :   };
     726             : 
     727             :   using LoopToScevMapT = DenseMap<const Loop *, const SCEV *>;
     728             : 
     729             :   /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
     730             :   /// the Map (Loop -> SCEV) to all AddRecExprs.
     731        3264 :   class SCEVLoopAddRecRewriter
     732             :       : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
     733             :   public:
     734             :     SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
     735        3264 :         : SCEVRewriteVisitor(SE), Map(M) {}
     736             : 
     737        1632 :     static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
     738             :                                ScalarEvolution &SE) {
     739        3264 :       SCEVLoopAddRecRewriter Rewriter(SE, Map);
     740        3264 :       return Rewriter.visit(Scev);
     741             :     }
     742             : 
     743        1394 :     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
     744        2788 :       SmallVector<const SCEV *, 2> Operands;
     745        4188 :       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
     746        5588 :         Operands.push_back(visit(Expr->getOperand(i)));
     747             : 
     748        1394 :       const Loop *L = Expr->getLoop();
     749        2788 :       const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
     750             : 
     751        2788 :       if (0 == Map.count(L))
     752             :         return Res;
     753             : 
     754        1390 :       const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
     755        2780 :       return Rec->evaluateAtIteration(Map[L], SE);
     756             :     }
     757             : 
     758             :   private:
     759             :     LoopToScevMapT &Map;
     760             :   };
     761             : 
     762             : } // end namespace llvm
     763             : 
     764             : #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

Generated by: LCOV version 1.13