Short-circuiting reductions

[twesterhout]

Is there a way to achieve an early return or a short-circuiting reduction in Halide? (E.g. for a linear search)

[zvookin]

Only way is the .where(...) clause on an RDom and then hope the loop gets optimized. If the reduction operation is particularly expensive, the where clause will still help because it effectively puts an if around the computation of the reduction.

[twesterhout]

If I understand you correctly, you mean to use something like this:

Func reduction;
reduction() = Tuple{0, true};
RDom k{0, 5, "k"};
k.where(reduction()[1]);
reduction() = Tuple{reduction()[0] + k, select(k > 2, false, true)};

I would expect this to compute the sum for k up to 2. However, it throws the following error:

Unhandled exception: Internal Error at /home/halidenightly/build_bot/worker/halide-release_12-x86-64-linux-cmake/halide-source/src/IR.cpp:181 triggered by user code at : Condition failed: a.type().is_bool(): lhs of And is not a bool

[abadams]

The issue is that C silently promotes "false" and "true" to ints, so when Halide sees true or false it receives it as an int constant. That means reduction()[1] is an int. Use cast<bool>(true) instead.

[twesterhout]

Thanks! Halide produces very reasonable stmt now.