Halide 22.0.0 Halide compiler and libraries

Scope.h
Go to the documentation of this file.
1#ifndef HALIDE_SCOPE_H
2#define HALIDE_SCOPE_H
3
4#include <iostream>
5#include <map>
6#include <stack>
7#include <string>
8#include <utility>
9#include <vector>
10
11#include "Debug.h"
12#include "Error.h"
13
14/** \file
15 * Defines the Scope class, which is used for keeping track of names in a scope while traversing IR
16 */
17
18namespace Halide {
19namespace Internal {
20
21/** A stack which can store one item very efficiently. Using this
22 * instead of std::stack speeds up Scope substantially. */
23template<typename T>
24 class SmallStack {
25private:
26 T _top;
27 std::vector<T> _rest;
28 bool _empty = true;
29
30public:
31 SmallStack() = default;
32
33 void pop() {
34 if (_rest.empty()) {
35 _empty = true;
36 _top = T();
37 } else {
38 _top = std::move(_rest.back());
39 _rest.pop_back();
40 }
41 }
42
43 void push(T t) {
44 if (!_empty) {
45 _rest.push_back(std::move(_top));
46 }
47 _top = std::move(t);
48 _empty = false;
49 }
50
51 T top() const {
52 return _top;
53 }
54
55 T &top_ref() {
56 return _top;
57 }
58
59 const T &top_ref() const {
60 return _top;
61 }
62
63 bool empty() const {
64 return _empty;
65 }
66
67 size_t size() const {
68 return _empty ? 0 : (_rest.size() + 1);
69 }
70};
71
72template<>
73 class SmallStack<void> {
74 // A stack of voids. Voids are all the same, so just record how many voids are in the stack
75 int counter = 0;
76
77public:
78 void pop() {
79 counter--;
80 }
81 void push() {
82 counter++;
83 }
84 bool empty() const {
85 return counter == 0;
86 }
87};
88
89/** A common pattern when traversing Halide IR is that you need to
90 * keep track of stuff when you find a Let or a LetStmt, and that it
91 * should hide previous values with the same name until you leave the
92 * Let or LetStmt nodes This class helps with that. */
93template<typename T = void>
94 class Scope {
95private:
96 std::map<std::string, SmallStack<T>> table;
97
98 const Scope<T> *containing_scope = nullptr;
99
100public:
101 Scope() = default;
102 Scope(Scope &&that) noexcept = default;
103 Scope &operator=(Scope &&that) noexcept = default;
104
105 // Copying a scope object copies a large table full of strings and
106 // stacks. Bad idea.
107 Scope(const Scope<T> &) = delete;
108 Scope<T> &operator=(const Scope<T> &) = delete;
109
110 /** Set the parent scope. If lookups fail in this scope, they
111 * check the containing scope before returning an error. Caller is
112 * responsible for managing the memory of the containing scope. */
113 void set_containing_scope(const Scope<T> *s) {
114 containing_scope = s;
115 }
116
117 /** A const ref to an empty scope. Useful for default function
118 * arguments, which would otherwise require a copy constructor
119 * (with llvm in c++98 mode) */
120 static const Scope<T> &empty_scope() {
121 static Scope<T> _empty_scope;
122 return _empty_scope;
123 }
124
125 /** Retrieve the value referred to by a name */
126 template<typename T2 = T,
127 typename = std::enable_if_t<!std::is_void_v<T2>>>
128 T2 get(const std::string &name) const {
129 typename std::map<std::string, SmallStack<T>>::const_iterator iter = table.find(name);
130 if (iter == table.end() || iter->second.empty()) {
131 if (containing_scope) {
132 return containing_scope->get(name);
133 } else {
134 internal_error << "Name not in Scope: " << name << "\n"
135 << *this << "\n";
136 }
137 }
138 return iter->second.top();
139 }
140
141 /** Return a reference to an entry. Does not consider the containing scope. */
142 template<typename T2 = T,
143 typename = std::enable_if_t<!std::is_void_v<T2>>>
144 T2 &ref(const std::string &name) {
145 typename std::map<std::string, SmallStack<T>>::iterator iter = table.find(name);
146 if (iter == table.end() || iter->second.empty()) {
147 internal_error << "Name not in Scope: " << name << "\n"
148 << *this << "\n";
149 }
150 return iter->second.top_ref();
151 }
152
153 /** Returns a const pointer to an entry if it exists in this scope or any
154 * containing scope, or nullptr if it does not. Use this instead of if
155 * (scope.contains(foo)) { ... scope.get(foo) ... } to avoid doing two
156 * lookups. */
157 template<typename T2 = T,
158 typename = std::enable_if_t<!std::is_void_v<T2>>>
159 const T2 *find(const std::string &name) const {
160 typename std::map<std::string, SmallStack<T>>::const_iterator iter = table.find(name);
161 if (iter == table.end() || iter->second.empty()) {
162 if (containing_scope) {
163 return containing_scope->find(name);
164 } else {
165 return nullptr;
166 }
167 }
168 return &(iter->second.top_ref());
169 }
170
171 /** A version of find that returns a non-const pointer, but ignores
172 * containing scope. */
173 template<typename T2 = T,
174 typename = std::enable_if_t<!std::is_void_v<T2>>>
175 T2 *shallow_find(const std::string &name) {
176 typename std::map<std::string, SmallStack<T>>::iterator iter = table.find(name);
177 if (iter == table.end() || iter->second.empty()) {
178 return nullptr;
179 } else {
180 return &(iter->second.top_ref());
181 }
182 }
183
184 /** Tests if a name is in scope. If you plan to use the value if it is, call
185 * find instead. */
186 bool contains(const std::string &name) const {
187 typename std::map<std::string, SmallStack<T>>::const_iterator iter = table.find(name);
188 if (iter == table.end() || iter->second.empty()) {
189 if (containing_scope) {
190 return containing_scope->contains(name);
191 } else {
192 return false;
193 }
194 }
195 return true;
196 }
197
198 /** How many nested definitions of a single name exist? */
199 size_t count(const std::string &name) const {
200 auto it = table.find(name);
201 if (it == table.end()) {
202 return 0;
203 } else {
204 return it->second.size();
205 }
206 }
207
208 /** How many distinct names exist (does not count nested definitions of the same name) */
209 size_t size() const {
210 return table.size();
211 }
212
213 struct PushToken {
214 typename std::map<std::string, SmallStack<T>>::iterator iter;
215 };
216
217 /** Add a new (name, value) pair to the current scope. Hide old values that
218 * have this name until we pop this name. Returns a token that can be used
219 * to pop the same value without doing a fresh lookup.
220 */
221 template<typename T2 = T,
222 typename = std::enable_if_t<!std::is_void_v<T2>>>
223 PushToken push(const std::string &name, T2 &&value) {
224 auto it = table.try_emplace(name).first;
225 it->second.push(std::forward<T2>(value));
226 return PushToken{it};
227 }
228
229 template<typename T2 = T,
230 typename = std::enable_if_t<std::is_void_v<T2>>>
231 PushToken push(const std::string &name) {
232 auto it = table.try_emplace(name).first;
233 it->second.push();
234 return PushToken{it};
235 }
236
237 /** A name goes out of scope. Restore whatever its old value
238 * was (or remove it entirely if there was nothing else of the
239 * same name in an outer scope) */
240 void pop(const std::string &name) {
241 typename std::map<std::string, SmallStack<T>>::iterator iter = table.find(name);
242 internal_assert(iter != table.end()) << "Name not in Scope: " << name << "\n"
243 << *this << "\n";
244 iter->second.pop();
245 if (iter->second.empty()) {
246 table.erase(iter);
247 }
248 }
249
250 /** Pop a name using a token returned by push instead of a string. */
251 void pop(PushToken p) {
252 p.iter->second.pop();
253 if (p.iter->second.empty()) {
254 table.erase(p.iter);
255 }
256 }
257
258 /** Iterate through the scope. Does not capture any containing scope. */
259 class const_iterator {
260 typename std::map<std::string, SmallStack<T>>::const_iterator iter;
261
262 public:
263 explicit const_iterator(const typename std::map<std::string, SmallStack<T>>::const_iterator &i)
264 : iter(i) {
265 }
266
267 const_iterator() = default;
268
269 bool operator!=(const const_iterator &other) {
270 return iter != other.iter;
271 }
272
273 void operator++() {
274 ++iter;
275 }
276
277 const std::string &name() {
278 return iter->first;
279 }
280
281 const SmallStack<T> &stack() {
282 return iter->second;
283 }
284
285 template<typename T2 = T,
286 typename = std::enable_if_t<!std::is_void_v<T2>>>
287 const T2 &value() {
288 return iter->second.top_ref();
289 }
290 };
291
292 const_iterator cbegin() const {
293 return const_iterator(table.begin());
294 }
295
296 const_iterator cend() const {
297 return const_iterator(table.end());
298 }
299
300 void swap(Scope<T> &other) noexcept {
301 table.swap(other.table);
302 std::swap(containing_scope, other.containing_scope);
303 }
304};
305
306template<typename T>
307std::ostream &operator<<(std::ostream &stream, const Scope<T> &s) {
308 stream << "{\n";
309 typename Scope<T>::const_iterator iter;
310 for (iter = s.cbegin(); iter != s.cend(); ++iter) {
311 stream << " " << iter.name() << "\n";
312 }
313 stream << "}";
314 return stream;
315}
316
317/** Helper class for pushing/popping Scope<> values, to allow
318 * for early-exit in Visitor/Mutators that preserves correctness.
319 * Note that this name can be a bit confusing, since there are two "scopes"
320 * involved here:
321 * - the Scope object itself
322 * - the lifetime of this helper object
323 * The "Scoped" in this class name refers to the latter, as it temporarily binds
324 * a name within the scope of this helper's lifetime. */
325template<typename T = void>
326 struct ScopedBinding {
327 Scope<T> *scope = nullptr;
328 typename Scope<T>::PushToken token;
329
330 ScopedBinding() = default;
331
332 ScopedBinding(Scope<T> &s, const std::string &n, T value)
333 : scope(&s), token(scope->push(n, std::move(value))) {
334 }
335
336 ScopedBinding(bool condition, Scope<T> &s, const std::string &n, const T &value)
337 : scope(condition ? &s : nullptr),
338 token(condition ? scope->push(n, value) : typename Scope<T>::PushToken{}) {
339 }
340
341 bool bound() const {
342 return scope != nullptr;
343 }
344
345 ~ScopedBinding() {
346 if (scope) {
347 scope->pop(token);
348 }
349 }
350
351 // allow move but not copy
352 ScopedBinding(const ScopedBinding &that) = delete;
353 ScopedBinding(ScopedBinding &&that) noexcept
354 : scope(that.scope),
355 token(that.token) {
356 // The move constructor must null out scope, so we don't try to pop it
357 that.scope = nullptr;
358 }
359
360 void operator=(const ScopedBinding &that) = delete;
361 void operator=(ScopedBinding &&that) = delete;
362};
363
364template<>
365 struct ScopedBinding<void> {
366 Scope<> *scope;
367 Scope<>::PushToken token;
368 ScopedBinding(Scope<> &s, const std::string &n)
369 : scope(&s), token(scope->push(n)) {
370 }
371 ScopedBinding(bool condition, Scope<> &s, const std::string &n)
372 : scope(condition ? &s : nullptr),
373 token(condition ? scope->push(n) : Scope<>::PushToken{}) {
374 }
375 ~ScopedBinding() {
376 if (scope) {
377 scope->pop(token);
378 }
379 }
380
381 // allow move but not copy
382 ScopedBinding(const ScopedBinding &that) = delete;
383 ScopedBinding(ScopedBinding &&that) noexcept
384 : scope(that.scope),
385 token(that.token) {
386 // The move constructor must null out scope, so we don't try to pop it
387 that.scope = nullptr;
388 }
389
390 void operator=(const ScopedBinding &that) = delete;
391 void operator=(ScopedBinding &&that) = delete;
392};
393
394} // namespace Internal
395} // namespace Halide
396
397#endif
Debug.h
Defines functions for debug logging during code generation.
Error.h
internal_error
#define internal_error
Definition: Error.h:229
internal_assert
#define internal_assert(c)
Definition: Error.h:232
Halide::Internal::Scope::const_iterator
Iterate through the scope.
Definition: Scope.h:259
Halide::Internal::Scope::const_iterator::value
const T2 & value()
Definition: Scope.h:287
Halide::Internal::Scope::const_iterator::operator++
void operator++()
Definition: Scope.h:273
Halide::Internal::Scope::const_iterator::operator!=
bool operator!=(const const_iterator &other)
Definition: Scope.h:269
Halide::Internal::Scope::const_iterator::const_iterator
const_iterator()=default
Halide::Internal::Scope::const_iterator::name
const std::string & name()
Definition: Scope.h:277
Halide::Internal::Scope::const_iterator::stack
const SmallStack< T > & stack()
Definition: Scope.h:281
Halide::Internal::Scope::const_iterator::const_iterator
const_iterator(const typename std::map< std::string, SmallStack< T > >::const_iterator &i)
Definition: Scope.h:263
Halide::Internal::Scope
A common pattern when traversing Halide IR is that you need to keep track of stuff when you find a Le...
Definition: Scope.h:94
Halide::Internal::Scope::swap
void swap(Scope< T > &other) noexcept
Definition: Scope.h:300
Halide::Internal::Scope::find
const T2 * find(const std::string &name) const
Returns a const pointer to an entry if it exists in this scope or any containing scope,...
Definition: Scope.h:159
Halide::Internal::Scope::operator=
Scope & operator=(Scope &&that) noexcept=default
Halide::Internal::Scope::Scope
Scope(const Scope< T > &)=delete
Halide::Internal::Scope::Scope
Scope(Scope &&that) noexcept=default
Halide::Internal::Scope::ref
T2 & ref(const std::string &name)
Return a reference to an entry.
Definition: Scope.h:144
Halide::Internal::Scope::operator=
Scope< T > & operator=(const Scope< T > &)=delete
Halide::Internal::Scope::push
PushToken push(const std::string &name)
Definition: Scope.h:231
Halide::Internal::Scope::get
T2 get(const std::string &name) const
Retrieve the value referred to by a name.
Definition: Scope.h:128
Halide::Internal::Scope::pop
void pop(PushToken p)
Pop a name using a token returned by push instead of a string.
Definition: Scope.h:251
Halide::Internal::Scope::Scope
Scope()=default
Halide::Internal::Scope::count
size_t count(const std::string &name) const
How many nested definitions of a single name exist?
Definition: Scope.h:199
Halide::Internal::Scope::cbegin
const_iterator cbegin() const
Definition: Scope.h:292
Halide::Internal::Scope::empty_scope
static const Scope< T > & empty_scope()
A const ref to an empty scope.
Definition: Scope.h:120
Halide::Internal::Scope::contains
bool contains(const std::string &name) const
Tests if a name is in scope.
Definition: Scope.h:186
Halide::Internal::Scope::push
PushToken push(const std::string &name, T2 &&value)
Add a new (name, value) pair to the current scope.
Definition: Scope.h:223
Halide::Internal::Scope::shallow_find
T2 * shallow_find(const std::string &name)
A version of find that returns a non-const pointer, but ignores containing scope.
Definition: Scope.h:175
Halide::Internal::Scope::cend
const_iterator cend() const
Definition: Scope.h:296
Halide::Internal::Scope::set_containing_scope
void set_containing_scope(const Scope< T > *s)
Set the parent scope.
Definition: Scope.h:113
Halide::Internal::Scope::size
size_t size() const
How many distinct names exist (does not count nested definitions of the same name)
Definition: Scope.h:209
Halide::Internal::Scope::pop
void pop(const std::string &name)
A name goes out of scope.
Definition: Scope.h:240
Halide::Internal::SmallStack< void >::push
void push()
Definition: Scope.h:81
Halide::Internal::SmallStack< void >::pop
void pop()
Definition: Scope.h:78
Halide::Internal::SmallStack< void >::empty
bool empty() const
Definition: Scope.h:84
Halide::Internal::SmallStack
A stack which can store one item very efficiently.
Definition: Scope.h:24
Halide::Internal::SmallStack::SmallStack
SmallStack()=default
Halide::Internal::SmallStack::top_ref
const T & top_ref() const
Definition: Scope.h:59
Halide::Internal::SmallStack::push
void push(T t)
Definition: Scope.h:43
Halide::Internal::SmallStack::top_ref
T & top_ref()
Definition: Scope.h:55
Halide::Internal::SmallStack::empty
bool empty() const
Definition: Scope.h:63
Halide::Internal::SmallStack::pop
void pop()
Definition: Scope.h:33
Halide::Internal::SmallStack::size
size_t size() const
Definition: Scope.h:67
Halide::Internal::SmallStack::top
T top() const
Definition: Scope.h:51
Halide::Internal::operator<<
ConstantInterval operator<<(const ConstantInterval &a, const ConstantInterval &b)
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::Scope::PushToken
Definition: Scope.h:213
Halide::Internal::Scope::PushToken::iter
std::map< std::string, SmallStack< T > >::iterator iter
Definition: Scope.h:214
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(const ScopedBinding &that)=delete
Halide::Internal::ScopedBinding< void >::token
Scope ::PushToken token
Definition: Scope.h:367
Halide::Internal::ScopedBinding< void >::~ScopedBinding
~ScopedBinding()
Definition: Scope.h:375
Halide::Internal::ScopedBinding< void >::operator=
void operator=(const ScopedBinding &that)=delete
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(bool condition, Scope<> &s, const std::string &n)
Definition: Scope.h:371
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(Scope<> &s, const std::string &n)
Definition: Scope.h:368
Halide::Internal::ScopedBinding< void >::scope
Scope * scope
Definition: Scope.h:366
Halide::Internal::ScopedBinding< void >::operator=
void operator=(ScopedBinding &&that)=delete
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:383
Halide::Internal::ScopedBinding
Helper class for pushing/popping Scope<> values, to allow for early-exit in Visitor/Mutators that pre...
Definition: Scope.h:326
Halide::Internal::ScopedBinding::operator=
void operator=(const ScopedBinding &that)=delete
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(Scope< T > &s, const std::string &n, T value)
Definition: Scope.h:332
Halide::Internal::ScopedBinding::bound
bool bound() const
Definition: Scope.h:341
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(const ScopedBinding &that)=delete
Halide::Internal::ScopedBinding::token
Scope< T >::PushToken token
Definition: Scope.h:328
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding()=default
Halide::Internal::ScopedBinding::scope
Scope< T > * scope
Definition: Scope.h:327
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(bool condition, Scope< T > &s, const std::string &n, const T &value)
Definition: Scope.h:336
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:353
Halide::Internal::ScopedBinding::operator=
void operator=(ScopedBinding &&that)=delete
Halide::Internal::ScopedBinding::~ScopedBinding
~ScopedBinding()
Definition: Scope.h:345