LLVM  9.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 ||
194  S->getSCEVType() == scMulExpr ||
195  S->getSCEVType() == scSMaxExpr ||
196  S->getSCEVType() == scUMaxExpr ||
197  S->getSCEVType() == scAddRecExpr;
198  }
199  };
200 
201  /// This node is the base class for n'ary commutative operators.
203  protected:
205  enum SCEVTypes T, const SCEV *const *O, size_t N)
206  : SCEVNAryExpr(ID, T, O, N) {}
207 
208  public:
209  /// Methods for support type inquiry through isa, cast, and dyn_cast:
210  static bool classof(const SCEV *S) {
211  return S->getSCEVType() == scAddExpr ||
212  S->getSCEVType() == scMulExpr ||
213  S->getSCEVType() == scSMaxExpr ||
214  S->getSCEVType() == scUMaxExpr;
215  }
216 
217  /// Set flags for a non-recurrence without clearing previously set flags.
219  SubclassData |= Flags;
220  }
221  };
222 
223  /// This node represents an addition of some number of SCEVs.
225  friend class ScalarEvolution;
226 
228  const SCEV *const *O, size_t N)
229  : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}
230 
231  public:
232  Type *getType() const {
233  // Use the type of the last operand, which is likely to be a pointer
234  // type, if there is one. This doesn't usually matter, but it can help
235  // reduce casts when the expressions are expanded.
236  return getOperand(getNumOperands() - 1)->getType();
237  }
238 
239  /// Methods for support type inquiry through isa, cast, and dyn_cast:
240  static bool classof(const SCEV *S) {
241  return S->getSCEVType() == scAddExpr;
242  }
243  };
244 
245  /// This node represents multiplication of some number of SCEVs.
247  friend class ScalarEvolution;
248 
250  const SCEV *const *O, size_t N)
251  : SCEVCommutativeExpr(ID, scMulExpr, O, N) {}
252 
253  public:
254  /// Methods for support type inquiry through isa, cast, and dyn_cast:
255  static bool classof(const SCEV *S) {
256  return S->getSCEVType() == scMulExpr;
257  }
258  };
259 
260  /// This class represents a binary unsigned division operation.
261  class SCEVUDivExpr : public SCEV {
262  friend class ScalarEvolution;
263 
264  const SCEV *LHS;
265  const SCEV *RHS;
266 
267  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
268  : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})), LHS(lhs),
269  RHS(rhs) {}
270 
271  public:
272  const SCEV *getLHS() const { return LHS; }
273  const SCEV *getRHS() const { return RHS; }
274 
275  Type *getType() const {
276  // In most cases the types of LHS and RHS will be the same, but in some
277  // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
278  // depend on the type for correctness, but handling types carefully can
279  // avoid extra casts in the SCEVExpander. The LHS is more likely to be
280  // a pointer type than the RHS, so use the RHS' type here.
281  return getRHS()->getType();
282  }
283 
284  /// Methods for support type inquiry through isa, cast, and dyn_cast:
285  static bool classof(const SCEV *S) {
286  return S->getSCEVType() == scUDivExpr;
287  }
288  };
289 
290  /// This node represents a polynomial recurrence on the trip count
291  /// of the specified loop. This is the primary focus of the
292  /// ScalarEvolution framework; all the other SCEV subclasses are
293  /// mostly just supporting infrastructure to allow SCEVAddRecExpr
294  /// expressions to be created and analyzed.
295  ///
296  /// All operands of an AddRec are required to be loop invariant.
297  ///
298  class SCEVAddRecExpr : public SCEVNAryExpr {
299  friend class ScalarEvolution;
300 
301  const Loop *L;
302 
304  const SCEV *const *O, size_t N, const Loop *l)
305  : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
306 
307  public:
308  const SCEV *getStart() const { return Operands[0]; }
309  const Loop *getLoop() const { return L; }
310 
311  /// Constructs and returns the recurrence indicating how much this
312  /// expression steps by. If this is a polynomial of degree N, it
313  /// returns a chrec of degree N-1. We cannot determine whether
314  /// the step recurrence has self-wraparound.
316  if (isAffine()) return getOperand(1);
317  return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
318  op_end()),
319  getLoop(), FlagAnyWrap);
320  }
321 
322  /// Return true if this represents an expression A + B*x where A
323  /// and B are loop invariant values.
324  bool isAffine() const {
325  // We know that the start value is invariant. This expression is thus
326  // affine iff the step is also invariant.
327  return getNumOperands() == 2;
328  }
329 
330  /// Return true if this represents an expression A + B*x + C*x^2
331  /// where A, B and C are loop invariant values. This corresponds
332  /// to an addrec of the form {L,+,M,+,N}
333  bool isQuadratic() const {
334  return getNumOperands() == 3;
335  }
336 
337  /// Set flags for a recurrence without clearing any previously set flags.
338  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
339  /// to make it easier to propagate flags.
341  if (Flags & (FlagNUW | FlagNSW))
342  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
343  SubclassData |= Flags;
344  }
345 
346  /// Return the value of this chain of recurrences at the specified
347  /// iteration number.
348  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
349 
350  /// Return the number of iterations of this loop that produce
351  /// values in the specified constant range. Another way of
352  /// looking at this is that it returns the first iteration number
353  /// where the value is not in the condition, thus computing the
354  /// exit count. If the iteration count can't be computed, an
355  /// instance of SCEVCouldNotCompute is returned.
356  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
357  ScalarEvolution &SE) const;
358 
359  /// Return an expression representing the value of this expression
360  /// one iteration of the loop ahead.
361  const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
362 
363  /// Methods for support type inquiry through isa, cast, and dyn_cast:
364  static bool classof(const SCEV *S) {
365  return S->getSCEVType() == scAddRecExpr;
366  }
367  };
368 
369  /// This class represents a signed maximum selection.
371  friend class ScalarEvolution;
372 
374  const SCEV *const *O, size_t N)
375  : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
376  // Max never overflows.
377  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
378  }
379 
380  public:
381  /// Methods for support type inquiry through isa, cast, and dyn_cast:
382  static bool classof(const SCEV *S) {
383  return S->getSCEVType() == scSMaxExpr;
384  }
385  };
386 
387  /// This class represents an unsigned maximum selection.
389  friend class ScalarEvolution;
390 
392  const SCEV *const *O, size_t N)
393  : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
394  // Max never overflows.
395  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
396  }
397 
398  public:
399  /// Methods for support type inquiry through isa, cast, and dyn_cast:
400  static bool classof(const SCEV *S) {
401  return S->getSCEVType() == scUMaxExpr;
402  }
403  };
404 
405  /// This means that we are dealing with an entirely unknown SCEV
406  /// value, and only represent it as its LLVM Value. This is the
407  /// "bottom" value for the analysis.
408  class SCEVUnknown final : public SCEV, private CallbackVH {
409  friend class ScalarEvolution;
410 
411  /// The parent ScalarEvolution value. This is used to update the
412  /// parent's maps when the value associated with a SCEVUnknown is
413  /// deleted or RAUW'd.
414  ScalarEvolution *SE;
415 
416  /// The next pointer in the linked list of all SCEVUnknown
417  /// instances owned by a ScalarEvolution.
418  SCEVUnknown *Next;
419 
421  ScalarEvolution *se, SCEVUnknown *next) :
422  SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
423 
424  // Implement CallbackVH.
425  void deleted() override;
426  void allUsesReplacedWith(Value *New) override;
427 
428  public:
429  Value *getValue() const { return getValPtr(); }
430 
431  /// @{
432  /// Test whether this is a special constant representing a type
433  /// size, alignment, or field offset in a target-independent
434  /// manner, and hasn't happened to have been folded with other
435  /// operations into something unrecognizable. This is mainly only
436  /// useful for pretty-printing and other situations where it isn't
437  /// absolutely required for these to succeed.
438  bool isSizeOf(Type *&AllocTy) const;
439  bool isAlignOf(Type *&AllocTy) const;
440  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
441  /// @}
442 
443  Type *getType() const { return getValPtr()->getType(); }
444 
445  /// Methods for support type inquiry through isa, cast, and dyn_cast:
446  static bool classof(const SCEV *S) {
447  return S->getSCEVType() == scUnknown;
448  }
449  };
450 
451  /// This class defines a simple visitor class that may be used for
452  /// various SCEV analysis purposes.
453  template<typename SC, typename RetVal=void>
454  struct SCEVVisitor {
455  RetVal visit(const SCEV *S) {
456  switch (S->getSCEVType()) {
457  case scConstant:
458  return ((SC*)this)->visitConstant((const SCEVConstant*)S);
459  case scTruncate:
460  return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
461  case scZeroExtend:
462  return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
463  case scSignExtend:
464  return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
465  case scAddExpr:
466  return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
467  case scMulExpr:
468  return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
469  case scUDivExpr:
470  return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
471  case scAddRecExpr:
472  return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
473  case scSMaxExpr:
474  return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
475  case scUMaxExpr:
476  return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
477  case scUnknown:
478  return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
479  case scCouldNotCompute:
480  return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
481  default:
482  llvm_unreachable("Unknown SCEV type!");
483  }
484  }
485 
487  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
488  }
489  };
490 
491  /// Visit all nodes in the expression tree using worklist traversal.
492  ///
493  /// Visitor implements:
494  /// // return true to follow this node.
495  /// bool follow(const SCEV *S);
496  /// // return true to terminate the search.
497  /// bool isDone();
498  template<typename SV>
500  SV &Visitor;
503 
504  void push(const SCEV *S) {
505  if (Visited.insert(S).second && Visitor.follow(S))
506  Worklist.push_back(S);
507  }
508 
509  public:
510  SCEVTraversal(SV& V): Visitor(V) {}
511 
512  void visitAll(const SCEV *Root) {
513  push(Root);
514  while (!Worklist.empty() && !Visitor.isDone()) {
515  const SCEV *S = Worklist.pop_back_val();
516 
517  switch (S->getSCEVType()) {
518  case scConstant:
519  case scUnknown:
520  break;
521  case scTruncate:
522  case scZeroExtend:
523  case scSignExtend:
524  push(cast<SCEVCastExpr>(S)->getOperand());
525  break;
526  case scAddExpr:
527  case scMulExpr:
528  case scSMaxExpr:
529  case scUMaxExpr:
530  case scAddRecExpr:
531  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
532  push(Op);
533  break;
534  case scUDivExpr: {
535  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
536  push(UDiv->getLHS());
537  push(UDiv->getRHS());
538  break;
539  }
540  case scCouldNotCompute:
541  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
542  default:
543  llvm_unreachable("Unknown SCEV kind!");
544  }
545  }
546  }
547  };
548 
549  /// Use SCEVTraversal to visit all nodes in the given expression tree.
550  template<typename SV>
551  void visitAll(const SCEV *Root, SV& Visitor) {
552  SCEVTraversal<SV> T(Visitor);
553  T.visitAll(Root);
554  }
555 
556  /// Return true if any node in \p Root satisfies the predicate \p Pred.
557  template <typename PredTy>
558  bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
559  struct FindClosure {
560  bool Found = false;
561  PredTy Pred;
562 
563  FindClosure(PredTy Pred) : Pred(Pred) {}
564 
565  bool follow(const SCEV *S) {
566  if (!Pred(S))
567  return true;
568 
569  Found = true;
570  return false;
571  }
572 
573  bool isDone() const { return Found; }
574  };
575 
576  FindClosure FC(Pred);
577  visitAll(Root, FC);
578  return FC.Found;
579  }
580 
581  /// This visitor recursively visits a SCEV expression and re-writes it.
582  /// The result from each visit is cached, so it will return the same
583  /// SCEV for the same input.
584  template<typename SC>
585  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
586  protected:
588  // Memoize the result of each visit so that we only compute once for
589  // the same input SCEV. This is to avoid redundant computations when
590  // a SCEV is referenced by multiple SCEVs. Without memoization, this
591  // visit algorithm would have exponential time complexity in the worst
592  // case, causing the compiler to hang on certain tests.
594 
595  public:
597 
598  const SCEV *visit(const SCEV *S) {
599  auto It = RewriteResults.find(S);
600  if (It != RewriteResults.end())
601  return It->second;
602  auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
603  auto Result = RewriteResults.try_emplace(S, Visited);
604  assert(Result.second && "Should insert a new entry");
605  return Result.first->second;
606  }
607 
609  return Constant;
610  }
611 
613  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
614  return Operand == Expr->getOperand()
615  ? Expr
616  : SE.getTruncateExpr(Operand, Expr->getType());
617  }
618 
620  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
621  return Operand == Expr->getOperand()
622  ? Expr
623  : SE.getZeroExtendExpr(Operand, Expr->getType());
624  }
625 
627  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
628  return Operand == Expr->getOperand()
629  ? Expr
630  : SE.getSignExtendExpr(Operand, Expr->getType());
631  }
632 
633  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
635  bool Changed = false;
636  for (auto *Op : Expr->operands()) {
637  Operands.push_back(((SC*)this)->visit(Op));
638  Changed |= Op != Operands.back();
639  }
640  return !Changed ? Expr : SE.getAddExpr(Operands);
641  }
642 
643  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
645  bool Changed = false;
646  for (auto *Op : Expr->operands()) {
647  Operands.push_back(((SC*)this)->visit(Op));
648  Changed |= Op != Operands.back();
649  }
650  return !Changed ? Expr : SE.getMulExpr(Operands);
651  }
652 
653  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
654  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
655  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
656  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
657  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
658  }
659 
660  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
662  bool Changed = false;
663  for (auto *Op : Expr->operands()) {
664  Operands.push_back(((SC*)this)->visit(Op));
665  Changed |= Op != Operands.back();
666  }
667  return !Changed ? Expr
668  : SE.getAddRecExpr(Operands, Expr->getLoop(),
669  Expr->getNoWrapFlags());
670  }
671 
672  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
674  bool Changed = false;
675  for (auto *Op : Expr->operands()) {
676  Operands.push_back(((SC *)this)->visit(Op));
677  Changed |= Op != Operands.back();
678  }
679  return !Changed ? Expr : SE.getSMaxExpr(Operands);
680  }
681 
682  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
684  bool Changed = false;
685  for (auto *Op : Expr->operands()) {
686  Operands.push_back(((SC*)this)->visit(Op));
687  Changed |= Op != Operands.back();
688  }
689  return !Changed ? Expr : SE.getUMaxExpr(Operands);
690  }
691 
692  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
693  return Expr;
694  }
695 
697  return Expr;
698  }
699  };
700 
702 
703  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
704  /// the SCEVUnknown components following the Map (Value -> Value).
705  class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
706  public:
707  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
708  ValueToValueMap &Map,
709  bool InterpretConsts = false) {
710  SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
711  return Rewriter.visit(Scev);
712  }
713 
715  : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
716 
717  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
718  Value *V = Expr->getValue();
719  if (Map.count(V)) {
720  Value *NV = Map[V];
721  if (InterpretConsts && isa<ConstantInt>(NV))
722  return SE.getConstant(cast<ConstantInt>(NV));
723  return SE.getUnknown(NV);
724  }
725  return Expr;
726  }
727 
728  private:
729  ValueToValueMap &Map;
730  bool InterpretConsts;
731  };
732 
734 
735  /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
736  /// the Map (Loop -> SCEV) to all AddRecExprs.
738  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
739  public:
741  : SCEVRewriteVisitor(SE), Map(M) {}
742 
743  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
744  ScalarEvolution &SE) {
746  return Rewriter.visit(Scev);
747  }
748 
749  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
751  for (const SCEV *Op : Expr->operands())
752  Operands.push_back(visit(Op));
753 
754  const Loop *L = Expr->getLoop();
755  const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
756 
757  if (0 == Map.count(L))
758  return Res;
759 
760  const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
761  return Rec->evaluateAtIteration(Map[L], SE);
762  }
763 
764  private:
765  LoopToScevMapT &Map;
766  };
767 
768 } // end namespace llvm
769 
770 #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 * visitSMaxExpr(const SCEVSMaxExpr *Expr)
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
The main scalar evolution driver.
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:1959
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)
#define T
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
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 is an important base class in LLVM.
Definition: Constant.h:41
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)
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.
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 * getTruncateExpr(const SCEV *Op, Type *Ty)
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:839
This class represents a range of values.
Definition: ConstantRange.h:46
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:373
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.
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:464
#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
const SCEV * getRHS() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
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:
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.