Halide 22.0.0 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
18namespace Halide {
19
20template<typename T, int Dims>
21class Buffer;
22class 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;
31 Internal::ReductionDomain _domain;
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. */
42 RVar()
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. */
53 RVar(Internal::ReductionDomain domain, int index)
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. */
65 Internal::ReductionDomain domain() const {
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 {
194 Internal::ReductionDomain dom;
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(const Expr &min, const 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 // @{
232 RDom(const Buffer<void, -1> &);
233 RDom(const OutputImageParam &);
234 template<typename T, int Dims>
235 HALIDE_NO_USER_CODE_INLINE RDom(const Buffer<T, Dims> &im)
236 : RDom(Buffer<void, -1>(im)) {
237 }
238 // @}
239
240 /** Construct a reduction domain that wraps an Internal ReductionDomain object. */
241 RDom(const Internal::ReductionDomain &d);
242
243 /** Get at the internal reduction domain object that this wraps. */
244 Internal::ReductionDomain domain() const {
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
internal_assert
#define internal_assert(c)
Definition: Error.h:232
Expr.h
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt)
Reduction.h
Defines internal classes related to Reduction Domains.
Util.h
Various utility functions used internally Halide.
HALIDE_NO_USER_CODE_INLINE
#define HALIDE_NO_USER_CODE_INLINE
Definition: Util.h:47
Halide::Buffer
A Halide::Buffer is a named shared reference to a Halide::Runtime::Buffer.
Definition: Buffer.h:122
Halide::Internal::ReductionDomain
A reference-counted handle on a reduction domain, which is just a vector of ReductionVariable.
Definition: Reduction.h:38
Halide::Internal::ReductionDomain::defined
bool defined() const
Is this handle non-nullptr.
Definition: Reduction.h:69
Halide::Internal::ReductionDomain::domain
const std::vector< ReductionVariable > & domain() const
Immutable access to the reduction variables.
Halide::Internal::ReductionDomain::same_as
bool same_as(const ReductionDomain &other) const
Tests for equality of reference.
Definition: Reduction.h:76
Halide::OutputImageParam
A handle on the output buffer of a pipeline.
Definition: OutputImageParam.h:19
Halide::RDom
A multi-dimensional domain over which to iterate.
Definition: RDom.h:193
Halide::RDom::same_as
bool same_as(const RDom &other) const
Compare two reduction domains for equality of reference.
Definition: RDom.h:254
Halide::RDom::defined
bool defined() const
Check if this reduction domain is non-null.
Definition: RDom.h:249
Halide::RDom::dimensions
int dimensions() const
Get the dimensionality of a reduction domain.
Halide::RDom::w
RVar w
Definition: RDom.h:339
Halide::RDom::RDom
RDom(const Internal::ReductionDomain &d)
Construct a reduction domain that wraps an Internal ReductionDomain object.
Halide::RDom::z
RVar z
Definition: RDom.h:339
Halide::RDom::RDom
RDom()=default
Construct an undefined reduction domain.
Halide::RDom::RDom
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
Halide::RDom::x
RVar x
Direct access to the first four dimensions of the reduction domain.
Definition: RDom.h:339
Halide::RDom::RDom
HALIDE_NO_USER_CODE_INLINE RDom(const Expr &min, const Expr &extent, Args &&...args)
Definition: RDom.h:220
Halide::RDom::where
void where(Expr predicate)
Add a predicate to the RDom.
Halide::RDom::RDom
RDom(const Buffer< void, -1 > &)
Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.
Halide::RDom::y
RVar y
Definition: RDom.h:339
Halide::RDom::operator[]
RVar operator[](int) const
Get at one of the dimensions of the reduction domain.
Halide::RDom::RDom
RDom(const OutputImageParam &)
Halide::RDom::RDom
HALIDE_NO_USER_CODE_INLINE RDom(const Buffer< T, Dims > &im)
Definition: RDom.h:235
Halide::RDom::domain
Internal::ReductionDomain domain() const
Get at the internal reduction domain object that this wraps.
Definition: RDom.h:244
Halide::RVar
A reduction variable represents a single dimension of a reduction domain (RDom).
Definition: RDom.h:29
Halide::RVar::RVar
RVar(Internal::ReductionDomain domain, int index)
Construct a reduction variable with the given name and bounds.
Definition: RDom.h:53
Halide::RVar::name
const std::string & name() const
The name of this reduction variable.
Halide::RVar::RVar
RVar()
An empty reduction variable.
Definition: RDom.h:42
Halide::RVar::domain
Internal::ReductionDomain domain() const
The reduction domain this is associated with.
Definition: RDom.h:65
Halide::RVar::RVar
RVar(const std::string &n)
Construct an RVar with the given name.
Definition: RDom.h:47
Halide::RVar::extent
Expr extent() const
The number that this variable will take on.
Halide::RVar::min
Expr min() const
The minimum value that this variable will take on.
Halide::Internal::ArgInfoKind::Buffer
@ Buffer
Halide::Internal::unique_name
std::string unique_name(char prefix)
Generate a unique name starting with the given prefix.
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::operator<<
std::ostream & operator<<(std::ostream &stream, const Expr &)
Emit an expression on an output stream (such as std::cout) in human-readable form.
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:625
Halide::Region
std::vector< Range > Region
A multi-dimensional box.
Definition: Expr.h:350
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:258
Halide::Internal::ReductionVariable
A single named dimension of a reduction domain.
Definition: Reduction.h:16