Halide 22.0.0 Halide compiler and libraries

Public Member Functions | Public Attributes | List of all members
Halide::RDom Class Reference

A multi-dimensional domain over which to iterate. More...

`#include <RDom.h>`

## Public Member Functions
| RDom ()=default
| Construct an undefined reduction domain. More...
HALIDE_NO_USER_CODE_INLINE | RDom (const Region &region, std::string name="")
| Construct a multi-dimensional reduction domain with the given name. More...
template<typename... Args>
HALIDE_NO_USER_CODE_INLINE | RDom (const Expr &min, const Expr &extent, Args &&...args)
| RDom (const Buffer< void, -1 > &)
| Construct a reduction domain that iterates over all points in a given Buffer or ImageParam. More...
| RDom (const OutputImageParam &)
template<typename T , int Dims>
HALIDE_NO_USER_CODE_INLINE | RDom (const Buffer< T, Dims > &im)
| RDom (const Internal::ReductionDomain &d)
| Construct a reduction domain that wraps an Internal ReductionDomain object. More...
Internal::ReductionDomain | domain () const
| Get at the internal reduction domain object that this wraps. More...
bool | defined () const
| Check if this reduction domain is non-null. More...
bool | same_as (const RDom &other) const
| Compare two reduction domains for equality of reference. More...
int | dimensions () const
| Get the dimensionality of a reduction domain. More...
RVar | operator[] (int) const
| Get at one of the dimensions of the reduction domain. More...
| operator RVar () const
| Single-dimensional reduction domains can be used as RVars directly. More...
| operator Expr () const
| Single-dimensional reduction domains can be also be used as Exprs directly. More...
void | where (Expr predicate)
| Add a predicate to the RDom. More...

## Public Attributes
RVar | x
| Direct access to the first four dimensions of the reduction domain. More...
RVar | y
RVar | z
RVar | w

## Detailed Description

A multi-dimensional domain over which to iterate.

Used when defining functions with update definitions.

An reduction is a function with a two-part definition. It has an initial value, which looks much like a pure function, and an update definition, which may refer to some RDom. Evaluating such a function first initializes it over the required domain (which is inferred based on usage), and then runs update rule for all points in the RDom. For example:

Func f;
Var x;
RDom r(0, 10);
f(x) = x; // the initial value
f(r) = f(r) * 2;
Buffer<int> result = f.realize({10});
Halide::RDom::RDom
RDom()=default
Construct an undefined reduction domain.
Halide::RDom::x
RVar x
Direct access to the first four dimensions of the reduction domain.
Definition: RDom.h:339

This function creates a single-dimensional buffer of size 10, in which element x contains the value x*2. Internally, first the initialization rule fills in x at every site, and then the update definition doubles every site.

One use of reductions is to build a function recursively (pure functions in halide cannot be recursive). For example, this function fills in an array with the first 20 fibonacci numbers:

Func f;
Var x;
RDom r(2, 18);
f(x) = 1;
f(r) = f(r-1) + f(r-2);

Another use of reductions is to perform scattering operations, as unlike a pure function declaration, the left-hand-side of an update definition may contain general expressions:

ImageParam input(UInt(8), 2);
Func histogram;
Var x;
RDom r(input); // Iterate over all pixels in the input
histogram(x) = 0;
histogram(input(r.x, r.y)) = histogram(input(r.x, r.y)) + 1;
Halide::UInt
Type UInt(int bits, int lanes=1)
Constructing an unsigned integer type.
Definition: Type.h:546

An update definition may also be multi-dimensional. This example computes a summed-area table by first summing horizontally and then vertically:

ImageParam input(Float(32), 2);
Func sum_x, sum_y;
Var x, y;
RDom r(input);
sum_x(x, y) = input(x, y);
sum_x(r.x, r.y) = sum_x(r.x, r.y) + sum_x(r.x-1, r.y);
sum_y(x, y) = sum_x(x, y);
sum_y(r.x, r.y) = sum_y(r.x, r.y) + sum_y(r.x, r.y-1);
Halide::RDom::y
RVar y
Definition: RDom.h:339
Halide::Float
Type Float(int bits, int lanes=1)
Construct a floating-point type.
Definition: Type.h:551

You can also mix pure dimensions with reduction variables. In the previous example, note that there's no need for the y coordinate in sum_x to be traversed serially. The sum within each row is entirely independent. The rows could be computed in parallel, or in a different order, without changing the meaning. Therefore, we can instead write this definition as follows:

ImageParam input(Float(32), 2);
Func sum_x, sum_y;
Var x, y;
RDom r(input);
sum_x(x, y) = input(x, y);
sum_x(r.x, y) = sum_x(r.x, y) + sum_x(r.x-1, y);
sum_y(x, y) = sum_x(x, y);
sum_y(x, r.y) = sum_y(x, r.y) + sum_y(x, r.y-1);

This lets us schedule it more flexibly. You can now parallelize the update step of sum_x over y by calling:

sum_x.update().parallel(y).

Note that calling sum_x.parallel(y) only parallelizes the initialization step, and not the update step! Scheduling the update step of a reduction must be done using the handle returned by Func::update(). This code parallelizes both the initialization step and the update step:

sum_x.parallel(y);
sum_x.update().parallel(y);

When you mix reduction variables and pure dimensions, the reduction domain is traversed outermost. That is, for each point in the reduction domain, the inferred pure domain is traversed in its entirety. For the above example, this means that sum_x walks down the columns, and sum_y walks along the rows. This may not be cache-coherent. You may try reordering these dimensions using the schedule, but Halide will return an error if it decides that this risks changing the meaning of your function. The solution lies in clever scheduling. If we say:

