glsl: Modify strategy for accumulating conditions when lowering if-statements
authorIan Romanick <ian.d.romanick@intel.com>
Mon, 1 Aug 2011 21:13:10 +0000 (14:13 -0700)
committerIan Romanick <ian.d.romanick@intel.com>
Mon, 15 Aug 2011 18:44:27 +0000 (11:44 -0700)
commita352e2d08e0a141298275e77f25541218a97afb7
tree7b5e74350cc9169fb88253d9c3f88dcfc949c2eb
parent4a026d6ba50034c326eb6cfd0b555f57d83ab609
glsl: Modify strategy for accumulating conditions when lowering if-statements

Previously if-statements were lowered from inner-most to outer-most
(i.e., bottom-up).  All assignments within an if-statement would have
the condition of the if-statement appended to its existing condition.
As a result the assignments from a deeply nested if-statement would
have a very long and complex condition.

Several shaders in the OpenGL ES2 conformance test suite contain
non-constant array indexing that has been lowered by the shader
writer.  These tests usually look something like:

    if (i == 0) {
        value = array[0];
    } else if (i == 1) {
        value = array[1];
    } else ...

The IR for the last assignment ends up as:

    (assign (expression bool && (expression bool ! (var_ref if_to_cond_assign_condition) ) (expression bool && (expression bool ! (var_ref if_to_cond_assign_condition@20) ) (expression bool && (expression bool ! (var_ref if_to_cond_assign_condition@22) ) (expression bool && (expression bool ! (var_ref if_to_cond_assign_condition@24) ) (var_ref if_to_cond_assign_condition@26) ) ) ) )  (x) (var_ref value) (array_ref (var_ref array) (constant int (5)))

The Mesa IR that is generated from this is just as awesome as you
might expect.

Three changes are made to the way if-statements are lowered.

1. Two condition variables, if_to_cond_assign_then and
if_to_cond_assign_else, are created for each if-then-else structure.
The former contains the "positive" condition, and the later contains
the "negative" condtion.  This change was implemented in the previous
patch.

2. Each condition variable is added to a hash-table when it is created.

3. When lowering an if-statement, assignments to existing condtion
variables get the current condition anded.  This ensures that nested
condition variables are only set to true when the condition variable
for all outer if-statements is also true.

Changes #1 and #3 combine to ensure the correctness of the resulting
code.

4. When a condition assignment is encountered with a condition that is
a dereference of a previously added condition variable, the condition
is not modified.

Change #4 prevents the continuous accumulation of conditions on
assignments.

If the original if-statements were:

    if (x) {
        if (a && b && c && d && e) {
            ...
        } else {
            ...
        }
    } else {
        if (g && h && i && j && k) {
            ...
        } else {
            ...
        }
    }

The lowered code will be

    if_to_cond_assign_then@1 = x;
    if_to_cond_assign_then@2 = a && b && c && d && e
        && if_to_cond_assign_then@1;
    ...
    if_to_cond_assign_else@2 = !if_to_cond_assign_then
        && if_to_cond_assign_then@1;
    ...

    if_to_cond_assign_else@1 = !if_to_cond_assign_then@1;
    if_to_cond_assign_then@3 = g && h && i && j;
        && if_to_cond_assign_else@1;
    ...
    if_to_cond_assign_else@3 = !if_to_cond_assign_then
        && if_to_cond_assign_else@1;
    ...

Depending on how instructions are emitted, there may be an extra
instruction due to the duplication of the '&&
if_to_cond_assign_{then,else}@1' on the nested else conditions.  In
addition, this may cause some unnecessary register pressure since in
the simple case (where the nested conditions are not complex) the
nested then-condition variables are live longer than strictly
necessary.

Before this change, one of the shaders in the OpenGL ES2 conformance
test suite's acos_float_frag_xvary generated 348 Mesa IR instructions.
After this change it only generates 124.  Many, but not all, of these
instructions would have also been eliminated by CSE.

Reviewed-by: Eric Anholt <eric@anholt.net>
src/glsl/lower_if_to_cond_assign.cpp