LLVM  8.0.0svn
ScalarEvolutionExpressions.h
Go to the documentation of this file.
1 //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the classes used to represent and build scalar expressions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
15 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/FoldingSet.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Value.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Support/Casting.h"
28 #include <cassert>
29 #include <cstddef>
30 
31 namespace llvm {
32 
33 class APInt;
34 class Constant;
35 class ConstantRange;
36 class Loop;
37 class Type;
38 
39  enum SCEVTypes {
40  // These should be ordered in terms of increasing complexity to make the
41  // folders simpler.
45  };
46 
47  /// This class represents a constant integer value.
48  class SCEVConstant : public SCEV {
49  friend class ScalarEvolution;
50 
51  ConstantInt *V;
52 
54  SCEV(ID, scConstant), V(v) {}
55 
56  public:
57  ConstantInt *getValue() const { return V; }
58  const APInt &getAPInt() const { return getValue()->getValue(); }
59 
60  Type *getType() const { return V->getType(); }
61 
62  /// Methods for support type inquiry through isa, cast, and dyn_cast:
63  static bool classof(const SCEV *S) {
64  return S->getSCEVType() == scConstant;
65  }
66  };
67 
68  /// This is the base class for unary cast operator classes.
69  class SCEVCastExpr : public SCEV {
70  protected:
71  const SCEV *Op;
72  Type *Ty;
73 
75  unsigned SCEVTy, const SCEV *op, Type *ty);
76 
77  public:
78  const SCEV *getOperand() const { return Op; }
79  Type *getType() const { return Ty; }
80 
81  /// Methods for support type inquiry through isa, cast, and dyn_cast:
82  static bool classof(const SCEV *S) {
83  return S->getSCEVType() == scTruncate ||
84  S->getSCEVType() == scZeroExtend ||
85  S->getSCEVType() == scSignExtend;
86  }
87  };
88 
89  /// This class represents a truncation of an integer value to a
90  /// smaller integer value.
91  class SCEVTruncateExpr : public SCEVCastExpr {
92  friend class ScalarEvolution;
93 
95  const SCEV *op, Type *ty);
96 
97  public:
98  /// Methods for support type inquiry through isa, cast, and dyn_cast:
99  static bool classof(const SCEV *S) {
100  return S->getSCEVType() == scTruncate;
101  }
102  };
103 
104  /// This class represents a zero extension of a small integer value
105  /// to a larger integer value.
107  friend class ScalarEvolution;
108 
110  const SCEV *op, Type *ty);
111 
112  public:
113  /// Methods for support type inquiry through isa, cast, and dyn_cast:
114  static bool classof(const SCEV *S) {
115  return S->getSCEVType() == scZeroExtend;
116  }
117  };
118 
119  /// This class represents a sign extension of a small integer value
120  /// to a larger integer value.
122  friend class ScalarEvolution;
123 
125  const SCEV *op, Type *ty);
126 
127  public:
128  /// Methods for support type inquiry through isa, cast, and dyn_cast:
129  static bool classof(const SCEV *S) {
130  return S->getSCEVType() == scSignExtend;
131  }
132  };
133 
134  /// This node is a base class providing common functionality for
135  /// n'ary operators.
136  class SCEVNAryExpr : public SCEV {
137  protected:
138  // Since SCEVs are immutable, ScalarEvolution allocates operand
139  // arrays with its SCEVAllocator, so this class just needs a simple
140  // pointer rather than a more elaborate vector-like data structure.
141  // This also avoids the need for a non-trivial destructor.
142  const SCEV *const *Operands;
143  size_t NumOperands;
144 
146  enum SCEVTypes T, const SCEV *const *O, size_t N)
147  : SCEV(ID, T), Operands(O), NumOperands(N) {}
148 
149  public:
150  size_t getNumOperands() const { return NumOperands; }
151 
152  const SCEV *getOperand(unsigned i) const {
153  assert(i < NumOperands && "Operand index out of range!");
154  return Operands[i];
155  }
156 
157  using op_iterator = const SCEV *const *;
159 
160  op_iterator op_begin() const { return Operands; }
161  op_iterator op_end() const { return Operands + NumOperands; }
162  op_range operands() const {
163  return make_range(op_begin(), op_end());
164  }
165 
166  Type *getType() const { return getOperand(0)->getType(); }
167 
169  return (NoWrapFlags)(SubclassData & Mask);
170  }
171 
172  bool hasNoUnsignedWrap() const {
173  return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
174  }
175 
176  bool hasNoSignedWrap() const {
177  return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
178  }
179 
180  bool hasNoSelfWrap() const {
181  return getNoWrapFlags(FlagNW) != FlagAnyWrap;
182  }
183 
184  /// Methods for support type inquiry through isa, cast, and dyn_cast:
185  static bool classof(const SCEV *S) {
186  return S->getSCEVType() == scAddExpr ||
187  S->getSCEVType() == scMulExpr ||
188  S->getSCEVType() == scSMaxExpr ||
189  S->getSCEVType() == scUMaxExpr ||
190  S->getSCEVType() == scAddRecExpr;
191  }
192  };
193 
194  /// This node is the base class for n'ary commutative operators.
196  protected:
198  enum SCEVTypes T, const SCEV *const *O, size_t N)
199  : SCEVNAryExpr(ID, T, O, N) {}
200 
201  public:
202  /// Methods for support type inquiry through isa, cast, and dyn_cast:
203  static bool classof(const SCEV *S) {
204  return S->getSCEVType() == scAddExpr ||
205  S->getSCEVType() == scMulExpr ||
206  S->getSCEVType() == scSMaxExpr ||
207  S->getSCEVType() == scUMaxExpr;
208  }
209 
210  /// Set flags for a non-recurrence without clearing previously set flags.
212  SubclassData |= Flags;
213  }
214  };
215 
216  /// This node represents an addition of some number of SCEVs.
218  friend class ScalarEvolution;
219 
221  const SCEV *const *O, size_t N)
222  : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}
223 
224  public:
225  Type *getType() const {
226  // Use the type of the last operand, which is likely to be a pointer
227  // type, if there is one. This doesn't usually matter, but it can help
228  // reduce casts when the expressions are expanded.
229  return getOperand(getNumOperands() - 1)->getType();
230  }
231 
232  /// Methods for support type inquiry through isa, cast, and dyn_cast:
233  static bool classof(const SCEV *S) {
234  return S->getSCEVType() == scAddExpr;
235  }
236  };
237 
238  /// This node represents multiplication of some number of SCEVs.
240  friend class ScalarEvolution;
241 
243  const SCEV *const *O, size_t N)
244  : SCEVCommutativeExpr(ID, scMulExpr, O, N) {}
245 
246  public:
247  /// Methods for support type inquiry through isa, cast, and dyn_cast:
248  static bool classof(const SCEV *S) {
249  return S->getSCEVType() == scMulExpr;
250  }
251  };
252 
253  /// This class represents a binary unsigned division operation.
254  class SCEVUDivExpr : public SCEV {
255  friend class ScalarEvolution;
256 
257  const SCEV *LHS;
258  const SCEV *RHS;
259 
260  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
261  : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
262 
263  public:
264  const SCEV *getLHS() const { return LHS; }
265  const SCEV *getRHS() const { return RHS; }
266 
267  Type *getType() const {
268  // In most cases the types of LHS and RHS will be the same, but in some
269  // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
270  // depend on the type for correctness, but handling types carefully can
271  // avoid extra casts in the SCEVExpander. The LHS is more likely to be
272  // a pointer type than the RHS, so use the RHS' type here.
273  return getRHS()->getType();
274  }
275 
276  /// Methods for support type inquiry through isa, cast, and dyn_cast:
277  static bool classof(const SCEV *S) {
278  return S->getSCEVType() == scUDivExpr;
279  }
280  };
281 
282  /// This node represents a polynomial recurrence on the trip count
283  /// of the specified loop. This is the primary focus of the
284  /// ScalarEvolution framework; all the other SCEV subclasses are
285  /// mostly just supporting infrastructure to allow SCEVAddRecExpr
286  /// expressions to be created and analyzed.
287  ///
288  /// All operands of an AddRec are required to be loop invariant.
289  ///
290  class SCEVAddRecExpr : public SCEVNAryExpr {
291  friend class ScalarEvolution;
292 
293  const Loop *L;
294 
296  const SCEV *const *O, size_t N, const Loop *l)
297  : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
298 
299  public:
300  const SCEV *getStart() const { return Operands[0]; }
301  const Loop *getLoop() const { return L; }
302 
303  /// Constructs and returns the recurrence indicating how much this
304  /// expression steps by. If this is a polynomial of degree N, it
305  /// returns a chrec of degree N-1. We cannot determine whether
306  /// the step recurrence has self-wraparound.
308  if (isAffine()) return getOperand(1);
309  return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
310  op_end()),
311  getLoop(), FlagAnyWrap);
312  }
313 
314  /// Return true if this represents an expression A + B*x where A
315  /// and B are loop invariant values.
316  bool isAffine() const {
317  // We know that the start value is invariant. This expression is thus
318  // affine iff the step is also invariant.
319  return getNumOperands() == 2;
320  }
321 
322  /// Return true if this represents an expression A + B*x + C*x^2
323  /// where A, B and C are loop invariant values. This corresponds
324  /// to an addrec of the form {L,+,M,+,N}
325  bool isQuadratic() const {
326  return getNumOperands() == 3;
327  }
328 
329  /// Set flags for a recurrence without clearing any previously set flags.
330  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
331  /// to make it easier to propagate flags.
333  if (Flags & (FlagNUW | FlagNSW))
334  Flags = ScalarEvolution::setFlags(Flags, FlagNW);
335  SubclassData |= Flags;
336  }
337 
338  /// Return the value of this chain of recurrences at the specified
339  /// iteration number.
340  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
341 
342  /// Return the number of iterations of this loop that produce
343  /// values in the specified constant range. Another way of
344  /// looking at this is that it returns the first iteration number
345  /// where the value is not in the condition, thus computing the
346  /// exit count. If the iteration count can't be computed, an
347  /// instance of SCEVCouldNotCompute is returned.
348  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
349  ScalarEvolution &SE) const;
350 
351  /// Return an expression representing the value of this expression
352  /// one iteration of the loop ahead.
353  const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
354 
355  /// Methods for support type inquiry through isa, cast, and dyn_cast:
356  static bool classof(const SCEV *S) {
357  return S->getSCEVType() == scAddRecExpr;
358  }
359  };
360 
361  /// This class represents a signed maximum selection.
363  friend class ScalarEvolution;
364 
366  const SCEV *const *O, size_t N)
367  : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
368  // Max never overflows.
369  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
370  }
371 
372  public:
373  /// Methods for support type inquiry through isa, cast, and dyn_cast:
374  static bool classof(const SCEV *S) {
375  return S->getSCEVType() == scSMaxExpr;
376  }
377  };
378 
379  /// This class represents an unsigned maximum selection.
381  friend class ScalarEvolution;
382 
384  const SCEV *const *O, size_t N)
385  : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
386  // Max never overflows.
387  setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
388  }
389 
390  public:
391  /// Methods for support type inquiry through isa, cast, and dyn_cast:
392  static bool classof(const SCEV *S) {
393  return S->getSCEVType() == scUMaxExpr;
394  }
395  };
396 
397  /// This means that we are dealing with an entirely unknown SCEV
398  /// value, and only represent it as its LLVM Value. This is the
399  /// "bottom" value for the analysis.
400  class SCEVUnknown final : public SCEV, private CallbackVH {
401  friend class ScalarEvolution;
402 
403  /// The parent ScalarEvolution value. This is used to update the
404  /// parent's maps when the value associated with a SCEVUnknown is
405  /// deleted or RAUW'd.
406  ScalarEvolution *SE;
407 
408  /// The next pointer in the linked list of all SCEVUnknown
409  /// instances owned by a ScalarEvolution.
410  SCEVUnknown *Next;
411 
413  ScalarEvolution *se, SCEVUnknown *next) :
414  SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
415 
416  // Implement CallbackVH.
417  void deleted() override;
418  void allUsesReplacedWith(Value *New) override;
419 
420  public:
421  Value *getValue() const { return getValPtr(); }
422 
423  /// @{
424  /// Test whether this is a special constant representing a type
425  /// size, alignment, or field offset in a target-independent
426  /// manner, and hasn't happened to have been folded with other
427  /// operations into something unrecognizable. This is mainly only
428  /// useful for pretty-printing and other situations where it isn't
429  /// absolutely required for these to succeed.
430  bool isSizeOf(Type *&AllocTy) const;
431  bool isAlignOf(Type *&AllocTy) const;
432  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
433  /// @}
434 
435  Type *getType() const { return getValPtr()->getType(); }
436 
437  /// Methods for support type inquiry through isa, cast, and dyn_cast:
438  static bool classof(const SCEV *S) {
439  return S->getSCEVType() == scUnknown;
440  }
441  };
442 
443  /// This class defines a simple visitor class that may be used for
444  /// various SCEV analysis purposes.
445  template<typename SC, typename RetVal=void>
446  struct SCEVVisitor {
447  RetVal visit(const SCEV *S) {
448  switch (S->getSCEVType()) {
449  case scConstant:
450  return ((SC*)this)->visitConstant((const SCEVConstant*)S);
451  case scTruncate:
452  return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
453  case scZeroExtend:
454  return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
455  case scSignExtend:
456  return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
457  case scAddExpr:
458  return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
459  case scMulExpr:
460  return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
461  case scUDivExpr:
462  return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
463  case scAddRecExpr:
464  return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
465  case scSMaxExpr:
466  return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
467  case scUMaxExpr:
468  return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
469  case scUnknown:
470  return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
471  case scCouldNotCompute:
472  return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
473  default:
474  llvm_unreachable("Unknown SCEV type!");
475  }
476  }
477 
479  llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
480  }
481  };
482 
483  /// Visit all nodes in the expression tree using worklist traversal.
484  ///
485  /// Visitor implements:
486  /// // return true to follow this node.
487  /// bool follow(const SCEV *S);
488  /// // return true to terminate the search.
489  /// bool isDone();
490  template<typename SV>
492  SV &Visitor;
495 
496  void push(const SCEV *S) {
497  if (Visited.insert(S).second && Visitor.follow(S))
498  Worklist.push_back(S);
499  }
500 
501  public:
502  SCEVTraversal(SV& V): Visitor(V) {}
503 
504  void visitAll(const SCEV *Root) {
505  push(Root);
506  while (!Worklist.empty() && !Visitor.isDone()) {
507  const SCEV *S = Worklist.pop_back_val();
508 
509  switch (S->getSCEVType()) {
510  case scConstant:
511  case scUnknown:
512  break;
513  case scTruncate:
514  case scZeroExtend:
515  case scSignExtend:
516  push(cast<SCEVCastExpr>(S)->getOperand());
517  break;
518  case scAddExpr:
519  case scMulExpr:
520  case scSMaxExpr:
521  case scUMaxExpr:
522  case scAddRecExpr:
523  for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
524  push(Op);
525  break;
526  case scUDivExpr: {
527  const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
528  push(UDiv->getLHS());
529  push(UDiv->getRHS());
530  break;
531  }
532  case scCouldNotCompute:
533  llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
534  default:
535  llvm_unreachable("Unknown SCEV kind!");
536  }
537  }
538  }
539  };
540 
541  /// Use SCEVTraversal to visit all nodes in the given expression tree.
542  template<typename SV>
543  void visitAll(const SCEV *Root, SV& Visitor) {
544  SCEVTraversal<SV> T(Visitor);
545  T.visitAll(Root);
546  }
547 
548  /// Return true if any node in \p Root satisfies the predicate \p Pred.
549  template <typename PredTy>
550  bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
551  struct FindClosure {
552  bool Found = false;
553  PredTy Pred;
554 
555  FindClosure(PredTy Pred) : Pred(Pred) {}
556 
557  bool follow(const SCEV *S) {
558  if (!Pred(S))
559  return true;
560 
561  Found = true;
562  return false;
563  }
564 
565  bool isDone() const { return Found; }
566  };
567 
568  FindClosure FC(Pred);
569  visitAll(Root, FC);
570  return FC.Found;
571  }
572 
573  /// This visitor recursively visits a SCEV expression and re-writes it.
574  /// The result from each visit is cached, so it will return the same
575  /// SCEV for the same input.
576  template<typename SC>
577  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
578  protected:
580  // Memoize the result of each visit so that we only compute once for
581  // the same input SCEV. This is to avoid redundant computations when
582  // a SCEV is referenced by multiple SCEVs. Without memoization, this
583  // visit algorithm would have exponential time complexity in the worst
584  // case, causing the compiler to hang on certain tests.
586 
587  public:
589 
590  const SCEV *visit(const SCEV *S) {
591  auto It = RewriteResults.find(S);
592  if (It != RewriteResults.end())
593  return It->second;
594  auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
595  auto Result = RewriteResults.try_emplace(S, Visited);
596  assert(Result.second && "Should insert a new entry");
597  return Result.first->second;
598  }
599 
601  return Constant;
602  }
603 
605  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
606  return Operand == Expr->getOperand()
607  ? Expr
608  : SE.getTruncateExpr(Operand, Expr->getType());
609  }
610 
612  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
613  return Operand == Expr->getOperand()
614  ? Expr
615  : SE.getZeroExtendExpr(Operand, Expr->getType());
616  }
617 
619  const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
620  return Operand == Expr->getOperand()
621  ? Expr
622  : SE.getSignExtendExpr(Operand, Expr->getType());
623  }
624 
625  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
627  bool Changed = false;
628  for (auto *Op : Expr->operands()) {
629  Operands.push_back(((SC*)this)->visit(Op));
630  Changed |= Op != Operands.back();
631  }
632  return !Changed ? Expr : SE.getAddExpr(Operands);
633  }
634 
635  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
637  bool Changed = false;
638  for (auto *Op : Expr->operands()) {
639  Operands.push_back(((SC*)this)->visit(Op));
640  Changed |= Op != Operands.back();
641  }
642  return !Changed ? Expr : SE.getMulExpr(Operands);
643  }
644 
645  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
646  auto *LHS = ((SC *)this)->visit(Expr->getLHS());
647  auto *RHS = ((SC *)this)->visit(Expr->getRHS());
648  bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
649  return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
650  }
651 
652  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
654  bool Changed = false;
655  for (auto *Op : Expr->operands()) {
656  Operands.push_back(((SC*)this)->visit(Op));
657  Changed |= Op != Operands.back();
658  }
659  return !Changed ? Expr
660  : SE.getAddRecExpr(Operands, Expr->getLoop(),
661  Expr->getNoWrapFlags());
662  }
663 
664  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
666  bool Changed = false;
667  for (auto *Op : Expr->operands()) {
668  Operands.push_back(((SC *)this)->visit(Op));
669  Changed |= Op != Operands.back();
670  }
671  return !Changed ? Expr : SE.getSMaxExpr(Operands);
672  }
673 
674  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
676  bool Changed = false;
677  for (auto *Op : Expr->operands()) {
678  Operands.push_back(((SC*)this)->visit(Op));
679  Changed |= Op != Operands.back();
680  }
681  return !Changed ? Expr : SE.getUMaxExpr(Operands);
682  }
683 
684  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
685  return Expr;
686  }
687 
689  return Expr;
690  }
691  };
692 
694 
695  /// The SCEVParameterRewriter takes a scalar evolution expression and updates
696  /// the SCEVUnknown components following the Map (Value -> Value).
697  class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
698  public:
699  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
700  ValueToValueMap &Map,
701  bool InterpretConsts = false) {
702  SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
703  return Rewriter.visit(Scev);
704  }
705 
707  : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
708 
709  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
710  Value *V = Expr->getValue();
711  if (Map.count(V)) {
712  Value *NV = Map[V];
713  if (InterpretConsts && isa<ConstantInt>(NV))
714  return SE.getConstant(cast<ConstantInt>(NV));
715  return SE.getUnknown(NV);
716  }
717  return Expr;
718  }
719 
720  private:
721  ValueToValueMap &Map;
722  bool InterpretConsts;
723  };
724 
726 
727  /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
728  /// the Map (Loop -> SCEV) to all AddRecExprs.
730  : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
731  public:
733  : SCEVRewriteVisitor(SE), Map(M) {}
734 
735  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
736  ScalarEvolution &SE) {
738  return Rewriter.visit(Scev);
739  }
740 
741  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
743  for (const SCEV *Op : Expr->operands())
744  Operands.push_back(visit(Op));
745 
746  const Loop *L = Expr->getLoop();
747  const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
748 
749  if (0 == Map.count(L))
750  return Res;
751 
752  const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
753  return Rec->evaluateAtIteration(Map[L], SE);
754  }
755 
756  private:
757  LoopToScevMapT &Map;
758  };
759 
760 } // end namespace llvm
761 
762 #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:172
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:49
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...
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
DiagnosticInfoOptimizationBase::Argument NV
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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.
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)
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)
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:138
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)
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:46
This is an important base class in LLVM.
Definition: Constant.h:42
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:371
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.
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:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
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:847
This class represents a range of values.
Definition: ConstantRange.h:47
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
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:70
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:222
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:278
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:56
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#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.
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:73
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:81
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:389
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)
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.