Halide 19.0.0
Halide compiler and libraries
Loading...
Searching...
No Matches
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
18namespace Halide {
19
20template<typename T, int Dims>
21class Buffer;
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. */
29class 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
40public:
41 /** An empty reduction variable. */
43 : _name(Internal::unique_name('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 */
193class RDom {
195
196 void init_vars(const std::string &name);
197
198 void validate_min_extent(const Expr &min, const Expr &extent);
199 void initialize_from_region(const Region &region, std::string name = "");
200
201 template<typename... Args>
202 HALIDE_NO_USER_CODE_INLINE void initialize_from_region(Region &region, const Expr &min, const Expr &extent, Args &&...args) {
203 validate_min_extent(min, extent);
204 region.emplace_back(min, extent);
205 initialize_from_region(region, std::forward<Args>(args)...);
206 }
207
208public:
209 /** Construct an undefined reduction domain. */
210 RDom() = default;
211
212 /** Construct a multi-dimensional reduction domain with the given name. If the name
213 * is left blank, a unique one is auto-generated. */
214 // @{
215 HALIDE_NO_USER_CODE_INLINE RDom(const Region &region, std::string name = "") {
216 initialize_from_region(region, std::move(name));
217 }
218
219 template<typename... Args>
220 HALIDE_NO_USER_CODE_INLINE RDom(Expr min, Expr extent, Args &&...args) {
221 // This should really just be a delegating constructor, but I couldn't make
222 // that work with variadic template unpacking in visual studio 2013
223 Region region;
224 initialize_from_region(region, min, extent, std::forward<Args>(args)...);
225 }
226 // @}
227
228 /** Construct a reduction domain that iterates over all points in
229 * a given Buffer or ImageParam. Has the same dimensionality as
230 * the argument. */
231 // @{
234 template<typename T, int Dims>
236 : RDom(Buffer<void, -1>(im)) {
237 }
238 // @}
239
240 /** Construct a reduction domain that wraps an Internal ReductionDomain object. */
242
243 /** Get at the internal reduction domain object that this wraps. */
245 return dom;
246 }
247
248 /** Check if this reduction domain is non-null */
249 bool defined() const {
250 return dom.defined();
251 }
252
253 /** Compare two reduction domains for equality of reference */
254 bool same_as(const RDom &other) const {
255 return dom.same_as(other.dom);
256 }
257
258 /** Get the dimensionality of a reduction domain */
259 int dimensions() const;
260
261 /** Get at one of the dimensions of the reduction domain */
262 RVar operator[](int) const;
263
264 /** Single-dimensional reduction domains can be used as RVars directly. */
265 operator RVar() const;
266
267 /** Single-dimensional reduction domains can be also be used as Exprs directly. */
268 operator Expr() const;
269
270 /** Add a predicate to the RDom. An RDom may have multiple
271 * predicates associated with it. An update definition that uses
272 * an RDom only iterates over the subset points in the domain for
273 * which all of its predicates are true. The predicate expression
274 * obeys the same rules as the expressions used on the
275 * right-hand-side of the corresponding update definition. It may
276 * refer to the RDom's variables and free variables in the Func's
277 * update definition. It may include calls to other Funcs, or make
278 * recursive calls to the same Func. This permits iteration over
279 * non-rectangular domains, or domains with sizes that vary with
280 * some free variable, or domains with shapes determined by some
281 * other Func.
282 *
283 * Note that once RDom is used in the update definition of some
284 * Func, no new predicates can be added to the RDom.
285 *
286 * Consider a simple example:
287 \code
288 RDom r(0, 20, 0, 20);
289 r.where(r.x < r.y);
290 r.where(r.x == 10);
291 r.where(r.y > 13);
292 f(r.x, r.y) += 1;
293 \endcode
294 * This is equivalent to:
295 \code
296 for (int r.y = 0; r.y < 20; r.y++) {
297 if (r.y > 13) {
298 for (int r.x = 0; r.x < 20; r.x++) {
299 if (r.x == 10) {
300 if (r.x < r.y) {
301 f[r.x, r.y] += 1;
302 }
303 }
304 }
305 }
306 }
307 \endcode
308 *
309 * Where possible Halide restricts the range of the containing for
310 * loops to avoid the cases where the predicate is false so that
311 * the if statement can be removed entirely. The case above would
312 * be further simplified into:
313 *
314 \code
315 for (int r.y = 14; r.y < 20; r.y++) {
316 f[10, r.y] += 1;
317 }
318 \endcode
319 *
320 * In general, the predicates that we can simplify away by
321 * restricting loop ranges are inequalities that compare an inner
322 * Var or RVar to some expression in outer Vars or RVars.
323 *
324 * You can also pack multiple conditions into one predicate like so:
325 *
326 \code
327 RDom r(0, 20, 0, 20);
328 r.where((r.x < r.y) && (r.x == 10) && (r.y > 13));
329 f(r.x, r.y) += 1;
330 \endcode
331 *
332 */
333 void where(Expr predicate);
334
335 /** Direct access to the first four dimensions of the reduction
336 * domain. Some of these variables may be undefined if the
337 * reduction domain has fewer than four dimensions. */
338 // @{
339 RVar x, y, z, w;
340 // @}
341};
342
343/** Emit an RVar in a human-readable form */
344std::ostream &operator<<(std::ostream &stream, const RVar &);
345
346/** Emit an RDom in a human-readable form. */
347std::ostream &operator<<(std::ostream &stream, const RDom &);
348} // namespace Halide
349
350#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:47
A Halide::Buffer is a named shared reference to a Halide::Runtime::Buffer.
Definition RDom.h:21
A reference-counted handle on a reduction domain, which is just a vector of ReductionVariable.
Definition Reduction.h:33
bool defined() const
Is this handle non-nullptr.
Definition Reduction.h:64
const std::vector< ReductionVariable > & domain() const
Immutable access to the reduction variables.
bool same_as(const ReductionDomain &other) const
Tests for equality of reference.
Definition Reduction.h:71
A handle on the output buffer of a pipeline.
A multi-dimensional domain over which to iterate.
Definition RDom.h:193
bool same_as(const RDom &other) const
Compare two reduction domains for equality of reference.
Definition RDom.h:254
bool defined() const
Check if this reduction domain is non-null.
Definition RDom.h:249
int dimensions() const
Get the dimensionality of a reduction domain.
RVar w
Definition RDom.h:339
RDom(const Internal::ReductionDomain &d)
Construct a reduction domain that wraps an Internal ReductionDomain object.
RVar z
Definition RDom.h:339
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:215
RVar x
Direct access to the first four dimensions of the reduction domain.
Definition RDom.h:339
void where(Expr predicate)
Add a predicate to the RDom.
RDom(const Buffer< void, -1 > &)
Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.
RVar y
Definition RDom.h:339
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:220
HALIDE_NO_USER_CODE_INLINE RDom(const Buffer< T, Dims > &im)
Definition RDom.h:235
Internal::ReductionDomain domain() const
Get at the internal reduction domain object that this wraps.
Definition RDom.h:244
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
const std::string & name() const
The name of this reduction variable.
RVar()
An empty reduction variable.
Definition RDom.h:42
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.
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.
std::vector< Range > Region
A multi-dimensional box.
Definition Expr.h:350
A fragment of Halide syntax.
Definition Expr.h:258
A single named dimension of a reduction domain.
Definition Reduction.h:16