Halide  12.0.1
Halide compiler and libraries
RDom.h
Go to the documentation of this file.
1 #ifndef HALIDE_RDOM_H
2 #define HALIDE_RDOM_H
3 
4 /** \file
5  * Defines the front-end syntax for reduction domains and reduction
6  * variables.
7  */
8 
9 #include <iostream>
10 #include <string>
11 #include <utility>
12 #include <vector>
13 
14 #include "Expr.h"
15 #include "Reduction.h"
16 #include "Util.h"
17 
18 namespace Halide {
19 
20 template<typename T>
21 class Buffer;
22 class OutputImageParam;
23 
24 /** A reduction variable represents a single dimension of a reduction
25  * domain (RDom). Don't construct them directly, instead construct an
26  * RDom, and use RDom::operator[] to get at the variables. For
27  * single-dimensional reduction domains, you can just cast a
28  * single-dimensional RDom to an RVar. */
29 class RVar {
30  std::string _name;
32  int _index = -1;
33 
34  const Internal::ReductionVariable &_var() const {
35  const auto &d = _domain.domain();
36  internal_assert(_index >= 0 && _index < (int)d.size());
37  return d.at(_index);
38  }
39 
40 public:
41  /** An empty reduction variable. */
42  RVar()
43  : _name(Internal::make_entity_name(this, "Halide:.*:RVar", 'r')) {
44  }
45 
46  /** Construct an RVar with the given name */
47  explicit RVar(const std::string &n)
48  : _name(n) {
49  }
50 
51  /** Construct a reduction variable with the given name and
52  * bounds. Must be a member of the given reduction domain. */
54  : _domain(std::move(domain)), _index(index) {
55  }
56 
57  /** The minimum value that this variable will take on */
58  Expr min() const;
59 
60  /** The number that this variable will take on. The maximum value
61  * of this variable will be min() + extent() - 1 */
62  Expr extent() const;
63 
64  /** The reduction domain this is associated with. */
66  return _domain;
67  }
68 
69  /** The name of this reduction variable */
70  const std::string &name() const;
71 
72  /** Reduction variables can be used as expressions. */
73  operator Expr() const;
74 };
75 
76 /** A multi-dimensional domain over which to iterate. Used when
77  * defining functions with update definitions.
78  *
79  * An reduction is a function with a two-part definition. It has an
80  * initial value, which looks much like a pure function, and an update
81  * definition, which may refer to some RDom. Evaluating such a
82  * function first initializes it over the required domain (which is
83  * inferred based on usage), and then runs update rule for all points
84  * in the RDom. For example:
85  *
86  \code
87  Func f;
88  Var x;
89  RDom r(0, 10);
90  f(x) = x; // the initial value
91  f(r) = f(r) * 2;
92  Buffer<int> result = f.realize({10});
93  \endcode
94  *
95  * This function creates a single-dimensional buffer of size 10, in
96  * which element x contains the value x*2. Internally, first the
97  * initialization rule fills in x at every site, and then the update
98  * definition doubles every site.
99  *
100  * One use of reductions is to build a function recursively (pure
101  * functions in halide cannot be recursive). For example, this
102  * function fills in an array with the first 20 fibonacci numbers:
103  *
104  \code
105  Func f;
106  Var x;
107  RDom r(2, 18);
108  f(x) = 1;
109  f(r) = f(r-1) + f(r-2);
110  \endcode
111  *
112  * Another use of reductions is to perform scattering operations, as
113  * unlike a pure function declaration, the left-hand-side of an update
114  * definition may contain general expressions:
115  *
116  \code
117  ImageParam input(UInt(8), 2);
118  Func histogram;
119  Var x;
120  RDom r(input); // Iterate over all pixels in the input
121  histogram(x) = 0;
122  histogram(input(r.x, r.y)) = histogram(input(r.x, r.y)) + 1;
123  \endcode
124  *
125  * An update definition may also be multi-dimensional. This example
126  * computes a summed-area table by first summing horizontally and then
127  * vertically:
128  *
129  \code
130  ImageParam input(Float(32), 2);
131  Func sum_x, sum_y;
132  Var x, y;
133  RDom r(input);
134  sum_x(x, y) = input(x, y);
135  sum_x(r.x, r.y) = sum_x(r.x, r.y) + sum_x(r.x-1, r.y);
136  sum_y(x, y) = sum_x(x, y);
137  sum_y(r.x, r.y) = sum_y(r.x, r.y) + sum_y(r.x, r.y-1);
138  \endcode
139  *
140  * You can also mix pure dimensions with reduction variables. In the
141  * previous example, note that there's no need for the y coordinate in
142  * sum_x to be traversed serially. The sum within each row is entirely
143  * independent. The rows could be computed in parallel, or in a
144  * different order, without changing the meaning. Therefore, we can
145  * instead write this definition as follows:
146  *
147  \code
148  ImageParam input(Float(32), 2);
149  Func sum_x, sum_y;
150  Var x, y;
151  RDom r(input);
152  sum_x(x, y) = input(x, y);
153  sum_x(r.x, y) = sum_x(r.x, y) + sum_x(r.x-1, y);
154  sum_y(x, y) = sum_x(x, y);
155  sum_y(x, r.y) = sum_y(x, r.y) + sum_y(x, r.y-1);
156  \endcode
157  *
158  * This lets us schedule it more flexibly. You can now parallelize the
159  * update step of sum_x over y by calling:
160  \code
161  sum_x.update().parallel(y).
162  \endcode
163  *
164  * Note that calling sum_x.parallel(y) only parallelizes the
165  * initialization step, and not the update step! Scheduling the update
166  * step of a reduction must be done using the handle returned by
167  * \ref Func::update(). This code parallelizes both the initialization
168  * step and the update step:
169  *
170  \code
171  sum_x.parallel(y);
172  sum_x.update().parallel(y);
173  \endcode
174  *
175  * When you mix reduction variables and pure dimensions, the reduction
176  * domain is traversed outermost. That is, for each point in the
177  * reduction domain, the inferred pure domain is traversed in its
178  * entirety. For the above example, this means that sum_x walks down
179  * the columns, and sum_y walks along the rows. This may not be
180  * cache-coherent. You may try reordering these dimensions using the
181  * schedule, but Halide will return an error if it decides that this
182  * risks changing the meaning of your function. The solution lies in
183  * clever scheduling. If we say:
184  *
185  \code
186  sum_x.compute_at(sum_y, y);
187  \endcode
188  *
189  * Then the sum in x is computed only as necessary for each scanline
190  * of the sum in y. This not only results in sum_x walking along the
191  * rows, it also improves the locality of the entire pipeline.
192  */
193 class RDom {
195 
196  void init_vars(const std::string &name);
197 
198  void initialize_from_region(const Region &region, std::string name = "");
199 
200  template<typename... Args>
201  HALIDE_NO_USER_CODE_INLINE void initialize_from_region(Region &region, const Expr &min, const Expr &extent, Args &&...args) {
202  region.push_back({min, extent});
203  initialize_from_region(region, std::forward<Args>(args)...);
204  }
205 
206 public:
207  /** Construct an undefined reduction domain. */
208  RDom() = default;
209 
210  /** Construct a multi-dimensional reduction domain with the given name. If the name
211  * is left blank, a unique one is auto-generated. */
212  // @{
213  HALIDE_NO_USER_CODE_INLINE RDom(const Region &region, std::string name = "") {
214  initialize_from_region(region, std::move(name));
215  }
216 
217  template<typename... Args>
218  HALIDE_NO_USER_CODE_INLINE RDom(Expr min, Expr extent, Args &&...args) {
219  // This should really just be a delegating constructor, but I couldn't make
220  // that work with variadic template unpacking in visual studio 2013
221  Region region;
222  initialize_from_region(region, min, extent, std::forward<Args>(args)...);
223  }
224  // @}
225 
226  /** Construct a reduction domain that iterates over all points in
227  * a given Buffer or ImageParam. Has the same dimensionality as
228  * the argument. */
229  // @{
230  RDom(const Buffer<void> &);
232  template<typename T>
234  : RDom(Buffer<void>(im)) {
235  }
236  // @}
237 
238  /** Construct a reduction domain that wraps an Internal ReductionDomain object. */
240 
241  /** Get at the internal reduction domain object that this wraps. */
243  return dom;
244  }
245 
246  /** Check if this reduction domain is non-null */
247  bool defined() const {
248  return dom.defined();
249  }
250 
251  /** Compare two reduction domains for equality of reference */
252  bool same_as(const RDom &other) const {
253  return dom.same_as(other.dom);
254  }
255 
256  /** Get the dimensionality of a reduction domain */
257  int dimensions() const;
258 
259  /** Get at one of the dimensions of the reduction domain */
260  RVar operator[](int) const;
261 
262  /** Single-dimensional reduction domains can be used as RVars directly. */
263  operator RVar() const;
264 
265  /** Single-dimensional reduction domains can be also be used as Exprs directly. */
266  operator Expr() const;
267 
268  /** Add a predicate to the RDom. An RDom may have multiple
269  * predicates associated with it. An update definition that uses
270  * an RDom only iterates over the subset points in the domain for
271  * which all of its predicates are true. The predicate expression
272  * obeys the same rules as the expressions used on the
273  * right-hand-side of the corresponding update definition. It may
274  * refer to the RDom's variables and free variables in the Func's
275  * update definition. It may include calls to other Funcs, or make
276  * recursive calls to the same Func. This permits iteration over
277  * non-rectangular domains, or domains with sizes that vary with
278  * some free variable, or domains with shapes determined by some
279  * other Func.
280  *
281  * Note that once RDom is used in the update definition of some
282  * Func, no new predicates can be added to the RDom.
283  *
284  * Consider a simple example:
285  \code
286  RDom r(0, 20, 0, 20);
287  r.where(r.x < r.y);
288  r.where(r.x == 10);
289  r.where(r.y > 13);
290  f(r.x, r.y) += 1;
291  \endcode
292  * This is equivalent to:
293  \code
294  for (int r.y = 0; r.y < 20; r.y++) {
295  if (r.y > 13) {
296  for (int r.x = 0; r.x < 20; r.x++) {
297  if (r.x == 10) {
298  if (r.x < r.y) {
299  f[r.x, r.y] += 1;
300  }
301  }
302  }
303  }
304  }
305  \endcode
306  *
307  * Where possible Halide restricts the range of the containing for
308  * loops to avoid the cases where the predicate is false so that
309  * the if statement can be removed entirely. The case above would
310  * be further simplified into:
311  *
312  \code
313  for (int r.y = 14; r.y < 20; r.y++) {
314  f[r.x, r.y] += 1;
315  }
316  \endcode
317  *
318  * In general, the predicates that we can simplify away by
319  * restricting loop ranges are inequalities that compare an inner
320  * Var or RVar to some expression in outer Vars or RVars.
321  *
322  * You can also pack multiple conditions into one predicate like so:
323  *
324  \code
325  RDom r(0, 20, 0, 20);
326  r.where((r.x < r.y) && (r.x == 10) && (r.y > 13));
327  f(r.x, r.y) += 1;
328  \endcode
329  *
330  */
332 
333  /** Direct access to the first four dimensions of the reduction
334  * domain. Some of these variables may be undefined if the
335  * reduction domain has fewer than four dimensions. */
336  // @{
337  RVar x, y, z, w;
338  // @}
339 };
340 
341 /** Emit an RVar in a human-readable form */
342 std::ostream &operator<<(std::ostream &stream, const RVar &);
343 
344 /** Emit an RDom in a human-readable form. */
345 std::ostream &operator<<(std::ostream &stream, const RDom &);
346 } // namespace Halide
347 
348 #endif
#define internal_assert(c)
Definition: Errors.h:19
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt)
Defines internal classes related to Reduction Domains.
Various utility functions used internally Halide.
#define HALIDE_NO_USER_CODE_INLINE
Definition: Util.h:45
A reference-counted handle on a reduction domain, which is just a vector of ReductionVariable.
Definition: Reduction.h:33
const std::vector< ReductionVariable > & domain() const
Immutable access to the reduction variables.
bool defined() const
Is this handle non-nullptr.
Definition: Reduction.h:61
bool same_as(const ReductionDomain &other) const
Tests for equality of reference.
Definition: Reduction.h:68
A handle on the output buffer of a pipeline.
A multi-dimensional domain over which to iterate.
Definition: RDom.h:193
HALIDE_NO_USER_CODE_INLINE RDom(const Buffer< T > &im)
Definition: RDom.h:233
bool same_as(const RDom &other) const
Compare two reduction domains for equality of reference.
Definition: RDom.h:252
bool defined() const
Check if this reduction domain is non-null.
Definition: RDom.h:247
int dimensions() const
Get the dimensionality of a reduction domain.
RVar w
Definition: RDom.h:337
RDom(const Internal::ReductionDomain &d)
Construct a reduction domain that wraps an Internal ReductionDomain object.
RVar z
Definition: RDom.h:337
RDom()=default
Construct an undefined reduction domain.
HALIDE_NO_USER_CODE_INLINE RDom(const Region &region, std::string name="")
Construct a multi-dimensional reduction domain with the given name.
Definition: RDom.h:213
RDom(const Buffer< void > &)
Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.
RVar x
Direct access to the first four dimensions of the reduction domain.
Definition: RDom.h:337
void where(Expr predicate)
Add a predicate to the RDom.
RVar y
Definition: RDom.h:337
RVar operator[](int) const
Get at one of the dimensions of the reduction domain.
RDom(const OutputImageParam &)
HALIDE_NO_USER_CODE_INLINE RDom(Expr min, Expr extent, Args &&...args)
Definition: RDom.h:218
Internal::ReductionDomain domain() const
Get at the internal reduction domain object that this wraps.
Definition: RDom.h:242
A reduction variable represents a single dimension of a reduction domain (RDom).
Definition: RDom.h:29
RVar(Internal::ReductionDomain domain, int index)
Construct a reduction variable with the given name and bounds.
Definition: RDom.h:53
RVar()
An empty reduction variable.
Definition: RDom.h:42
const std::string & name() const
The name of this reduction variable.
Internal::ReductionDomain domain() const
The reduction domain this is associated with.
Definition: RDom.h:65
RVar(const std::string &n)
Construct an RVar with the given name.
Definition: RDom.h:47
Expr extent() const
The number that this variable will take on.
Expr min() const
The minimum value that this variable will take on.
std::string make_entity_name(void *stack_ptr, const std::string &type, char prefix)
Make a unique name for an object based on the name of the stack variable passed in.
Expr predicate(Expr e)
Expressions tagged with this intrinsic are suggestions that vectorization of loops with guard ifs sho...
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::ostream & operator<<(std::ostream &stream, const Expr &)
Emit an expression on an output stream (such as std::cout) in human-readable form.
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:578
std::vector< Range > Region
A multi-dimensional box.
Definition: Expr.h:343
A fragment of Halide syntax.
Definition: Expr.h:256
A single named dimension of a reduction domain.
Definition: Reduction.h:16