LLVM  13.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 
213  Type *getType() const { return getOperand(0)->getType(); }
214 
216  return (NoWrapFlags)(SubclassData & Mask);
217  }
218 
219  bool hasNoUnsignedWrap() const {
221  }
222 
223  bool hasNoSignedWrap() const {
225  }
226 
227  bool hasNoSelfWrap() const {
228  return getNoWrapFlags(FlagNW) != FlagAnyWrap;
229  }
230 
231  /// Methods for support type inquiry through isa, cast, and dyn_cast:
232  static bool classof(const SCEV *S) {
233  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
234  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
235  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
236  S->getSCEVType() == scAddRecExpr;
237  }
238  };
239 
240  /// This node is the base class for n'ary commutative operators.
242  protected:
244  enum SCEVTypes T, const SCEV *const *O, size_t N)
245  : SCEVNAryExpr(ID, T, O, N) {}
246 
247  public:
248  /// Methods for support type inquiry through isa, cast, and dyn_cast:
249  static bool classof(const SCEV *S) {
250  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
251  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
252  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
253  }
254 
255  /// Set flags for a non-recurrence without clearing previously set flags.
257  SubclassData |= Flags;
258  }
259  };
260 
261  /// This node represents an addition of some number of SCEVs.
263  friend class ScalarEvolution;
264 
265  Type *Ty;
266 
267  SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
269  auto *FirstPointerTypedOp = find_if(operands(), [](const SCEV *Op) {
270  return Op->getType()->isPointerTy();
271  });
272  if (FirstPointerTypedOp != operands().end())
273  Ty = (*FirstPointerTypedOp)->getType();
274  else
275  Ty = getOperand(0)->getType();
276  }
277 
278  public:
279  Type *getType() const { return Ty; }
280 
281  /// Methods for support type inquiry through isa, cast, and dyn_cast:
282  static bool classof(const SCEV *S) {
283  return S->getSCEVType() == scAddExpr;
284  }
285  };
286 
287  /// This node represents multiplication of some number of SCEVs.
289  friend class ScalarEvolution;
290 
292  const SCEV *const *O, size_t N)
294 
295  public:
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  const SCEV *getStart() const { return Operands[0]; }
363  const Loop *getLoop() const { return L; }
364 
365  /// Constructs and returns the recurrence indicating how much this
366  /// expression steps by. If this is a polynomial of degree N, it
367  /// returns a chrec of degree N-1. We cannot determine whether
368  /// the step recurrence has self-wraparound.
370  if (isAffine()) return getOperand(1);
372  op_end()),
373  getLoop(), FlagAnyWrap);
374  }
375 
376  /// Return true if this represents an expression A + B*x where A
377  /// and B are loop invariant values.
378  bool isAffine() const {
379  // We know that the start value is invariant. This expression is thus
380  // affine iff the step is also invariant.
381  return getNumOperands() == 2;
382  }
383 
384  /// Return true if this represents an expression A + B*x + C*x^2
385  /// where A, B and C are loop invariant values. This corresponds
386  /// to an addrec of the form {L,+,M,+,N}
387  bool isQuadratic() const {
388  return getNumOperands() == 3;
389  }
390 
391  /// Set flags for a recurrence without clearing any previously set flags.
392  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
393  /// to make it easier to propagate flags.
395  if (Flags & (FlagNUW | FlagNSW))
396  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
397  SubclassData |= Flags;
398  }
399 
400  /// Return the value of this chain of recurrences at the specified
401  /// iteration number.
402  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
403 
404  /// Return the number of iterations of this loop that produce
405  /// values in the specified constant range. Another way of
406  /// looking at this is that it returns the first iteration number
407  /// where the value is not in the condition, thus computing the
408  /// exit count. If the iteration count can't be computed, an
409  /// instance of SCEVCouldNotCompute is returned.
410  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
411  ScalarEvolution &SE) const;
412 
413  /// Return an expression representing the value of this expression
414  /// one iteration of the loop ahead.
416 
417  /// Methods for support type inquiry through isa, cast, and dyn_cast:
418  static bool classof(const SCEV *S) {
419  return S->getSCEVType() == scAddRecExpr;
420  }
421  };
422 
423  /// This node is the base class min/max selections.
425  friend class ScalarEvolution;
426 
427  static bool isMinMaxType(enum SCEVTypes T) {
428  return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
429  T == scUMinExpr;
430  }
431 
432  protected:
433  /// Note: Constructing subclasses via this constructor is allowed
435  const SCEV *const *O, size_t N)
436  : SCEVCommutativeExpr(ID, T, O, N) {
437  assert(isMinMaxType(T));
438  // Min and max never overflow
440  }
441 
442  public:
443  static bool classof(const SCEV *S) {
444  return isMinMaxType(S->getSCEVType());
445  }
446 
447  static enum SCEVTypes negate(enum SCEVTypes T) {
448  switch (T) {
449  case scSMaxExpr:
450  return scSMinExpr;
451  case scSMinExpr:
452  return scSMaxExpr;
453  case scUMaxExpr:
454  return scUMinExpr;
455  case scUMinExpr:
456  return scUMaxExpr;
457  default:
458  llvm_unreachable("Not a min or max SCEV type!");
459  }
460  }
461  };
462 
463  /// This class represents a signed maximum selection.
464  class SCEVSMaxExpr : public SCEVMinMaxExpr {
465  friend class ScalarEvolution;
466 
467  SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
468  : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
469 
470  public:
471  /// Methods for support type inquiry through isa, cast, and dyn_cast:
472  static bool classof(const SCEV *S) {
473  return S->getSCEVType() == scSMaxExpr;
474  }
475  };
476 
477  /// This class represents an unsigned maximum selection.
478  class SCEVUMaxExpr : public SCEVMinMaxExpr {
479  friend class ScalarEvolution;
480 
481  SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
482  : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
483 
484  public:
485  /// Methods for support type inquiry through isa, cast, and dyn_cast:
486  static bool classof(const SCEV *S) {
487  return S->getSCEVType() == scUMaxExpr;
488  }
489  };
490 
491  /// This class represents a signed minimum selection.
492  class SCEVSMinExpr : public SCEVMinMaxExpr {
493  friend class ScalarEvolution;
494 
495  SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
496  : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
497 
498  public:
499  /// Methods for support type inquiry through isa, cast, and dyn_cast:
500  static bool classof(const SCEV *S) {
501  return S->getSCEVType() == scSMinExpr;
502  }
503  };
504 
505  /// This class represents an unsigned minimum selection.
506  class SCEVUMinExpr : public SCEVMinMaxExpr {
507  friend class ScalarEvolution;
508 
509  SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
510  : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
511 
512  public:
513  /// Methods for support type inquiry through isa, cast, and dyn_cast:
514  static bool classof(const SCEV *S) {
515  return S->getSCEVType() == scUMinExpr;
516  }
517  };
518 
519  /// This means that we are dealing with an entirely unknown SCEV
520  /// value, and only represent it as its LLVM Value. This is the
521  /// "bottom" value for the analysis.
522  class SCEVUnknown final : public SCEV, private CallbackVH {
523  friend class ScalarEvolution;
524 
525  /// The parent ScalarEvolution value. This is used to update the
526  /// parent's maps when the value associated with a SCEVUnknown is
527  /// deleted or RAUW'd.
528  ScalarEvolution *SE;
529 
530  /// The next pointer in the linked list of all SCEVUnknown
531  /// instances owned by a ScalarEvolution.
532  SCEVUnknown *Next;
533 
535  ScalarEvolution *se, SCEVUnknown *next) :
536  SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
537 
538  // Implement CallbackVH.
539  void deleted() override;
540  void allUsesReplacedWith(Value *New) override;
541 
542  public:
543  Value *getValue() const { return getValPtr(); }
544 
545  /// @{
546  /// Test whether this is a special constant representing a type
547  /// size, alignment, or field offset in a target-independent
548  /// manner, and hasn't happened to have been folded with other
549  /// operations into something unrecognizable. This is mainly only
550  /// useful for pretty-printing and other situations where it isn't
551  /// absolutely required for these to succeed.
552  bool isSizeOf(Type *&AllocTy) const;
553  bool isAlignOf(Type *&AllocTy) const;
554  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
555  /// @}
556 
557  Type *getType() const { return getValPtr()->getType(); }
558 
559  /// Methods for support type inquiry through isa, cast, and dyn_cast:
560  static bool classof(const SCEV *S) {
561  return S->getSCEVType() == scUnknown;
562  }
563  };
564 
565  /// This class defines a simple visitor class that may be used for
566  /// various SCEV analysis purposes.
567  template<typename SC, typename RetVal=void>
568  struct SCEVVisitor {
569  RetVal visit(const SCEV *S) {
570  switch (S->getSCEVType()) {
571  case scConstant:
572  return ((SC*)this)->visitConstant((const SCEVConstant*)S);
573  case scPtrToInt:
574  return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
575  case scTruncate:
576  return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
577  case scZeroExtend:
578  return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
579  case scSignExtend:
580  return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
581  case scAddExpr:
582  return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
583  case scMulExpr:
584  return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
585  case scUDivExpr:
586  return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
587  case scAddRecExpr:
588  return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
589  case scSMaxExpr:
590  return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
591  case scUMaxExpr:
592  return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
593  case scSMinExpr:
594  return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
595  case scUMinExpr:
596  return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
597  case scUnknown:
598  return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
599  case scCouldNotCompute:
600  return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
601  }
602  llvm_unreachable("Unknown SCEV kind!");
603  }
604 
606  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
607  }
608  };
609 
610  /// Visit all nodes in the expression tree using worklist traversal.
611  ///
612  /// Visitor implements:
613  /// // return true to follow this node.
614  /// bool follow(const SCEV *S);
615  /// // return true to terminate the search.
616  /// bool isDone();
617  template<typename SV>
619  SV &Visitor;
622 
623  void push(const SCEV *S) {
624  if (Visited.insert(S).second && Visitor.follow(S))
625  Worklist.push_back(S);
626  }
627 
628  public:
629  SCEVTraversal(SV& V): Visitor(V) {}
630 
631  void visitAll(const SCEV *Root) {
632  push(Root);
633  while (!Worklist.empty() && !Visitor.isDone()) {
634  const SCEV *S = Worklist.pop_back_val();
635 
636  switch (S->getSCEVType()) {
637  case scConstant:
638  case scUnknown:
639  continue;
640  case scPtrToInt:
641  case scTruncate:
642  case scZeroExtend:
643  case scSignExtend:
644  push(cast<SCEVCastExpr>(S)->getOperand());
645  continue;
646  case scAddExpr:
647  case scMulExpr:
648  case scSMaxExpr:
649  case scUMaxExpr:
650  case scSMinExpr:
651  case scUMinExpr:
652  case scAddRecExpr:
653  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
654  push(Op);
655  continue;
656  case scUDivExpr: {
657  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
658  push(UDiv->getLHS());
659  push(UDiv->getRHS());
660  continue;
661  }
662  case scCouldNotCompute:
663  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
664  }
665  llvm_unreachable("Unknown SCEV kind!");
666  }
667  }
668  };
669 
670  /// Use SCEVTraversal to visit all nodes in the given expression tree.
671  template<typename SV>
672  void visitAll(const SCEV *Root, SV& Visitor) {
673  SCEVTraversal<SV> T(Visitor);
674  T.visitAll(Root);
675  }
676 
677  /// Return true if any node in \p Root satisfies the predicate \p Pred.
678  template <typename PredTy>
679  bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
680  struct FindClosure {
681  bool Found = false;
682  PredTy Pred;
683 
684  FindClosure(PredTy Pred) : Pred(Pred) {}
685 
686  bool follow(const SCEV *S) {
687  if (!Pred(S))
688  return true;
689 
690  Found = true;
691  return false;
692  }
693 
694  bool isDone() const { return Found; }
695  };
696 
697  FindClosure FC(Pred);
698  visitAll(Root, FC);
699  return FC.Found;
700  }
701 
702  /// This visitor recursively visits a SCEV expression and re-writes it.
703  /// The result from each visit is cached, so it will return the same
704  /// SCEV for the same input.
705  template<typename SC>
706  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
707  protected:
709  // Memoize the result of each visit so that we only compute once for
710  // the same input SCEV. This is to avoid redundant computations when
711  // a SCEV is referenced by multiple SCEVs. Without memoization, this
712  // visit algorithm would have exponential time complexity in the worst
713  // case, causing the compiler to hang on certain tests.
715 
716  public:
718 
719  const SCEV *visit(const SCEV *S) {
720  auto It = RewriteResults.find(S);
721  if (It != RewriteResults.end())
722  return It->second;
723  auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
724  auto Result = RewriteResults.try_emplace(S, Visited);
725  assert(Result.second && "Should insert a new entry");
726  return Result.first->second;
727  }
728 
730  return Constant;
731  }
732 
734  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
735  return Operand == Expr->getOperand()
736  ? Expr
737  : SE.getPtrToIntExpr(Operand, Expr->getType());
738  }
739 
741  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
742  return Operand == Expr->getOperand()
743  ? Expr
744  : SE.getTruncateExpr(Operand, Expr->getType());
745  }
746 
748  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
749  return Operand == Expr->getOperand()
750  ? Expr
751  : SE.getZeroExtendExpr(Operand, Expr->getType());
752  }
753 
755  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
756  return Operand == Expr->getOperand()
757  ? Expr
758  : SE.getSignExtendExpr(Operand, Expr->getType());
759  }
760 
761  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
763  bool Changed = false;
764  for (auto *Op : Expr->operands()) {
765  Operands.push_back(((SC*)this)->visit(Op));
766  Changed |= Op != Operands.back();
767  }
768  return !Changed ? Expr : SE.getAddExpr(Operands);
769  }
770 
771  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
773  bool Changed = false;
774  for (auto *Op : Expr->operands()) {
775  Operands.push_back(((SC*)this)->visit(Op));
776  Changed |= Op != Operands.back();
777  }
778  return !Changed ? Expr : SE.getMulExpr(Operands);
779  }
780 
781  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
782  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
783  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
784  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
785  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
786  }
787 
788  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
790  bool Changed = false;
791  for (auto *Op : Expr->operands()) {
792  Operands.push_back(((SC*)this)->visit(Op));
793  Changed |= Op != Operands.back();
794  }
795  return !Changed ? Expr
796  : SE.getAddRecExpr(Operands, Expr->getLoop(),
797  Expr->getNoWrapFlags());
798  }
799 
800  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
802  bool Changed = false;
803  for (auto *Op : Expr->operands()) {
804  Operands.push_back(((SC *)this)->visit(Op));
805  Changed |= Op != Operands.back();
806  }
807  return !Changed ? Expr : SE.getSMaxExpr(Operands);
808  }
809 
810  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
812  bool Changed = false;
813  for (auto *Op : Expr->operands()) {
814  Operands.push_back(((SC*)this)->visit(Op));
815  Changed |= Op != Operands.back();
816  }
817  return !Changed ? Expr : SE.getUMaxExpr(Operands);
818  }
819 
820  const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
822  bool Changed = false;
823  for (auto *Op : Expr->operands()) {
824  Operands.push_back(((SC *)this)->visit(Op));
825  Changed |= Op != Operands.back();
826  }
827  return !Changed ? Expr : SE.getSMinExpr(Operands);
828  }
829 
830  const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
832  bool Changed = false;
833  for (auto *Op : Expr->operands()) {
834  Operands.push_back(((SC *)this)->visit(Op));
835  Changed |= Op != Operands.back();
836  }
837  return !Changed ? Expr : SE.getUMinExpr(Operands);
838  }
839 
840  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
841  return Expr;
842  }
843 
845  return Expr;
846  }
847  };
848 
851 
852  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
853  /// the SCEVUnknown components following the Map (Value -> SCEV).
854  class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
855  public:
856  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
857  ValueToSCEVMapTy &Map) {
859  return Rewriter.visit(Scev);
860  }
861 
863  : SCEVRewriteVisitor(SE), Map(M) {}
864 
865  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
866  auto I = Map.find(Expr->getValue());
867  if (I == Map.end())
868  return Expr;
869  return I->second;
870  }
871 
872  private:
873  ValueToSCEVMapTy &Map;
874  };
875 
877 
878  /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
879  /// the Map (Loop -> SCEV) to all AddRecExprs.
881  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
882  public:
884  : SCEVRewriteVisitor(SE), Map(M) {}
885 
886  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
887  ScalarEvolution &SE) {
889  return Rewriter.visit(Scev);
890  }
891 
892  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
894  for (const SCEV *Op : Expr->operands())
895  Operands.push_back(visit(Op));
896 
897  const Loop *L = Expr->getLoop();
898  const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
899 
900  if (0 == Map.count(L))
901  return Res;
902 
903  const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
904  return Rec->evaluateAtIteration(Map[L], SE);
905  }
906 
907  private:
908  LoopToScevMapT &Map;
909  };
910 
911 } // end namespace llvm
912 
913 #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:631
llvm::SCEVUDivExpr
This class represents a binary unsigned division operation.
Definition: ScalarEvolutionExpressions.h:303
llvm
Definition: AllocatorList.h:23
llvm::SCEVUMinExpr
This class represents an unsigned minimum selection.
Definition: ScalarEvolutionExpressions.h:506
llvm::SCEVRewriteVisitor::visitMulExpr
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
Definition: ScalarEvolutionExpressions.h:771
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:394
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:171
llvm::SCEVNAryExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:232
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:378
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:362
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:464
llvm::SCEVRewriteVisitor::visitSMaxExpr
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:800
llvm::scConstant
@ scConstant
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVParameterRewriter::rewrite
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
Definition: ScalarEvolutionExpressions.h:856
llvm::SCEVRewriteVisitor::visitCouldNotCompute
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
Definition: ScalarEvolutionExpressions.h:844
llvm::SCEVUnknown::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:560
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
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:219
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:3346
ErrorHandling.h
llvm::SCEVCommutativeExpr::SCEVCommutativeExpr
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Definition: ScalarEvolutionExpressions.h:243
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:542
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::SCEV::NoWrapMask
@ NoWrapMask
Definition: ScalarEvolution.h:120
llvm::SCEVTypes
SCEVTypes
Definition: ScalarEvolutionExpressions.h:38
llvm::ScalarEvolution::getTruncateExpr
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1176
llvm::SCEV::FlagNW
@ FlagNW
Definition: ScalarEvolution.h:117
llvm::SCEVUnknown::isOffsetOf
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
Definition: ScalarEvolution.cpp:567
ScalarEvolution.h
llvm::SCEVRewriteVisitor::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:840
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
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:472
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:467
llvm::ValueHandleBase::getValPtr
Value * getValPtr() const
Definition: ValueHandle.h:99
llvm::SCEVRewriteVisitor::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:788
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:434
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:733
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:2829
llvm::SCEVTraversal
Visit all nodes in the expression tree using worklist traversal.
Definition: ScalarEvolutionExpressions.h:618
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::SCEVRewriteVisitor::RewriteResults
DenseMap< const SCEV *, const SCEV * > RewriteResults
Definition: ScalarEvolutionExpressions.h:714
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:568
llvm::SCEVUnknown::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:557
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:672
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:229
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:249
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:69
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:3660
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:486
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:3122
llvm::SCEVParameterRewriter::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:865
llvm::scUMaxExpr
@ scUMaxExpr
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVRewriteVisitor::visitUDivExpr
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
Definition: ScalarEvolutionExpressions.h:781
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:862
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:288
llvm::SCEVVisitor::visitCouldNotCompute
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)
Definition: ScalarEvolutionExpressions.h:605
llvm::SCEVUMaxExpr
This class represents an unsigned maximum selection.
Definition: ScalarEvolutionExpressions.h:478
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:679
llvm::SCEVMinMaxExpr::classof
static bool classof(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:443
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:543
llvm::SCEVRewriteVisitor::visitAddExpr
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
Definition: ScalarEvolutionExpressions.h:761
llvm::SCEVRewriteVisitor::SCEVRewriteVisitor
SCEVRewriteVisitor(ScalarEvolution &SE)
Definition: ScalarEvolutionExpressions.h:717
llvm::SCEVCommutativeExpr
This node is the base class for n'ary commutative operators.
Definition: ScalarEvolutionExpressions.h:241
llvm::SCEVAddRecExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:418
llvm::SCEVLoopAddRecRewriter::SCEVLoopAddRecRewriter
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
Definition: ScalarEvolutionExpressions.h:883
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:94
llvm::SCEVUDivExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:318
llvm::SCEVNAryExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:213
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:132
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:3651
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:886
llvm::scAddExpr
@ scAddExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:119
llvm::SCEVUDivExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:325
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:116
llvm::ScalarEvolution::getPtrToIntExpr
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:1166
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCEVNAryExpr::hasNoSelfWrap
bool hasNoSelfWrap() const
Definition: ScalarEvolutionExpressions.h:227
llvm::SCEVSMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:500
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:706
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:3679
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:447
llvm::SCEVTraversal::SCEVTraversal
SCEVTraversal(SV &V)
Definition: ScalarEvolutionExpressions.h:629
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:387
iterator_range.h
llvm::SCEVCouldNotCompute
An object of this class is returned by queries that could not be answered.
Definition: ScalarEvolution.h:191
llvm::scSignExtend
@ scSignExtend
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVRewriteVisitor::visitUMaxExpr
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:810
llvm::SCEVRewriteVisitor::visit
const SCEV * visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:719
llvm::SCEVUMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:514
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:70
llvm::SCEVRewriteVisitor::visitUMinExpr
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:830
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:854
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:215
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:1868
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:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::SCEV::FlagNUW
@ FlagNUW
Definition: ScalarEvolution.h:118
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:740
llvm::SCEVMinMaxExpr
This node is the base class min/max selections.
Definition: ScalarEvolutionExpressions.h:424
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:1509
llvm::scPtrToInt
@ scPtrToInt
Definition: ScalarEvolutionExpressions.h:43
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:115
llvm::SCEVLoopAddRecRewriter::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:892
llvm::SCEVRewriteVisitor::visitZeroExtendExpr
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:747
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:363
llvm::SCEVSMinExpr
This class represents a signed minimum selection.
Definition: ScalarEvolutionExpressions.h:492
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::SCEVRewriteVisitor::visitSMinExpr
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:820
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:11578
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:11506
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:522
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:256
llvm::SCEVVisitor::visit
RetVal visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:569
llvm::SCEVRewriteVisitor::visitSignExtendExpr
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:754
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:474
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:1566
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:262
llvm::scMulExpr
@ scMulExpr
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVRewriteVisitor::SE
ScalarEvolution & SE
Definition: ScalarEvolutionExpressions.h:708
SmallVector.h
llvm::SCEVNAryExpr::hasNoSignedWrap
bool hasNoSignedWrap() const
Definition: ScalarEvolutionExpressions.h:223
llvm::SCEVRewriteVisitor::visitConstant
const SCEV * visitConstant(const SCEVConstant *Constant)
Definition: ScalarEvolutionExpressions.h:729
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:279
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:379
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:2313
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:880
Value.h
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3669
llvm::SCEVAddExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:282
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:369
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:1026
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:38