FFT optimizations/bug fixes

This pull request contains a bunch of optimizations to the FFT, as well as some optimizations/bug fixes I found in Halide while working on this.

Some notable changes are:

- Simplification rules for (x - y)*-a -> (y - x)*a, this is helpful to optimize complex multiplications that arise in the FFT frequently.
- Simplification for constant ramps modulo constants.
- More aggressive simplification of nested ifs with redundant conditions.
- Folds adjacent ifs with identical conditions (and fixed bug found in IREquality for blocks when writing unit tests for this).
- Added vector of Var/Expr parameters to Func::operator(). This helps support situations where placeholders don't work because the pure definition is undefined.
I guess I'd like more discussion and exploration of the design space before
extending the Func argument syntax.

-Z-


On Jul 12, 2014, at 11:28 AM, Andrew Adams <notifications@github.com> wrote:

In test/performance/fft.cpp:

>          exchange.bound(n1, 0, N);
>
> +        std::vector<Expr> _;

The issues at play here are: 1) The code is used with different numbers of
dimensions in different places, so some kind of underscore is needed 2) The
pure step needs to have the same pure args list as the update steps. So the
underscore needs to shake out the same way in the pure step as the update
steps. 3) One way to hack around 2 is to include a dummy reference to x in
the pure step, but this disallows the desired schedule (compute_at within
the update steps) Given all this I suggested that he just make an explicit
vector of args, starting from x's args. Calling it underscore is a probably
a bad idea. I also suggested adding a final optional std::vector<Var>
argument to FuncRefVar to support this sort of (var, var, rest of the vars)
style usage. Seeing as this is controversial, I'd suggest reverting this
change and doing: vector<args> a = ( x's args except for the first) Expr x0
= x(cons(0, a)); where cons is a local function the returns a new vector
prepended with the given arg. Also, there's no need for the lowercase x
references to be FuncRefExpr, right? They can just be Expr.
… <#>
On Sat, Jul 12, 2014 at 11:07 AM, Zalman Stern <notifications@github.com>
wrote: In test/performance/fft.cpp: > exchange.bound(n1, 0, N); > > +
std::vector<Expr> _; Please do not use underscore this way. The underscore
placeholder feature already takes us into a realm where we have to be very
careful to not write impenetrable code. Used properly it allows expressing
a function of an arbitrary number of arguments and sometimes that is
obviously the right thing. But those arguments don't have names and it has
to be obvious what they are and why their names are not needed. Moreover,
when scheduling, you can depend in the implicit arguments having the names
_0, _1, etc. It is not clear to me this property is preserved here. I'd
like to discuss why the standard underscore pattern doesn't work and
whether we can fix it without hacks like this. I'll comment directly on the
changes to Func.h, but I'd like to avoid those as I'm not sure they're
going to interact well with using variadic templates to do the function
application operators. I also think the code can be written clearly by
making to std:vectors of args with a shared suffix. Possibly with the help
of a vec_flattening operator: std::vector lhs = vec_flattening(n0,
(s_/S)*R*S + s_%S + r_*S, args); std::vector rhs = vec_flattening(r_, s_,
n0, r_*S, args); exchange(lhs) = exchange(rhs); std:: — Reply to this email
directly or view it on GitHub <
https://github.com/halide/Halide/pull/372/files#r14854553>.

—
Reply to this email directly or view it on GitHub
<https://github.com/halide/Halide/pull/372/files#r14854674>.