sum_x.compute_at(sum_y, y);

Then the sum in x is computed only as necessary for each scanline of the sum in y. This not only results in sum_x walking along the rows, it also improves the locality of the entire pipeline.

Definition at line 193 of file RDom.h.

## Constructor & Destructor Documentation

## ◆ RDom() [1/7]

Halide::RDom::RDom | ( |  | ) |
| default

Construct an undefined reduction domain.

## ◆ RDom() [2/7]

HALIDE_NO_USER_CODE_INLINE Halide::RDom::RDom | ( | const Region & | region,
|  | std::string | name = `""`
| ) |  |
| inline

Construct a multi-dimensional reduction domain with the given name.

If the name is left blank, a unique one is auto-generated.

Definition at line 215 of file RDom.h.

## ◆ RDom() [3/7]

template<typename... Args>

HALIDE_NO_USER_CODE_INLINE Halide::RDom::RDom | ( | const Expr & | min,
|  | const Expr & | extent,
|  | Args &&... | args
| ) |  |
| inline

Definition at line 220 of file RDom.h.

References Halide::min().

## ◆ RDom() [4/7]

Halide::RDom::RDom | ( | const Buffer< void, -1 > & |  | ) |

Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.

Has the same dimensionality as the argument.

## ◆ RDom() [5/7]

Halide::RDom::RDom | ( | const OutputImageParam & |  | ) |

## ◆ RDom() [6/7]

template<typename T , int Dims>

HALIDE_NO_USER_CODE_INLINE Halide::RDom::RDom | ( | const Buffer< T, Dims > & | im | ) |
| inline

Definition at line 235 of file RDom.h.

## ◆ RDom() [7/7]

Halide::RDom::RDom | ( | const Internal::ReductionDomain & | d | ) |

Construct a reduction domain that wraps an Internal ReductionDomain object.

## Member Function Documentation

## ◆ domain()

Internal::ReductionDomain Halide::RDom::domain | ( |  | ) | const
| inline

Get at the internal reduction domain object that this wraps.

Definition at line 244 of file RDom.h.

## ◆ defined()

bool Halide::RDom::defined | ( |  | ) | const
| inline

Check if this reduction domain is non-null.

Definition at line 249 of file RDom.h.

References Halide::Internal::ReductionDomain::defined().

## ◆ same_as()

bool Halide::RDom::same_as | ( | const RDom & | other | ) | const
| inline

Compare two reduction domains for equality of reference.

Definition at line 254 of file RDom.h.

References Halide::Internal::ReductionDomain::same_as().

## ◆ dimensions()

int Halide::RDom::dimensions | ( |  | ) | const

Get the dimensionality of a reduction domain.

## ◆ operator[]()

RVar Halide::RDom::operator[] | ( | int |  | ) | const

Get at one of the dimensions of the reduction domain.

## ◆ operator RVar()

Halide::RDom::operator RVar | ( |  | ) | const

Single-dimensional reduction domains can be used as RVars directly.

## ◆ operator Expr()

Halide::RDom::operator Expr | ( |  | ) | const

Single-dimensional reduction domains can be also be used as Exprs directly.

## ◆ where()

void Halide::RDom::where | ( | Expr | predicate | ) |

Add a predicate to the RDom.

An RDom may have multiple predicates associated with it. An update definition that uses an RDom only iterates over the subset points in the domain for which all of its predicates are true. The predicate expression obeys the same rules as the expressions used on the right-hand-side of the corresponding update definition. It may refer to the RDom's variables and free variables in the Func's update definition. It may include calls to other Funcs, or make recursive calls to the same Func. This permits iteration over non-rectangular domains, or domains with sizes that vary with some free variable, or domains with shapes determined by some other Func.

Note that once RDom is used in the update definition of some Func, no new predicates can be added to the RDom.

Consider a simple example:

RDom r(0, 20, 0, 20);
r.where(r.x < r.y);
r.where(r.x == 10);
r.where(r.y > 13);
f(r.x, r.y) += 1;

This is equivalent to:

for (int r.y = 0; r.y < 20; r.y++) {
if (r.y > 13) {
for (int r.x = 0; r.x < 20; r.x++) {
if (r.x == 10) {
if (r.x < r.y) {
f[r.x, r.y] += 1;
}
}
}
}
}

Where possible Halide restricts the range of the containing for loops to avoid the cases where the predicate is false so that the if statement can be removed entirely. The case above would be further simplified into:

for (int r.y = 14; r.y < 20; r.y++) {
f[10, r.y] += 1;
}

In general, the predicates that we can simplify away by restricting loop ranges are inequalities that compare an inner Var or RVar to some expression in outer Vars or RVars.

You can also pack multiple conditions into one predicate like so:

RDom r(0, 20, 0, 20);
r.where((r.x < r.y) && (r.x == 10) && (r.y > 13));
f(r.x, r.y) += 1;

## Member Data Documentation

## ◆ x

RVar Halide::RDom::x

Direct access to the first four dimensions of the reduction domain.

Some of these variables may be undefined if the reduction domain has fewer than four dimensions.

Definition at line 339 of file RDom.h.

Referenced by Halide::SimdOpCheckTest::check_one().

## ◆ y

RVar Halide::RDom::y

Definition at line 339 of file RDom.h.

Referenced by Halide::SimdOpCheckTest::check_one().

## ◆ z

RVar Halide::RDom::z

Definition at line 339 of file RDom.h.

## ◆ w

RVar Halide::RDom::w

Definition at line 339 of file RDom.h.

The documentation for this class was generated from the following file:

- src/RDom.h