Halide
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  /** 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 
214  }
215 
216  bool operator!=(const const_iterator &other) {
217  return iter != other.iter;
218  }
219 
220  void operator++() {
221  ++iter;
222  }
223 
224  const std::string &name() {
225  return iter->first;
226  }
227 
228  const SmallStack<T> &stack() {
229  return iter->second;
230  }
231 
232  template<typename T2 = T,
233  typename = typename std::enable_if<!std::is_same<T2, void>::value>::type>
234  const T2 &value() {
235  return iter->second.top_ref();
236  }
237  };
238 
239  const_iterator cbegin() const {
240  return const_iterator(table.begin());
241  }
242 
243  const_iterator cend() const {
244  return const_iterator(table.end());
245  }
246 
247  void swap(Scope<T> &other) {
248  table.swap(other.table);
249  std::swap(containing_scope, other.containing_scope);
250  }
251 };
252 
253 template<typename T>
254 std::ostream &operator<<(std::ostream &stream, const Scope<T> &s) {
255  stream << "{\n";
256  typename Scope<T>::const_iterator iter;
257  for (iter = s.cbegin(); iter != s.cend(); ++iter) {
258  stream << " " << iter.name() << "\n";
259  }
260  stream << "}";
261  return stream;
262 }
263 
264 /** Helper class for pushing/popping Scope<> values, to allow
265  * for early-exit in Visitor/Mutators that preserves correctness.
266  * Note that this name can be a bit confusing, since there are two "scopes"
267  * involved here:
268  * - the Scope object itself
269  * - the lifetime of this helper object
270  * The "Scoped" in this class name refers to the latter, as it temporarily binds
271  * a name within the scope of this helper's lifetime. */
272 template<typename T = void>
274  Scope<T> *scope = nullptr;
275  std::string name;
276 
277  ScopedBinding() = default;
278 
279  ScopedBinding(Scope<T> &s, const std::string &n, T value)
280  : scope(&s), name(n) {
281  scope->push(name, std::move(value));
282  }
283 
284  ScopedBinding(bool condition, Scope<T> &s, const std::string &n, const T &value)
285  : scope(condition ? &s : nullptr), name(n) {
286  if (condition) {
287  scope->push(name, value);
288  }
289  }
290 
291  bool bound() const {
292  return scope != nullptr;
293  }
294 
296  if (scope) {
297  scope->pop(name);
298  }
299  }
300 
301  // allow move but not copy
302  ScopedBinding(const ScopedBinding &that) = delete;
303  ScopedBinding(ScopedBinding &&that) noexcept
304  : scope(that.scope),
305  name(std::move(that.name)) {
306  // The move constructor must null out scope, so we don't try to pop it
307  that.scope = nullptr;
308  }
309 
310  void operator=(const ScopedBinding &that) = delete;
311  void operator=(ScopedBinding &&that) = delete;
312 };
313 
314 template<>
315 struct ScopedBinding<void> {
317  std::string name;
318  ScopedBinding(Scope<> &s, const std::string &n)
319  : scope(&s), name(n) {
320  scope->push(name);
321  }
322  ScopedBinding(bool condition, Scope<> &s, const std::string &n)
323  : scope(condition ? &s : nullptr), name(n) {
324  if (condition) {
325  scope->push(name);
326  }
327  }
329  if (scope) {
330  scope->pop(name);
331  }
332  }
333 
334  // allow move but not copy
335  ScopedBinding(const ScopedBinding &that) = delete;
336  ScopedBinding(ScopedBinding &&that) noexcept
337  : scope(that.scope),
338  name(std::move(that.name)) {
339  // The move constructor must null out scope, so we don't try to pop it
340  that.scope = nullptr;
341  }
342 
343  void operator=(const ScopedBinding &that) = delete;
344  void operator=(ScopedBinding &&that) = delete;
345 };
346 
347 } // namespace Internal
348 } // namespace Halide
349 
350 #endif
Halide::Internal::Scope::const_iterator::const_iterator
const_iterator(const typename std::map< std::string, SmallStack< T >>::const_iterator &i)
Definition: Scope.h:209
Halide::Internal::Scope::const_iterator
Iterate through the scope.
Definition: Scope.h:205
Halide::Internal::Scope::const_iterator::name
const std::string & name()
Definition: Scope.h:224
internal_assert
#define internal_assert(c)
Definition: Errors.h:19
Error.h
Halide::Internal::ScopedBinding::operator=
void operator=(const ScopedBinding &that)=delete
Halide::Internal::operator<<
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.
Halide::Internal::SmallStack< void >::push
void push()
Definition: Scope.h:81
Halide::Internal::ScopedBinding< void >::scope
Scope * scope
Definition: Scope.h:316
Halide::Internal::Scope::pop
void pop(const std::string &name)
A name goes out of scope.
Definition: Scope.h:194
Halide::Internal::ScopedBinding
Helper class for pushing/popping Scope<> values, to allow for early-exit in Visitor/Mutators that pre...
Definition: Scope.h:273
Halide::Internal::Scope::contains
bool contains(const std::string &name) const
Tests if a name is in scope.
Definition: Scope.h:154
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(Scope< T > &s, const std::string &n, T value)
Definition: Scope.h:279
Halide::Internal::Scope::Scope
Scope()=default
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
A common pattern when traversing Halide IR is that you need to keep track of stuff when you find a Le...
Definition: ModulusRemainder.h:17
Halide::Internal::Scope::set_containing_scope
void set_containing_scope(const Scope< T > *s)
Set the parent scope.
Definition: Scope.h:113
Debug.h
Halide::Internal::ScopedBinding< void >::~ScopedBinding
~ScopedBinding()
Definition: Scope.h:328
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(Scope<> &s, const std::string &n)
Definition: Scope.h:318
Halide::Internal::Scope::swap
void swap(Scope< T > &other)
Definition: Scope.h:247
Halide::Internal::Scope::const_iterator::const_iterator
const_iterator()
Definition: Scope.h:213
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::Internal::Scope::count
size_t count(const std::string &name) const
How many nested definitions of a single name exist?
Definition: Scope.h:167
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:303
Halide::Internal::Scope::const_iterator::stack
const SmallStack< T > & stack()
Definition: Scope.h:228
Halide::Internal::Scope::const_iterator::value
const T2 & value()
Definition: Scope.h:234
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::Scope::const_iterator::operator!=
bool operator!=(const const_iterator &other)
Definition: Scope.h:216
Halide::Internal::SmallStack::empty
bool empty() const
Definition: Scope.h:63
Halide::Internal::SmallStack::top_ref
T & top_ref()
Definition: Scope.h:55
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding()=default
Halide::Internal::SmallStack< void >::pop
void pop()
Definition: Scope.h:78
Halide::Internal::Scope::push
void push(const std::string &name)
Definition: Scope.h:187
Halide::Internal::ScopedBinding::ScopedBinding
ScopedBinding(bool condition, Scope< T > &s, const std::string &n, const T &value)
Definition: Scope.h:284
Halide::Internal::ScopedBinding::~ScopedBinding
~ScopedBinding()
Definition: Scope.h:295
Halide::Internal::Scope::operator=
Scope & operator=(Scope &&that) noexcept=default
Halide::Internal::SmallStack::size
size_t size() const
Definition: Scope.h:67
Halide::Internal::ScopedBinding::scope
Scope< T > * scope
Definition: Scope.h:274
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(ScopedBinding &&that) noexcept
Definition: Scope.h:336
Halide::Internal::Scope::push
void push(const std::string &name, T2 &&value)
Add a new (name, value) pair to the current scope.
Definition: Scope.h:181
Halide::Internal::Scope::const_iterator::operator++
void operator++()
Definition: Scope.h:220
Halide::Internal::SmallStack::push
void push(T t)
Definition: Scope.h:43
Halide::Internal::SmallStack::SmallStack
SmallStack()=default
Halide::Internal::ScopedBinding::name
std::string name
Definition: Scope.h:275
internal_error
#define internal_error
Definition: Errors.h:23
Halide::Internal::SmallStack
A stack which can store one item very efficiently.
Definition: Scope.h:24
Halide::Internal::ScopedBinding::bound
bool bound() const
Definition: Scope.h:291
Halide::Internal::Scope::empty_scope
static const Scope< T > & empty_scope()
A const ref to an empty scope.
Definition: Scope.h:120
Halide::Internal::ScopedBinding< void >::ScopedBinding
ScopedBinding(bool condition, Scope<> &s, const std::string &n)
Definition: Scope.h:322
Halide::Internal::SmallStack::top_ref
const T & top_ref() const
Definition: Scope.h:59
Halide::Internal::SmallStack::top
T top() const
Definition: Scope.h:51
Halide::Internal::Scope::ref
T2 & ref(const std::string &name)
Return a reference to an entry.
Definition: Scope.h:144
Halide::Internal::SmallStack::pop
void pop()
Definition: Scope.h:33
table
#define table
Definition: synchronization_common.h:498
Halide::Internal::Scope::cend
const_iterator cend() const
Definition: Scope.h:243
Halide::Internal::SmallStack< void >::empty
bool empty() const
Definition: Scope.h:84
Halide::Internal::Scope::cbegin
const_iterator cbegin() const
Definition: Scope.h:239
Halide::Internal::ScopedBinding< void >::name
std::string name
Definition: Scope.h:317