optimize for affine values

[pca006132]

For SDFs like the metaballs where $r_i, p_i$ are the radius and the center for the ball $i$, and $g$ be some interpolation from 0 to 1:

$$f(p) = \sum_i g(r_i - \left\vert p - p_i \right\vert )$$

Oftentimes the interpolation function will be capped at 0 or 1, making some of the summands constants. However, currently there is no way to partially evaluate this and collapse those constant summands.

To optimize for this kind of situation, we can try to track affine values, e.g. $r * c_1 + c_2$ where $r$ is a register and $c_1, c_2$ are constants. We can mark some instructions like $r_3 = r_1 + r_2$ as dead if either $r_1$ or $r_2$ is a constant, or they are both affine values with the same register. And we can later convert this result back to an interval when necessary, i.e. when an instruction that does not produce an affine value takes it.

[mkeeter]

Would short-circuiting Add and Mul opcodes work to simplify this kind of summation? e.g. something like

• SpecialAdd performs addition, and could be simplified if either side was 0
• SpecialMul performs multiplication, and could be simplified if either side was 0 or 1

I wrote And and Or opcodes for a similar short-circuiting use case (see #58), but – for reason I've forgotten – didn't give them Mul / Add semantics.

[pca006132]

Short-circuiting Add and Mul can help, but it would be less general. That said, maybe the less general approach is good enough and can make evaluation/simplification faster :)

[avibryant]

This is a bit of a hobby horse for me but I've had very good results from this kind of affine representation in simplifying compute DAGs. There's a brief description of how I did it for Rainier at https://rainier.fit/img/rainier.pdf . It can be done as an IR that expands back into normal Add, Mul etc in the bytecode (which is what I did there also).

[pca006132]

Note that this can also be helpful when you optimize the code statically, for example you can optimize the following without trying to do things like a re-association pass and rerun constant folding.

x1 = x + 1
x2 = x1 + 1
-----------
x1 = x + 1 // may now be dead code
x2 = x + 2

I did this in the manifold implementation (statically, tape optimization is the next thing to do) and this removes some more instructions.