LLVM 20.0.0git
Interval.h
Go to the documentation of this file.
1//===- Interval.h -----------------------------------------------*- 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// The Interval class is a generic interval of ordered objects that implement:
10// - T * T::getPrevNode()
11// - T * T::getNextNode()
12// - bool T::comesBefore(const T *) const
13//
14// This is currently used for Instruction intervals.
15// It provides an API for some basic operations on the interval, including some
16// simple set operations, like union, intersection and others.
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H
21#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H
22
23#include "llvm/ADT/ArrayRef.h"
26#include <iterator>
27#include <type_traits>
28
29namespace llvm::sandboxir {
30
31/// A simple iterator for iterating the interval.
32template <typename T, typename IntervalType> class IntervalIterator {
33 T *I;
34 IntervalType &R;
35
36public:
37 using difference_type = std::ptrdiff_t;
38 using value_type = T;
40 using reference = T &;
41 using iterator_category = std::bidirectional_iterator_tag;
42
43 IntervalIterator(T *I, IntervalType &R) : I(I), R(R) {}
44 bool operator==(const IntervalIterator &Other) const {
45 assert(&R == &Other.R && "Iterators belong to different regions!");
46 return Other.I == I;
47 }
48 bool operator!=(const IntervalIterator &Other) const {
49 return !(*this == Other);
50 }
52 assert(I != nullptr && "already at end()!");
53 I = I->getNextNode();
54 return *this;
55 }
57 auto ItCopy = *this;
58 ++*this;
59 return ItCopy;
60 }
62 // `I` is nullptr for end() when To is the BB terminator.
63 I = I != nullptr ? I->getPrevNode() : R.bottom();
64 return *this;
65 }
67 auto ItCopy = *this;
68 --*this;
69 return ItCopy;
70 }
71 template <typename HT = std::enable_if<std::is_same<T, T *&>::value>>
73 return *I;
74 }
75 T &operator*() const { return *I; }
76};
77
78template <typename T> class Interval {
79 T *Top;
80 T *Bottom;
81
82public:
83 Interval() : Top(nullptr), Bottom(nullptr) {}
84 Interval(T *Top, T *Bottom) : Top(Top), Bottom(Bottom) {
85 assert((Top == Bottom || Top->comesBefore(Bottom)) &&
86 "Top should come before Bottom!");
87 }
89 assert(!Elems.empty() && "Expected non-empty Elems!");
90 Top = Elems[0];
91 Bottom = Elems[0];
92 for (auto *I : drop_begin(Elems)) {
93 if (I->comesBefore(Top))
94 Top = I;
95 else if (Bottom->comesBefore(I))
96 Bottom = I;
97 }
98 }
99 bool empty() const {
100 assert(((Top == nullptr && Bottom == nullptr) ||
101 (Top != nullptr && Bottom != nullptr)) &&
102 "Either none or both should be null");
103 return Top == nullptr;
104 }
105 bool contains(T *I) const {
106 if (empty())
107 return false;
108 return (Top == I || Top->comesBefore(I)) &&
109 (I == Bottom || I->comesBefore(Bottom));
110 }
111 T *top() const { return Top; }
112 T *bottom() const { return Bottom; }
113
115 iterator begin() { return iterator(Top, *this); }
117 return iterator(Bottom != nullptr ? Bottom->getNextNode() : nullptr, *this);
118 }
119 iterator begin() const {
120 return iterator(Top, const_cast<Interval &>(*this));
121 }
122 iterator end() const {
123 return iterator(Bottom != nullptr ? Bottom->getNextNode() : nullptr,
124 const_cast<Interval &>(*this));
125 }
126 /// Equality.
127 bool operator==(const Interval &Other) const {
128 return Top == Other.Top && Bottom == Other.Bottom;
129 }
130 /// Inequality.
131 bool operator!=(const Interval &Other) const { return !(*this == Other); }
132 /// \Returns true if this interval comes before \p Other in program order.
133 /// This expects disjoint intervals.
134 bool comesBefore(const Interval &Other) const {
135 assert(disjoint(Other) && "Expect disjoint intervals!");
136 return bottom()->comesBefore(Other.top());
137 }
138 /// \Returns true if this and \p Other have nothing in common.
139 bool disjoint(const Interval &Other) const;
140 /// \Returns the intersection between this and \p Other.
141 // Example:
142 // |----| this
143 // |---| Other
144 // |-| this->getIntersection(Other)
146 if (empty())
147 return *this;
148 if (Other.empty())
149 return Interval();
150 // 1. No overlap
151 // A---B this
152 // C--D Other
153 if (Bottom->comesBefore(Other.Top) || Other.Bottom->comesBefore(Top))
154 return Interval();
155 // 2. Overlap.
156 // A---B this
157 // C--D Other
158 auto NewTopI = Top->comesBefore(Other.Top) ? Other.Top : Top;
159 auto NewBottomI = Bottom->comesBefore(Other.Bottom) ? Bottom : Other.Bottom;
160 return Interval(NewTopI, NewBottomI);
161 }
162 /// Difference operation. This returns up to two intervals.
163 // Example:
164 // |--------| this
165 // |-| Other
166 // |-| |--| this - Other
168 if (disjoint(Other))
169 return {*this};
170 if (Other.empty())
171 return {*this};
172 if (*this == Other)
173 return {Interval()};
174 Interval Intersection = intersection(Other);
176 // Part 1, skip if empty.
177 if (Top != Intersection.Top)
178 Result.emplace_back(Top, Intersection.Top->getPrevNode());
179 // Part 2, skip if empty.
180 if (Intersection.Bottom != Bottom)
181 Result.emplace_back(Intersection.Bottom->getNextNode(), Bottom);
182 return Result;
183 }
184 /// \Returns the interval difference `this - Other`. This will crash in Debug
185 /// if the result is not a single interval.
187 auto Diff = *this - Other;
188 assert(Diff.size() == 1 && "Expected a single interval!");
189 return Diff[0];
190 }
191 /// \Returns a single interval that spans across both this and \p Other.
192 // For example:
193 // |---| this
194 // |---| Other
195 // |----------| this->getUnionInterval(Other)
197 if (empty())
198 return Other;
199 if (Other.empty())
200 return *this;
201 auto *NewTop = Top->comesBefore(Other.Top) ? Top : Other.Top;
202 auto *NewBottom = Bottom->comesBefore(Other.Bottom) ? Other.Bottom : Bottom;
203 return {NewTop, NewBottom};
204 }
205
206 /// Update the interval when \p I is about to be moved before \p Before.
207 // SFINAE disables this for non-Instructions.
208 template <typename HelperT = T>
209 std::enable_if_t<std::is_same<HelperT, Instruction>::value, void>
210 notifyMoveInstr(HelperT *I, decltype(I->getIterator()) BeforeIt) {
211 assert(contains(I) && "Expect `I` in interval!");
212 assert(I->getIterator() != BeforeIt && "Can't move `I` before itself!");
213
214 // Nothing to do if the instruction won't move.
215 if (std::next(I->getIterator()) == BeforeIt)
216 return;
217
218 T *NewTop = Top->getIterator() == BeforeIt ? I
219 : I == Top ? Top->getNextNode()
220 : Top;
221 T *NewBottom = std::next(Bottom->getIterator()) == BeforeIt ? I
222 : I == Bottom ? Bottom->getPrevNode()
223 : Bottom;
224 Top = NewTop;
225 Bottom = NewBottom;
226 }
227
228#ifndef NDEBUG
229 void print(raw_ostream &OS) const;
230 LLVM_DUMP_METHOD void dump() const;
231#endif
232};
233
234} // namespace llvm::sandboxir
235
236#endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_INSTRINTERVAL_H
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:622
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:163
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A simple iterator for iterating the interval.
Definition: Interval.h:32
bool operator!=(const IntervalIterator &Other) const
Definition: Interval.h:48
IntervalIterator & operator--()
Definition: Interval.h:61
IntervalIterator(T *I, IntervalType &R)
Definition: Interval.h:43
std::bidirectional_iterator_tag iterator_category
Definition: Interval.h:41
bool operator==(const IntervalIterator &Other) const
Definition: Interval.h:44
IntervalIterator operator++(int)
Definition: Interval.h:56
std::ptrdiff_t difference_type
Definition: Interval.h:37
IntervalIterator & operator++()
Definition: Interval.h:51
IntervalIterator operator--(int)
Definition: Interval.h:66
Interval(T *Top, T *Bottom)
Definition: Interval.h:84
SmallVector< Interval, 2 > operator-(const Interval &Other)
Difference operation. This returns up to two intervals.
Definition: Interval.h:167
bool operator==(const Interval &Other) const
Equality.
Definition: Interval.h:127
Interval getUnionInterval(const Interval &Other)
\Returns a single interval that spans across both this and Other.
Definition: Interval.h:196
LLVM_DUMP_METHOD void dump() const
Definition: Interval.cpp:42
bool contains(T *I) const
Definition: Interval.h:105
Interval getSingleDiff(const Interval &Other)
\Returns the interval difference this - Other.
Definition: Interval.h:186
bool operator!=(const Interval &Other) const
Inequality.
Definition: Interval.h:131
Interval(ArrayRef< T * > Elems)
Definition: Interval.h:88
IntervalIterator< T, Interval > iterator
Definition: Interval.h:114
iterator end() const
Definition: Interval.h:122
bool empty() const
Definition: Interval.h:99
bool disjoint(const Interval &Other) const
\Returns true if this and Other have nothing in common.
Definition: Interval.cpp:16
bool comesBefore(const Interval &Other) const
\Returns true if this interval comes before Other in program order.
Definition: Interval.h:134
void print(raw_ostream &OS) const
Definition: Interval.cpp:25
iterator begin() const
Definition: Interval.h:119
Interval intersection(const Interval &Other) const
\Returns the intersection between this and Other.
Definition: Interval.h:145
std::enable_if_t< std::is_same< HelperT, Instruction >::value, void > notifyMoveInstr(HelperT *I, decltype(I->getIterator()) BeforeIt)
Update the interval when I is about to be moved before Before.
Definition: Interval.h:210
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
@ Other
Any other memory.