halide/Halide — pull request #469 by kree-colemcalughlin (2014-09-16 21:56:51+00:00)
Title: 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