[Mesa-dev] [PATCH] glsl: Add an optimization pass to flatten simple nested if blocks.

[Kenneth Graunke]

On 04/04/2013 09:08 AM, Eric Anholt wrote:
> Kenneth Graunke <kenneth at whitecape.org> writes:
>> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
>> index c294aa4..b5282a6 100644
>> --- a/src/glsl/Makefile.sources
>> +++ b/src/glsl/Makefile.sources
>> @@ -80,6 +80,7 @@ LIBGLSL_FILES = \
>>   	$(GLSL_SRCDIR)/opt_dead_code.cpp \
>>   	$(GLSL_SRCDIR)/opt_dead_code_local.cpp \
>>   	$(GLSL_SRCDIR)/opt_dead_functions.cpp \
>> +	$(GLSL_SRCDIR)/opt_flatten_nested_if_blocks.cpp \
>>   	$(GLSL_SRCDIR)/opt_function_inlining.cpp \
>>   	$(GLSL_SRCDIR)/opt_if_simplification.cpp \
>>   	$(GLSL_SRCDIR)/opt_noop_swizzle.cpp \
>> diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
>> index 9740903..0992294 100644
>> --- a/src/glsl/glsl_parser_extras.cpp
>> +++ b/src/glsl/glsl_parser_extras.cpp
>> @@ -1218,6 +1218,7 @@ do_common_optimization(exec_list *ir, bool linked,
>>         progress = do_structure_splitting(ir) || progress;
>>      }
>>      progress = do_if_simplification(ir) || progress;
>> +   progress = opt_flatten_nested_if_blocks(ir) || progress;
>>      progress = do_copy_propagation(ir) || progress;
>>      progress = do_copy_propagation_elements(ir) || progress;
>>      if (linked)
>> diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
>> index 2454bbe..a8885d7 100644
>> --- a/src/glsl/ir_optimization.h
>> +++ b/src/glsl/ir_optimization.h
>> @@ -82,6 +82,7 @@ bool do_function_inlining(exec_list *instructions);
>>   bool do_lower_jumps(exec_list *instructions, bool pull_out_jumps = true, bool lower_sub_return = true, bool lower_main_return = false, bool lower_continue = false, bool lower_break = false);
>>   bool do_lower_texture_projection(exec_list *instructions);
>>   bool do_if_simplification(exec_list *instructions);
>> +bool opt_flatten_nested_if_blocks(exec_list *instructions);
>>   bool do_discard_simplification(exec_list *instructions);
>>   bool lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth = 0);
>>   bool do_mat_op_to_vec(exec_list *instructions);
>> diff --git a/src/glsl/opt_flatten_nested_if_blocks.cpp b/src/glsl/opt_flatten_nested_if_blocks.cpp
>> new file mode 100644
>> index 0000000..c702102
>> --- /dev/null
>> +++ b/src/glsl/opt_flatten_nested_if_blocks.cpp
>> @@ -0,0 +1,103 @@
>> +/*
>> + * Copyright © 2013 Intel Corporation
>> + *
>> + * Permission is hereby granted, free of charge, to any person obtaining a
>> + * copy of this software and associated documentation files (the "Software"),
>> + * to deal in the Software without restriction, including without limitation
>> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
>> + * and/or sell copies of the Software, and to permit persons to whom the
>> + * Software is furnished to do so, subject to the following conditions:
>> + *
>> + * The above copyright notice and this permission notice (including the next
>> + * paragraph) shall be included in all copies or substantial portions of the
>> + * Software.
>> + *
>> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
>> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
>> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
>> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
>> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
>> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
>> + * DEALINGS IN THE SOFTWARE.
>> + */
>> +
>> +/**
>> + * \file opt_flatten_nested_if_blocks.cpp
>> + *
>> + * Flattens nested if blocks such as:
>> + *
>> + * if (x) {
>> + *    if (y) {
>> + *       ...
>> + *    }
>> + * }
>> + *
>> + * into a single if block with a combined condition:
>> + *
>> + * if (x && y) {
>> + *    ...
>> + * }
>> + */
>> +
>> +#include "ir.h"
>> +#include "ir_builder.h"
>> +
>> +using namespace ir_builder;
>> +
>> +namespace {
>> +
>> +class nested_if_flattener : public ir_hierarchical_visitor {
>> +public:
>> +   nested_if_flattener()
>> +   {
>> +      progress = false;
>> +   }
>> +
>> +   ir_visitor_status visit_leave(ir_if *);
>> +   ir_visitor_status visit_enter(ir_assignment *);
>> +
>> +   bool progress;
>> +};
>> +
>> +} /* unnamed namespace */
>> +
>> +/* We only care about the top level "if" instructions, so don't
>> + * descend into expressions.
>> + */
>> +ir_visitor_status
>> +nested_if_flattener::visit_enter(ir_assignment *ir)
>> +{
>> +   (void) ir;
>> +   return visit_continue_with_parent;
>> +}
>> +
>> +bool
>> +opt_flatten_nested_if_blocks(exec_list *instructions)
>> +{
>> +   nested_if_flattener v;
>> +
>> +   v.run(instructions);
>> +   return v.progress;
>> +}
>> +
>> +
>> +ir_visitor_status
>> +nested_if_flattener::visit_leave(ir_if *ir)
>> +{
>> +   /* Only handle a single ir_if within the then clause of an ir_if.  No extra
>> +    * instructions, no else clauses, nothing.
>> +    */
>> +   if (ir->then_instructions.is_empty() || !ir->else_instructions.is_empty())
>> +      return visit_continue;
>> +
>> +   ir_if *inner = ((ir_instruction *) ir->then_instructions.head)->as_if();
>> +   if (!inner || !inner->next->is_tail_sentinel() ||
>> +       !inner->else_instructions.is_empty())
>> +      return visit_continue;
>> +
>> +   ir->condition = logic_and(ir->condition, inner->condition);
>> +   inner->then_instructions.move_nodes_to(&ir->then_instructions);
>> +
>
> Also inner->remove() right now instead of leaving it up to the
> empty-if-statement-remover?  Equivalent functionality, but may take one
> less turn through the giant loop.

It's not actually necessary.  move_nodes_to throws away all nodes in the 
target list, effectively doing the remove for us.

> Other than that,
> Reviewed-by: Eric Anholt <eric at anholt.net>
>
> I'm glad to see this failry simple optimization made possible by us
> having removed things-with-side-effects from expression trees.  We may
> some day find a need to not do this optimization if the inner expression
> tree is very large, but for now it looks like it's an obvious win on the
> shaders we have on Linux.

Yeah, pure expression trees are really nice.

Thanks!