LLVM  14.0.0git
ScalarEvolutionExpressions.h
Go to the documentation of this file.
1 //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the classes used to represent and build scalar expressions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
14 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/IR/ValueHandle.h"
25 #include "llvm/Support/Casting.h"
27 #include <cassert>
28 #include <cstddef>
29 
30 namespace llvm {
31 
32 class APInt;
33 class Constant;
34 class ConstantRange;
35 class Loop;
36 class Type;
37 
38  enum SCEVTypes : unsigned short {
39  // These should be ordered in terms of increasing complexity to make the
40  // folders simpler.
44  };
45 
46  /// This class represents a constant integer value.
47  class SCEVConstant : public SCEV {
48  friend class ScalarEvolution;
49 
50  ConstantInt *V;
51 
53  SCEV(ID, scConstant, 1), V(v) {}
54 
55  public:
56  ConstantInt *getValue() const { return V; }
57  const APInt &getAPInt() const { return getValue()->getValue(); }
58 
59  Type *getType() const { return V->getType(); }
60 
61  /// Methods for support type inquiry through isa, cast, and dyn_cast:
62  static bool classof(const SCEV *S) {
63  return S->getSCEVType() == scConstant;
64  }
65  };
66 
68  APInt Size(16, 1);
69  for (auto *Arg : Args)
70  Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
71  return (unsigned short)Size.getZExtValue();
72  }
73 
74  /// This is the base class for unary cast operator classes.
75  class SCEVCastExpr : public SCEV {
76  protected:
77  std::array<const SCEV *, 1> Operands;
78  Type *Ty;
79 
80  SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op,
81  Type *ty);
82 
83  public:
84  const SCEV *getOperand() const { return Operands[0]; }
85  const SCEV *getOperand(unsigned i) const {
86  assert(i == 0 && "Operand index out of range!");
87  return Operands[0];
88  }
89  using op_iterator = std::array<const SCEV *, 1>::const_iterator;
91 
92  op_range operands() const {
93  return make_range(Operands.begin(), Operands.end());
94  }
95  size_t getNumOperands() const { return 1; }
96  Type *getType() const { return Ty; }
97 
98  /// Methods for support type inquiry through isa, cast, and dyn_cast:
99  static bool classof(const SCEV *S) {
100  return S->getSCEVType() == scPtrToInt || S->getSCEVType() == scTruncate ||
101  S->getSCEVType() == scZeroExtend ||
102  S->getSCEVType() == scSignExtend;
103  }
104  };
105 
106  /// This class represents a cast from a pointer to a pointer-sized integer
107  /// value.
109  friend class ScalarEvolution;
110 
111  SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, Type *ITy);
112 
113  public:
114  /// Methods for support type inquiry through isa, cast, and dyn_cast:
115  static bool classof(const SCEV *S) {
116  return S->getSCEVType() == scPtrToInt;
117  }
118  };
119 
120  /// This is the base class for unary integral cast operator classes.
122  protected:
124  const SCEV *op, Type *ty);
125 
126  public:
127  /// Methods for support type inquiry through isa, cast, and dyn_cast:
128  static bool classof(const SCEV *S) {
129  return S->getSCEVType() == scTruncate ||
130  S->getSCEVType() == scZeroExtend ||
131  S->getSCEVType() == scSignExtend;
132  }
133  };
134 
135  /// This class represents a truncation of an integer value to a
136  /// smaller integer value.
138  friend class ScalarEvolution;
139 
141  const SCEV *op, Type *ty);
142 
143  public:
144  /// Methods for support type inquiry through isa, cast, and dyn_cast:
145  static bool classof(const SCEV *S) {
146  return S->getSCEVType() == scTruncate;
147  }
148  };
149 
150  /// This class represents a zero extension of a small integer value
151  /// to a larger integer value.
153  friend class ScalarEvolution;
154 
156  const SCEV *op, Type *ty);
157 
158  public:
159  /// Methods for support type inquiry through isa, cast, and dyn_cast:
160  static bool classof(const SCEV *S) {
161  return S->getSCEVType() == scZeroExtend;
162  }
163  };
164 
165  /// This class represents a sign extension of a small integer value
166  /// to a larger integer value.
168  friend class ScalarEvolution;
169 
171  const SCEV *op, Type *ty);
172 
173  public:
174  /// Methods for support type inquiry through isa, cast, and dyn_cast:
175  static bool classof(const SCEV *S) {
176  return S->getSCEVType() == scSignExtend;
177  }
178  };
179 
180  /// This node is a base class providing common functionality for
181  /// n'ary operators.
182  class SCEVNAryExpr : public SCEV {
183  protected:
184  // Since SCEVs are immutable, ScalarEvolution allocates operand
185  // arrays with its SCEVAllocator, so this class just needs a simple
186  // pointer rather than a more elaborate vector-like data structure.
187  // This also avoids the need for a non-trivial destructor.
188  const SCEV *const *Operands;
189  size_t NumOperands;
190 
192  const SCEV *const *O, size_t N)
194  NumOperands(N) {}
195 
196  public:
197  size_t getNumOperands() const { return NumOperands; }
198 
199  const SCEV *getOperand(unsigned i) const {
200  assert(i < NumOperands && "Operand index out of range!");
201  return Operands[i];
202  }
203 
204  using op_iterator = const SCEV *const *;
206 
207  op_iterator op_begin() const { return Operands; }
208  op_iterator op_end() const { return Operands + NumOperands; }
209  op_range operands() const {
210  return make_range(op_begin(), op_end());
211  }
212 
214  return (NoWrapFlags)(SubclassData & Mask);
215  }
216 
217  bool hasNoUnsignedWrap() const {
219  }
220 
221  bool hasNoSignedWrap() const {
223  }
224 
225  bool hasNoSelfWrap() const {
226  return getNoWrapFlags(FlagNW) != FlagAnyWrap;
227  }
228 
229  /// Methods for support type inquiry through isa, cast, and dyn_cast:
230  static bool classof(const SCEV *S) {
231  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
232  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
233  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
234  S->getSCEVType() == scAddRecExpr;
235  }
236  };
237 
238  /// This node is the base class for n'ary commutative operators.
240  protected:
242  enum SCEVTypes T, const SCEV *const *O, size_t N)
243  : SCEVNAryExpr(ID, T, O, N) {}
244 
245  public:
246  /// Methods for support type inquiry through isa, cast, and dyn_cast:
247  static bool classof(const SCEV *S) {
248  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
249  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
250  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
251  }
252 
253  /// Set flags for a non-recurrence without clearing previously set flags.
255  SubclassData |= Flags;
256  }
257  };
258 
259  /// This node represents an addition of some number of SCEVs.
261  friend class ScalarEvolution;
262 
263  Type *Ty;
264 
265  SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
267  auto *FirstPointerTypedOp = find_if(operands(), [](const SCEV *Op) {
268  return Op->getType()->isPointerTy();
269  });
270  if (FirstPointerTypedOp != operands().end())
271  Ty = (*FirstPointerTypedOp)->getType();
272  else
273  Ty = getOperand(0)->getType();
274  }
275 
276  public:
277  Type *getType() const { return Ty; }
278 
279  /// Methods for support type inquiry through isa, cast, and dyn_cast:
280  static bool classof(const SCEV *S) {
281  return S->getSCEVType() == scAddExpr;
282  }
283  };
284 
285  /// This node represents multiplication of some number of SCEVs.
287  friend class ScalarEvolution;
288 
290  const SCEV *const *O, size_t N)
292 
293  public:
294  Type *getType() const { return getOperand(0)->getType(); }
295 
296  /// Methods for support type inquiry through isa, cast, and dyn_cast:
297  static bool classof(const SCEV *S) {
298  return S->getSCEVType() == scMulExpr;
299  }
300  };
301 
302  /// This class represents a binary unsigned division operation.
303  class SCEVUDivExpr : public SCEV {
304  friend class ScalarEvolution;
305 
306  std::array<const SCEV *, 2> Operands;
307 
308  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
309  : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})) {
310  Operands[0] = lhs;
311  Operands[1] = rhs;
312  }
313 
314  public:
315  const SCEV *getLHS() const { return Operands[0]; }
316  const SCEV *getRHS() const { return Operands[1]; }
317  size_t getNumOperands() const { return 2; }
318  const SCEV *getOperand(unsigned i) const {
319  assert((i == 0 || i == 1) && "Operand index out of range!");
320  return i == 0 ? getLHS() : getRHS();
321  }
322 
323  using op_iterator = std::array<const SCEV *, 2>::const_iterator;
325  op_range operands() const {
326  return make_range(Operands.begin(), Operands.end());
327  }
328 
329  Type *getType() const {
330  // In most cases the types of LHS and RHS will be the same, but in some
331  // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
332  // depend on the type for correctness, but handling types carefully can
333  // avoid extra casts in the SCEVExpander. The LHS is more likely to be
334  // a pointer type than the RHS, so use the RHS' type here.
335  return getRHS()->getType();
336  }
337 
338  /// Methods for support type inquiry through isa, cast, and dyn_cast:
339  static bool classof(const SCEV *S) {
340  return S->getSCEVType() == scUDivExpr;
341  }
342  };
343 
344  /// This node represents a polynomial recurrence on the trip count
345  /// of the specified loop. This is the primary focus of the
346  /// ScalarEvolution framework; all the other SCEV subclasses are
347  /// mostly just supporting infrastructure to allow SCEVAddRecExpr
348  /// expressions to be created and analyzed.
349  ///
350  /// All operands of an AddRec are required to be loop invariant.
351  ///
352  class SCEVAddRecExpr : public SCEVNAryExpr {
353  friend class ScalarEvolution;
354 
355  const Loop *L;
356 
358  const SCEV *const *O, size_t N, const Loop *l)
359  : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
360 
361  public:
362  Type *getType() const { return getStart()->getType(); }
363  const SCEV *getStart() const { return Operands[0]; }
364  const Loop *getLoop() const { return L; }
365 
366  /// Constructs and returns the recurrence indicating how much this
367  /// expression steps by. If this is a polynomial of degree N, it
368  /// returns a chrec of degree N-1. We cannot determine whether
369  /// the step recurrence has self-wraparound.
371  if (isAffine()) return getOperand(1);
373  op_end()),
374  getLoop(), FlagAnyWrap);
375  }
376 
377  /// Return true if this represents an expression A + B*x where A
378  /// and B are loop invariant values.
379  bool isAffine() const {
380  // We know that the start value is invariant. This expression is thus
381  // affine iff the step is also invariant.
382  return getNumOperands() == 2;
383  }
384 
385  /// Return true if this represents an expression A + B*x + C*x^2
386  /// where A, B and C are loop invariant values. This corresponds
387  /// to an addrec of the form {L,+,M,+,N}
388  bool isQuadratic() const {
389  return getNumOperands() == 3;
390  }
391 
392  /// Set flags for a recurrence without clearing any previously set flags.
393  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
394  /// to make it easier to propagate flags.
396  if (Flags & (FlagNUW | FlagNSW))
397  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
398  SubclassData |= Flags;
399  }
400 
401  /// Return the value of this chain of recurrences at the specified
402  /// iteration number.
403  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
404 
405  /// Return the value of this chain of recurrences at the specified iteration
406  /// number. Takes an explicit list of operands to represent an AddRec.
408  const SCEV *It, ScalarEvolution &SE);
409 
410  /// Return the number of iterations of this loop that produce
411  /// values in the specified constant range. Another way of
412  /// looking at this is that it returns the first iteration number
413  /// where the value is not in the condition, thus computing the
414  /// exit count. If the iteration count can't be computed, an
415  /// instance of SCEVCouldNotCompute is returned.
416  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
417  ScalarEvolution &SE) const;
418 
419  /// Return an expression representing the value of this expression
420  /// one iteration of the loop ahead.
422 
423  /// Methods for support type inquiry through isa, cast, and dyn_cast:
424  static bool classof(const SCEV *S) {
425  return S->getSCEVType() == scAddRecExpr;
426  }
427  };
428 
429  /// This node is the base class min/max selections.
431  friend class ScalarEvolution;
432 
433  static bool isMinMaxType(enum SCEVTypes T) {
434  return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
435  T == scUMinExpr;
436  }
437 
438  protected:
439  /// Note: Constructing subclasses via this constructor is allowed
441  const SCEV *const *O, size_t N)
442  : SCEVCommutativeExpr(ID, T, O, N) {
443  assert(isMinMaxType(T));
444  // Min and max never overflow
446  }
447 
448  public:
449  Type *getType() const { return getOperand(0)->getType(); }
450 
451  static bool classof(const SCEV *S) {
452  return isMinMaxType(S->getSCEVType());
453  }
454 
455  static enum SCEVTypes negate(enum SCEVTypes T) {
456  switch (T) {
457  case scSMaxExpr:
458  return scSMinExpr;
459  case scSMinExpr:
460  return scSMaxExpr;
461  case scUMaxExpr:
462  return scUMinExpr;
463  case scUMinExpr:
464  return scUMaxExpr;
465  default:
466  llvm_unreachable("Not a min or max SCEV type!");
467  }
468  }
469  };
470 
471  /// This class represents a signed maximum selection.
472  class SCEVSMaxExpr : public SCEVMinMaxExpr {
473  friend class ScalarEvolution;
474 
475  SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
476  : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
477 
478  public:
479  /// Methods for support type inquiry through isa, cast, and dyn_cast:
480  static bool classof(const SCEV *S) {
481  return S->getSCEVType() == scSMaxExpr;
482  }
483  };
484 
485  /// This class represents an unsigned maximum selection.
486  class SCEVUMaxExpr : public SCEVMinMaxExpr {
487  friend class ScalarEvolution;
488 
489  SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
490  : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
491 
492  public:
493  /// Methods for support type inquiry through isa, cast, and dyn_cast:
494  static bool classof(const SCEV *S) {
495  return S->getSCEVType() == scUMaxExpr;
496  }
497  };
498 
499  /// This class represents a signed minimum selection.
500  class SCEVSMinExpr : public SCEVMinMaxExpr {
501  friend class ScalarEvolution;
502 
503  SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
504  : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
505 
506  public:
507  /// Methods for support type inquiry through isa, cast, and dyn_cast:
508  static bool classof(const SCEV *S) {
509  return S->getSCEVType() == scSMinExpr;
510  }
511  };
512 
513  /// This class represents an unsigned minimum selection.
514  class SCEVUMinExpr : public SCEVMinMaxExpr {
515  friend class ScalarEvolution;
516 
517  SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
518  : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
519 
520  public:
521  /// Methods for support type inquiry through isa, cast, and dyn_cast:
522  static bool classof(const SCEV *S) {
523  return S->getSCEVType() == scUMinExpr;
524  }
525  };
526 
527  /// This means that we are dealing with an entirely unknown SCEV
528  /// value, and only represent it as its LLVM Value. This is the
529  /// "bottom" value for the analysis.
530  class SCEVUnknown final : public SCEV, private CallbackVH {
531  friend class ScalarEvolution;
532 
533  /// The parent ScalarEvolution value. This is used to update the
534  /// parent's maps when the value associated with a SCEVUnknown is
535  /// deleted or RAUW'd.
536  ScalarEvolution *SE;
537 
538  /// The next pointer in the linked list of all SCEVUnknown
539  /// instances owned by a ScalarEvolution.
540  SCEVUnknown *Next;
541 
543  ScalarEvolution *se, SCEVUnknown *next) :
544  SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
545 
546  // Implement CallbackVH.
547  void deleted() override;
548  void allUsesReplacedWith(Value *New) override;
549 
550  public:
551  Value *getValue() const { return getValPtr(); }
552 
553  /// @{
554  /// Test whether this is a special constant representing a type
555  /// size, alignment, or field offset in a target-independent
556  /// manner, and hasn't happened to have been folded with other
557  /// operations into something unrecognizable. This is mainly only
558  /// useful for pretty-printing and other situations where it isn't
559  /// absolutely required for these to succeed.
560  bool isSizeOf(Type *&AllocTy) const;
561  bool isAlignOf(Type *&AllocTy) const;
562  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
563  /// @}
564 
565  Type *getType() const { return getValPtr()->getType(); }
566 
567  /// Methods for support type inquiry through isa, cast, and dyn_cast:
568  static bool classof(const SCEV *S) {
569  return S->getSCEVType() == scUnknown;
570  }
571  };
572 
573  /// This class defines a simple visitor class that may be used for
574  /// various SCEV analysis purposes.
575  template<typename SC, typename RetVal=void>
576  struct SCEVVisitor {
577  RetVal visit(const SCEV *S) {
578  switch (S->getSCEVType()) {
579  case scConstant:
580  return ((SC*)this)->visitConstant((const SCEVConstant*)S);
581  case scPtrToInt:
582  return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
583  case scTruncate:
584  return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
585  case scZeroExtend:
586  return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
587  case scSignExtend:
588  return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
589  case scAddExpr:
590  return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
591  case scMulExpr:
592  return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
593  case scUDivExpr:
594  return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
595  case scAddRecExpr:
596  return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
597  case scSMaxExpr:
598  return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
599  case scUMaxExpr:
600  return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
601  case scSMinExpr:
602  return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
603  case scUMinExpr:
604  return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
605  case scUnknown:
606  return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
607  case scCouldNotCompute:
608  return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
609  }
610  llvm_unreachable("Unknown SCEV kind!");
611  }
612 
614  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
615  }
616  };
617 
618  /// Visit all nodes in the expression tree using worklist traversal.
619  ///
620  /// Visitor implements:
621  /// // return true to follow this node.
622  /// bool follow(const SCEV *S);
623  /// // return true to terminate the search.
624  /// bool isDone();
625  template<typename SV>
627  SV &Visitor;
630 
631  void push(const SCEV *S) {
632  if (Visited.insert(S).second && Visitor.follow(S))
633  Worklist.push_back(S);
634  }
635 
636  public:
637  SCEVTraversal(SV& V): Visitor(V) {}
638 
639  void visitAll(const SCEV *Root) {
640  push(Root);
641  while (!Worklist.empty() && !Visitor.isDone()) {
642  const SCEV *S = Worklist.pop_back_val();
643 
644  switch (S->getSCEVType()) {
645  case scConstant:
646  case scUnknown:
647  continue;
648  case scPtrToInt:
649  case scTruncate:
650  case scZeroExtend:
651  case scSignExtend:
652  push(cast<SCEVCastExpr>(S)->getOperand());
653  continue;
654  case scAddExpr:
655  case scMulExpr:
656  case scSMaxExpr:
657  case scUMaxExpr:
658  case scSMinExpr:
659  case scUMinExpr:
660  case scAddRecExpr:
661  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
662  push(Op);
663  continue;
664  case scUDivExpr: {
665  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
666  push(UDiv->getLHS());
667  push(UDiv->getRHS());
668  continue;
669  }
670  case scCouldNotCompute:
671  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
672  }
673  llvm_unreachable("Unknown SCEV kind!");
674  }
675  }
676  };
677 
678  /// Use SCEVTraversal to visit all nodes in the given expression tree.
679  template<typename SV>
680  void visitAll(const SCEV *Root, SV& Visitor) {
681  SCEVTraversal<SV> T(Visitor);
682  T.visitAll(Root);
683  }
684 
685  /// Return true if any node in \p Root satisfies the predicate \p Pred.
686  template <typename PredTy>
687  bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
688  struct FindClosure {
689  bool Found = false;
690  PredTy Pred;
691 
692  FindClosure(PredTy Pred) : Pred(Pred) {}
693 
694  bool follow(const SCEV *S) {
695  if (!Pred(S))
696  return true;
697 
698  Found = true;
699  return false;
700  }
701 
702  bool isDone() const { return Found; }
703  };
704 
705  FindClosure FC(Pred);
706  visitAll(Root, FC);
707  return FC.Found;
708  }
709 
710  /// This visitor recursively visits a SCEV expression and re-writes it.
711  /// The result from each visit is cached, so it will return the same
712  /// SCEV for the same input.
713  template<typename SC>
714  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
715  protected:
717  // Memoize the result of each visit so that we only compute once for
718  // the same input SCEV. This is to avoid redundant computations when
719  // a SCEV is referenced by multiple SCEVs. Without memoization, this
720  // visit algorithm would have exponential time complexity in the worst
721  // case, causing the compiler to hang on certain tests.
723 
724  public:
726 
727  const SCEV *visit(const SCEV *S) {
728  auto It = RewriteResults.find(S);
729  if (It != RewriteResults.end())
730  return It->second;
731  auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
732  auto Result = RewriteResults.try_emplace(S, Visited);
733  assert(Result.second && "Should insert a new entry");
734  return Result.first->second;
735  }
736 
738  return Constant;
739  }
740 
742  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
743  return Operand == Expr->getOperand()
744  ? Expr
745  : SE.getPtrToIntExpr(Operand, Expr->getType());
746  }
747 
749  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
750  return Operand == Expr->getOperand()
751  ? Expr
752  : SE.getTruncateExpr(Operand, Expr->getType());
753  }
754 
756  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
757  return Operand == Expr->getOperand()
758  ? Expr
759  : SE.getZeroExtendExpr(Operand, Expr->getType());
760  }
761 
763  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
764  return Operand == Expr->getOperand()
765  ? Expr
766  : SE.getSignExtendExpr(Operand, Expr->getType());
767  }
768 
769  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
771  bool Changed = false;
772  for (auto *Op : Expr->operands()) {
773  Operands.push_back(((SC*)this)->visit(Op));
774  Changed |= Op != Operands.back();
775  }
776  return !Changed ? Expr : SE.getAddExpr(Operands);
777  }
778 
779  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
781  bool Changed = false;
782  for (auto *Op : Expr->operands()) {
783  Operands.push_back(((SC*)this)->visit(Op));
784  Changed |= Op != Operands.back();
785  }
786  return !Changed ? Expr : SE.getMulExpr(Operands);
787  }
788 
789  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
790  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
791  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
792  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
793  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
794  }
795 
796  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
798  bool Changed = false;
799  for (auto *Op : Expr->operands()) {
800  Operands.push_back(((SC*)this)->visit(Op));
801  Changed |= Op != Operands.back();
802  }
803  return !Changed ? Expr
804  : SE.getAddRecExpr(Operands, Expr->getLoop(),
805  Expr->getNoWrapFlags());
806  }
807 
808  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
810  bool Changed = false;
811  for (auto *Op : Expr->operands()) {
812  Operands.push_back(((SC *)this)->visit(Op));
813  Changed |= Op != Operands.back();
814  }
815  return !Changed ? Expr : SE.getSMaxExpr(Operands);
816  }
817 
818  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
820  bool Changed = false;
821  for (auto *Op : Expr->operands()) {
822  Operands.push_back(((SC*)this)->visit(Op));
823  Changed |= Op != Operands.back();
824  }
825  return !Changed ? Expr : SE.getUMaxExpr(Operands);
826  }
827 
828  const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
830  bool Changed = false;
831  for (auto *Op : Expr->operands()) {
832  Operands.push_back(((SC *)this)->visit(Op));
833  Changed |= Op != Operands.back();
834  }
835  return !Changed ? Expr : SE.getSMinExpr(Operands);
836  }
837 
838  const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
840  bool Changed = false;
841  for (auto *Op : Expr->operands()) {
842  Operands.push_back(((SC *)this)->visit(Op));
843  Changed |= Op != Operands.back();
844  }
845  return !Changed ? Expr : SE.getUMinExpr(Operands);
846  }
847 
848  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
849  return Expr;
850  }
851 
853  return Expr;
854  }
855  };
856 
859 
860  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
861  /// the SCEVUnknown components following the Map (Value -> SCEV).
862  class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
863  public:
864  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
865  ValueToSCEVMapTy &Map) {
867  return Rewriter.visit(Scev);
868  }
869 
871  : SCEVRewriteVisitor(SE), Map(M) {}
872 
873  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
874  auto I = Map.find(Expr->getValue());
875  if (I == Map.end())
876  return Expr;
877  return I->second;
878  }
879 
880  private:
881  ValueToSCEVMapTy &Map;
882  };
883 
885 
886  /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
887  /// the Map (Loop -> SCEV) to all AddRecExprs.
889  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
890  public:
892  : SCEVRewriteVisitor(SE), Map(M) {}
893 
894  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
895  ScalarEvolution &SE) {
897  return Rewriter.visit(Scev);
898  }
899 
900  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
902  for (const SCEV *Op : Expr->operands())
903  Operands.push_back(visit(Op));
904 
905  const Loop *L = Expr->getLoop();
906  if (0 == Map.count(L))
907  return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
908 
910  }
911 
912  private:
913  LoopToScevMapT &Map;
914  };
915 
916 } // end namespace llvm
917 
918 #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::SCEVTraversal::visitAll
void visitAll(const SCEV *Root)
Definition: ScalarEvolutionExpressions.h:639
llvm::SCEVUDivExpr
This class represents a binary unsigned division operation.
Definition: ScalarEvolutionExpressions.h:303
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::SCEVUMinExpr
This class represents an unsigned minimum selection.
Definition: ScalarEvolutionExpressions.h:514
llvm::SCEVRewriteVisitor::visitMulExpr
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
Definition: ScalarEvolutionExpressions.h:779
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::scSMinExpr
@ scSMinExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVAddRecExpr::setNoWrapFlags
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
Definition: ScalarEvolutionExpressions.h:395
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:173
llvm::SCEVNAryExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:230
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:379
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:363
llvm::computeExpressionSize
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
Definition: ScalarEvolutionExpressions.h:67
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SCEVSMaxExpr
This class represents a signed maximum selection.
Definition: ScalarEvolutionExpressions.h:472
llvm::SCEVRewriteVisitor::visitSMaxExpr
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:808
llvm::scConstant
@ scConstant
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVParameterRewriter::rewrite
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
Definition: ScalarEvolutionExpressions.h:864
llvm::SCEVRewriteVisitor::visitCouldNotCompute
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
Definition: ScalarEvolutionExpressions.h:852
llvm::SCEVUnknown::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:568
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
op
#define op(i)
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::SCEVUDivExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:329
llvm::SCEVNAryExpr::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Definition: ScalarEvolutionExpressions.h:217
llvm::SCEVPtrToIntExpr
This class represents a cast from a pointer to a pointer-sized integer value.
Definition: ScalarEvolutionExpressions.h:108
llvm::scCouldNotCompute
@ scCouldNotCompute
Definition: ScalarEvolutionExpressions.h:43
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
Definition: ScalarEvolution.cpp:3535
ErrorHandling.h
llvm::SCEVCommutativeExpr::SCEVCommutativeExpr
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Definition: ScalarEvolutionExpressions.h:241
llvm::SCEVNAryExpr::Operands
const SCEV *const * Operands
Definition: ScalarEvolutionExpressions.h:188
llvm::SCEVCastExpr::getOperand
const SCEV * getOperand() const
Definition: ScalarEvolutionExpressions.h:84
llvm::SCEVUnknown::isAlignOf
bool isAlignOf(Type *&AllocTy) const
Definition: ScalarEvolution.cpp:541
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::SCEV::NoWrapMask
@ NoWrapMask
Definition: ScalarEvolution.h:137
llvm::SCEVTypes
SCEVTypes
Definition: ScalarEvolutionExpressions.h:38
llvm::ScalarEvolution::getTruncateExpr
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1185
llvm::SCEVMulExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:294
llvm::SCEV::FlagNW
@ FlagNW
Definition: ScalarEvolution.h:134
llvm::SCEVUnknown::isOffsetOf
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
Definition: ScalarEvolution.cpp:565
ScalarEvolution.h
llvm::SCEVRewriteVisitor::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:848
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::SCEVSMaxExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:480
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::scSMaxExpr
@ scSMaxExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::ScalarEvolution::setFlags
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Definition: ScalarEvolution.h:484
llvm::ValueHandleBase::getValPtr
Value * getValPtr() const
Definition: ValueHandle.h:99
llvm::SCEVRewriteVisitor::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:796
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SCEVSignExtendExpr
This class represents a sign extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:167
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::scUnknown
@ scUnknown
Definition: ScalarEvolutionExpressions.h:43
llvm::SCEVConstant::getValue
ConstantInt * getValue() const
Definition: ScalarEvolutionExpressions.h:56
llvm::SCEVMinMaxExpr::SCEVMinMaxExpr
SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
Definition: ScalarEvolutionExpressions.h:440
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::SCEVNAryExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:209
llvm::SCEVConstant::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:62
llvm::SCEVZeroExtendExpr
This class represents a zero extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:152
llvm::SCEVRewriteVisitor::visitPtrToIntExpr
const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)
Definition: ScalarEvolutionExpressions.h:741
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3010
llvm::SCEVTraversal
Visit all nodes in the expression tree using worklist traversal.
Definition: ScalarEvolutionExpressions.h:626
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::SCEVRewriteVisitor::RewriteResults
DenseMap< const SCEV *, const SCEV * > RewriteResults
Definition: ScalarEvolutionExpressions.h:722
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:576
llvm::SCEVUnknown::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:565
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:680
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
llvm::SCEVCommutativeExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:247
llvm::SCEVNAryExpr::SCEVNAryExpr
SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Definition: ScalarEvolutionExpressions.h:191
Constants.h
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::SCEVCastExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:85
llvm::SCEVCastExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:92
llvm::SCEVConstant::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:59
llvm::ScalarEvolution::getUMaxExpr
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3867
llvm::scAddRecExpr
@ scAddRecExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVUMaxExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:494
llvm::SCEVTruncateExpr
This class represents a truncation of an integer value to a smaller integer value.
Definition: ScalarEvolutionExpressions.h:137
llvm::ScalarEvolution::getUDivExpr
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3304
llvm::SCEVParameterRewriter::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:873
llvm::scUMaxExpr
@ scUMaxExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVRewriteVisitor::visitUDivExpr
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
Definition: ScalarEvolutionExpressions.h:789
l
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
Definition: README.txt:100
llvm::SCEVMulExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:297
llvm::SCEVParameterRewriter::SCEVParameterRewriter
SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)
Definition: ScalarEvolutionExpressions.h:870
llvm::SCEVIntegralCastExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:128
llvm::SCEVMulExpr
This node represents multiplication of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:286
llvm::SCEVVisitor::visitCouldNotCompute
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)
Definition: ScalarEvolutionExpressions.h:613
llvm::SCEVUMaxExpr
This class represents an unsigned maximum selection.
Definition: ScalarEvolutionExpressions.h:486
llvm::SCEVCastExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:99
llvm::SCEVExprContains
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Definition: ScalarEvolutionExpressions.h:687
llvm::SCEVMinMaxExpr::classof
static bool classof(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:451
SmallPtrSet.h
llvm::SCEVNAryExpr
This node is a base class providing common functionality for n'ary operators.
Definition: ScalarEvolutionExpressions.h:182
llvm::SCEVUnknown::getValue
Value * getValue() const
Definition: ScalarEvolutionExpressions.h:551
llvm::SCEVRewriteVisitor::visitAddExpr
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
Definition: ScalarEvolutionExpressions.h:769
llvm::SCEVRewriteVisitor::SCEVRewriteVisitor
SCEVRewriteVisitor(ScalarEvolution &SE)
Definition: ScalarEvolutionExpressions.h:725
llvm::SCEVCommutativeExpr
This node is the base class for n'ary commutative operators.
Definition: ScalarEvolutionExpressions.h:239
llvm::SCEVAddRecExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:424
llvm::SCEVLoopAddRecRewriter::SCEVLoopAddRecRewriter
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
Definition: ScalarEvolutionExpressions.h:891
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::SCEV::SubclassData
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Definition: ScalarEvolution.h:93
llvm::SCEVUDivExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:318
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::SCEVUDivExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:339
llvm::ScalarEvolution::getSMaxExpr
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3858
llvm::scZeroExtend
@ scZeroExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVNAryExpr::op_end
op_iterator op_end() const
Definition: ScalarEvolutionExpressions.h:208
llvm::SCEVLoopAddRecRewriter::rewrite
static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
Definition: ScalarEvolutionExpressions.h:894
llvm::scAddExpr
@ scAddExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:136
llvm::SCEVUDivExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:325
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:133
llvm::ScalarEvolution::getPtrToIntExpr
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:1175
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCEVNAryExpr::hasNoSelfWrap
bool hasNoSelfWrap() const
Definition: ScalarEvolutionExpressions.h:225
llvm::SCEVSMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:508
llvm::SCEVCastExpr::SCEVCastExpr
SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
Definition: ScalarEvolution.cpp:465
llvm::SCEVUDivExpr::op_iterator
std::array< const SCEV *, 2 >::const_iterator op_iterator
Definition: ScalarEvolutionExpressions.h:323
llvm::SCEVUDivExpr::getLHS
const SCEV * getLHS() const
Definition: ScalarEvolutionExpressions.h:315
llvm::SCEVRewriteVisitor
This visitor recursively visits a SCEV expression and re-writes it.
Definition: ScalarEvolutionExpressions.h:714
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:47
TemplateParamKind::Type
@ Type
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::ScalarEvolution::getUMinExpr
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3886
llvm::scUDivExpr
@ scUDivExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVPtrToIntExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:115
llvm::SCEVMinMaxExpr::negate
static enum SCEVTypes negate(enum SCEVTypes T)
Definition: ScalarEvolutionExpressions.h:455
llvm::SCEVTraversal::SCEVTraversal
SCEVTraversal(SV &V)
Definition: ScalarEvolutionExpressions.h:637
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SCEVAddRecExpr::isQuadratic
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
Definition: ScalarEvolutionExpressions.h:388
iterator_range.h
llvm::SCEVCouldNotCompute
An object of this class is returned by queries that could not be answered.
Definition: ScalarEvolution.h:208
llvm::scSignExtend
@ scSignExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVRewriteVisitor::visitUMaxExpr
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:818
llvm::SCEVRewriteVisitor::visit
const SCEV * visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:727
llvm::SCEVUMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:522
llvm::SCEVCastExpr::op_iterator
std::array< const SCEV *, 1 >::const_iterator op_iterator
Definition: ScalarEvolutionExpressions.h:89
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::SCEVRewriteVisitor::visitUMinExpr
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:838
llvm::SCEVCastExpr::Operands
std::array< const SCEV *, 1 > Operands
Definition: ScalarEvolutionExpressions.h:77
llvm::SCEVParameterRewriter
The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...
Definition: ScalarEvolutionExpressions.h:862
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:213
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::ScalarEvolution::getSignExtendExpr
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1883
llvm::SCEVNAryExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:197
llvm::scTruncate
@ scTruncate
Definition: ScalarEvolutionExpressions.h:41
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::SCEV::FlagNUW
@ FlagNUW
Definition: ScalarEvolution.h:135
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
ValueHandle.h
llvm::SCEVRewriteVisitor::visitTruncateExpr
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)
Definition: ScalarEvolutionExpressions.h:748
llvm::SCEVMinMaxExpr
This node is the base class min/max selections.
Definition: ScalarEvolutionExpressions.h:430
FoldingSet.h
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1578
llvm::scPtrToInt
@ scPtrToInt
Definition: ScalarEvolutionExpressions.h:43
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:132
llvm::SCEVLoopAddRecRewriter::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:900
llvm::SCEVMinMaxExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:449
llvm::SCEVRewriteVisitor::visitZeroExtendExpr
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:755
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::SCEVSMinExpr
This class represents a signed minimum selection.
Definition: ScalarEvolutionExpressions.h:500
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::SCEVRewriteVisitor::visitSMinExpr
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:828
llvm::SCEVAddRecExpr::getPostIncExpr
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
Definition: ScalarEvolution.cpp:12197
llvm::SCEVCastExpr
This is the base class for unary cast operator classes.
Definition: ScalarEvolutionExpressions.h:75
llvm::SCEVAddRecExpr::getNumIterationsInRange
const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
Definition: ScalarEvolution.cpp:12125
llvm::SCEVNAryExpr::NumOperands
size_t NumOperands
Definition: ScalarEvolutionExpressions.h:189
llvm::SCEVNAryExpr::op_begin
op_iterator op_begin() const
Definition: ScalarEvolutionExpressions.h:207
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
Casting.h
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:530
llvm::SCEVUDivExpr::getRHS
const SCEV * getRHS() const
Definition: ScalarEvolutionExpressions.h:316
llvm::SCEVIntegralCastExpr::SCEVIntegralCastExpr
SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
Definition: ScalarEvolution.cpp:478
llvm::SCEVTruncateExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:145
llvm::SCEVCommutativeExpr::setNoWrapFlags
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
Definition: ScalarEvolutionExpressions.h:254
llvm::SCEVVisitor::visit
RetVal visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:577
llvm::SCEVRewriteVisitor::visitSignExtendExpr
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:762
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::SCEVConstant::getAPInt
const APInt & getAPInt() const
Definition: ScalarEvolutionExpressions.h:57
llvm::FoldingSetNodeIDRef
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:285
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::SCEVNAryExpr::op_iterator
const SCEV *const * op_iterator
Definition: ScalarEvolutionExpressions.h:204
llvm::SCEVIntegralCastExpr
This is the base class for unary integral cast operator classes.
Definition: ScalarEvolutionExpressions.h:121
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1578
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:260
llvm::scMulExpr
@ scMulExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVRewriteVisitor::SE
ScalarEvolution & SE
Definition: ScalarEvolutionExpressions.h:716
SmallVector.h
llvm::SCEVNAryExpr::hasNoSignedWrap
bool hasNoSignedWrap() const
Definition: ScalarEvolutionExpressions.h:221
llvm::SCEVRewriteVisitor::visitConstant
const SCEV * visitConstant(const SCEVConstant *Constant)
Definition: ScalarEvolutionExpressions.h:737
N
#define N
llvm::SCEVCastExpr::Ty
Type * Ty
Definition: ScalarEvolutionExpressions.h:78
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::SCEVAddExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:277
llvm::SCEVSignExtendExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:175
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:377
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:2424
llvm::SCEVCastExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:95
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::scUMinExpr
@ scUMinExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVNAryExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:199
llvm::SCEVUDivExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:317
llvm::SCEVLoopAddRecRewriter
The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies the Map (Loop -> SCEV) to ...
Definition: ScalarEvolutionExpressions.h:888
Value.h
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3876
llvm::SCEVAddExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:280
llvm::SCEVAddRecExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:362
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SCEVUnknown::isSizeOf
bool isSizeOf(Type *&AllocTy) const
Definition: ScalarEvolution.cpp:525
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370
llvm::SCEVZeroExtendExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:160
llvm::SCEVCastExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:96
llvm::SCEVAddRecExpr::evaluateAtIteration
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
Definition: ScalarEvolution.cpp:1023
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37