LLVM 18.0.0git
ScalarEvolutionExpressions.h
Go to the documentation of this file.
1//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the classes used to represent and build scalar expressions.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
14#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
15
16#include "llvm/ADT/DenseMap.h"
21#include "llvm/IR/Constants.h"
22#include "llvm/IR/ValueHandle.h"
25#include <cassert>
26#include <cstddef>
27
28namespace llvm {
29
30class APInt;
31class Constant;
32class ConstantInt;
33class ConstantRange;
34class Loop;
35class Type;
36class Value;
37
38enum SCEVTypes : unsigned short {
39 // These should be ordered in terms of increasing complexity to make the
40 // folders simpler.
58};
59
60/// This class represents a constant integer value.
61class SCEVConstant : public SCEV {
62 friend class ScalarEvolution;
63
64 ConstantInt *V;
65
67 : SCEV(ID, scConstant, 1), V(v) {}
68
69public:
70 ConstantInt *getValue() const { return V; }
71 const APInt &getAPInt() const { return getValue()->getValue(); }
72
73 Type *getType() const { return V->getType(); }
74
75 /// Methods for support type inquiry through isa, cast, and dyn_cast:
76 static bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; }
77};
78
79/// This class represents the value of vscale, as used when defining the length
80/// of a scalable vector or returned by the llvm.vscale() intrinsic.
81class SCEVVScale : public SCEV {
82 friend class ScalarEvolution;
83
85 : SCEV(ID, scVScale, 0), Ty(ty) {}
86
87 Type *Ty;
88
89public:
90 Type *getType() const { return Ty; }
91
92 /// Methods for support type inquiry through isa, cast, and dyn_cast:
93 static bool classof(const SCEV *S) { return S->getSCEVType() == scVScale; }
94};
95
96inline unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
97 APInt Size(16, 1);
98 for (const auto *Arg : Args)
99 Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
100 return (unsigned short)Size.getZExtValue();
101}
102
103/// This is the base class for unary cast operator classes.
104class SCEVCastExpr : public SCEV {
105protected:
106 const SCEV *Op;
108
109 SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op,
110 Type *ty);
111
112public:
113 const SCEV *getOperand() const { return Op; }
114 const SCEV *getOperand(unsigned i) const {
115 assert(i == 0 && "Operand index out of range!");
116 return Op;
117 }
119 size_t getNumOperands() const { return 1; }
120 Type *getType() const { return Ty; }
121
122 /// Methods for support type inquiry through isa, cast, and dyn_cast:
123 static bool classof(const SCEV *S) {
124 return S->getSCEVType() == scPtrToInt || S->getSCEVType() == scTruncate ||
126 }
127};
128
129/// This class represents a cast from a pointer to a pointer-sized integer
130/// value.
132 friend class ScalarEvolution;
133
134 SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, Type *ITy);
135
136public:
137 /// Methods for support type inquiry through isa, cast, and dyn_cast:
138 static bool classof(const SCEV *S) { return S->getSCEVType() == scPtrToInt; }
139};
140
141/// This is the base class for unary integral cast operator classes.
143protected:
145 const SCEV *op, Type *ty);
146
147public:
148 /// Methods for support type inquiry through isa, cast, and dyn_cast:
149 static bool classof(const SCEV *S) {
150 return S->getSCEVType() == scTruncate || S->getSCEVType() == scZeroExtend ||
152 }
153};
154
155/// This class represents a truncation of an integer value to a
156/// smaller integer value.
158 friend class ScalarEvolution;
159
161
162public:
163 /// Methods for support type inquiry through isa, cast, and dyn_cast:
164 static bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate; }
165};
166
167/// This class represents a zero extension of a small integer value
168/// to a larger integer value.
170 friend class ScalarEvolution;
171
173
174public:
175 /// Methods for support type inquiry through isa, cast, and dyn_cast:
176 static bool classof(const SCEV *S) {
177 return S->getSCEVType() == scZeroExtend;
178 }
179};
180
181/// This class represents a sign extension of a small integer value
182/// to a larger integer value.
184 friend class ScalarEvolution;
185
187
188public:
189 /// Methods for support type inquiry through isa, cast, and dyn_cast:
190 static bool classof(const SCEV *S) {
191 return S->getSCEVType() == scSignExtend;
192 }
193};
194
195/// This node is a base class providing common functionality for
196/// n'ary operators.
197class SCEVNAryExpr : public SCEV {
198protected:
199 // Since SCEVs are immutable, ScalarEvolution allocates operand
200 // arrays with its SCEVAllocator, so this class just needs a simple
201 // pointer rather than a more elaborate vector-like data structure.
202 // This also avoids the need for a non-trivial destructor.
203 const SCEV *const *Operands;
205
207 const SCEV *const *O, size_t N)
209 NumOperands(N) {}
210
211public:
212 size_t getNumOperands() const { return NumOperands; }
213
214 const SCEV *getOperand(unsigned i) const {
215 assert(i < NumOperands && "Operand index out of range!");
216 return Operands[i];
217 }
218
221 }
222
224 return (NoWrapFlags)(SubclassData & Mask);
225 }
226
227 bool hasNoUnsignedWrap() const {
229 }
230
231 bool hasNoSignedWrap() const {
233 }
234
235 bool hasNoSelfWrap() const { return getNoWrapFlags(FlagNW) != FlagAnyWrap; }
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 || S->getSCEVType() == scMulExpr ||
240 S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
241 S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
244 }
245};
246
247/// This node is the base class for n'ary commutative operators.
249protected:
251 const SCEV *const *O, size_t N)
252 : SCEVNAryExpr(ID, T, O, N) {}
253
254public:
255 /// Methods for support type inquiry through isa, cast, and dyn_cast:
256 static bool classof(const SCEV *S) {
257 return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
258 S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
259 S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
260 }
261
262 /// Set flags for a non-recurrence without clearing previously set flags.
263 void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
264};
265
266/// This node represents an addition of some number of SCEVs.
268 friend class ScalarEvolution;
269
270 Type *Ty;
271
272 SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
274 auto *FirstPointerTypedOp = find_if(operands(), [](const SCEV *Op) {
275 return Op->getType()->isPointerTy();
276 });
277 if (FirstPointerTypedOp != operands().end())
278 Ty = (*FirstPointerTypedOp)->getType();
279 else
280 Ty = getOperand(0)->getType();
281 }
282
283public:
284 Type *getType() const { return Ty; }
285
286 /// Methods for support type inquiry through isa, cast, and dyn_cast:
287 static bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr; }
288};
289
290/// This node represents multiplication of some number of SCEVs.
292 friend class ScalarEvolution;
293
294 SCEVMulExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
296
297public:
298 Type *getType() const { return getOperand(0)->getType(); }
299
300 /// Methods for support type inquiry through isa, cast, and dyn_cast:
301 static bool classof(const SCEV *S) { return S->getSCEVType() == scMulExpr; }
302};
303
304/// This class represents a binary unsigned division operation.
305class SCEVUDivExpr : public SCEV {
306 friend class ScalarEvolution;
307
308 std::array<const SCEV *, 2> Operands;
309
310 SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
311 : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})) {
312 Operands[0] = lhs;
313 Operands[1] = rhs;
314 }
315
316public:
317 const SCEV *getLHS() const { return Operands[0]; }
318 const SCEV *getRHS() const { return Operands[1]; }
319 size_t getNumOperands() const { return 2; }
320 const SCEV *getOperand(unsigned i) const {
321 assert((i == 0 || i == 1) && "Operand index out of range!");
322 return i == 0 ? getLHS() : getRHS();
323 }
324
326
327 Type *getType() const {
328 // In most cases the types of LHS and RHS will be the same, but in some
329 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
330 // depend on the type for correctness, but handling types carefully can
331 // avoid extra casts in the SCEVExpander. The LHS is more likely to be
332 // a pointer type than the RHS, so use the RHS' type here.
333 return getRHS()->getType();
334 }
335
336 /// Methods for support type inquiry through isa, cast, and dyn_cast:
337 static bool classof(const SCEV *S) { return S->getSCEVType() == scUDivExpr; }
338};
339
340/// This node represents a polynomial recurrence on the trip count
341/// of the specified loop. This is the primary focus of the
342/// ScalarEvolution framework; all the other SCEV subclasses are
343/// mostly just supporting infrastructure to allow SCEVAddRecExpr
344/// expressions to be created and analyzed.
345///
346/// All operands of an AddRec are required to be loop invariant.
347///
349 friend class ScalarEvolution;
350
351 const Loop *L;
352
353 SCEVAddRecExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N,
354 const Loop *l)
355 : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
356
357public:
358 Type *getType() const { return getStart()->getType(); }
359 const SCEV *getStart() const { return Operands[0]; }
360 const Loop *getLoop() const { return L; }
361
362 /// Constructs and returns the recurrence indicating how much this
363 /// expression steps by. If this is a polynomial of degree N, it
364 /// returns a chrec of degree N-1. We cannot determine whether
365 /// the step recurrence has self-wraparound.
367 if (isAffine())
368 return getOperand(1);
369 return SE.getAddRecExpr(
372 }
373
374 /// Return true if this represents an expression A + B*x where A
375 /// and B are loop invariant values.
376 bool isAffine() const {
377 // We know that the start value is invariant. This expression is thus
378 // affine iff the step is also invariant.
379 return getNumOperands() == 2;
380 }
381
382 /// Return true if this represents an expression A + B*x + C*x^2
383 /// where A, B and C are loop invariant values. This corresponds
384 /// to an addrec of the form {L,+,M,+,N}
385 bool isQuadratic() const { return getNumOperands() == 3; }
386
387 /// Set flags for a recurrence without clearing any previously set flags.
388 /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
389 /// to make it easier to propagate flags.
391 if (Flags & (FlagNUW | FlagNSW))
392 Flags = ScalarEvolution::setFlags(Flags, FlagNW);
393 SubclassData |= Flags;
394 }
395
396 /// Return the value of this chain of recurrences at the specified
397 /// iteration number.
398 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
399
400 /// Return the value of this chain of recurrences at the specified iteration
401 /// number. Takes an explicit list of operands to represent an AddRec.
403 const SCEV *It, ScalarEvolution &SE);
404
405 /// Return the number of iterations of this loop that produce
406 /// values in the specified constant range. Another way of
407 /// looking at this is that it returns the first iteration number
408 /// where the value is not in the condition, thus computing the
409 /// exit count. If the iteration count can't be computed, an
410 /// instance of SCEVCouldNotCompute is returned.
411 const SCEV *getNumIterationsInRange(const ConstantRange &Range,
412 ScalarEvolution &SE) const;
413
414 /// Return an expression representing the value of this expression
415 /// one iteration of the loop ahead.
417
418 /// Methods for support type inquiry through isa, cast, and dyn_cast:
419 static bool classof(const SCEV *S) {
420 return S->getSCEVType() == scAddRecExpr;
421 }
422};
423
424/// This node is the base class min/max selections.
426 friend class ScalarEvolution;
427
428 static bool isMinMaxType(enum SCEVTypes T) {
429 return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
430 T == scUMinExpr;
431 }
432
433protected:
434 /// Note: Constructing subclasses via this constructor is allowed
436 const SCEV *const *O, size_t N)
437 : SCEVCommutativeExpr(ID, T, O, N) {
438 assert(isMinMaxType(T));
439 // Min and max never overflow
441 }
442
443public:
444 Type *getType() const { return getOperand(0)->getType(); }
445
446 static bool classof(const SCEV *S) { return isMinMaxType(S->getSCEVType()); }
447
448 static enum SCEVTypes negate(enum SCEVTypes T) {
449 switch (T) {
450 case scSMaxExpr:
451 return scSMinExpr;
452 case scSMinExpr:
453 return scSMaxExpr;
454 case scUMaxExpr:
455 return scUMinExpr;
456 case scUMinExpr:
457 return scUMaxExpr;
458 default:
459 llvm_unreachable("Not a min or max SCEV type!");
460 }
461 }
462};
463
464/// This class represents a signed maximum selection.
466 friend class ScalarEvolution;
467
468 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
469 : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
470
471public:
472 /// Methods for support type inquiry through isa, cast, and dyn_cast:
473 static bool classof(const SCEV *S) { return S->getSCEVType() == scSMaxExpr; }
474};
475
476/// This class represents an unsigned maximum selection.
478 friend class ScalarEvolution;
479
480 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
481 : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
482
483public:
484 /// Methods for support type inquiry through isa, cast, and dyn_cast:
485 static bool classof(const SCEV *S) { return S->getSCEVType() == scUMaxExpr; }
486};
487
488/// This class represents a signed minimum selection.
490 friend class ScalarEvolution;
491
492 SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
493 : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
494
495public:
496 /// Methods for support type inquiry through isa, cast, and dyn_cast:
497 static bool classof(const SCEV *S) { return S->getSCEVType() == scSMinExpr; }
498};
499
500/// This class represents an unsigned minimum selection.
502 friend class ScalarEvolution;
503
504 SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
505 : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
506
507public:
508 /// Methods for support type inquiry through isa, cast, and dyn_cast:
509 static bool classof(const SCEV *S) { return S->getSCEVType() == scUMinExpr; }
510};
511
512/// This node is the base class for sequential/in-order min/max selections.
513/// Note that their fundamental difference from SCEVMinMaxExpr's is that they
514/// are early-returning upon reaching saturation point.
515/// I.e. given `0 umin_seq poison`, the result will be `0`,
516/// while the result of `0 umin poison` is `poison`.
518 friend class ScalarEvolution;
519
520 static bool isSequentialMinMaxType(enum SCEVTypes T) {
521 return T == scSequentialUMinExpr;
522 }
523
524 /// Set flags for a non-recurrence without clearing previously set flags.
525 void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
526
527protected:
528 /// Note: Constructing subclasses via this constructor is allowed
530 const SCEV *const *O, size_t N)
531 : SCEVNAryExpr(ID, T, O, N) {
532 assert(isSequentialMinMaxType(T));
533 // Min and max never overflow
534 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
535 }
536
537public:
538 Type *getType() const { return getOperand(0)->getType(); }
539
541 assert(isSequentialMinMaxType(Ty));
542 switch (Ty) {
544 return scUMinExpr;
545 default:
546 llvm_unreachable("Not a sequential min/max type.");
547 }
548 }
549
552 }
553
554 static bool classof(const SCEV *S) {
555 return isSequentialMinMaxType(S->getSCEVType());
556 }
557};
558
559/// This class represents a sequential/in-order unsigned minimum selection.
561 friend class ScalarEvolution;
562
563 SCEVSequentialUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O,
564 size_t N)
566
567public:
568 /// Methods for support type inquiry through isa, cast, and dyn_cast:
569 static bool classof(const SCEV *S) {
570 return S->getSCEVType() == scSequentialUMinExpr;
571 }
572};
573
574/// This means that we are dealing with an entirely unknown SCEV
575/// value, and only represent it as its LLVM Value. This is the
576/// "bottom" value for the analysis.
577class SCEVUnknown final : public SCEV, private CallbackVH {
578 friend class ScalarEvolution;
579
580 /// The parent ScalarEvolution value. This is used to update the
581 /// parent's maps when the value associated with a SCEVUnknown is
582 /// deleted or RAUW'd.
583 ScalarEvolution *SE;
584
585 /// The next pointer in the linked list of all SCEVUnknown
586 /// instances owned by a ScalarEvolution.
587 SCEVUnknown *Next;
588
590 SCEVUnknown *next)
591 : SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
592
593 // Implement CallbackVH.
594 void deleted() override;
595 void allUsesReplacedWith(Value *New) override;
596
597public:
598 Value *getValue() const { return getValPtr(); }
599
600 Type *getType() const { return getValPtr()->getType(); }
601
602 /// Methods for support type inquiry through isa, cast, and dyn_cast:
603 static bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; }
604};
605
606/// This class defines a simple visitor class that may be used for
607/// various SCEV analysis purposes.
608template <typename SC, typename RetVal = void> struct SCEVVisitor {
609 RetVal visit(const SCEV *S) {
610 switch (S->getSCEVType()) {
611 case scConstant:
612 return ((SC *)this)->visitConstant((const SCEVConstant *)S);
613 case scVScale:
614 return ((SC *)this)->visitVScale((const SCEVVScale *)S);
615 case scPtrToInt:
616 return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
617 case scTruncate:
618 return ((SC *)this)->visitTruncateExpr((const SCEVTruncateExpr *)S);
619 case scZeroExtend:
620 return ((SC *)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr *)S);
621 case scSignExtend:
622 return ((SC *)this)->visitSignExtendExpr((const SCEVSignExtendExpr *)S);
623 case scAddExpr:
624 return ((SC *)this)->visitAddExpr((const SCEVAddExpr *)S);
625 case scMulExpr:
626 return ((SC *)this)->visitMulExpr((const SCEVMulExpr *)S);
627 case scUDivExpr:
628 return ((SC *)this)->visitUDivExpr((const SCEVUDivExpr *)S);
629 case scAddRecExpr:
630 return ((SC *)this)->visitAddRecExpr((const SCEVAddRecExpr *)S);
631 case scSMaxExpr:
632 return ((SC *)this)->visitSMaxExpr((const SCEVSMaxExpr *)S);
633 case scUMaxExpr:
634 return ((SC *)this)->visitUMaxExpr((const SCEVUMaxExpr *)S);
635 case scSMinExpr:
636 return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
637 case scUMinExpr:
638 return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
640 return ((SC *)this)
641 ->visitSequentialUMinExpr((const SCEVSequentialUMinExpr *)S);
642 case scUnknown:
643 return ((SC *)this)->visitUnknown((const SCEVUnknown *)S);
645 return ((SC *)this)->visitCouldNotCompute((const SCEVCouldNotCompute *)S);
646 }
647 llvm_unreachable("Unknown SCEV kind!");
648 }
649
651 llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
652 }
653};
654
655/// Visit all nodes in the expression tree using worklist traversal.
656///
657/// Visitor implements:
658/// // return true to follow this node.
659/// bool follow(const SCEV *S);
660/// // return true to terminate the search.
661/// bool isDone();
662template <typename SV> class SCEVTraversal {
663 SV &Visitor;
666
667 void push(const SCEV *S) {
668 if (Visited.insert(S).second && Visitor.follow(S))
669 Worklist.push_back(S);
670 }
671
672public:
673 SCEVTraversal(SV &V) : Visitor(V) {}
674
675 void visitAll(const SCEV *Root) {
676 push(Root);
677 while (!Worklist.empty() && !Visitor.isDone()) {
678 const SCEV *S = Worklist.pop_back_val();
679
680 switch (S->getSCEVType()) {
681 case scConstant:
682 case scVScale:
683 case scUnknown:
684 continue;
685 case scPtrToInt:
686 case scTruncate:
687 case scZeroExtend:
688 case scSignExtend:
689 case scAddExpr:
690 case scMulExpr:
691 case scUDivExpr:
692 case scSMaxExpr:
693 case scUMaxExpr:
694 case scSMinExpr:
695 case scUMinExpr:
697 case scAddRecExpr:
698 for (const auto *Op : S->operands()) {
699 push(Op);
700 if (Visitor.isDone())
701 break;
702 }
703 continue;
705 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
706 }
707 llvm_unreachable("Unknown SCEV kind!");
708 }
709 }
710};
711
712/// Use SCEVTraversal to visit all nodes in the given expression tree.
713template <typename SV> void visitAll(const SCEV *Root, SV &Visitor) {
714 SCEVTraversal<SV> T(Visitor);
715 T.visitAll(Root);
716}
717
718/// Return true if any node in \p Root satisfies the predicate \p Pred.
719template <typename PredTy>
720bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
721 struct FindClosure {
722 bool Found = false;
723 PredTy Pred;
724
725 FindClosure(PredTy Pred) : Pred(Pred) {}
726
727 bool follow(const SCEV *S) {
728 if (!Pred(S))
729 return true;
730
731 Found = true;
732 return false;
733 }
734
735 bool isDone() const { return Found; }
736 };
737
738 FindClosure FC(Pred);
739 visitAll(Root, FC);
740 return FC.Found;
741}
742
743/// This visitor recursively visits a SCEV expression and re-writes it.
744/// The result from each visit is cached, so it will return the same
745/// SCEV for the same input.
746template <typename SC>
747class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
748protected:
750 // Memoize the result of each visit so that we only compute once for
751 // the same input SCEV. This is to avoid redundant computations when
752 // a SCEV is referenced by multiple SCEVs. Without memoization, this
753 // visit algorithm would have exponential time complexity in the worst
754 // case, causing the compiler to hang on certain tests.
756
757public:
759
760 const SCEV *visit(const SCEV *S) {
761 auto It = RewriteResults.find(S);
762 if (It != RewriteResults.end())
763 return It->second;
764 auto *Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
765 auto Result = RewriteResults.try_emplace(S, Visited);
766 assert(Result.second && "Should insert a new entry");
767 return Result.first->second;
768 }
769
771
772 const SCEV *visitVScale(const SCEVVScale *VScale) { return VScale; }
773
775 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
776 return Operand == Expr->getOperand()
777 ? Expr
778 : SE.getPtrToIntExpr(Operand, Expr->getType());
779 }
780
782 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
783 return Operand == Expr->getOperand()
784 ? Expr
785 : SE.getTruncateExpr(Operand, Expr->getType());
786 }
787
789 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
790 return Operand == Expr->getOperand()
791 ? Expr
792 : SE.getZeroExtendExpr(Operand, Expr->getType());
793 }
794
796 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
797 return Operand == Expr->getOperand()
798 ? Expr
799 : SE.getSignExtendExpr(Operand, Expr->getType());
800 }
801
802 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
804 bool Changed = false;
805 for (const auto *Op : Expr->operands()) {
806 Operands.push_back(((SC *)this)->visit(Op));
807 Changed |= Op != Operands.back();
808 }
809 return !Changed ? Expr : SE.getAddExpr(Operands);
810 }
811
812 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
814 bool Changed = false;
815 for (const auto *Op : Expr->operands()) {
816 Operands.push_back(((SC *)this)->visit(Op));
817 Changed |= Op != Operands.back();
818 }
819 return !Changed ? Expr : SE.getMulExpr(Operands);
820 }
821
822 const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
823 auto *LHS = ((SC *)this)->visit(Expr->getLHS());
824 auto *RHS = ((SC *)this)->visit(Expr->getRHS());
825 bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
826 return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
827 }
828
829 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
831 bool Changed = false;
832 for (const auto *Op : Expr->operands()) {
833 Operands.push_back(((SC *)this)->visit(Op));
834 Changed |= Op != Operands.back();
835 }
836 return !Changed ? Expr
837 : SE.getAddRecExpr(Operands, Expr->getLoop(),
838 Expr->getNoWrapFlags());
839 }
840
841 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
843 bool Changed = false;
844 for (const auto *Op : Expr->operands()) {
845 Operands.push_back(((SC *)this)->visit(Op));
846 Changed |= Op != Operands.back();
847 }
848 return !Changed ? Expr : SE.getSMaxExpr(Operands);
849 }
850
851 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
853 bool Changed = false;
854 for (const auto *Op : Expr->operands()) {
855 Operands.push_back(((SC *)this)->visit(Op));
856 Changed |= Op != Operands.back();
857 }
858 return !Changed ? Expr : SE.getUMaxExpr(Operands);
859 }
860
861 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
863 bool Changed = false;
864 for (const auto *Op : Expr->operands()) {
865 Operands.push_back(((SC *)this)->visit(Op));
866 Changed |= Op != Operands.back();
867 }
868 return !Changed ? Expr : SE.getSMinExpr(Operands);
869 }
870
871 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
873 bool Changed = false;
874 for (const auto *Op : Expr->operands()) {
875 Operands.push_back(((SC *)this)->visit(Op));
876 Changed |= Op != Operands.back();
877 }
878 return !Changed ? Expr : SE.getUMinExpr(Operands);
879 }
880
883 bool Changed = false;
884 for (const auto *Op : Expr->operands()) {
885 Operands.push_back(((SC *)this)->visit(Op));
886 Changed |= Op != Operands.back();
887 }
888 return !Changed ? Expr : SE.getUMinExpr(Operands, /*Sequential=*/true);
889 }
890
891 const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
892
894 return Expr;
895 }
896};
897
900
901/// The SCEVParameterRewriter takes a scalar evolution expression and updates
902/// the SCEVUnknown components following the Map (Value -> SCEV).
903class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
904public:
905 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
906 ValueToSCEVMapTy &Map) {
908 return Rewriter.visit(Scev);
909 }
910
912 : SCEVRewriteVisitor(SE), Map(M) {}
913
914 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
915 auto I = Map.find(Expr->getValue());
916 if (I == Map.end())
917 return Expr;
918 return I->second;
919 }
920
921private:
922 ValueToSCEVMapTy &Map;
923};
924
926
927/// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
928/// the Map (Loop -> SCEV) to all AddRecExprs.
930 : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
931public:
933 : SCEVRewriteVisitor(SE), Map(M) {}
934
935 static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
938 return Rewriter.visit(Scev);
939 }
940
941 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
943 for (const SCEV *Op : Expr->operands())
944 Operands.push_back(visit(Op));
945
946 const Loop *L = Expr->getLoop();
947 if (0 == Map.count(L))
948 return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
949
951 }
952
953private:
954 LoopToScevMapT &Map;
955};
956
957} // end namespace llvm
958
959#endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
RelocType Type
Definition: COFFYAML.cpp:391
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
uint64_t Size
#define op(i)
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
#define T
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
This class represents a range of values.
Definition: ConstantRange.h:47
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:288
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
This node represents an addition of some number of SCEVs.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
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...
const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This is the base class for unary cast operator classes.
const SCEV * getOperand(unsigned i) const
ArrayRef< const SCEV * > operands() const
const SCEV * getOperand() const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This node is the base class for n'ary commutative operators.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This is the base class for unary integral cast operator classes.
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 ...
static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
static bool classof(const SCEV *S)
This node represents multiplication of some number of SCEVs.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This node is a base class providing common functionality for n'ary operators.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
const SCEV * getOperand(unsigned i) const
const SCEV *const * Operands
ArrayRef< const SCEV * > operands() const
The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...
const SCEV * visitUnknown(const SCEVUnknown *Expr)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)
This class represents a cast from a pointer to a pointer-sized integer value.
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 * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
SmallDenseMap< const SCEV *, const SCEV * > RewriteResults
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
const SCEV * visitVScale(const SCEVVScale *VScale)
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
const SCEV * visitConstant(const SCEVConstant *Constant)
This class represents a signed maximum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a signed minimum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This node is the base class for sequential/in-order min/max selections.
SCEVSequentialMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sequential/in-order unsigned minimum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a sign extension of a small integer value to a larger integer value.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Visit all nodes in the expression tree using worklist traversal.
void visitAll(const SCEV *Root)
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:
This class represents a binary unsigned division operation.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
ArrayRef< const SCEV * > operands() const
const SCEV * getOperand(unsigned i) const
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned maximum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents an unsigned minimum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a zero extension of a small integer value to a larger integer value.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
SCEVTypes getSCEVType() const
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
The main scalar evolution driver.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
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.
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.
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Value * getValPtr() const
Definition: ValueHandle.h:99
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1754
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
#define N
An object of this class is returned by queries that could not be answered.
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
RetVal visit(const SCEV *S)
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)