[Mesa-dev] [PATCH] glsl: Optimize AND/OR reductions used in vec4 comparisons.

[Ian Romanick]

On 05/08/2013 07:21 PM, Matt Turner wrote:
> For vec4 equality comparisons we emit
>
>     (and (and (and a b) c) d)

Refresh my memory... what generates this?  Is this from the compiler 
itself, or are people writing this code by hand?  On old, vec4-centric 
architectures, this sort of thing was usually done with a dot-product. 
I'm assuming this showed up in some shader on a scalar architecture...

> which leads to three dependent instructions. We can reassociate the
> operands which allows the first two instructions to be issued
> independently. Turn it into:
>
>     (and (and a b) (and c d))
>
> Do the same thing for ORs, used in vec4 inequality comparisons.
> ---
> Maybe we should generally recognize reduction operations and reassociate
> operands to reduce tree depth? Do we see large reductions in real shaders?

It seems unlikely.  I believe other compilers have sophisticated passes 
that do Karnaugh map style simplifications of complex logic chains.  If 
we start to encounter complex bit- or logic- code, that will probably be 
the right thing to do.

>   src/glsl/opt_algebraic.cpp | 31 +++++++++++++++++++++++++++++++
>   1 file changed, 31 insertions(+)
>
> diff --git a/src/glsl/opt_algebraic.cpp b/src/glsl/opt_algebraic.cpp
> index d706a6a..af0229c 100644
> --- a/src/glsl/opt_algebraic.cpp
> +++ b/src/glsl/opt_algebraic.cpp
> @@ -32,8 +32,11 @@
>   #include "ir_visitor.h"
>   #include "ir_rvalue_visitor.h"
>   #include "ir_optimization.h"
> +#include "ir_builder.h"
>   #include "glsl_types.h"
>
> +using namespace ir_builder;
> +
>   namespace {
>
>   /**
> @@ -351,6 +354,20 @@ ir_algebraic_visitor::handle_expression(ir_expression *ir)
>         } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
>   	 this->progress = true;
>   	 return ir_constant::zero(mem_ctx, ir->type);
> +      } else if (op_expr[1] && op_expr[1]->operation == ir_binop_logic_and) {
> +         /* Translates (and (and (and a b) c) d) into
> +          *            (and (and a b) (and c d)).
> +          * This allows the independent ANDs to be issued at the same time.
> +          */
> +         ir_expression *expr = op_expr[1]->operands[1]->as_expression();
> +
> +         if (expr && expr->operation == ir_binop_logic_and) {
> +            ir->operands[0] = logic_and(ir->operands[0],
> +                                        ir->operands[1]->as_expression()->operands[0]);
> +            ir->operands[1] = logic_and(expr->operands[0],
> +                                        expr->operands[1]);
> +            this->progress = true;
> +         }
>         }
>         break;
>
> @@ -389,6 +406,20 @@ ir_algebraic_visitor::handle_expression(ir_expression *ir)
>
>   	 this->progress = true;
>   	 return new(mem_ctx) ir_constant(ir->type, &data);
> +      } else if (op_expr[1] && op_expr[1]->operation == ir_binop_logic_or) {
> +         /* Translates (or (or (or a b) c) d) into
> +          *            (or (or a b) (or c d)).
> +          * This allows the independent ORs to be issued at the same time.
> +          */
> +         ir_expression *expr = op_expr[1]->operands[1]->as_expression();
> +
> +         if (expr && expr->operation == ir_binop_logic_or) {
> +            ir->operands[0] = logic_or(ir->operands[0],
> +                                       ir->operands[1]->as_expression()->operands[0]);
> +            ir->operands[1] = logic_or(expr->operands[0],
> +                                       expr->operands[1]);
> +            this->progress = true;
> +         }
>         }
>         break;
>
>