LLVM 17.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.
57};
58
59/// This class represents a constant integer value.
60class SCEVConstant : public SCEV {
61 friend class ScalarEvolution;
62
63 ConstantInt *V;
64
66 : SCEV(ID, scConstant, 1), V(v) {}
67
68public:
69 ConstantInt *getValue() const { return V; }
70 const APInt &getAPInt() const { return getValue()->getValue(); }
71
72 Type *getType() const { return V->getType(); }
73
74 /// Methods for support type inquiry through isa, cast, and dyn_cast:
75 static bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; }
76};
77
78inline unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
79 APInt Size(16, 1);
80 for (const auto *Arg : Args)
81 Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
82 return (unsigned short)Size.getZExtValue();
83}
84
85/// This is the base class for unary cast operator classes.
86class SCEVCastExpr : public SCEV {
87protected:
88 const SCEV *Op;
90
91 SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op,
92 Type *ty);
93
94public:
95 const SCEV *getOperand() const { return Op; }
96 const SCEV *getOperand(unsigned i) const {
97 assert(i == 0 && "Operand index out of range!");
98 return Op;
99 }
101 size_t getNumOperands() const { return 1; }
102 Type *getType() const { return Ty; }
103
104 /// Methods for support type inquiry through isa, cast, and dyn_cast:
105 static bool classof(const SCEV *S) {
106 return S->getSCEVType() == scPtrToInt || S->getSCEVType() == scTruncate ||
108 }
109};
110
111/// This class represents a cast from a pointer to a pointer-sized integer
112/// value.
114 friend class ScalarEvolution;
115
116 SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, Type *ITy);
117
118public:
119 /// Methods for support type inquiry through isa, cast, and dyn_cast:
120 static bool classof(const SCEV *S) { return S->getSCEVType() == scPtrToInt; }
121};
122
123/// This is the base class for unary integral cast operator classes.
125protected:
127 const SCEV *op, Type *ty);
128
129public:
130 /// Methods for support type inquiry through isa, cast, and dyn_cast:
131 static bool classof(const SCEV *S) {
132 return S->getSCEVType() == scTruncate || S->getSCEVType() == scZeroExtend ||
134 }
135};
136
137/// This class represents a truncation of an integer value to a
138/// smaller integer value.
140 friend class ScalarEvolution;
141
143
144public:
145 /// Methods for support type inquiry through isa, cast, and dyn_cast:
146 static bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate; }
147};
148
149/// This class represents a zero extension of a small integer value
150/// to a larger integer value.
152 friend class ScalarEvolution;
153
155
156public:
157 /// Methods for support type inquiry through isa, cast, and dyn_cast:
158 static bool classof(const SCEV *S) {
159 return S->getSCEVType() == scZeroExtend;
160 }
161};
162
163/// This class represents a sign extension of a small integer value
164/// to a larger integer value.
166 friend class ScalarEvolution;
167
169
170public:
171 /// Methods for support type inquiry through isa, cast, and dyn_cast:
172 static bool classof(const SCEV *S) {
173 return S->getSCEVType() == scSignExtend;
174 }
175};
176
177/// This node is a base class providing common functionality for
178/// n'ary operators.
179class SCEVNAryExpr : public SCEV {
180protected:
181 // Since SCEVs are immutable, ScalarEvolution allocates operand
182 // arrays with its SCEVAllocator, so this class just needs a simple
183 // pointer rather than a more elaborate vector-like data structure.
184 // This also avoids the need for a non-trivial destructor.
185 const SCEV *const *Operands;
187
189 const SCEV *const *O, size_t N)
191 NumOperands(N) {}
192
193public:
194 size_t getNumOperands() const { return NumOperands; }
195
196 const SCEV *getOperand(unsigned i) const {
197 assert(i < NumOperands && "Operand index out of range!");
198 return Operands[i];
199 }
200
203 }
204
206 return (NoWrapFlags)(SubclassData & Mask);
207 }
208
209 bool hasNoUnsignedWrap() const {
211 }
212
213 bool hasNoSignedWrap() const {
215 }
216
217 bool hasNoSelfWrap() const { return getNoWrapFlags(FlagNW) != FlagAnyWrap; }
218
219 /// Methods for support type inquiry through isa, cast, and dyn_cast:
220 static bool classof(const SCEV *S) {
221 return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
222 S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
223 S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
226 }
227};
228
229/// This node is the base class for n'ary commutative operators.
231protected:
233 const SCEV *const *O, size_t N)
234 : SCEVNAryExpr(ID, T, O, N) {}
235
236public:
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;
242 }
243
244 /// Set flags for a non-recurrence without clearing previously set flags.
245 void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
246};
247
248/// This node represents an addition of some number of SCEVs.
250 friend class ScalarEvolution;
251
252 Type *Ty;
253
254 SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
256 auto *FirstPointerTypedOp = find_if(operands(), [](const SCEV *Op) {
257 return Op->getType()->isPointerTy();
258 });
259 if (FirstPointerTypedOp != operands().end())
260 Ty = (*FirstPointerTypedOp)->getType();
261 else
262 Ty = getOperand(0)->getType();
263 }
264
265public:
266 Type *getType() const { return Ty; }
267
268 /// Methods for support type inquiry through isa, cast, and dyn_cast:
269 static bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr; }
270};
271
272/// This node represents multiplication of some number of SCEVs.
274 friend class ScalarEvolution;
275
276 SCEVMulExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
278
279public:
280 Type *getType() const { return getOperand(0)->getType(); }
281
282 /// Methods for support type inquiry through isa, cast, and dyn_cast:
283 static bool classof(const SCEV *S) { return S->getSCEVType() == scMulExpr; }
284};
285
286/// This class represents a binary unsigned division operation.
287class SCEVUDivExpr : public SCEV {
288 friend class ScalarEvolution;
289
290 std::array<const SCEV *, 2> Operands;
291
292 SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
293 : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})) {
294 Operands[0] = lhs;
295 Operands[1] = rhs;
296 }
297
298public:
299 const SCEV *getLHS() const { return Operands[0]; }
300 const SCEV *getRHS() const { return Operands[1]; }
301 size_t getNumOperands() const { return 2; }
302 const SCEV *getOperand(unsigned i) const {
303 assert((i == 0 || i == 1) && "Operand index out of range!");
304 return i == 0 ? getLHS() : getRHS();
305 }
306
308
309 Type *getType() const {
310 // In most cases the types of LHS and RHS will be the same, but in some
311 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
312 // depend on the type for correctness, but handling types carefully can
313 // avoid extra casts in the SCEVExpander. The LHS is more likely to be
314 // a pointer type than the RHS, so use the RHS' type here.
315 return getRHS()->getType();
316 }
317
318 /// Methods for support type inquiry through isa, cast, and dyn_cast:
319 static bool classof(const SCEV *S) { return S->getSCEVType() == scUDivExpr; }
320};
321
322/// This node represents a polynomial recurrence on the trip count
323/// of the specified loop. This is the primary focus of the
324/// ScalarEvolution framework; all the other SCEV subclasses are
325/// mostly just supporting infrastructure to allow SCEVAddRecExpr
326/// expressions to be created and analyzed.
327///
328/// All operands of an AddRec are required to be loop invariant.
329///
331 friend class ScalarEvolution;
332
333 const Loop *L;
334
335 SCEVAddRecExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N,
336 const Loop *l)
337 : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
338
339public:
340 Type *getType() const { return getStart()->getType(); }
341 const SCEV *getStart() const { return Operands[0]; }
342 const Loop *getLoop() const { return L; }
343
344 /// Constructs and returns the recurrence indicating how much this
345 /// expression steps by. If this is a polynomial of degree N, it
346 /// returns a chrec of degree N-1. We cannot determine whether
347 /// the step recurrence has self-wraparound.
349 if (isAffine())
350 return getOperand(1);
351 return SE.getAddRecExpr(
354 }
355
356 /// Return true if this represents an expression A + B*x where A
357 /// and B are loop invariant values.
358 bool isAffine() const {
359 // We know that the start value is invariant. This expression is thus
360 // affine iff the step is also invariant.
361 return getNumOperands() == 2;
362 }
363
364 /// Return true if this represents an expression A + B*x + C*x^2
365 /// where A, B and C are loop invariant values. This corresponds
366 /// to an addrec of the form {L,+,M,+,N}
367 bool isQuadratic() const { return getNumOperands() == 3; }
368
369 /// Set flags for a recurrence without clearing any previously set flags.
370 /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
371 /// to make it easier to propagate flags.
373 if (Flags & (FlagNUW | FlagNSW))
374 Flags = ScalarEvolution::setFlags(Flags, FlagNW);
375 SubclassData |= Flags;
376 }
377
378 /// Return the value of this chain of recurrences at the specified
379 /// iteration number.
380 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
381
382 /// Return the value of this chain of recurrences at the specified iteration
383 /// number. Takes an explicit list of operands to represent an AddRec.
385 const SCEV *It, ScalarEvolution &SE);
386
387 /// Return the number of iterations of this loop that produce
388 /// values in the specified constant range. Another way of
389 /// looking at this is that it returns the first iteration number
390 /// where the value is not in the condition, thus computing the
391 /// exit count. If the iteration count can't be computed, an
392 /// instance of SCEVCouldNotCompute is returned.
393 const SCEV *getNumIterationsInRange(const ConstantRange &Range,
394 ScalarEvolution &SE) const;
395
396 /// Return an expression representing the value of this expression
397 /// one iteration of the loop ahead.
399
400 /// Methods for support type inquiry through isa, cast, and dyn_cast:
401 static bool classof(const SCEV *S) {
402 return S->getSCEVType() == scAddRecExpr;
403 }
404};
405
406/// This node is the base class min/max selections.
408 friend class ScalarEvolution;
409
410 static bool isMinMaxType(enum SCEVTypes T) {
411 return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
412 T == scUMinExpr;
413 }
414
415protected:
416 /// Note: Constructing subclasses via this constructor is allowed
418 const SCEV *const *O, size_t N)
419 : SCEVCommutativeExpr(ID, T, O, N) {
420 assert(isMinMaxType(T));
421 // Min and max never overflow
423 }
424
425public:
426 Type *getType() const { return getOperand(0)->getType(); }
427
428 static bool classof(const SCEV *S) { return isMinMaxType(S->getSCEVType()); }
429
430 static enum SCEVTypes negate(enum SCEVTypes T) {
431 switch (T) {
432 case scSMaxExpr:
433 return scSMinExpr;
434 case scSMinExpr:
435 return scSMaxExpr;
436 case scUMaxExpr:
437 return scUMinExpr;
438 case scUMinExpr:
439 return scUMaxExpr;
440 default:
441 llvm_unreachable("Not a min or max SCEV type!");
442 }
443 }
444};
445
446/// This class represents a signed maximum selection.
448 friend class ScalarEvolution;
449
450 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
451 : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
452
453public:
454 /// Methods for support type inquiry through isa, cast, and dyn_cast:
455 static bool classof(const SCEV *S) { return S->getSCEVType() == scSMaxExpr; }
456};
457
458/// This class represents an unsigned maximum selection.
460 friend class ScalarEvolution;
461
462 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
463 : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
464
465public:
466 /// Methods for support type inquiry through isa, cast, and dyn_cast:
467 static bool classof(const SCEV *S) { return S->getSCEVType() == scUMaxExpr; }
468};
469
470/// This class represents a signed minimum selection.
472 friend class ScalarEvolution;
473
474 SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
475 : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
476
477public:
478 /// Methods for support type inquiry through isa, cast, and dyn_cast:
479 static bool classof(const SCEV *S) { return S->getSCEVType() == scSMinExpr; }
480};
481
482/// This class represents an unsigned minimum selection.
484 friend class ScalarEvolution;
485
486 SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
487 : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
488
489public:
490 /// Methods for support type inquiry through isa, cast, and dyn_cast:
491 static bool classof(const SCEV *S) { return S->getSCEVType() == scUMinExpr; }
492};
493
494/// This node is the base class for sequential/in-order min/max selections.
495/// Note that their fundamental difference from SCEVMinMaxExpr's is that they
496/// are early-returning upon reaching saturation point.
497/// I.e. given `0 umin_seq poison`, the result will be `0`,
498/// while the result of `0 umin poison` is `poison`.
500 friend class ScalarEvolution;
501
502 static bool isSequentialMinMaxType(enum SCEVTypes T) {
503 return T == scSequentialUMinExpr;
504 }
505
506 /// Set flags for a non-recurrence without clearing previously set flags.
507 void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
508
509protected:
510 /// Note: Constructing subclasses via this constructor is allowed
512 const SCEV *const *O, size_t N)
513 : SCEVNAryExpr(ID, T, O, N) {
514 assert(isSequentialMinMaxType(T));
515 // Min and max never overflow
516 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
517 }
518
519public:
520 Type *getType() const { return getOperand(0)->getType(); }
521
523 assert(isSequentialMinMaxType(Ty));
524 switch (Ty) {
526 return scUMinExpr;
527 default:
528 llvm_unreachable("Not a sequential min/max type.");
529 }
530 }
531
534 }
535
536 static bool classof(const SCEV *S) {
537 return isSequentialMinMaxType(S->getSCEVType());
538 }
539};
540
541/// This class represents a sequential/in-order unsigned minimum selection.
543 friend class ScalarEvolution;
544
545 SCEVSequentialUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O,
546 size_t N)
548
549public:
550 /// Methods for support type inquiry through isa, cast, and dyn_cast:
551 static bool classof(const SCEV *S) {
552 return S->getSCEVType() == scSequentialUMinExpr;
553 }
554};
555
556/// This means that we are dealing with an entirely unknown SCEV
557/// value, and only represent it as its LLVM Value. This is the
558/// "bottom" value for the analysis.
559class SCEVUnknown final : public SCEV, private CallbackVH {
560 friend class ScalarEvolution;
561
562 /// The parent ScalarEvolution value. This is used to update the
563 /// parent's maps when the value associated with a SCEVUnknown is
564 /// deleted or RAUW'd.
565 ScalarEvolution *SE;
566
567 /// The next pointer in the linked list of all SCEVUnknown
568 /// instances owned by a ScalarEvolution.
569 SCEVUnknown *Next;
570
572 SCEVUnknown *next)
573 : SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
574
575 // Implement CallbackVH.
576 void deleted() override;
577 void allUsesReplacedWith(Value *New) override;
578
579public:
580 Value *getValue() const { return getValPtr(); }
581
582 /// @{
583 /// Test whether this is a special constant representing a type
584 /// size, alignment, or field offset in a target-independent
585 /// manner, and hasn't happened to have been folded with other
586 /// operations into something unrecognizable. This is mainly only
587 /// useful for pretty-printing and other situations where it isn't
588 /// absolutely required for these to succeed.
589 bool isSizeOf(Type *&AllocTy) const;
590 bool isAlignOf(Type *&AllocTy) const;
591 bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
592 /// @}
593
594 Type *getType() const { return getValPtr()->getType(); }
595
596 /// Methods for support type inquiry through isa, cast, and dyn_cast:
597 static bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; }
598};
599
600/// This class defines a simple visitor class that may be used for
601/// various SCEV analysis purposes.
602template <typename SC, typename RetVal = void> struct SCEVVisitor {
603 RetVal visit(const SCEV *S) {
604 switch (S->getSCEVType()) {
605 case scConstant:
606 return ((SC *)this)->visitConstant((const SCEVConstant *)S);
607 case scPtrToInt:
608 return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
609 case scTruncate:
610 return ((SC *)this)->visitTruncateExpr((const SCEVTruncateExpr *)S);
611 case scZeroExtend:
612 return ((SC *)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr *)S);
613 case scSignExtend:
614 return ((SC *)this)->visitSignExtendExpr((const SCEVSignExtendExpr *)S);
615 case scAddExpr:
616 return ((SC *)this)->visitAddExpr((const SCEVAddExpr *)S);
617 case scMulExpr:
618 return ((SC *)this)->visitMulExpr((const SCEVMulExpr *)S);
619 case scUDivExpr:
620 return ((SC *)this)->visitUDivExpr((const SCEVUDivExpr *)S);
621 case scAddRecExpr:
622 return ((SC *)this)->visitAddRecExpr((const SCEVAddRecExpr *)S);
623 case scSMaxExpr:
624 return ((SC *)this)->visitSMaxExpr((const SCEVSMaxExpr *)S);
625 case scUMaxExpr:
626 return ((SC *)this)->visitUMaxExpr((const SCEVUMaxExpr *)S);
627 case scSMinExpr:
628 return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
629 case scUMinExpr:
630 return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
632 return ((SC *)this)
633 ->visitSequentialUMinExpr((const SCEVSequentialUMinExpr *)S);
634 case scUnknown:
635 return ((SC *)this)->visitUnknown((const SCEVUnknown *)S);
637 return ((SC *)this)->visitCouldNotCompute((const SCEVCouldNotCompute *)S);
638 }
639 llvm_unreachable("Unknown SCEV kind!");
640 }
641
643 llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
644 }
645};
646
647/// Visit all nodes in the expression tree using worklist traversal.
648///
649/// Visitor implements:
650/// // return true to follow this node.
651/// bool follow(const SCEV *S);
652/// // return true to terminate the search.
653/// bool isDone();
654template <typename SV> class SCEVTraversal {
655 SV &Visitor;
658
659 void push(const SCEV *S) {
660 if (Visited.insert(S).second && Visitor.follow(S))
661 Worklist.push_back(S);
662 }
663
664public:
665 SCEVTraversal(SV &V) : Visitor(V) {}
666
667 void visitAll(const SCEV *Root) {
668 push(Root);
669 while (!Worklist.empty() && !Visitor.isDone()) {
670 const SCEV *S = Worklist.pop_back_val();
671
672 switch (S->getSCEVType()) {
673 case scConstant:
674 case scUnknown:
675 continue;
676 case scPtrToInt:
677 case scTruncate:
678 case scZeroExtend:
679 case scSignExtend:
680 case scAddExpr:
681 case scMulExpr:
682 case scUDivExpr:
683 case scSMaxExpr:
684 case scUMaxExpr:
685 case scSMinExpr:
686 case scUMinExpr:
688 case scAddRecExpr:
689 for (const auto *Op : S->operands()) {
690 push(Op);
691 if (Visitor.isDone())
692 break;
693 }
694 continue;
696 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
697 }
698 llvm_unreachable("Unknown SCEV kind!");
699 }
700 }
701};
702
703/// Use SCEVTraversal to visit all nodes in the given expression tree.
704template <typename SV> void visitAll(const SCEV *Root, SV &Visitor) {
705 SCEVTraversal<SV> T(Visitor);
706 T.visitAll(Root);
707}
708
709/// Return true if any node in \p Root satisfies the predicate \p Pred.
710template <typename PredTy>
711bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
712 struct FindClosure {
713 bool Found = false;
714 PredTy Pred;
715
716 FindClosure(PredTy Pred) : Pred(Pred) {}
717
718 bool follow(const SCEV *S) {
719 if (!Pred(S))
720 return true;
721
722 Found = true;
723 return false;
724 }
725
726 bool isDone() const { return Found; }
727 };
728
729 FindClosure FC(Pred);
730 visitAll(Root, FC);
731 return FC.Found;
732}
733
734/// This visitor recursively visits a SCEV expression and re-writes it.
735/// The result from each visit is cached, so it will return the same
736/// SCEV for the same input.
737template <typename SC>
738class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
739protected:
741 // Memoize the result of each visit so that we only compute once for
742 // the same input SCEV. This is to avoid redundant computations when
743 // a SCEV is referenced by multiple SCEVs. Without memoization, this
744 // visit algorithm would have exponential time complexity in the worst
745 // case, causing the compiler to hang on certain tests.
747
748public:
750
751 const SCEV *visit(const SCEV *S) {
752 auto It = RewriteResults.find(S);
753 if (It != RewriteResults.end())
754 return It->second;
755 auto *Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
756 auto Result = RewriteResults.try_emplace(S, Visited);
757 assert(Result.second && "Should insert a new entry");
758 return Result.first->second;
759 }
760
762
764 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
765 return Operand == Expr->getOperand()
766 ? Expr
767 : SE.getPtrToIntExpr(Operand, Expr->getType());
768 }
769
771 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
772 return Operand == Expr->getOperand()
773 ? Expr
774 : SE.getTruncateExpr(Operand, Expr->getType());
775 }
776
778 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
779 return Operand == Expr->getOperand()
780 ? Expr
781 : SE.getZeroExtendExpr(Operand, Expr->getType());
782 }
783
785 const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
786 return Operand == Expr->getOperand()
787 ? Expr
788 : SE.getSignExtendExpr(Operand, Expr->getType());
789 }
790
791 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
793 bool Changed = false;
794 for (const auto *Op : Expr->operands()) {
795 Operands.push_back(((SC *)this)->visit(Op));
796 Changed |= Op != Operands.back();
797 }
798 return !Changed ? Expr : SE.getAddExpr(Operands);
799 }
800
801 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
803 bool Changed = false;
804 for (const auto *Op : Expr->operands()) {
805 Operands.push_back(((SC *)this)->visit(Op));
806 Changed |= Op != Operands.back();
807 }
808 return !Changed ? Expr : SE.getMulExpr(Operands);
809 }
810
811 const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
812 auto *LHS = ((SC *)this)->visit(Expr->getLHS());
813 auto *RHS = ((SC *)this)->visit(Expr->getRHS());
814 bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
815 return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
816 }
817
818 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
820 bool Changed = false;
821 for (const auto *Op : Expr->operands()) {
822 Operands.push_back(((SC *)this)->visit(Op));
823 Changed |= Op != Operands.back();
824 }
825 return !Changed ? Expr
826 : SE.getAddRecExpr(Operands, Expr->getLoop(),
827 Expr->getNoWrapFlags());
828 }
829
830 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
832 bool Changed = false;
833 for (const auto *Op : Expr->operands()) {
834 Operands.push_back(((SC *)this)->visit(Op));
835 Changed |= Op != Operands.back();
836 }
837 return !Changed ? Expr : SE.getSMaxExpr(Operands);
838 }
839
840 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
842 bool Changed = false;
843 for (const auto *Op : Expr->operands()) {
844 Operands.push_back(((SC *)this)->visit(Op));
845 Changed |= Op != Operands.back();
846 }
847 return !Changed ? Expr : SE.getUMaxExpr(Operands);
848 }
849
850 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
852 bool Changed = false;
853 for (const auto *Op : Expr->operands()) {
854 Operands.push_back(((SC *)this)->visit(Op));
855 Changed |= Op != Operands.back();
856 }
857 return !Changed ? Expr : SE.getSMinExpr(Operands);
858 }
859
860 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
862 bool Changed = false;
863 for (const auto *Op : Expr->operands()) {
864 Operands.push_back(((SC *)this)->visit(Op));
865 Changed |= Op != Operands.back();
866 }
867 return !Changed ? Expr : SE.getUMinExpr(Operands);
868 }
869
872 bool Changed = false;
873 for (const auto *Op : Expr->operands()) {
874 Operands.push_back(((SC *)this)->visit(Op));
875 Changed |= Op != Operands.back();
876 }
877 return !Changed ? Expr : SE.getUMinExpr(Operands, /*Sequential=*/true);
878 }
879
880 const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
881
883 return Expr;
884 }
885};
886
889
890/// The SCEVParameterRewriter takes a scalar evolution expression and updates
891/// the SCEVUnknown components following the Map (Value -> SCEV).
892class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
893public:
894 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
895 ValueToSCEVMapTy &Map) {
897 return Rewriter.visit(Scev);
898 }
899
901 : SCEVRewriteVisitor(SE), Map(M) {}
902
903 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
904 auto I = Map.find(Expr->getValue());
905 if (I == Map.end())
906 return Expr;
907 return I->second;
908 }
909
910private:
911 ValueToSCEVMapTy &Map;
912};
913
915
916/// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
917/// the Map (Loop -> SCEV) to all AddRecExprs.
919 : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
920public:
922 : SCEVRewriteVisitor(SE), Map(M) {}
923
924 static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
927 return Rewriter.visit(Scev);
928 }
929
930 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
932 for (const SCEV *Op : Expr->operands())
933 Operands.push_back(visit(Op));
934
935 const Loop *L = Expr->getLoop();
936 if (0 == Map.count(L))
937 return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
938
940 }
941
942private:
943 LoopToScevMapT &Map;
944};
945
946} // end namespace llvm
947
948#endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
RelocType Type
Definition: COFFYAML.cpp:390
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:75
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
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:132
This class represents a range of values.
Definition: ConstantRange.h:47
This is an important base class in LLVM.
Definition: Constant.h:41
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
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:145
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:547
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)
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 * visitAddRecExpr(const SCEVAddRecExpr *Expr)
DenseMap< const SCEV *, const SCEV * > RewriteResults
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...
bool isSizeOf(Type *&AllocTy) const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool isAlignOf(Type *&AllocTy) const
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:1762
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)