LLVM  15.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/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/ValueHandle.h"
23 #include "llvm/Support/Casting.h"
25 #include <cassert>
26 #include <cstddef>
27 
28 namespace llvm {
29 
30 class APInt;
31 class Constant;
32 class ConstantInt;
33 class ConstantRange;
34 class Loop;
35 class Type;
36 class Value;
37 
38 enum SCEVTypes : unsigned short {
39  // These should be ordered in terms of increasing complexity to make the
40  // folders simpler.
57 };
58 
59 /// This class represents a constant integer value.
60 class SCEVConstant : public SCEV {
61  friend class ScalarEvolution;
62 
63  ConstantInt *V;
64 
66  : SCEV(ID, scConstant, 1), V(v) {}
67 
68 public:
69  ConstantInt *getValue() const { return V; }
70  const APInt &getAPInt() const { return getValue()->getValue(); }
71 
72  Type *getType() const { return V->getType(); }
73 
74  /// Methods for support type inquiry through isa, cast, and dyn_cast:
75  static bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; }
76 };
77 
79  APInt Size(16, 1);
80  for (auto *Arg : Args)
81  Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
82  return (unsigned short)Size.getZExtValue();
83 }
84 
85 /// This is the base class for unary cast operator classes.
86 class SCEVCastExpr : public SCEV {
87 protected:
88  std::array<const SCEV *, 1> Operands;
89  Type *Ty;
90 
91  SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op,
92  Type *ty);
93 
94 public:
95  const SCEV *getOperand() const { return Operands[0]; }
96  const SCEV *getOperand(unsigned i) const {
97  assert(i == 0 && "Operand index out of range!");
98  return Operands[0];
99  }
100  using op_iterator = std::array<const SCEV *, 1>::const_iterator;
102 
103  op_range operands() const {
104  return make_range(Operands.begin(), Operands.end());
105  }
106  size_t getNumOperands() const { return 1; }
107  Type *getType() const { return Ty; }
108 
109  /// Methods for support type inquiry through isa, cast, and dyn_cast:
110  static bool classof(const SCEV *S) {
111  return S->getSCEVType() == scPtrToInt || S->getSCEVType() == scTruncate ||
112  S->getSCEVType() == scZeroExtend || S->getSCEVType() == scSignExtend;
113  }
114 };
115 
116 /// This class represents a cast from a pointer to a pointer-sized integer
117 /// value.
119  friend class ScalarEvolution;
120 
121  SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, Type *ITy);
122 
123 public:
124  /// Methods for support type inquiry through isa, cast, and dyn_cast:
125  static bool classof(const SCEV *S) { return S->getSCEVType() == scPtrToInt; }
126 };
127 
128 /// This is the base class for unary integral cast operator classes.
130 protected:
132  const SCEV *op, Type *ty);
133 
134 public:
135  /// Methods for support type inquiry through isa, cast, and dyn_cast:
136  static bool classof(const SCEV *S) {
137  return S->getSCEVType() == scTruncate || S->getSCEVType() == scZeroExtend ||
138  S->getSCEVType() == scSignExtend;
139  }
140 };
141 
142 /// This class represents a truncation of an integer value to a
143 /// smaller integer value.
145  friend class ScalarEvolution;
146 
147  SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, Type *ty);
148 
149 public:
150  /// Methods for support type inquiry through isa, cast, and dyn_cast:
151  static bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate; }
152 };
153 
154 /// This class represents a zero extension of a small integer value
155 /// to a larger integer value.
157  friend class ScalarEvolution;
158 
159  SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, Type *ty);
160 
161 public:
162  /// Methods for support type inquiry through isa, cast, and dyn_cast:
163  static bool classof(const SCEV *S) {
164  return S->getSCEVType() == scZeroExtend;
165  }
166 };
167 
168 /// This class represents a sign extension of a small integer value
169 /// to a larger integer value.
171  friend class ScalarEvolution;
172 
173  SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, Type *ty);
174 
175 public:
176  /// Methods for support type inquiry through isa, cast, and dyn_cast:
177  static bool classof(const SCEV *S) {
178  return S->getSCEVType() == scSignExtend;
179  }
180 };
181 
182 /// This node is a base class providing common functionality for
183 /// n'ary operators.
184 class SCEVNAryExpr : public SCEV {
185 protected:
186  // Since SCEVs are immutable, ScalarEvolution allocates operand
187  // arrays with its SCEVAllocator, so this class just needs a simple
188  // pointer rather than a more elaborate vector-like data structure.
189  // This also avoids the need for a non-trivial destructor.
190  const SCEV *const *Operands;
191  size_t NumOperands;
192 
194  const SCEV *const *O, size_t N)
196  NumOperands(N) {}
197 
198 public:
199  size_t getNumOperands() const { return NumOperands; }
200 
201  const SCEV *getOperand(unsigned i) const {
202  assert(i < NumOperands && "Operand index out of range!");
203  return Operands[i];
204  }
205 
206  using op_iterator = const SCEV *const *;
208 
209  op_iterator op_begin() const { return Operands; }
210  op_iterator op_end() const { return Operands + NumOperands; }
211  op_range operands() const { return make_range(op_begin(), op_end()); }
212 
214  return (NoWrapFlags)(SubclassData & Mask);
215  }
216 
217  bool hasNoUnsignedWrap() const {
219  }
220 
221  bool hasNoSignedWrap() const {
223  }
224 
225  bool hasNoSelfWrap() const { return getNoWrapFlags(FlagNW) != FlagAnyWrap; }
226 
227  /// Methods for support type inquiry through isa, cast, and dyn_cast:
228  static bool classof(const SCEV *S) {
229  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
230  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
231  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
232  S->getSCEVType() == scSequentialUMinExpr ||
233  S->getSCEVType() == scAddRecExpr;
234  }
235 };
236 
237 /// This node is the base class for n'ary commutative operators.
239 protected:
241  const SCEV *const *O, size_t N)
242  : SCEVNAryExpr(ID, T, O, N) {}
243 
244 public:
245  /// Methods for support type inquiry through isa, cast, and dyn_cast:
246  static bool classof(const SCEV *S) {
247  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
248  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
249  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
250  }
251 
252  /// Set flags for a non-recurrence without clearing previously set flags.
253  void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
254 };
255 
256 /// This node represents an addition of some number of SCEVs.
258  friend class ScalarEvolution;
259 
260  Type *Ty;
261 
262  SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
264  auto *FirstPointerTypedOp = find_if(operands(), [](const SCEV *Op) {
265  return Op->getType()->isPointerTy();
266  });
267  if (FirstPointerTypedOp != operands().end())
268  Ty = (*FirstPointerTypedOp)->getType();
269  else
270  Ty = getOperand(0)->getType();
271  }
272 
273 public:
274  Type *getType() const { return Ty; }
275 
276  /// Methods for support type inquiry through isa, cast, and dyn_cast:
277  static bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr; }
278 };
279 
280 /// This node represents multiplication of some number of SCEVs.
282  friend class ScalarEvolution;
283 
284  SCEVMulExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
286 
287 public:
288  Type *getType() const { return getOperand(0)->getType(); }
289 
290  /// Methods for support type inquiry through isa, cast, and dyn_cast:
291  static bool classof(const SCEV *S) { return S->getSCEVType() == scMulExpr; }
292 };
293 
294 /// This class represents a binary unsigned division operation.
295 class SCEVUDivExpr : public SCEV {
296  friend class ScalarEvolution;
297 
298  std::array<const SCEV *, 2> Operands;
299 
300  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
301  : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})) {
302  Operands[0] = lhs;
303  Operands[1] = rhs;
304  }
305 
306 public:
307  const SCEV *getLHS() const { return Operands[0]; }
308  const SCEV *getRHS() const { return Operands[1]; }
309  size_t getNumOperands() const { return 2; }
310  const SCEV *getOperand(unsigned i) const {
311  assert((i == 0 || i == 1) && "Operand index out of range!");
312  return i == 0 ? getLHS() : getRHS();
313  }
314 
315  using op_iterator = std::array<const SCEV *, 2>::const_iterator;
317  op_range operands() const {
318  return make_range(Operands.begin(), Operands.end());
319  }
320 
321  Type *getType() const {
322  // In most cases the types of LHS and RHS will be the same, but in some
323  // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
324  // depend on the type for correctness, but handling types carefully can
325  // avoid extra casts in the SCEVExpander. The LHS is more likely to be
326  // a pointer type than the RHS, so use the RHS' type here.
327  return getRHS()->getType();
328  }
329 
330  /// Methods for support type inquiry through isa, cast, and dyn_cast:
331  static bool classof(const SCEV *S) { return S->getSCEVType() == scUDivExpr; }
332 };
333 
334 /// This node represents a polynomial recurrence on the trip count
335 /// of the specified loop. This is the primary focus of the
336 /// ScalarEvolution framework; all the other SCEV subclasses are
337 /// mostly just supporting infrastructure to allow SCEVAddRecExpr
338 /// expressions to be created and analyzed.
339 ///
340 /// All operands of an AddRec are required to be loop invariant.
341 ///
342 class SCEVAddRecExpr : public SCEVNAryExpr {
343  friend class ScalarEvolution;
344 
345  const Loop *L;
346 
347  SCEVAddRecExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N,
348  const Loop *l)
349  : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
350 
351 public:
352  Type *getType() const { return getStart()->getType(); }
353  const SCEV *getStart() const { return Operands[0]; }
354  const Loop *getLoop() const { return L; }
355 
356  /// Constructs and returns the recurrence indicating how much this
357  /// expression steps by. If this is a polynomial of degree N, it
358  /// returns a chrec of degree N-1. We cannot determine whether
359  /// the step recurrence has self-wraparound.
361  if (isAffine())
362  return getOperand(1);
363  return SE.getAddRecExpr(
365  FlagAnyWrap);
366  }
367 
368  /// Return true if this represents an expression A + B*x where A
369  /// and B are loop invariant values.
370  bool isAffine() const {
371  // We know that the start value is invariant. This expression is thus
372  // affine iff the step is also invariant.
373  return getNumOperands() == 2;
374  }
375 
376  /// Return true if this represents an expression A + B*x + C*x^2
377  /// where A, B and C are loop invariant values. This corresponds
378  /// to an addrec of the form {L,+,M,+,N}
379  bool isQuadratic() const { return getNumOperands() == 3; }
380 
381  /// Set flags for a recurrence without clearing any previously set flags.
382  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
383  /// to make it easier to propagate flags.
385  if (Flags & (FlagNUW | FlagNSW))
386  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
387  SubclassData |= Flags;
388  }
389 
390  /// Return the value of this chain of recurrences at the specified
391  /// iteration number.
392  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
393 
394  /// Return the value of this chain of recurrences at the specified iteration
395  /// number. Takes an explicit list of operands to represent an AddRec.
397  const SCEV *It, ScalarEvolution &SE);
398 
399  /// Return the number of iterations of this loop that produce
400  /// values in the specified constant range. Another way of
401  /// looking at this is that it returns the first iteration number
402  /// where the value is not in the condition, thus computing the
403  /// exit count. If the iteration count can't be computed, an
404  /// instance of SCEVCouldNotCompute is returned.
405  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
406  ScalarEvolution &SE) const;
407 
408  /// Return an expression representing the value of this expression
409  /// one iteration of the loop ahead.
411 
412  /// Methods for support type inquiry through isa, cast, and dyn_cast:
413  static bool classof(const SCEV *S) {
414  return S->getSCEVType() == scAddRecExpr;
415  }
416 };
417 
418 /// This node is the base class min/max selections.
420  friend class ScalarEvolution;
421 
422  static bool isMinMaxType(enum SCEVTypes T) {
423  return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
424  T == scUMinExpr;
425  }
426 
427 protected:
428  /// Note: Constructing subclasses via this constructor is allowed
430  const SCEV *const *O, size_t N)
431  : SCEVCommutativeExpr(ID, T, O, N) {
432  assert(isMinMaxType(T));
433  // Min and max never overflow
435  }
436 
437 public:
438  Type *getType() const { return getOperand(0)->getType(); }
439 
440  static bool classof(const SCEV *S) { return isMinMaxType(S->getSCEVType()); }
441 
442  static enum SCEVTypes negate(enum SCEVTypes T) {
443  switch (T) {
444  case scSMaxExpr:
445  return scSMinExpr;
446  case scSMinExpr:
447  return scSMaxExpr;
448  case scUMaxExpr:
449  return scUMinExpr;
450  case scUMinExpr:
451  return scUMaxExpr;
452  default:
453  llvm_unreachable("Not a min or max SCEV type!");
454  }
455  }
456 };
457 
458 /// This class represents a signed maximum selection.
459 class SCEVSMaxExpr : public SCEVMinMaxExpr {
460  friend class ScalarEvolution;
461 
462  SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
463  : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
464 
465 public:
466  /// Methods for support type inquiry through isa, cast, and dyn_cast:
467  static bool classof(const SCEV *S) { return S->getSCEVType() == scSMaxExpr; }
468 };
469 
470 /// This class represents an unsigned maximum selection.
471 class SCEVUMaxExpr : public SCEVMinMaxExpr {
472  friend class ScalarEvolution;
473 
474  SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
475  : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
476 
477 public:
478  /// Methods for support type inquiry through isa, cast, and dyn_cast:
479  static bool classof(const SCEV *S) { return S->getSCEVType() == scUMaxExpr; }
480 };
481 
482 /// This class represents a signed minimum selection.
483 class SCEVSMinExpr : public SCEVMinMaxExpr {
484  friend class ScalarEvolution;
485 
486  SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
487  : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
488 
489 public:
490  /// Methods for support type inquiry through isa, cast, and dyn_cast:
491  static bool classof(const SCEV *S) { return S->getSCEVType() == scSMinExpr; }
492 };
493 
494 /// This class represents an unsigned minimum selection.
495 class SCEVUMinExpr : public SCEVMinMaxExpr {
496  friend class ScalarEvolution;
497 
498  SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
499  : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
500 
501 public:
502  /// Methods for support type inquiry through isa, cast, and dyn_cast:
503  static bool classof(const SCEV *S) { return S->getSCEVType() == scUMinExpr; }
504 };
505 
506 /// This node is the base class for sequential/in-order min/max selections.
507 /// Note that their fundamental difference from SCEVMinMaxExpr's is that they
508 /// are early-returning upon reaching saturation point.
509 /// I.e. given `0 umin_seq poison`, the result will be `0`,
510 /// while the result of `0 umin poison` is `poison`.
512  friend class ScalarEvolution;
513 
514  static bool isSequentialMinMaxType(enum SCEVTypes T) {
515  return T == scSequentialUMinExpr;
516  }
517 
518  /// Set flags for a non-recurrence without clearing previously set flags.
519  void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
520 
521 protected:
522  /// Note: Constructing subclasses via this constructor is allowed
524  const SCEV *const *O, size_t N)
525  : SCEVNAryExpr(ID, T, O, N) {
526  assert(isSequentialMinMaxType(T));
527  // Min and max never overflow
528  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
529  }
530 
531 public:
532  Type *getType() const { return getOperand(0)->getType(); }
533 
535  assert(isSequentialMinMaxType(Ty));
536  switch (Ty) {
538  return scUMinExpr;
539  default:
540  llvm_unreachable("Not a sequential min/max type.");
541  }
542  }
543 
546  }
547 
548  static bool classof(const SCEV *S) {
549  return isSequentialMinMaxType(S->getSCEVType());
550  }
551 };
552 
553 /// This class represents a sequential/in-order unsigned minimum selection.
555  friend class ScalarEvolution;
556 
557  SCEVSequentialUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O,
558  size_t N)
560 
561 public:
562  /// Methods for support type inquiry through isa, cast, and dyn_cast:
563  static bool classof(const SCEV *S) {
564  return S->getSCEVType() == scSequentialUMinExpr;
565  }
566 };
567 
568 /// This means that we are dealing with an entirely unknown SCEV
569 /// value, and only represent it as its LLVM Value. This is the
570 /// "bottom" value for the analysis.
571 class SCEVUnknown final : public SCEV, private CallbackVH {
572  friend class ScalarEvolution;
573 
574  /// The parent ScalarEvolution value. This is used to update the
575  /// parent's maps when the value associated with a SCEVUnknown is
576  /// deleted or RAUW'd.
577  ScalarEvolution *SE;
578 
579  /// The next pointer in the linked list of all SCEVUnknown
580  /// instances owned by a ScalarEvolution.
581  SCEVUnknown *Next;
582 
584  SCEVUnknown *next)
585  : SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
586 
587  // Implement CallbackVH.
588  void deleted() override;
589  void allUsesReplacedWith(Value *New) override;
590 
591 public:
592  Value *getValue() const { return getValPtr(); }
593 
594  /// @{
595  /// Test whether this is a special constant representing a type
596  /// size, alignment, or field offset in a target-independent
597  /// manner, and hasn't happened to have been folded with other
598  /// operations into something unrecognizable. This is mainly only
599  /// useful for pretty-printing and other situations where it isn't
600  /// absolutely required for these to succeed.
601  bool isSizeOf(Type *&AllocTy) const;
602  bool isAlignOf(Type *&AllocTy) const;
603  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
604  /// @}
605 
606  Type *getType() const { return getValPtr()->getType(); }
607 
608  /// Methods for support type inquiry through isa, cast, and dyn_cast:
609  static bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; }
610 };
611 
612 /// This class defines a simple visitor class that may be used for
613 /// various SCEV analysis purposes.
614 template <typename SC, typename RetVal = void> struct SCEVVisitor {
615  RetVal visit(const SCEV *S) {
616  switch (S->getSCEVType()) {
617  case scConstant:
618  return ((SC *)this)->visitConstant((const SCEVConstant *)S);
619  case scPtrToInt:
620  return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
621  case scTruncate:
622  return ((SC *)this)->visitTruncateExpr((const SCEVTruncateExpr *)S);
623  case scZeroExtend:
624  return ((SC *)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr *)S);
625  case scSignExtend:
626  return ((SC *)this)->visitSignExtendExpr((const SCEVSignExtendExpr *)S);
627  case scAddExpr:
628  return ((SC *)this)->visitAddExpr((const SCEVAddExpr *)S);
629  case scMulExpr:
630  return ((SC *)this)->visitMulExpr((const SCEVMulExpr *)S);
631  case scUDivExpr:
632  return ((SC *)this)->visitUDivExpr((const SCEVUDivExpr *)S);
633  case scAddRecExpr:
634  return ((SC *)this)->visitAddRecExpr((const SCEVAddRecExpr *)S);
635  case scSMaxExpr:
636  return ((SC *)this)->visitSMaxExpr((const SCEVSMaxExpr *)S);
637  case scUMaxExpr:
638  return ((SC *)this)->visitUMaxExpr((const SCEVUMaxExpr *)S);
639  case scSMinExpr:
640  return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
641  case scUMinExpr:
642  return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
644  return ((SC *)this)
645  ->visitSequentialUMinExpr((const SCEVSequentialUMinExpr *)S);
646  case scUnknown:
647  return ((SC *)this)->visitUnknown((const SCEVUnknown *)S);
648  case scCouldNotCompute:
649  return ((SC *)this)->visitCouldNotCompute((const SCEVCouldNotCompute *)S);
650  }
651  llvm_unreachable("Unknown SCEV kind!");
652  }
653 
655  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
656  }
657 };
658 
659 /// Visit all nodes in the expression tree using worklist traversal.
660 ///
661 /// Visitor implements:
662 /// // return true to follow this node.
663 /// bool follow(const SCEV *S);
664 /// // return true to terminate the search.
665 /// bool isDone();
666 template <typename SV> class SCEVTraversal {
667  SV &Visitor;
670 
671  void push(const SCEV *S) {
672  if (Visited.insert(S).second && Visitor.follow(S))
673  Worklist.push_back(S);
674  }
675 
676 public:
677  SCEVTraversal(SV &V) : Visitor(V) {}
678 
679  void visitAll(const SCEV *Root) {
680  push(Root);
681  while (!Worklist.empty() && !Visitor.isDone()) {
682  const SCEV *S = Worklist.pop_back_val();
683 
684  switch (S->getSCEVType()) {
685  case scConstant:
686  case scUnknown:
687  continue;
688  case scPtrToInt:
689  case scTruncate:
690  case scZeroExtend:
691  case scSignExtend:
692  push(cast<SCEVCastExpr>(S)->getOperand());
693  continue;
694  case scAddExpr:
695  case scMulExpr:
696  case scSMaxExpr:
697  case scUMaxExpr:
698  case scSMinExpr:
699  case scUMinExpr:
701  case scAddRecExpr:
702  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands()) {
703  push(Op);
704  if (Visitor.isDone())
705  break;
706  }
707  continue;
708  case scUDivExpr: {
709  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
710  push(UDiv->getLHS());
711  push(UDiv->getRHS());
712  continue;
713  }
714  case scCouldNotCompute:
715  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
716  }
717  llvm_unreachable("Unknown SCEV kind!");
718  }
719  }
720 };
721 
722 /// Use SCEVTraversal to visit all nodes in the given expression tree.
723 template <typename SV> void visitAll(const SCEV *Root, SV &Visitor) {
724  SCEVTraversal<SV> T(Visitor);
725  T.visitAll(Root);
726 }
727 
728 /// Return true if any node in \p Root satisfies the predicate \p Pred.
729 template <typename PredTy>
730 bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
731  struct FindClosure {
732  bool Found = false;
733  PredTy Pred;
734 
735  FindClosure(PredTy Pred) : Pred(Pred) {}
736 
737  bool follow(const SCEV *S) {
738  if (!Pred(S))
739  return true;
740 
741  Found = true;
742  return false;
743  }
744 
745  bool isDone() const { return Found; }
746  };
747 
748  FindClosure FC(Pred);
749  visitAll(Root, FC);
750  return FC.Found;
751 }
752 
753 /// This visitor recursively visits a SCEV expression and re-writes it.
754 /// The result from each visit is cached, so it will return the same
755 /// SCEV for the same input.
756 template <typename SC>
757 class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
758 protected:
760  // Memoize the result of each visit so that we only compute once for
761  // the same input SCEV. This is to avoid redundant computations when
762  // a SCEV is referenced by multiple SCEVs. Without memoization, this
763  // visit algorithm would have exponential time complexity in the worst
764  // case, causing the compiler to hang on certain tests.
766 
767 public:
769 
770  const SCEV *visit(const SCEV *S) {
771  auto It = RewriteResults.find(S);
772  if (It != RewriteResults.end())
773  return It->second;
774  auto *Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
775  auto Result = RewriteResults.try_emplace(S, Visited);
776  assert(Result.second && "Should insert a new entry");
777  return Result.first->second;
778  }
779 
780  const SCEV *visitConstant(const SCEVConstant *Constant) { return Constant; }
781 
783  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
784  return Operand == Expr->getOperand()
785  ? Expr
786  : SE.getPtrToIntExpr(Operand, Expr->getType());
787  }
788 
790  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
791  return Operand == Expr->getOperand()
792  ? Expr
793  : SE.getTruncateExpr(Operand, Expr->getType());
794  }
795 
797  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
798  return Operand == Expr->getOperand()
799  ? Expr
800  : SE.getZeroExtendExpr(Operand, Expr->getType());
801  }
802 
804  const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
805  return Operand == Expr->getOperand()
806  ? Expr
807  : SE.getSignExtendExpr(Operand, Expr->getType());
808  }
809 
810  const SCEV *visitAddExpr(const SCEVAddExpr *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.getAddExpr(Operands);
818  }
819 
820  const SCEV *visitMulExpr(const SCEVMulExpr *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.getMulExpr(Operands);
828  }
829 
830  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
831  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
832  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
833  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
834  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
835  }
836 
837  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
839  bool Changed = false;
840  for (auto *Op : Expr->operands()) {
841  Operands.push_back(((SC *)this)->visit(Op));
842  Changed |= Op != Operands.back();
843  }
844  return !Changed ? Expr
845  : SE.getAddRecExpr(Operands, Expr->getLoop(),
846  Expr->getNoWrapFlags());
847  }
848 
849  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
851  bool Changed = false;
852  for (auto *Op : Expr->operands()) {
853  Operands.push_back(((SC *)this)->visit(Op));
854  Changed |= Op != Operands.back();
855  }
856  return !Changed ? Expr : SE.getSMaxExpr(Operands);
857  }
858 
859  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
861  bool Changed = false;
862  for (auto *Op : Expr->operands()) {
863  Operands.push_back(((SC *)this)->visit(Op));
864  Changed |= Op != Operands.back();
865  }
866  return !Changed ? Expr : SE.getUMaxExpr(Operands);
867  }
868 
869  const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
871  bool Changed = false;
872  for (auto *Op : Expr->operands()) {
873  Operands.push_back(((SC *)this)->visit(Op));
874  Changed |= Op != Operands.back();
875  }
876  return !Changed ? Expr : SE.getSMinExpr(Operands);
877  }
878 
879  const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
881  bool Changed = false;
882  for (auto *Op : Expr->operands()) {
883  Operands.push_back(((SC *)this)->visit(Op));
884  Changed |= Op != Operands.back();
885  }
886  return !Changed ? Expr : SE.getUMinExpr(Operands);
887  }
888 
891  bool Changed = false;
892  for (auto *Op : Expr->operands()) {
893  Operands.push_back(((SC *)this)->visit(Op));
894  Changed |= Op != Operands.back();
895  }
896  return !Changed ? Expr : SE.getUMinExpr(Operands, /*Sequential=*/true);
897  }
898 
899  const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
900 
902  return Expr;
903  }
904 };
905 
908 
909 /// The SCEVParameterRewriter takes a scalar evolution expression and updates
910 /// the SCEVUnknown components following the Map (Value -> SCEV).
911 class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
912 public:
913  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
914  ValueToSCEVMapTy &Map) {
916  return Rewriter.visit(Scev);
917  }
918 
920  : SCEVRewriteVisitor(SE), Map(M) {}
921 
922  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
923  auto I = Map.find(Expr->getValue());
924  if (I == Map.end())
925  return Expr;
926  return I->second;
927  }
928 
929 private:
930  ValueToSCEVMapTy &Map;
931 };
932 
934 
935 /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
936 /// the Map (Loop -> SCEV) to all AddRecExprs.
938  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
939 public:
941  : SCEVRewriteVisitor(SE), Map(M) {}
942 
943  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
944  ScalarEvolution &SE) {
946  return Rewriter.visit(Scev);
947  }
948 
949  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
951  for (const SCEV *Op : Expr->operands())
952  Operands.push_back(visit(Op));
953 
954  const Loop *L = Expr->getLoop();
955  if (0 == Map.count(L))
956  return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
957 
959  }
960 
961 private:
962  LoopToScevMapT &Map;
963 };
964 
965 } // end namespace llvm
966 
967 #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:76
i
i
Definition: README.txt:29
llvm::SCEVTraversal::visitAll
void visitAll(const SCEV *Root)
Definition: ScalarEvolutionExpressions.h:679
llvm::SCEVUDivExpr
This class represents a binary unsigned division operation.
Definition: ScalarEvolutionExpressions.h:295
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SCEVUMinExpr
This class represents an unsigned minimum selection.
Definition: ScalarEvolutionExpressions.h:495
llvm::SCEVRewriteVisitor::visitMulExpr
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
Definition: ScalarEvolutionExpressions.h:820
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:52
llvm::SCEVAddRecExpr::setNoWrapFlags
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
Definition: ScalarEvolutionExpressions.h:384
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:228
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:370
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:353
llvm::computeExpressionSize
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
Definition: ScalarEvolutionExpressions.h:78
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:459
llvm::SCEVRewriteVisitor::visitSMaxExpr
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:849
llvm::scConstant
@ scConstant
Definition: ScalarEvolutionExpressions.h:41
llvm::SCEVParameterRewriter::rewrite
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
Definition: ScalarEvolutionExpressions.h:913
llvm::SCEVRewriteVisitor::visitCouldNotCompute
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
Definition: ScalarEvolutionExpressions.h:901
llvm::SCEVUnknown::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:609
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:1185
llvm::SCEVUDivExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:321
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:118
llvm::scCouldNotCompute
@ scCouldNotCompute
Definition: ScalarEvolutionExpressions.h:56
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:3576
ErrorHandling.h
llvm::SCEVCommutativeExpr::SCEVCommutativeExpr
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Definition: ScalarEvolutionExpressions.h:240
llvm::SCEVNAryExpr::Operands
const SCEV *const * Operands
Definition: ScalarEvolutionExpressions.h:190
llvm::SCEVCastExpr::getOperand
const SCEV * getOperand() const
Definition: ScalarEvolutionExpressions.h:95
llvm::SCEVUnknown::isAlignOf
bool isAlignOf(Type *&AllocTy) const
Definition: ScalarEvolution.cpp:560
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::SCEV::NoWrapMask
@ NoWrapMask
Definition: ScalarEvolution.h:135
llvm::SCEVTypes
SCEVTypes
Definition: ScalarEvolutionExpressions.h:38
llvm::ScalarEvolution::getTruncateExpr
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1204
llvm::SCEVMulExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:288
llvm::SCEV::FlagNW
@ FlagNW
Definition: ScalarEvolution.h:132
llvm::SCEVUnknown::isOffsetOf
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
Definition: ScalarEvolution.cpp:584
ScalarEvolution.h
llvm::SCEVRewriteVisitor::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:899
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:467
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::scSMaxExpr
@ scSMaxExpr
Definition: ScalarEvolutionExpressions.h:50
llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType
SCEVTypes getEquivalentNonSequentialSCEVType() const
Definition: ScalarEvolutionExpressions.h:544
llvm::ScalarEvolution::setFlags
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Definition: ScalarEvolution.h:473
llvm::ValueHandleBase::getValPtr
Value * getValPtr() const
Definition: ValueHandle.h:99
llvm::SCEVRewriteVisitor::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:837
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:147
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:450
llvm::SCEVSequentialMinMaxExpr
This node is the base class for sequential/in-order min/max selections.
Definition: ScalarEvolutionExpressions.h:511
llvm::SCEV::getSCEVType
SCEVTypes getSCEVType() const
Definition: ScalarEvolution.h:144
llvm::SCEVSignExtendExpr
This class represents a sign extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:170
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::scUnknown
@ scUnknown
Definition: ScalarEvolutionExpressions.h:55
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::SCEVConstant::getValue
ConstantInt * getValue() const
Definition: ScalarEvolutionExpressions.h:69
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:429
llvm::SCEVNAryExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:211
llvm::SCEVConstant::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:75
llvm::SCEVZeroExtendExpr
This class represents a zero extension of a small integer value to a larger integer value.
Definition: ScalarEvolutionExpressions.h:156
llvm::SCEVRewriteVisitor::visitPtrToIntExpr
const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)
Definition: ScalarEvolutionExpressions.h:782
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:3051
llvm::SCEVTraversal
Visit all nodes in the expression tree using worklist traversal.
Definition: ScalarEvolutionExpressions.h:666
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::BitmaskEnumDetail::Mask
constexpr 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
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:765
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:614
llvm::SCEVUnknown::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:606
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:723
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:418
llvm::SCEVCommutativeExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:246
llvm::SCEVNAryExpr::SCEVNAryExpr
SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Definition: ScalarEvolutionExpressions.h:193
Constants.h
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::SCEVCastExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:96
llvm::SCEVCastExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:103
llvm::SCEVConstant::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:72
llvm::ScalarEvolution::getUMaxExpr
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4192
llvm::scAddRecExpr
@ scAddRecExpr
Definition: ScalarEvolutionExpressions.h:48
llvm::SCEVUMaxExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:479
llvm::SCEVTruncateExpr
This class represents a truncation of an integer value to a smaller integer value.
Definition: ScalarEvolutionExpressions.h:144
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:3346
llvm::SCEVParameterRewriter::visitUnknown
const SCEV * visitUnknown(const SCEVUnknown *Expr)
Definition: ScalarEvolutionExpressions.h:922
llvm::scUMaxExpr
@ scUMaxExpr
Definition: ScalarEvolutionExpressions.h:49
llvm::SCEVRewriteVisitor::visitUDivExpr
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
Definition: ScalarEvolutionExpressions.h:830
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:291
llvm::SCEVParameterRewriter::SCEVParameterRewriter
SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)
Definition: ScalarEvolutionExpressions.h:919
llvm::SCEVIntegralCastExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:136
llvm::SCEVMulExpr
This node represents multiplication of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:281
llvm::SCEVVisitor::visitCouldNotCompute
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)
Definition: ScalarEvolutionExpressions.h:654
llvm::SCEVUMaxExpr
This class represents an unsigned maximum selection.
Definition: ScalarEvolutionExpressions.h:471
llvm::SCEVCastExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:110
llvm::SCEVExprContains
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Definition: ScalarEvolutionExpressions.h:730
llvm::SCEVMinMaxExpr::classof
static bool classof(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:440
SmallPtrSet.h
llvm::SCEVNAryExpr
This node is a base class providing common functionality for n'ary operators.
Definition: ScalarEvolutionExpressions.h:184
llvm::SCEVUnknown::getValue
Value * getValue() const
Definition: ScalarEvolutionExpressions.h:592
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::SCEVRewriteVisitor::visitAddExpr
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
Definition: ScalarEvolutionExpressions.h:810
llvm::SCEVRewriteVisitor::SCEVRewriteVisitor
SCEVRewriteVisitor(ScalarEvolution &SE)
Definition: ScalarEvolutionExpressions.h:768
llvm::SCEVCommutativeExpr
This node is the base class for n'ary commutative operators.
Definition: ScalarEvolutionExpressions.h:238
llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
Definition: ScalarEvolutionExpressions.h:534
llvm::SCEVAddRecExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:413
llvm::SCEVLoopAddRecRewriter::SCEVLoopAddRecRewriter
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
Definition: ScalarEvolutionExpressions.h:940
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
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:91
llvm::SCEVUDivExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:310
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
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:331
llvm::ScalarEvolution::getSMaxExpr
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4183
llvm::scZeroExtend
@ scZeroExtend
Definition: ScalarEvolutionExpressions.h:43
llvm::SCEVNAryExpr::op_end
op_iterator op_end() const
Definition: ScalarEvolutionExpressions.h:210
llvm::SCEVLoopAddRecRewriter::rewrite
static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
Definition: ScalarEvolutionExpressions.h:943
llvm::scAddExpr
@ scAddExpr
Definition: ScalarEvolutionExpressions.h:45
llvm::DenseMap
Definition: DenseMap.h:716
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:134
llvm::SCEVUDivExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:317
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:131
llvm::ScalarEvolution::getPtrToIntExpr
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:1194
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:491
llvm::SCEVCastExpr::SCEVCastExpr
SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
Definition: ScalarEvolution.cpp:483
llvm::SCEVUDivExpr::op_iterator
std::array< const SCEV *, 2 >::const_iterator op_iterator
Definition: ScalarEvolutionExpressions.h:315
llvm::SCEVUDivExpr::getLHS
const SCEV * getLHS() const
Definition: ScalarEvolutionExpressions.h:307
llvm::SCEVRewriteVisitor
This visitor recursively visits a SCEV expression and re-writes it.
Definition: ScalarEvolutionExpressions.h:757
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:60
TemplateParamKind::Type
@ Type
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::scUDivExpr
@ scUDivExpr
Definition: ScalarEvolutionExpressions.h:47
llvm::SCEVPtrToIntExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:125
llvm::SCEVMinMaxExpr::negate
static enum SCEVTypes negate(enum SCEVTypes T)
Definition: ScalarEvolutionExpressions.h:442
llvm::SCEVTraversal::SCEVTraversal
SCEVTraversal(SV &V)
Definition: ScalarEvolutionExpressions.h:677
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:379
iterator_range.h
llvm::SCEVCouldNotCompute
An object of this class is returned by queries that could not be answered.
Definition: ScalarEvolution.h:206
llvm::scSignExtend
@ scSignExtend
Definition: ScalarEvolutionExpressions.h:44
llvm::SCEVRewriteVisitor::visitUMaxExpr
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
Definition: ScalarEvolutionExpressions.h:859
llvm::SCEVRewriteVisitor::visit
const SCEV * visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:770
llvm::SCEVUMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:503
llvm::SCEVCastExpr::op_iterator
std::array< const SCEV *, 1 >::const_iterator op_iterator
Definition: ScalarEvolutionExpressions.h:100
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::SCEVRewriteVisitor::visitUMinExpr
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:879
llvm::SCEVCastExpr::Operands
std::array< const SCEV *, 1 > Operands
Definition: ScalarEvolutionExpressions.h:88
llvm::SCEVParameterRewriter
The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...
Definition: ScalarEvolutionExpressions.h:911
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:1897
llvm::SCEVNAryExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:199
llvm::scTruncate
@ scTruncate
Definition: ScalarEvolutionExpressions.h:42
llvm::SCEVSequentialUMinExpr
This class represents a sequential/in-order unsigned minimum selection.
Definition: ScalarEvolutionExpressions.h:554
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
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:133
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
llvm::ScalarEvolution::getUMinExpr
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Definition: ScalarEvolution.cpp:4211
ValueHandle.h
llvm::SCEVSequentialMinMaxExpr::SCEVSequentialMinMaxExpr
SCEVSequentialMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
Definition: ScalarEvolutionExpressions.h:523
llvm::SCEVRewriteVisitor::visitTruncateExpr
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)
Definition: ScalarEvolutionExpressions.h:789
llvm::SCEVMinMaxExpr
This node is the base class min/max selections.
Definition: ScalarEvolutionExpressions.h:419
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:1632
llvm::scPtrToInt
@ scPtrToInt
Definition: ScalarEvolutionExpressions.h:54
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:130
llvm::SCEVLoopAddRecRewriter::visitAddRecExpr
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Definition: ScalarEvolutionExpressions.h:949
llvm::SCEVSequentialUMinExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:563
llvm::SCEVSequentialMinMaxExpr::classof
static bool classof(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:548
llvm::SCEVMinMaxExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:438
llvm::SCEVRewriteVisitor::visitZeroExtendExpr
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:796
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:354
llvm::SCEVSMinExpr
This class represents a signed minimum selection.
Definition: ScalarEvolutionExpressions.h:483
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::SCEVRewriteVisitor::visitSMinExpr
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:869
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:12796
llvm::SCEVCastExpr
This is the base class for unary cast operator classes.
Definition: ScalarEvolutionExpressions.h:86
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:12724
llvm::SCEVNAryExpr::NumOperands
size_t NumOperands
Definition: ScalarEvolutionExpressions.h:191
llvm::SCEVNAryExpr::op_begin
op_iterator op_begin() const
Definition: ScalarEvolutionExpressions.h:209
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
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:571
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SCEVUDivExpr::getRHS
const SCEV * getRHS() const
Definition: ScalarEvolutionExpressions.h:308
llvm::SCEVIntegralCastExpr::SCEVIntegralCastExpr
SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
Definition: ScalarEvolution.cpp:496
llvm::SCEVTruncateExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:151
llvm::SCEVCommutativeExpr::setNoWrapFlags
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
Definition: ScalarEvolutionExpressions.h:253
llvm::SCEVVisitor::visit
RetVal visit(const SCEV *S)
Definition: ScalarEvolutionExpressions.h:615
llvm::SCEVRewriteVisitor::visitSignExtendExpr
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
Definition: ScalarEvolutionExpressions.h:803
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:70
llvm::FoldingSetNodeIDRef
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:287
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::SCEVRewriteVisitor::visitSequentialUMinExpr
const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr)
Definition: ScalarEvolutionExpressions.h:889
llvm::SCEVNAryExpr::op_iterator
const SCEV *const * op_iterator
Definition: ScalarEvolutionExpressions.h:206
llvm::SCEVIntegralCastExpr
This is the base class for unary integral cast operator classes.
Definition: ScalarEvolutionExpressions.h:129
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1595
llvm::SCEVAddExpr
This node represents an addition of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:257
llvm::scMulExpr
@ scMulExpr
Definition: ScalarEvolutionExpressions.h:46
llvm::SCEVRewriteVisitor::SE
ScalarEvolution & SE
Definition: ScalarEvolutionExpressions.h:759
SmallVector.h
llvm::SCEVNAryExpr::hasNoSignedWrap
bool hasNoSignedWrap() const
Definition: ScalarEvolutionExpressions.h:221
llvm::SCEVRewriteVisitor::visitConstant
const SCEV * visitConstant(const SCEVConstant *Constant)
Definition: ScalarEvolutionExpressions.h:780
N
#define N
llvm::SCEVCastExpr::Ty
Type * Ty
Definition: ScalarEvolutionExpressions.h:89
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:274
llvm::SCEVSignExtendExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:177
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:393
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:2454
llvm::scSequentialUMinExpr
@ scSequentialUMinExpr
Definition: ScalarEvolutionExpressions.h:53
llvm::SCEVCastExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:106
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::scUMinExpr
@ scUMinExpr
Definition: ScalarEvolutionExpressions.h:51
llvm::SCEVNAryExpr::getOperand
const SCEV * getOperand(unsigned i) const
Definition: ScalarEvolutionExpressions.h:201
llvm::SCEVUDivExpr::getNumOperands
size_t getNumOperands() const
Definition: ScalarEvolutionExpressions.h:309
llvm::SCEVLoopAddRecRewriter
The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies the Map (Loop -> SCEV) to ...
Definition: ScalarEvolutionExpressions.h:937
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4201
llvm::SCEVAddExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:277
llvm::SCEVAddRecExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:352
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SCEVUnknown::isSizeOf
bool isSizeOf(Type *&AllocTy) const
Definition: ScalarEvolution.cpp:544
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:360
llvm::SCEVZeroExtendExpr::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolutionExpressions.h:163
llvm::SCEVSequentialMinMaxExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:532
llvm::SCEVCastExpr::getType
Type * getType() const
Definition: ScalarEvolutionExpressions.h:107
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:1043
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:365