LLVM  10.0.0svn
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 {
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  const SCEV *Op;
78  Type *Ty;
79 
81  unsigned SCEVTy, const SCEV *op, Type *ty);
82 
83  public:
84  const SCEV *getOperand() const { return Op; }
85  Type *getType() const { return Ty; }
86 
87  /// Methods for support type inquiry through isa, cast, and dyn_cast:
88  static bool classof(const SCEV *S) {
89  return S->getSCEVType() == scTruncate ||
90  S->getSCEVType() == scZeroExtend ||
91  S->getSCEVType() == scSignExtend;
92  }
93  };
94 
95  /// This class represents a truncation of an integer value to a
96  /// smaller integer value.
97  class SCEVTruncateExpr : public SCEVCastExpr {
98  friend class ScalarEvolution;
99 
101  const SCEV *op, Type *ty);
102 
103  public:
104  /// Methods for support type inquiry through isa, cast, and dyn_cast:
105  static bool classof(const SCEV *S) {
106  return S->getSCEVType() == scTruncate;
107  }
108  };
109 
110  /// This class represents a zero extension of a small integer value
111  /// to a larger integer value.
113  friend class ScalarEvolution;
114 
116  const SCEV *op, Type *ty);
117 
118  public:
119  /// Methods for support type inquiry through isa, cast, and dyn_cast:
120  static bool classof(const SCEV *S) {
121  return S->getSCEVType() == scZeroExtend;
122  }
123  };
124 
125  /// This class represents a sign extension of a small integer value
126  /// to a larger integer value.
128  friend class ScalarEvolution;
129 
131  const SCEV *op, Type *ty);
132 
133  public:
134  /// Methods for support type inquiry through isa, cast, and dyn_cast:
135  static bool classof(const SCEV *S) {
136  return S->getSCEVType() == scSignExtend;
137  }
138  };
139 
140  /// This node is a base class providing common functionality for
141  /// n'ary operators.
142  class SCEVNAryExpr : public SCEV {
143  protected:
144  // Since SCEVs are immutable, ScalarEvolution allocates operand
145  // arrays with its SCEVAllocator, so this class just needs a simple
146  // pointer rather than a more elaborate vector-like data structure.
147  // This also avoids the need for a non-trivial destructor.
148  const SCEV *const *Operands;
149  size_t NumOperands;
150 
152  const SCEV *const *O, size_t N)
153  : SCEV(ID, T, computeExpressionSize(makeArrayRef(O, N))), Operands(O),
154  NumOperands(N) {}
155 
156  public:
157  size_t getNumOperands() const { return NumOperands; }
158 
159  const SCEV *getOperand(unsigned i) const {
160  assert(i < NumOperands && "Operand index out of range!");
161  return Operands[i];
162  }
163 
164  using op_iterator = const SCEV *const *;
166 
167  op_iterator op_begin() const { return Operands; }
168  op_iterator op_end() const { return Operands + NumOperands; }
169  op_range operands() const {
170  return make_range(op_begin(), op_end());
171  }
172 
173  Type *getType() const { return getOperand(0)->getType(); }
174 
176  return (NoWrapFlags)(SubclassData & Mask);
177  }
178 
179  bool hasNoUnsignedWrap() const {
180  return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
181  }
182 
183  bool hasNoSignedWrap() const {
184  return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
185  }
186 
187  bool hasNoSelfWrap() const {
188  return getNoWrapFlags(FlagNW) != FlagAnyWrap;
189  }
190 
191  /// Methods for support type inquiry through isa, cast, and dyn_cast:
192  static bool classof(const SCEV *S) {
193  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
194  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
195  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
196  S->getSCEVType() == scAddRecExpr;
197  }
198  };
199 
200  /// This node is the base class for n'ary commutative operators.
202  protected:
204  enum SCEVTypes T, const SCEV *const *O, size_t N)
205  : SCEVNAryExpr(ID, T, O, N) {}
206 
207  public:
208  /// Methods for support type inquiry through isa, cast, and dyn_cast:
209  static bool classof(const SCEV *S) {
210  return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
211  S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
212  S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
213  }
214 
215  /// Set flags for a non-recurrence without clearing previously set flags.
217  SubclassData |= Flags;
218  }
219  };
220 
221  /// This node represents an addition of some number of SCEVs.
223  friend class ScalarEvolution;
224 
226  const SCEV *const *O, size_t N)
227  : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}
228 
229  public:
230  Type *getType() const {
231  // Use the type of the last operand, which is likely to be a pointer
232  // type, if there is one. This doesn't usually matter, but it can help
233  // reduce casts when the expressions are expanded.
234  return getOperand(getNumOperands() - 1)->getType();
235  }
236 
237  /// Methods for support type inquiry through isa, cast, and dyn_cast:
238  static bool classof(const SCEV *S) {
239  return S->getSCEVType() == scAddExpr;
240  }
241  };
242 
243  /// This node represents multiplication of some number of SCEVs.
245  friend class ScalarEvolution;
246 
248  const SCEV *const *O, size_t N)
249  : SCEVCommutativeExpr(ID, scMulExpr, O, N) {}
250 
251  public:
252  /// Methods for support type inquiry through isa, cast, and dyn_cast:
253  static bool classof(const SCEV *S) {
254  return S->getSCEVType() == scMulExpr;
255  }
256  };
257 
258  /// This class represents a binary unsigned division operation.
259  class SCEVUDivExpr : public SCEV {
260  friend class ScalarEvolution;
261 
262  const SCEV *LHS;
263  const SCEV *RHS;
264 
265  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
266  : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})), LHS(lhs),
267  RHS(rhs) {}
268 
269  public:
270  const SCEV *getLHS() const { return LHS; }
271  const SCEV *getRHS() const { return RHS; }
272 
273  Type *getType() const {
274  // In most cases the types of LHS and RHS will be the same, but in some
275  // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
276  // depend on the type for correctness, but handling types carefully can
277  // avoid extra casts in the SCEVExpander. The LHS is more likely to be
278  // a pointer type than the RHS, so use the RHS' type here.
279  return getRHS()->getType();
280  }
281 
282  /// Methods for support type inquiry through isa, cast, and dyn_cast:
283  static bool classof(const SCEV *S) {
284  return S->getSCEVType() == scUDivExpr;
285  }
286  };
287 
288  /// This node represents a polynomial recurrence on the trip count
289  /// of the specified loop. This is the primary focus of the
290  /// ScalarEvolution framework; all the other SCEV subclasses are
291  /// mostly just supporting infrastructure to allow SCEVAddRecExpr
292  /// expressions to be created and analyzed.
293  ///
294  /// All operands of an AddRec are required to be loop invariant.
295  ///
296  class SCEVAddRecExpr : public SCEVNAryExpr {
297  friend class ScalarEvolution;
298 
299  const Loop *L;
300 
302  const SCEV *const *O, size_t N, const Loop *l)
303  : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
304 
305  public:
306  const SCEV *getStart() const { return Operands[0]; }
307  const Loop *getLoop() const { return L; }
308 
309  /// Constructs and returns the recurrence indicating how much this
310  /// expression steps by. If this is a polynomial of degree N, it
311  /// returns a chrec of degree N-1. We cannot determine whether
312  /// the step recurrence has self-wraparound.
314  if (isAffine()) return getOperand(1);
315  return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
316  op_end()),
317  getLoop(), FlagAnyWrap);
318  }
319 
320  /// Return true if this represents an expression A + B*x where A
321  /// and B are loop invariant values.
322  bool isAffine() const {
323  // We know that the start value is invariant. This expression is thus
324  // affine iff the step is also invariant.
325  return getNumOperands() == 2;
326  }
327 
328  /// Return true if this represents an expression A + B*x + C*x^2
329  /// where A, B and C are loop invariant values. This corresponds
330  /// to an addrec of the form {L,+,M,+,N}
331  bool isQuadratic() const {
332  return getNumOperands() == 3;
333  }
334 
335  /// Set flags for a recurrence without clearing any previously set flags.
336  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
337  /// to make it easier to propagate flags.
339  if (Flags & (FlagNUW | FlagNSW))
340  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
341  SubclassData |= Flags;
342  }
343 
344  /// Return the value of this chain of recurrences at the specified
345  /// iteration number.
346  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
347 
348  /// Return the number of iterations of this loop that produce
349  /// values in the specified constant range. Another way of
350  /// looking at this is that it returns the first iteration number
351  /// where the value is not in the condition, thus computing the
352  /// exit count. If the iteration count can't be computed, an
353  /// instance of SCEVCouldNotCompute is returned.
354  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
355  ScalarEvolution &SE) const;
356 
357  /// Return an expression representing the value of this expression
358  /// one iteration of the loop ahead.
359  const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
360 
361  /// Methods for support type inquiry through isa, cast, and dyn_cast:
362  static bool classof(const SCEV *S) {
363  return S->getSCEVType() == scAddRecExpr;
364  }
365  };
366 
367  /// This node is the base class min/max selections.
369  friend class ScalarEvolution;
370 
371  static bool isMinMaxType(enum SCEVTypes T) {
372  return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
373  T == scUMinExpr;
374  }
375 
376  protected:
377  /// Note: Constructing subclasses via this constructor is allowed
379  const SCEV *const *O, size_t N)
380  : SCEVCommutativeExpr(ID, T, O, N) {
381  assert(isMinMaxType(T));
382  // Min and max never overflow
383  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
384  }
385 
386  public:
387  static bool classof(const SCEV *S) {
388  return isMinMaxType(static_cast<SCEVTypes>(S->getSCEVType()));
389  }
390 
391  static enum SCEVTypes negate(enum SCEVTypes T) {
392  switch (T) {
393  case scSMaxExpr:
394  return scSMinExpr;
395  case scSMinExpr:
396  return scSMaxExpr;
397  case scUMaxExpr:
398  return scUMinExpr;
399  case scUMinExpr:
400  return scUMaxExpr;
401  default:
402  llvm_unreachable("Not a min or max SCEV type!");
403  }
404  }
405  };
406 
407  /// This class represents a signed maximum selection.
408  class SCEVSMaxExpr : public SCEVMinMaxExpr {
409  friend class ScalarEvolution;
410 
411  SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
412  : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
413 
414  public:
415  /// Methods for support type inquiry through isa, cast, and dyn_cast:
416  static bool classof(const SCEV *S) {
417  return S->getSCEVType() == scSMaxExpr;
418  }
419  };
420 
421  /// This class represents an unsigned maximum selection.
422  class SCEVUMaxExpr : public SCEVMinMaxExpr {
423  friend class ScalarEvolution;
424 
425  SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
426  : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
427 
428  public:
429  /// Methods for support type inquiry through isa, cast, and dyn_cast:
430  static bool classof(const SCEV *S) {
431  return S->getSCEVType() == scUMaxExpr;
432  }
433  };
434 
435  /// This class represents a signed minimum selection.
436  class SCEVSMinExpr : public SCEVMinMaxExpr {
437  friend class ScalarEvolution;
438 
439  SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
440  : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
441 
442  public:
443  /// Methods for support type inquiry through isa, cast, and dyn_cast:
444  static bool classof(const SCEV *S) {
445  return S->getSCEVType() == scSMinExpr;
446  }
447  };
448 
449  /// This class represents an unsigned minimum selection.
450  class SCEVUMinExpr : public SCEVMinMaxExpr {
451  friend class ScalarEvolution;
452 
453  SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
454  : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
455 
456  public:
457  /// Methods for support type inquiry through isa, cast, and dyn_cast:
458  static bool classof(const SCEV *S) {
459  return S->getSCEVType() == scUMinExpr;
460  }
461  };
462 
463  /// This means that we are dealing with an entirely unknown SCEV
464  /// value, and only represent it as its LLVM Value. This is the
465  /// "bottom" value for the analysis.
466  class SCEVUnknown final : public SCEV, private CallbackVH {
467  friend class ScalarEvolution;
468 
469  /// The parent ScalarEvolution value. This is used to update the
470  /// parent's maps when the value associated with a SCEVUnknown is
471  /// deleted or RAUW'd.
472  ScalarEvolution *SE;
473 
474  /// The next pointer in the linked list of all SCEVUnknown
475  /// instances owned by a ScalarEvolution.
476  SCEVUnknown *Next;
477 
479  ScalarEvolution *se, SCEVUnknown *next) :
480  SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
481 
482  // Implement CallbackVH.
483  void deleted() override;
484  void allUsesReplacedWith(Value *New) override;
485 
486  public:
487  Value *getValue() const { return getValPtr(); }
488 
489  /// @{
490  /// Test whether this is a special constant representing a type
491  /// size, alignment, or field offset in a target-independent
492  /// manner, and hasn't happened to have been folded with other
493  /// operations into something unrecognizable. This is mainly only
494  /// useful for pretty-printing and other situations where it isn't
495  /// absolutely required for these to succeed.
496  bool isSizeOf(Type *&AllocTy) const;
497  bool isAlignOf(Type *&AllocTy) const;
498  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
499  /// @}
500 
501  Type *getType() const { return getValPtr()->getType(); }
502 
503  /// Methods for support type inquiry through isa, cast, and dyn_cast:
504  static bool classof(const SCEV *S) {
505  return S->getSCEVType() == scUnknown;
506  }
507  };
508 
509  /// This class defines a simple visitor class that may be used for
510  /// various SCEV analysis purposes.
511  template<typename SC, typename RetVal=void>
512  struct SCEVVisitor {
513  RetVal visit(const SCEV *S) {
514  switch (S->getSCEVType()) {
515  case scConstant:
516  return ((SC*)this)->visitConstant((const SCEVConstant*)S);
517  case scTruncate:
518  return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
519  case scZeroExtend:
520  return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
521  case scSignExtend:
522  return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
523  case scAddExpr:
524  return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
525  case scMulExpr:
526  return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
527  case scUDivExpr:
528  return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
529  case scAddRecExpr:
530  return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
531  case scSMaxExpr:
532  return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
533  case scUMaxExpr:
534  return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
535  case scSMinExpr:
536  return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
537  case scUMinExpr:
538  return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
539  case scUnknown:
540  return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
541  case scCouldNotCompute:
542  return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
543  default:
544  llvm_unreachable("Unknown SCEV type!");
545  }
546  }
547 
549  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
550  }
551  };
552 
553  /// Visit all nodes in the expression tree using worklist traversal.
554  ///
555  /// Visitor implements:
556  /// // return true to follow this node.
557  /// bool follow(const SCEV *S);
558  /// // return true to terminate the search.
559  /// bool isDone();
560  template<typename SV>
562  SV &Visitor;
565 
566  void push(const SCEV *S) {
567  if (Visited.insert(S).second && Visitor.follow(S))
568  Worklist.push_back(S);
569  }
570 
571  public:
572  SCEVTraversal(SV& V): Visitor(V) {}
573 
574  void visitAll(const SCEV *Root) {
575  push(Root);
576  while (!Worklist.empty() && !Visitor.isDone()) {
577  const SCEV *S = Worklist.pop_back_val();
578 
579  switch (S->getSCEVType()) {
580  case scConstant:
581  case scUnknown:
582  break;
583  case scTruncate:
584  case scZeroExtend:
585  case scSignExtend:
586  push(cast<SCEVCastExpr>(S)->getOperand());
587  break;
588  case scAddExpr:
589  case scMulExpr:
590  case scSMaxExpr:
591  case scUMaxExpr:
592  case scSMinExpr:
593  case scUMinExpr:
594  case scAddRecExpr:
595  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
596  push(Op);
597  break;
598  case scUDivExpr: {
599  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
600  push(UDiv->getLHS());
601  push(UDiv->getRHS());
602  break;
603  }
604  case scCouldNotCompute:
605  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
606  default:
607  llvm_unreachable("Unknown SCEV kind!");
608  }
609  }
610  }
611  };
612 
613  /// Use SCEVTraversal to visit all nodes in the given expression tree.
614  template<typename SV>
615  void visitAll(const SCEV *Root, SV& Visitor) {
616  SCEVTraversal<SV> T(Visitor);
617  T.visitAll(Root);
618  }
619 
620  /// Return true if any node in \p Root satisfies the predicate \p Pred.
621  template <typename PredTy>
622  bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
623  struct FindClosure {
624  bool Found = false;
625  PredTy Pred;
626 
627  FindClosure(PredTy Pred) : Pred(Pred) {}
628 
629  bool follow(const SCEV *S) {
630  if (!Pred(S))
631  return true;
632 
633  Found = true;
634  return false;
635  }
636 
637  bool isDone() const { return Found; }
638  };
639 
640  FindClosure FC(Pred);
641  visitAll(Root, FC);
642  return FC.Found;
643  }
644 
645  /// This visitor recursively visits a SCEV expression and re-writes it.
646  /// The result from each visit is cached, so it will return the same
647  /// SCEV for the same input.
648  template<typename SC>
649  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
650  protected:
652  // Memoize the result of each visit so that we only compute once for
653  // the same input SCEV. This is to avoid redundant computations when
654  // a SCEV is referenced by multiple SCEVs. Without memoization, this
655  // visit algorithm would have exponential time complexity in the worst
656  // case, causing the compiler to hang on certain tests.
658 
659  public:
661 
662  const SCEV *visit(const SCEV *S) {
663  auto It = RewriteResults.find(S);
664  if (It != RewriteResults.end())
665  return It->second;
666  auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
667  auto Result = RewriteResults.try_emplace(S, Visited);
668  assert(Result.second && "Should insert a new entry");
669  return Result.first->second;
670  }
671 
673  return Constant;
674  }
675 
677  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
678  return Operand == Expr->getOperand()
679  ? Expr
680  : SE.getTruncateExpr(Operand, Expr->getType());
681  }
682 
684  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
685  return Operand == Expr->getOperand()
686  ? Expr
687  : SE.getZeroExtendExpr(Operand, Expr->getType());
688  }
689 
691  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
692  return Operand == Expr->getOperand()
693  ? Expr
694  : SE.getSignExtendExpr(Operand, Expr->getType());
695  }
696 
697  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
699  bool Changed = false;
700  for (auto *Op : Expr->operands()) {
701  Operands.push_back(((SC*)this)->visit(Op));
702  Changed |= Op != Operands.back();
703  }
704  return !Changed ? Expr : SE.getAddExpr(Operands);
705  }
706 
707  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
709  bool Changed = false;
710  for (auto *Op : Expr->operands()) {
711  Operands.push_back(((SC*)this)->visit(Op));
712  Changed |= Op != Operands.back();
713  }
714  return !Changed ? Expr : SE.getMulExpr(Operands);
715  }
716 
717  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
718  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
719  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
720  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
721  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
722  }
723 
724  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
726  bool Changed = false;
727  for (auto *Op : Expr->operands()) {
728  Operands.push_back(((SC*)this)->visit(Op));
729  Changed |= Op != Operands.back();
730  }
731  return !Changed ? Expr
732  : SE.getAddRecExpr(Operands, Expr->getLoop(),
733  Expr->getNoWrapFlags());
734  }
735 
736  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
738  bool Changed = false;
739  for (auto *Op : Expr->operands()) {
740  Operands.push_back(((SC *)this)->visit(Op));
741  Changed |= Op != Operands.back();
742  }
743  return !Changed ? Expr : SE.getSMaxExpr(Operands);
744  }
745 
746  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
748  bool Changed = false;
749  for (auto *Op : Expr->operands()) {
750  Operands.push_back(((SC*)this)->visit(Op));
751  Changed |= Op != Operands.back();
752  }
753  return !Changed ? Expr : SE.getUMaxExpr(Operands);
754  }
755 
756  const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
758  bool Changed = false;
759  for (auto *Op : Expr->operands()) {
760  Operands.push_back(((SC *)this)->visit(Op));
761  Changed |= Op != Operands.back();
762  }
763  return !Changed ? Expr : SE.getSMinExpr(Operands);
764  }
765 
766  const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
768  bool Changed = false;
769  for (auto *Op : Expr->operands()) {
770  Operands.push_back(((SC *)this)->visit(Op));
771  Changed |= Op != Operands.back();
772  }
773  return !Changed ? Expr : SE.getUMinExpr(Operands);
774  }
775 
776  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
777  return Expr;
778  }
779 
781  return Expr;
782  }
783  };
784 
786 
787  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
788  /// the SCEVUnknown components following the Map (Value -> Value).
789  class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
790  public:
791  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
792  ValueToValueMap &Map,
793  bool InterpretConsts = false) {
794  SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
795  return Rewriter.visit(Scev);
796  }
797 
799  : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
800 
801  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
802  Value *V = Expr->getValue();
803  if (Map.count(V)) {
804  Value *NV = Map[V];
805  if (InterpretConsts && isa<ConstantInt>(NV))
806  return SE.getConstant(cast<ConstantInt>(NV));
807  return SE.getUnknown(NV);
808  }
809  return Expr;
810  }
811 
812  private:
813  ValueToValueMap &Map;
814  bool InterpretConsts;
815  };
816 
818 
819  /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
820  /// the Map (Loop -> SCEV) to all AddRecExprs.
822  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
823  public:
825  : SCEVRewriteVisitor(SE), Map(M) {}
826 
827  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
828  ScalarEvolution &SE) {
830  return Rewriter.visit(Scev);
831  }
832 
833  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
835  for (const SCEV *Op : Expr->operands())
836  Operands.push_back(visit(Op));
837 
838  const Loop *L = Expr->getLoop();
839  const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
840 
841  if (0 == Map.count(L))
842  return Res;
843 
844  const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
845  return Rec->evaluateAtIteration(Map[L], SE);
846  }
847 
848  private:
849  LoopToScevMapT &Map;
850  };
851 
852 } // end namespace llvm
853 
854 #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
uint64_t CallInst * C
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:171
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
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...
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1562
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
DiagnosticInfoOptimizationBase::Argument NV
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
The main scalar evolution driver.
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:1971
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a truncation of an integer value to a smaller integer value.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV *const * Operands
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
const SCEV * getOperand() const
An object of this class is returned by queries that could not be answered.
#define op(i)
RetVal visit(const SCEV *S)
const SCEV * visit(const SCEV *S)
This is the base class for unary cast operator classes.
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies the Map (Loop -> SCEV) to ...
const SCEV * visitConstant(const SCEVConstant *Constant)
SCEVParameterRewriter(ScalarEvolution &SE, ValueToValueMap &M, bool C)
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information...
This node is the base class for n&#39;ary commutative operators.
This node represents multiplication of some number of SCEVs.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
const APInt & getAPInt() const
const SCEV * visitUnknown(const SCEVUnknown *Expr)
ConstantInt * getValue() const
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
op_iterator op_begin() const
This class represents a signed minimum selection.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
Visit all nodes in the expression tree using worklist traversal.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
const SCEV * getOperand(unsigned i) const
This class defines a simple visitor class that may be used for various SCEV analysis purposes...
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
static unsigned short computeExpressionSize(ArrayRef< const SCEV *> Args)
This class represents a binary unsigned division operation.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This node is the base class min/max selections.
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an unsigned minimum selection.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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:370
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.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getLHS() const
void visitAll(const SCEV *Root)
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
SCEVRewriteVisitor(ScalarEvolution &SE)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
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.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getSCEVType() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV *const * op_iterator
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
This class represents a range of values.
Definition: ConstantRange.h:47
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
CHAIN = SC CHAIN, Imm128 - System call.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
A range adaptor for a pair of iterators.
Class for arbitrary precision integers.
Definition: APInt.h:69
This node represents an addition of some number of SCEVs.
SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
This class represents a signed maximum selection.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
This class represents a zero extension of a small integer value to a larger integer value...
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node id data rather than using plain FoldingSetNodeIDs, since the 32-element SmallVector is often much larger than necessary, and the possibility of heap allocation means it requires a non-trivial destructor call.
Definition: FoldingSet.h:277
const SCEV * visitUnknown(const SCEVUnknown *Expr)
This class represents an analyzed expression in the program.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
#define N
This class represents a sign extension of a small integer value to a larger integer value...
This class represents an unsigned maximum selection.
uint32_t Size
Definition: Profile.cpp:46
static bool classof(const SCEV *S)
const SCEV * getRHS() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
LLVM Value Representation.
Definition: Value.h:72
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
DenseMap< const SCEV *, const SCEV * > RewriteResults
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToValueMap &Map, bool InterpretConsts=false)
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
This node is a base class providing common functionality for n&#39;ary operators.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a constant integer value.