[Mesa-dev] [PATCH 1/9] glsl: Optimize min/max expression trees
Petri Latvala
petri.latvala at intel.com
Mon Aug 18 06:10:26 PDT 2014
On 08/14/2014 04:33 AM, Ian Romanick wrote:
> On 07/29/2014 02:36 AM, Petri Latvala wrote:
>> 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.
> And I assume no piglit regressions?
Indeed no regressions, or new successes. I wrote that in the cover
letter, I should have written it also in this patch's commit message...
> Also... have you tried this in combination with Abdiel's related work on
> saturates?
Tested the combination now, after some fighting with shader-db. The
results are the same, except :
>> 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.
This shader compiled into the same code with or without my patches.
Talked with Abdiel about the combination, recapping here: Our changes
are orthogonal and not conflicting, so we can both proceed at our own paces.
>>
>> Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=76861
>> Signed-off-by: Petri Latvala <petri.latvala at intel.com>
>> ---
>> src/glsl/Makefile.sources | 1 +
>> src/glsl/glsl_parser_extras.cpp | 1 +
>> src/glsl/ir_optimization.h | 1 +
>> src/glsl/opt_minmax.cpp | 395 ++++++++++++++++++++++++++++++++++++++++
>> 4 files changed, 398 insertions(+)
>> create mode 100644 src/glsl/opt_minmax.cpp
>>
>> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
>> index b54eae7..1ee80a3 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 890123a..9f57ef3 100644
>> --- a/src/glsl/glsl_parser_extras.cpp
>> +++ b/src/glsl/glsl_parser_extras.cpp
>> @@ -1561,6 +1561,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 b83c225..9d22585 100644
>> --- a/src/glsl/ir_optimization.h
>> +++ b/src/glsl/ir_optimization.h
>> @@ -98,6 +98,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..5656059
>> --- /dev/null
>> +++ b/src/glsl/opt_minmax.cpp
>> @@ -0,0 +1,395 @@
>> +/*
>> + * 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 "glsl_types.h"
>> +#include "main/macros.h"
>> +
>> +namespace
>> +{
>> +class minmax_range
>> +{
>> +public:
>> +
>> + minmax_range(ir_constant *low = NULL, ir_constant *high = NULL)
>> + {
>> + range[0] = low;
>> + range[1] = high;
>> + }
>> +
>> + /* [0] is the lower limit of the range, [1] is the higher limit. NULL on
>> + * [0] means negative infinity (unlimited) and on [1] positive infinity
>> + * (unlimited). Because of the two interpretations of the value NULL,
>> + * arbitrary comparison between ir_constants is impossible.
>> + */
>> + ir_constant *range[2];
>> +};
>> +
>> +class ir_minmax_visitor : public ir_rvalue_enter_visitor {
>> +public:
>> + ir_minmax_visitor()
>> + : progress(false)
>> + , valid(true)
>> + {
>> + }
>> +
>> + virtual ~ir_minmax_visitor()
>> + {
>> + }
>> +
>> + bool
>> + less_all_components(ir_constant *one, ir_constant *two);
>> +
>> + ir_constant *
>> + smaller_constant(ir_constant *one, ir_constant *two);
>> +
>> + ir_constant *
>> + larger_constant(ir_constant *one, ir_constant *two);
>> +
>> + minmax_range
>> + combine_range(minmax_range r0, minmax_range r1, bool ismin);
>> +
>> + minmax_range
>> + range_intersection(minmax_range r0, minmax_range r1);
>> +
>> + minmax_range
>> + get_range(ir_rvalue *rval);
>> +
>> + ir_rvalue *
>> + prune_expression(ir_expression *expr, minmax_range baserange);
>> +
>> + void
>> + handle_rvalue(ir_rvalue **rvalue);
>> +
>> + bool progress;
>> + bool valid;
>> +};
>> +
>> +/*
>> + * Returns true if all vector components of `one' are less than of `two'.
>> + *
>> + * If there are vector components that are less while others are greater, the
>> + * visitor is marked invalid and no further changes will be made to the IR.
>> + */
>> +bool
>> +ir_minmax_visitor::less_all_components(ir_constant *one, ir_constant *two)
>> +{
>> + assert(one != NULL);
>> + assert(two != NULL);
>> +
>> + assert(one->type->base_type == two->type->base_type);
>> +
>> + unsigned oneinc = one->type->is_scalar() ? 0 : 1;
>> + unsigned twoinc = two->type->is_scalar() ? 0 : 1;
>> + unsigned components = MAX2(one->type->components(), two->type->components());
>> +
>> + /* No early escape. We need to go through all components and mark the
>> + * visitor as invalid if comparison yields less for some components and
>> + * greater for others. If some components compare as equal, it's not
>> + * invalid.
>> + */
>> +
>> + bool foundless = false;
>> + bool foundgreater = false;
>> + bool foundequal = false;
>> +
>> + for (unsigned i = 0, c0 = 0, c1 = 0;
>> + i < components;
>> + c0 += oneinc, c1 += twoinc, ++i) {
>> + switch (one->type->base_type) {
>> + case GLSL_TYPE_UINT:
>> + if (one->value.u[c0] < two->value.u[c1])
>> + foundless = true;
>> + else if (one->value.u[c0] > two->value.u[c1])
>> + foundgreater = true;
>> + else
>> + foundequal = true;
>> + continue;
> Since there's nothing else in the loop, I'd rather see these be break
> statements. Seeing continue here is a weird and a little unnerving.
>
>
Fair enough. Changing.
>> + case GLSL_TYPE_INT:
>> + if (one->value.i[c0] < two->value.i[c1])
>> + foundless = true;
>> + else if (one->value.i[c0] > two->value.i[c1])
>> + foundgreater = true;
>> + else
>> + foundequal = true;
>> + continue;
>> + case GLSL_TYPE_FLOAT:
>> + if (one->value.f[c0] < two->value.f[c1])
>> + foundless = true;
>> + else if (one->value.f[c0] > two->value.f[c1])
>> + foundgreater = true;
>> + else
>> + foundequal = true;
>> + continue;
>> + default:
>> + assert(!"not reached");
> Use unreachable("Invalid type") here.
Changing.
>
>> + }
>> + }
>> +
>> + if (foundless && foundgreater) {
>> + valid = false;
>> + return false;
>> + }
>> +
>> + if (foundequal)
>> + return false;
>> +
>> + return foundless;
>> +}
>> +
>> +ir_constant *
>> +ir_minmax_visitor::smaller_constant(ir_constant *one, ir_constant *two)
>> +{
>> + assert(one != NULL);
>> + assert(two != NULL);
>> +
>> + if (less_all_components(one, two))
>> + return one;
>> + else
>> + return two;
>> +}
>> +
>> +ir_constant *
>> +ir_minmax_visitor::larger_constant(ir_constant *one, ir_constant *two)
>> +{
>> + assert(one != NULL);
>> + assert(two != NULL);
>> +
>> + if (less_all_components(one, two))
>> + return two;
>> + else
>> + return one;
>> +}
>> +
>> +/* 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)
>> +{
>> + minmax_range ret;
>> +
>> + if (!r0.range[0]) {
>> + ret.range[0] = ismin ? r0.range[0] : r1.range[0];
>> + } else if (!r1.range[0]) {
>> + ret.range[0] = ismin ? r1.range[0] : r0.range[0];
>> + } else {
>> + ret.range[0] = ismin ? smaller_constant(r0.range[0], r1.range[0]) :
>> + larger_constant(r0.range[0], r1.range[0]);
>> + }
>> +
>> + if (!r0.range[1]) {
>> + ret.range[1] = ismin ? r1.range[1] : r0.range[1];
>> + } else if (!r1.range[1]) {
>> + ret.range[1] = ismin ? r0.range[1] : r1.range[1];
>> + } else {
>> + ret.range[1] = ismin ? smaller_constant(r0.range[1], r1.range[1]) :
>> + larger_constant(r0.range[1], r1.range[1]);
>> + }
>> +
>> + 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)
>> +{
>> + minmax_range ret;
>> +
>> + if (!r0.range[0])
>> + ret.range[0] = r1.range[0];
>> + else if (!r1.range[0])
>> + ret.range[0] = r0.range[0];
>> + else
>> + ret.range[0] = larger_constant(r0.range[0], r1.range[0]);
>> +
>> + if (!r0.range[1])
>> + ret.range[1] = r1.range[1];
>> + else if (!r1.range[1])
>> + ret.range[1] = r0.range[1];
>> + else
>> + ret.range[1] = smaller_constant(r0.range[1], r1.range[1]);
>> +
>> + return ret;
>> +}
>> +
>> +minmax_range
>> +ir_minmax_visitor::get_range(ir_rvalue *rval)
>> +{
>> + if (ir_expression *expr = rval->as_expression()) {
>> + if (expr->operation == ir_binop_min ||
>> + expr->operation == ir_binop_max) {
>> + minmax_range r0 = get_range(expr->operands[0]);
>> + minmax_range r1 = get_range(expr->operands[1]);
>> +
>> + return combine_range(r0, r1, expr->operation == ir_binop_min);
>> + }
>> + }
>> +
>> + if (ir_constant *c = rval->as_constant()) {
>> + return minmax_range(c, c);
>> + }
>> +
>> + return minmax_range();
>> +}
>> +
>> +ir_rvalue *
>> +ir_minmax_visitor::prune_expression(ir_expression *expr, minmax_range baserange)
>> +{
>> + assert(expr->operation == ir_binop_min ||
>> + expr->operation == ir_binop_max);
>> +
>> + if (!valid)
>> + return expr;
>> +
>> + bool ismin = expr->operation == ir_binop_min;
>> + minmax_range limits[2];
>> +
>> + for (unsigned i = 0; i < 2; ++i) {
>> + limits[i] = get_range(expr->operands[i]);
>> + }
>> +
>> + for (unsigned i = 0; i < 2; ++i) {
>> + /* Operands are dropped if their range doesn't reach the given baserange
>> + * or the other operand's limit from the appropriate direction.
>> + */
>> +
>> + minmax_range basereach;
>> + minmax_range otherreach;
>> +
>> + if (ismin) {
>> + basereach.range[0] = limits[i].range[0];
>> + otherreach.range[0] = limits[i].range[0];
>> + basereach.range[1] = baserange.range[1];
>> + otherreach.range[1] = limits[1 - i].range[1];
>> + } else {
>> + basereach.range[0] = baserange.range[0];
>> + otherreach.range[0] = limits[1 - i].range[0];
>> + basereach.range[1] = limits[i].range[1];
>> + otherreach.range[1] = limits[i].range[1];
>> + }
>> +
>> + if ((basereach.range[0] && basereach.range[1] &&
>> + !less_all_components(basereach.range[0], basereach.range[1])) ||
>> + (otherreach.range[0] && otherreach.range[1] &&
>> + !less_all_components(otherreach.range[0], otherreach.range[1]))) {
>> + /* Bail out if those comparisons made the visitor invalid. */
>> + if (!valid)
>> + return expr;
>> +
>> + progress = true;
>> +
>> + /* Recurse if necessary. */
>> + if (ir_expression* opexpr = expr->operands[1 - i]->as_expression()) {
>> + if (opexpr->operation == ir_binop_min ||
>> + opexpr->operation == ir_binop_max) {
>> + return prune_expression(opexpr, 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.
>> + */
>> +
>> + unsigned clear = (ismin ? 0 : 1);
>> +
>> + for (unsigned i = 0; i < 2; ++i) {
>> + if (ir_expression *opexpr = expr->operands[i]->as_expression()) {
>> + if (opexpr->operation == ir_binop_min ||
>> + opexpr->operation == ir_binop_max) {
>> + limits[1 - i].range[clear] = NULL;
>> + minmax_range base = range_intersection(limits[1 - i], baserange);
>> + expr->operands[i] = prune_expression(opexpr, base);
>> + }
>> + }
>> + }
>> +
>> + return expr;
>> +}
>> +
>> +ir_rvalue *
>> +swizzle_if_required(ir_expression *expr,
>> + ir_rvalue *rval)
>> +{
>> + if (expr->type->is_vector() && rval->type->is_scalar()) {
>> + return new(expr) ir_swizzle(rval, 0, 0, 0, 0,
>> + 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 (!valid || 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;
>> +}
>>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list