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.
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>.
>