Halide 16.0.0
Halide compiler and libraries
Loading...
Searching...
No Matches
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>
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<>
73class 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>
94class 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. */
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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
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 /** Tests if a name is in scope */
154 bool contains(const std::string &name) const {
155 typename std::map<std::string, SmallStack<T>>::const_iterator iter = table.find(name);
156 if (iter == table.end() || iter->second.empty()) {
157 if (containing_scope) {
158 return containing_scope->contains(name);
159 } else {
160 return false;
161 }
162 }
163 return true;
164 }
165
166 /** How many nested definitions of a single name exist? */
167 size_t count(const std::string &name) const {
168 auto it = table.find(name);
169 if (it == table.end()) {
170 return 0;
171 } else {
172 return it->second.size();
173 }
174 }
175
176 /** Add a new (name, value) pair to the current scope. Hide old
177 * values that have this name until we pop this name.
178 */
179 template<typename T2 = T,
180 typename = typename std::enable_if<!std::is_same<T2, void>::value>::type>
181 void push(const std::string &name, T2 &&value) {
182 table[name].push(std::forward<T2>(value));
183 }
184
185 template<typename T2 = T,
186 typename = typename std::enable_if<std::is_same<T2, void>::value>::type>
187 void push(const std::string &name) {
188 table[name].push();
189 }
190
191 /** A name goes out of scope. Restore whatever its old value
192 * was (or remove it entirely if there was nothing else of the
193 * same name in an outer scope) */
194 void pop(const std::string &name) {
195 typename std::map<std::string, SmallStack<T>>::iterator iter = table.find(name);
196 internal_assert(iter != table.end()) << "Name not in Scope: " << name << "\n"
197 << *this << "\n";
198 iter->second.pop();
199 if (iter->second.empty()) {
200 table.erase(iter);
201 }
202 }
203
204 /** Iterate through the scope. Does not capture any containing scope. */
206 typename std::map<std::string, SmallStack<T>>::const_iterator iter;
207
208 public:
209 explicit const_iterator(const typename std::map<std::string, SmallStack<T>>::const_iterator &i)
210 : iter(i) {
211 }
212
213 const_iterator() = default;
214
216 return iter != other.iter;
217 }
218
219 void operator++() {
220 ++iter;
221 }
222
223 const std::string &name() {
224 return iter->first;
225 }
226
228 return iter->second;
229 }
230
231 template<typename T2 = T,
232 typename = typename std::enable_if<!std::is_same<T2, void>::value>::type>
233 const T2 &value() {
234 return iter->second.top_ref();
235 }
236 };
237
239 return const_iterator(table.begin());
240 }
241
243 return const_iterator(table.end());
244 }
245
247 table.swap(other.table);
248 std::swap(containing_scope, other.containing_scope);
249 }
250};
251
252template<typename T>
253std::ostream &operator<<(std::ostream &stream, const Scope<T> &s) {
254 stream << "{\n";
255 typename Scope<T>::const_iterator iter;
256 for (iter = s.cbegin(); iter != s.cend(); ++iter) {
257 stream << " " << iter.name() << "\n";
258 }
259 stream << "}";
260 return stream;
261}
262
263/** Helper class for pushing/popping Scope<> values, to allow
264 * for early-exit in Visitor/Mutators that preserves correctness.
265 * Note that this name can be a bit confusing, since there are two "scopes"
266 * involved here:
267 * - the Scope object itself
268 * - the lifetime of this helper object
269 * The "Scoped" in this class name refers to the latter, as it temporarily binds
270 * a name within the scope of this helper's lifetime. */
271template<typename T = void>
273 Scope<T> *scope = nullptr;
274 std::string name;
275
276 ScopedBinding() = default;
277
278 ScopedBinding(Scope<T> &s, const std::string &n, T value)
279 : scope(&s), name(n) {
280 scope->push(name, std::move(value));
281 }
282
283 ScopedBinding(bool condition, Scope<T> &s, const std::string &n, const T &value)
284 : scope(condition ? &s : nullptr), name(n) {
285 if (condition) {
286 scope->push(name, value);
287 }
288 }
289
290 bool bound() const {
291 return scope != nullptr;
292 }
293
295 if (scope) {
296 scope->pop(name);
297 }
298 }
299
300 // allow move but not copy
303 : scope(that.scope),
304 name(std::move(that.name)) {
305 // The move constructor must null out scope, so we don't try to pop it
306 that.scope = nullptr;
307 }
308
309 void operator=(const ScopedBinding &that) = delete;
310 void operator=(ScopedBinding &&that) = delete;
311};
312
313template<>
314struct ScopedBinding<void> {
316 std::string name;
317 ScopedBinding(Scope<> &s, const std::string &n)
318 : scope(&s), name(n) {
319 scope->push(name);
320 }
321 ScopedBinding(bool condition, Scope<> &s, const std::string &n)
322 : scope(condition ? &s : nullptr), name(n) {
323 if (condition) {
324 scope->push(name);
325 }
326 }
328 if (scope) {
329 scope->pop(name);
330 }
331 }
332
333 // allow move but not copy
336 : scope(that.scope),
337 name(std::move(that.name)) {
338 // The move constructor must null out scope, so we don't try to pop it
339 that.scope = nullptr;
340 }
341
342 void operator=(const ScopedBinding &that) = delete;
343 void operator=(ScopedBinding &&that) = delete;
344};
345
346} // namespace Internal
347} // namespace Halide
348
349#endif
Defines functions for debug logging during code generation.
#define internal_error
Definition Errors.h:23
#define internal_assert(c)
Definition Errors.h:19
Iterate through the scope.
Definition Scope.h:205
bool operator!=(const const_iterator &other)
Definition Scope.h:215
const SmallStack< T > & stack()
Definition Scope.h:227
const_iterator(const typename std::map< std::string, SmallStack< T > >::const_iterator &i)
Definition Scope.h:209
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
Scope & operator=(Scope &&that) noexcept=default
Scope(const Scope< T > &)=delete
Scope(Scope &&that) noexcept=default
T2 & ref(const std::string &name)
Return a reference to an entry.
Definition Scope.h:144
void push(const std::string &name, T2 &&value)
Add a new (name, value) pair to the current scope.
Definition Scope.h:181
Scope< T > & operator=(const Scope< T > &)=delete
void swap(Scope< T > &other)
Definition Scope.h:246
T2 get(const std::string &name) const
Retrieve the value referred to by a name.
Definition Scope.h:128
size_t count(const std::string &name) const
How many nested definitions of a single name exist?
Definition Scope.h:167
const_iterator cbegin() const
Definition Scope.h:238
static const Scope< T > & empty_scope()
A const ref to an empty scope.
Definition Scope.h:120
bool contains(const std::string &name) const
Tests if a name is in scope.
Definition Scope.h:154
void push(const std::string &name)
Definition Scope.h:187
const_iterator cend() const
Definition Scope.h:242
void set_containing_scope(const Scope< T > *s)
Set the parent scope.
Definition Scope.h:113
void pop(const std::string &name)
A name goes out of scope.
Definition Scope.h:194
A stack which can store one item very efficiently.
Definition Scope.h:24
const T & top_ref() const
Definition Scope.h:59
size_t size() const
Definition Scope.h:67
std::ostream & operator<<(std::ostream &stream, const Stmt &)
Emit a halide statement on an output stream (such as std::cout) in a human-readable form.
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
Expr cast(Expr a)
Cast an expression to the halide type corresponding to the C++ type T.
Definition IROperator.h:358
ScopedBinding(const ScopedBinding &that)=delete
void operator=(const ScopedBinding &that)=delete
ScopedBinding(bool condition, Scope<> &s, const std::string &n)
Definition Scope.h:321
ScopedBinding(Scope<> &s, const std::string &n)
Definition Scope.h:317
void operator=(ScopedBinding &&that)=delete
ScopedBinding(ScopedBinding &&that) noexcept
Definition Scope.h:335
Helper class for pushing/popping Scope<> values, to allow for early-exit in Visitor/Mutators that pre...
Definition Scope.h:272
void operator=(const ScopedBinding &that)=delete
ScopedBinding(Scope< T > &s, const std::string &n, T value)
Definition Scope.h:278
ScopedBinding(const ScopedBinding &that)=delete
ScopedBinding(bool condition, Scope< T > &s, const std::string &n, const T &value)
Definition Scope.h:283
ScopedBinding(ScopedBinding &&that) noexcept
Definition Scope.h:302
void operator=(ScopedBinding &&that)=delete