Halide  19.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 
18 namespace Halide {
19 namespace Internal {
20 
21 /** A stack which can store one item very efficiently. Using this
22  * instead of std::stack speeds up Scope substantially. */
23 template<typename T>
24 class SmallStack {
25 private:
26  T _top;
27  std::vector<T> _rest;
28  bool _empty = true;
29 
30 public:
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 
72 template<>
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 
77 public:
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. */
93 template<typename T = void>
94 class Scope {
95 private:
96  std::map<std::string, SmallStack<T>> table;
97 
98  const Scope<T> *containing_scope = nullptr;
99 
100 public:
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  /** 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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
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 = typename std::enable_if<std::is_same<T2, void>::value>::type>
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. */
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 = typename std::enable_if<!std::is_same<T2, void>::value>::type>
287  const T2 &value() {
288  return iter->second.top_ref();
289  }
290  };
291 
293  return const_iterator(table.begin());
294  }
295 
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 
306 template<typename T>
307 std::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. */
325 template<typename T = void>
327  Scope<T> *scope = nullptr;
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 
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 
364 template<>
365 struct ScopedBinding<void> {
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  }
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
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:259
bool operator!=(const const_iterator &other)
Definition: Scope.h:269
const std::string & name()
Definition: Scope.h:277
const_iterator(const typename std::map< std::string, SmallStack< T >>::const_iterator &i)
Definition: Scope.h:263
const SmallStack< T > & stack()
Definition: Scope.h:281
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
void swap(Scope< T > &other) noexcept
Definition: Scope.h:300
Scope< T > & operator=(const Scope< T > &)=delete
Scope(const Scope< T > &)=delete
Scope(Scope &&that) noexcept=default
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
PushToken push(const std::string &name)
Definition: Scope.h:231
T2 get(const std::string &name) const
Retrieve the value referred to by a name.
Definition: Scope.h:128
void pop(PushToken p)
Pop a name using a token returned by push instead of a string.
Definition: Scope.h:251
size_t count(const std::string &name) const
How many nested definitions of a single name exist?
Definition: Scope.h:199
const_iterator cbegin() const
Definition: Scope.h:292
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:186
PushToken push(const std::string &name, T2 &&value)
Add a new (name, value) pair to the current scope.
Definition: Scope.h:223
Scope & operator=(Scope &&that) noexcept=default
const_iterator cend() const
Definition: Scope.h:296
void set_containing_scope(const Scope< T > *s)
Set the parent scope.
Definition: Scope.h:113
size_t size() const
How many distinct names exist (does not count nested definitions of the same name)
Definition: Scope.h:209
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
T2 & ref(const std::string &name)
Return a reference to an entry.
Definition: Scope.h:144
void pop(const std::string &name)
A name goes out of scope.
Definition: Scope.h:240
A stack which can store one item very efficiently.
Definition: Scope.h:24
bool empty() const
Definition: Scope.h:63
size_t size() const
Definition: Scope.h:67
const T & top_ref() const
Definition: Scope.h:59
ConstantInterval operator<<(const ConstantInterval &a, const ConstantInterval &b)
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
std::map< std::string, SmallStack< T > >::iterator iter
Definition: Scope.h:214
ScopedBinding(const ScopedBinding &that)=delete
void operator=(const ScopedBinding &that)=delete
ScopedBinding(bool condition, Scope<> &s, const std::string &n)
Definition: Scope.h:371
ScopedBinding(Scope<> &s, const std::string &n)
Definition: Scope.h:368
void operator=(ScopedBinding &&that)=delete
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:383
Helper class for pushing/popping Scope<> values, to allow for early-exit in Visitor/Mutators that pre...
Definition: Scope.h:326
void operator=(const ScopedBinding &that)=delete
ScopedBinding(Scope< T > &s, const std::string &n, T value)
Definition: Scope.h:332
ScopedBinding(const ScopedBinding &that)=delete
Scope< T >::PushToken token
Definition: Scope.h:328
ScopedBinding(bool condition, Scope< T > &s, const std::string &n, const T &value)
Definition: Scope.h:336
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:353
void operator=(ScopedBinding &&that)=delete