[Mesa-dev] [PATCH v2] glsl: Optimize min/max expression trees
Iago Toral Quiroga
itoral at igalia.com
Sun Sep 28 23:11:49 PDT 2014
On vie, 2014-09-26 at 12:57 -0400, Connor Abbott wrote:
> On Fri, Sep 26, 2014 at 9:02 AM, Iago Toral Quiroga <itoral at igalia.com> wrote:
> > Original patch by Petri Latvala <petri.latvala at intel.com>:
> >
> > Add an optimization pass that drops min/max expression operands that
> > can be proven to not contribute to the final result. The algorithm is
> > similar to alpha-beta pruning on a minmax search, from the field of
> > AI.
> >
> > This optimization pass can optimize min/max expressions where operands
> > are min/max expressions. Such code can appear in shaders by itself, or
> > as the result of clamp() or AMD_shader_trinary_minmax functions.
> >
> > This optimization pass improves the generated code for piglit's
> > AMD_shader_trinary_minmax tests as follows:
> >
> > total instructions in shared programs: 75 -> 67 (-10.67%)
> > instructions in affected programs: 60 -> 52 (-13.33%)
> > GAINED: 0
> > LOST: 0
> >
> > All tests (max3, min3, mid3) improved.
> >
> > A full shader-db run:
> >
> > total instructions in shared programs: 4293603 -> 4293575 (-0.00%)
> > instructions in affected programs: 1188 -> 1160 (-2.36%)
> > GAINED: 0
> > LOST: 0
> >
> > Improvements happen in Guacamelee and Serious Sam 3. One shader from
> > Dungeon Defenders is hurt by shader-db metrics (26 -> 28), because of
> > dropping of a (constant float (0.00000)) operand, which was
> > compiled to a saturate modifier.
> >
> > Version 2 by Iago Toral Quiroga <itoral at igalia.com>:
> >
> > Changes from review feedback:
> > - Squashed various cosmetic changes sent by Matt Turner.
> > - Make less_all_components return an enum rather than setting a class member.
> > (Suggested by Mat Turner). Also, renamed it to compare_components.
> > - Make less_all_components, smaller_constant and larger_constant static.
> > (Suggested by Mat Turner)
> > - Change mixmax_range to call its limits "low" and "high" instead of
> > "range[0]" and "range[1]". (Suggested by Connor Abbot).
> > - Use ir_builder swizzle helpers in swizzle_if_required(). (Suggested by
> > Connor Abbot).
> > - Make the logic more clearer by rearrenging the code and commenting.
> > (Suggested by Connor Abbot).
> > - Added comment to explain why we need to recurse twice. (Suggested by
> > Connor Abbot).
> > - If we cannot prune an expression, do not return early. Instead, attempt
> > to prune its children. (Suggested by Connor Abbot).
> >
> > Other changes:
> > - Instead of having a global "valid" visitor member, let the various functions
> > that can determine this status return a boolean and check for its value
> > to decide what to do in each case. This is more flexible and allows to
> > recurse into children of parents that could not be prunned due to invalid
> > ranges (so related to the last bullet in the review feedback).
> > - Make sure we always check if a range is valid before working with it. Since
> > any use of get_range, combine_range or range_intersection can invalidate
> > a range we should check for this situation every time we use any of these
> > functions.
> >
> > No piglit regressions observed with Version 2.
> >
> > Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=76861
> > ---
> >
> > Version 2 also passes all unit tests sent by Petri in the original series.
> >
> > src/glsl/Makefile.sources | 1 +
> > src/glsl/glsl_parser_extras.cpp | 1 +
> > src/glsl/ir_optimization.h | 1 +
> > src/glsl/opt_minmax.cpp | 457 ++++++++++++++++++++++++++++++++++++++++
> > 4 files changed, 460 insertions(+)
> > create mode 100644 src/glsl/opt_minmax.cpp
> >
> > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> > index cb8d5a6..1c08697 100644
> > --- a/src/glsl/Makefile.sources
> > +++ b/src/glsl/Makefile.sources
> > @@ -95,6 +95,7 @@ LIBGLSL_FILES = \
> > $(GLSL_SRCDIR)/opt_flip_matrices.cpp \
> > $(GLSL_SRCDIR)/opt_function_inlining.cpp \
> > $(GLSL_SRCDIR)/opt_if_simplification.cpp \
> > + $(GLSL_SRCDIR)/opt_minmax.cpp \
> > $(GLSL_SRCDIR)/opt_noop_swizzle.cpp \
> > $(GLSL_SRCDIR)/opt_rebalance_tree.cpp \
> > $(GLSL_SRCDIR)/opt_redundant_jumps.cpp \
> > diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
> > index 490c3c8..ae19ce4 100644
> > --- a/src/glsl/glsl_parser_extras.cpp
> > +++ b/src/glsl/glsl_parser_extras.cpp
> > @@ -1586,6 +1586,7 @@ do_common_optimization(exec_list *ir, bool linked,
> > else
> > progress = do_constant_variable_unlinked(ir) || progress;
> > progress = do_constant_folding(ir) || progress;
> > + progress = do_minmax_prune(ir) || progress;
> > progress = do_cse(ir) || progress;
> > progress = do_rebalance_tree(ir) || progress;
> > progress = do_algebraic(ir, native_integers, options) || progress;
> > diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
> > index 369dcd1..8fbd992 100644
> > --- a/src/glsl/ir_optimization.h
> > +++ b/src/glsl/ir_optimization.h
> > @@ -99,6 +99,7 @@ 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);
> > +bool do_minmax_prune(exec_list *instructions);
> > bool do_noop_swizzle(exec_list *instructions);
> > bool do_structure_splitting(exec_list *instructions);
> > bool do_swizzle_swizzle(exec_list *instructions);
> > diff --git a/src/glsl/opt_minmax.cpp b/src/glsl/opt_minmax.cpp
> > new file mode 100644
> > index 0000000..08bb739
> > --- /dev/null
> > +++ b/src/glsl/opt_minmax.cpp
> > @@ -0,0 +1,457 @@
> > +/*
> > + * Copyright © 2014 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_minmax.cpp
> > + *
> > + * Drop operands from an expression tree of only min/max operations if they
> > + * can be proven to not contribute to the final result.
> > + *
> > + * The algorithm is similar to alpha-beta pruning on a minmax search.
> > + */
> > +
> > +#include "ir.h"
> > +#include "ir_visitor.h"
> > +#include "ir_rvalue_visitor.h"
> > +#include "ir_optimization.h"
> > +#include "ir_builder.h"
> > +#include "program/prog_instruction.h"
> > +#include "glsl_types.h"
> > +#include "main/macros.h"
> > +
> > +using namespace ir_builder;
> > +
> > +namespace {
> > +
> > +enum compare_components_result {
> > + LESS,
> > + LESS_OR_EQUAL,
> > + EQUAL,
> > + GREATER_OR_EQUAL,
> > + GREATER,
> > + MIXED
> > +};
> > +
> > +class minmax_range {
> > +public:
> > + minmax_range(ir_constant *low = NULL, ir_constant *high = NULL)
> > + {
> > + this->low = low;
> > + this->high = high;
> > + }
> > +
> > + /* low is the lower limit of the range, high is the higher limit. NULL on
> > + * low means negative infinity (unlimited) and on high positive infinity
> > + * (unlimited). Because of the two interpretations of the value NULL,
> > + * arbitrary comparison between ir_constants is impossible.
> > + */
> > + ir_constant *low;
> > + ir_constant *high;
> > +};
> > +
> > +class ir_minmax_visitor : public ir_rvalue_enter_visitor {
> > +public:
> > + ir_minmax_visitor()
> > + : progress(false)
> > + {
> > + }
> > +
> > +
> > + minmax_range combine_range(minmax_range r0, minmax_range r1, bool ismin, bool *valid);
> > +
> > + minmax_range range_intersection(minmax_range r0, minmax_range r1, bool *valid);
> > +
> > + minmax_range get_range(ir_rvalue *rval, bool *valid);
> > +
> > + ir_rvalue *prune_expression(ir_expression *expr, minmax_range baserange);
> > +
> > + void handle_rvalue(ir_rvalue **rvalue);
> > +
> > + bool progress;
> > +};
> > +
> > +/*
> > + * Returns LESS if all vector components of `a' are strictly lower than of `b',
> > + * GREATER if all vector components of `a' are strictly greater than of `b',
> > + * MIXED if some vector components of `a' are strictly lower than of `b' while
> > + * others are strictly greater, or EQUAL otherwise.
> > + */
> > +static enum compare_components_result
> > +compare_components(ir_constant *a, ir_constant *b)
> > +{
> > + assert(a != NULL);
> > + assert(b != NULL);
> > +
> > + assert(a->type->base_type == b->type->base_type);
> > +
> > + unsigned a_inc = a->type->is_scalar() ? 0 : 1;
> > + unsigned b_inc = b->type->is_scalar() ? 0 : 1;
> > + unsigned components = MAX2(a->type->components(), b->type->components());
> > +
> > + bool foundless = false;
> > + bool foundgreater = false;
> > + bool foundequal = false;
> > +
> > + for (unsigned i = 0, c0 = 0, c1 = 0;
> > + i < components;
> > + c0 += a_inc, c1 += b_inc, ++i) {
> > + switch (a->type->base_type) {
> > + case GLSL_TYPE_UINT:
> > + if (a->value.u[c0] < b->value.u[c1])
> > + foundless = true;
> > + else if (a->value.u[c0] > b->value.u[c1])
> > + foundgreater = true;
> > + else
> > + foundequal = true;
> > + break;
> > + case GLSL_TYPE_INT:
> > + if (a->value.i[c0] < b->value.i[c1])
> > + foundless = true;
> > + else if (a->value.i[c0] > b->value.i[c1])
> > + foundgreater = true;
> > + else
> > + foundequal = true;
> > + break;
> > + case GLSL_TYPE_FLOAT:
> > + if (a->value.f[c0] < b->value.f[c1])
> > + foundless = true;
> > + else if (a->value.f[c0] > b->value.f[c1])
> > + foundgreater = true;
> > + else
> > + foundequal = true;
> > + break;
> > + default:
> > + unreachable("not reached");
> > + }
> > + }
> > +
> > + if (foundless && foundgreater) {
> > + /* Some components are strictly lower, others are strictly greater */
> > + return MIXED;
> > + }
> > +
> > + if (foundequal) {
> > + /* It is not mixed, but it is not strictly lower or greater */
> > + if (foundless)
> > + return LESS_OR_EQUAL;
> > + if (foundgreater)
> > + return GREATER_OR_EQUAL;
> > + return EQUAL;
> > + }
> > +
> > + /* All components are strictly lower or strictly greater */
> > + return foundless ? LESS : GREATER;
> > +}
> > +
> > +static ir_constant *
> > +smaller_constant(ir_constant *a, ir_constant *b)
> > +{
> > + assert(a != NULL);
> > + assert(b != NULL);
> > +
> > + enum compare_components_result ret = compare_components(a, b);
> > + if (ret == MIXED)
> > + return NULL;
> > + else if (ret < EQUAL)
> > + return a;
> > + else
> > + return b;
> > +}
> > +
> > +static ir_constant *
> > +larger_constant(ir_constant *a, ir_constant *b)
> > +{
> > + assert(a != NULL);
> > + assert(b != NULL);
> > +
> > + enum compare_components_result ret = compare_components(a, b);
> > + if (ret == MIXED)
> > + return NULL;
> > + else if (ret < EQUAL)
> > + return b;
> > + else
> > + return a;
> > +}
>
> Instead of bailing out and returning NULL here if a and b are mixed in
> these 2 functions, maybe we should actually go and combine each
> component of a and b and return a new constant? It might be more code,
> but it should be slightly more powerful, and more importantly it seems
> like we could then get rid of the whole valid/operands_valid mess
> which IMHO is worse than the (pretty straightforward) additions you'd
> need. If you decide not to change this, you should probably at least
> change the comment below which implies that we do do component-wise
> comparisons.
Yes, this seems like a good idea.
> > +
> > +/* Combines two ranges by doing an element-wise min() / max() depending on the
> > + * operation.
> > + */
> > +minmax_range
> > +ir_minmax_visitor::combine_range(minmax_range r0, minmax_range r1,
> > + bool ismin, bool *valid)
> > +{
> > + minmax_range ret;
> > +
> > + *valid = true;
> > + if (!r0.low) {
> > + ret.low = ismin ? r0.low : r1.low;
> > + } else if (!r1.low) {
> > + ret.low = ismin ? r1.low : r0.low;
> > + } else {
> > + ret.low = ismin ? smaller_constant(r0.low, r1.low) :
> > + larger_constant(r0.low, r1.low);
> > + if (!ret.low)
> > + *valid = false;
> > + }
> > +
> > + if (!r0.high) {
> > + ret.high = ismin ? r1.high : r0.high;
> > + } else if (!r1.high) {
> > + ret.high = ismin ? r0.high : r1.high;
> > + } else {
> > + ret.high = ismin ? smaller_constant(r0.high, r1.high) :
> > + larger_constant(r0.high, r1.high);
> > + if (!ret.high)
> > + *valid = false;
> > + }
> > +
> > + return ret;
> > +}
> > +
> > +/* Returns a range so that lower limit is the larger of the two lower limits,
> > + * and higher limit is the smaller of the two higher limits.
> > + */
> > +minmax_range
> > +ir_minmax_visitor::range_intersection(minmax_range r0, minmax_range r1,
> > + bool *valid)
> > +{
> > + minmax_range ret;
> > +
> > + *valid = true;
> > + if (!r0.low)
> > + ret.low = r1.low;
> > + else if (!r1.low)
> > + ret.low = r0.low;
> > + else {
> > + ret.low = larger_constant(r0.low, r1.low);
> > + if (!ret.low)
> > + *valid = false;
> > + }
> > +
> > + if (!r0.high)
> > + ret.high = r1.high;
> > + else if (!r1.high)
> > + ret.high = r0.high;
> > + else {
> > + ret.high = smaller_constant(r0.high, r1.high);
> > + if (!ret.high)
> > + *valid = false;
> > + }
> > +
> > + return ret;
> > +}
> > +
> > +minmax_range
> > +ir_minmax_visitor::get_range(ir_rvalue *rval, bool *valid)
> > +{
> > + *valid = true;
> > +
> > + ir_expression *expr = rval->as_expression();
> > + if (expr && (expr->operation == ir_binop_min ||
> > + expr->operation == ir_binop_max)) {
> > + bool valid_r0, valid_r1;
> > + minmax_range r0 = get_range(expr->operands[0], &valid_r0);
> > + minmax_range r1 = get_range(expr->operands[1], &valid_r1);
> > + if (valid_r0 && valid_r1) {
> > + return combine_range(r0, r1, expr->operation == ir_binop_min, valid);
> > + } else {
> > + *valid = false;
> > + return minmax_range();
> > + }
> > + }
> > +
> > + ir_constant *c = rval->as_constant();
> > + if (c) {
> > + return minmax_range(c, c);
> > + }
> > +
> > + return minmax_range();
> > +}
>
> Is there something I'm missing, or can these methods become static
> functions as well? It doesn't seem like they depend on any
> ir_minmax_visitor state.
You are right, I'll make these static too.
> > +
> > +ir_rvalue *
> > +ir_minmax_visitor::prune_expression(ir_expression *expr, minmax_range baserange)
>
> Can we have a comment explaining what baserange is here? IIRC it's
> something like "the range that the parents of this min/max in the
> min/max tree will clamp its value to." I had a little trouble
> remembering what it was, and I'm afraid someone new to the code will
> have even more trouble.
Sure, I will add that.
Thanks for the feedback, I'll send a new patch with these changes.
Iago
> > +{
> > + assert(expr->operation == ir_binop_min ||
> > + expr->operation == ir_binop_max);
> > +
> > + bool ismin = expr->operation == ir_binop_min;
> > + minmax_range limits[2];
> > +
> > + /* Recurse to get the ranges for each of the subtrees of this
> > + * expression. We need to do this as a separate step because we need to
> > + * know the ranges of each of the subtrees before we prune either one.
> > + * Consider something like this:
> > + *
> > + * max
> > + * / \
> > + * max max
> > + * / \ / \
> > + * 3 a b 2
> > + *
> > + * We would like to prune away the max on the bottom-right, but to do so
> > + * we need to know the range of the expression on the left beforehand,
> > + * and there's no guarantee that we will visit either subtree in a
> > + * particular order.
> > + */
> > + bool operands_valid[2];
> > + for (unsigned i = 0; i < 2; ++i) {
> > + limits[i] = get_range(expr->operands[i], &operands_valid[i]);
> > + }
> > +
> > + if (operands_valid[0] && operands_valid[1]) {
> > + for (unsigned i = 0; i < 2; ++i) {
> > + bool is_redundant = false;
> > +
> > + if (ismin) {
> > + /* If this operand will always be greater than the other one, it's
> > + * redundant.
> > + */
> > + if (limits[i].low && limits[1 - i].high) {
> > + enum compare_components_result cr =
> > + compare_components(limits[i].low, limits[1 - i].high);
> > + if (cr >= EQUAL && cr != MIXED)
> > + is_redundant = true;
> > + }
> > + /* If this operand is always greater than baserange, then even if
> > + * it's smaller than the other one it'll get clamped, so it's
> > + * redundant.
> > + */
> > + if (!is_redundant && limits[i].low && baserange.high) {
> > + enum compare_components_result cr =
> > + compare_components(limits[i].low, baserange.high);
> > + if (cr >= EQUAL && cr != MIXED)
> > + is_redundant = true;
> > + }
> > + } else {
> > + /* If this operand will always be lower than the other one, it's
> > + * redundant.
> > + */
> > + if (limits[i].high && limits[1 - i].low &&
> > + compare_components(limits[i].high, limits[1 - i].low) <= EQUAL) {
> > + is_redundant = true;
> > + }
> > + /* If this operand is always lower than baserange, then even if
> > + * it's greater than the other one it'll get clamped, so it's
> > + * redundant.
> > + */
> > + if (!is_redundant && limits[i].high && baserange.low &&
> > + compare_components(limits[i].high, baserange.low) <= EQUAL) {
> > + is_redundant = true;
> > + }
> > + }
> > +
> > + if (is_redundant) {
> > + progress = true;
> > +
> > + /* Recurse if necessary. */
> > + ir_expression *op_expr = expr->operands[1 - i]->as_expression();
> > + if (op_expr && (op_expr->operation == ir_binop_min ||
> > + op_expr->operation == ir_binop_max)) {
> > + return prune_expression(op_expr, baserange);
> > + }
> > +
> > + return expr->operands[1 - i];
> > + }
> > + }
> > + }
> > +
> > + /* Now recurse to operands giving them the proper baserange. The baserange
> > + * to pass is the intersection of our baserange and the other operand's
> > + * limit with one of the ranges unlimited. If we can't compute a valid
> > + * intersection, we use the current baserange.
> > + */
> > + for (unsigned i = 0; i < 2; ++i) {
> > + ir_expression *op_expr = expr->operands[i]->as_expression();
> > + if (op_expr && (op_expr->operation == ir_binop_min ||
> > + op_expr->operation == ir_binop_max)) {
> > + /* We can only compute a new baserange for this operand if we managed
> > + * to compute a valid range for the other operand.
> > + */
> > + if (operands_valid[1 - i]) {
> > + if (ismin)
> > + limits[1 - i].low = NULL;
> > + else
> > + limits[1 - i].high = NULL;
> > + bool valid;
> > + minmax_range base = range_intersection(limits[1 - i], baserange,
> > + &valid);
> > + if (valid)
> > + expr->operands[i] = prune_expression(op_expr, base);
> > + else
> > + expr->operands[i] = prune_expression(op_expr, baserange);
> > + } else {
> > + /* If we cannot compute a new baserange for this operand,
> > + * simply pass the parent's baserange.
> > + */
> > + expr->operands[i] = prune_expression(op_expr, baserange);
> > + }
> > + }
> > + }
> > +
> > + return expr;
> > +}
> > +
> > +static ir_rvalue *
> > +swizzle_if_required(ir_expression *expr, ir_rvalue *rval)
> > +{
> > + if (expr->type->is_vector() && rval->type->is_scalar()) {
> > + return swizzle(rval, SWIZZLE_XXXX, expr->type->vector_elements);
> > + } else {
> > + return rval;
> > + }
> > +}
> > +
> > +void
> > +ir_minmax_visitor::handle_rvalue(ir_rvalue **rvalue)
> > +{
> > + if (!*rvalue)
> > + return;
> > +
> > + ir_expression *expr = (*rvalue)->as_expression();
> > + if (!expr || (expr->operation != ir_binop_min &&
> > + expr->operation != ir_binop_max))
> > + return;
> > +
> > + ir_rvalue *new_rvalue = prune_expression(expr, minmax_range());
> > + if (new_rvalue == *rvalue)
> > + return;
> > +
> > + /* If the expression type is a vector and the optimization leaves a scalar
> > + * as the result, we need to turn it into a vector.
> > + */
> > + *rvalue = swizzle_if_required(expr, new_rvalue);
> > +
> > + progress = true;
> > +}
> > +
> > +}
> > +
> > +bool
> > +do_minmax_prune(exec_list *instructions)
> > +{
> > + ir_minmax_visitor v;
> > +
> > + visit_list_elements(&v, instructions);
> > +
> > + return v.progress;
> > +}
> > --
> > 1.9.1
> >
>
More information about the mesa-dev
mailing list