Specialize branched loops

This pull request introduces a mutator that pulls branch statements outside of loops, breaking the loops into various special cases for each branch. We are conservative in deciding when to branch, the main trigger being explicit IfThenElse loops, which are introduced during the previous specialize_clamped_ramps pass. Select nodes of a vector type, but with a scalar condition can also trigger this, but I'm not sure how useful that is.

In order to explicitly create the branches I have also added a LinearSolver mutator, which may or may not be more generally useful. Basically, this mutator solves an expression that must be a comparison node (i.e. EQ, NE, LE, GE, LT, or GT) for a named variable. The expression must be linear in all "free" variables, i.e. variables not in the scope provided to the solver. The result of running the solver is an equivalent comparison Expr, where op->a (i.e. the LHS of the expression) is the requested variable.

I've done initial testing of the performance this code by running a 4-point Laplacian operator on the domain with varying boundary conditions. The rough data throughput rates for 2 basic boundary conditions are compared below:

repeat_edge:
------------------------------
master:  ~350 GB/s
branch:  ~1800 GB/s

constant_exterior:
------------------------------
master:  ~250 GB/s
branch:  ~500 GB/s

I'd just bail on unsigned types. We really only care about Int(32) in
practice. Maybe also Float for glsl.

On Fri, Sep 19, 2014 at 2:53 PM, Kree Cole-McLaughlin <
notifications@github.com> wrote:

> In src/LinearSolve.cpp:
>
> > +
> > +    if (terms[0].var) {
> > +        expr = Mul::make(terms[0].coeff, terms[0].var);
> > +    } else {
> > +        expr = terms[0].coeff;
> > +    }
> > +
> > +    for (size_t i = 1; i < terms.size(); ++i) {
> > +        if (terms[i].var) {
> > +            Expr c = terms[i].coeff;
> > +            Expr var = terms[i].var;
> > +            match_types(c, var);
> > +
> > +            Expr prod = Mul::make(c, var);
> > +            match_types(prod, expr);
> > +            expr = Add::make(expr, prod);
>
> This is a really good point, and I am addressing this. It would be great
> to get rid of all the match_types call around this visitor. But I do have
> one question about UInt's. I use normalize_types to convert any UInt Exprs
> to Int's, since you can really do the full range of solving operations
> you'd like to do on UInt's. Should I continue to do this, or should we say
> the solver doesn't handle UInt's and just bail out if it finds one?
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/halide/Halide/pull/469/files#r17811754>.
>