[Mesa-dev] [PATCH] squash! glsl: Optimize min/max expression trees
Connor Abbott
cwabbott0 at gmail.com
Thu Aug 14 01:00:48 PDT 2014
On Wed, Aug 13, 2014 at 9:04 PM, Matt Turner <mattst88 at gmail.com> wrote:
> ---
> I'd squash this in at minimum. The changes are
>
> - Whitespace
> - Removal of unnecessary destructor
> - Renaming "one" and "two" to "a" and "b" (one->value.u[c0] < two->value.u[c0]...)
> - continue -> break
> - assert(!...) -> unreachable
> - Not doing assignments in if conditionals
> - Marking swizzle_if_required as static
>
> I also think less_all_components should just return an enum like
> { MIXED, EQUAL, LESS, GREATER }, rather than setting a variable in
> the class. It, as well as smaller/larger_constant, can then be
> static functions outside of the visitor.
I agree. Also, I realized that in the only place where we care about
the valid variable,
Another thing I'd like to see is to change minmax_range to call things
"low" and "high" instead of "range[0]" and "range[1]." This helps
readability, and the tricks with indirect addressing that having an
array lets you do are things we really shouldn't be doing anyways
because it's hard to follow.
As I mentioned before, swizzle_if_required() should probably use the
ir_builder swizzle helpers.
I'm still not convinced that the algorithm is the best way to go about
it. Right now, AFAICT, we do something like:
- Pass in a "base range," which is what the min's and max's above us
in the tree will clamp the value we return to
- Get the ranges for each subexpression (this is a recursive call)
- Check and see if each operand is unnecessary (i.e. its range is
strictly greater than the base range or strictly greater than the
other argument for mins, the other way around for max's)
As another thing, the logic for this part could be made a *lot*
clearer by rearranging the code and commenting. I'd do something like:
bool is_redundant = false /* whether this operand will never affect
the final value of the min-max tree */
if (is_min) {
/* if this operand will always be greater than the other one, it's
redundant */
if (limit[i].low > limit[1 - i].high)
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 (limit[i].low > baserange.high)
is_redundant = true;
} else {
... the exact same logic mirrored ...
}
- Recurse into the subexpressions, computing the new baserange.
What I think we should do instead is change prune_expression() to also
return the range for the expression (it's now returning two things, so
one would have to be passed via a class variable), so it would look
like:
- Pass in the base range
- If this is a constant, return ourself and the range with low == high
- Recurse into both subexpressions, setting both the range (limits[i])
and the new subexpression
- If one of the subexpressions is redundant, return the other
subexpression and its range
- Otherwise, return ourself and the combination of the ranges
This will allow us to do the recursion only once, instead of once in
get_range() and once in prune_expression(), which will make things
simpler and faster.
>
> I think the algorithm itself looks correct.
>
> src/glsl/opt_minmax.cpp | 145 +++++++++++++++++++++---------------------------
> 1 file changed, 63 insertions(+), 82 deletions(-)
>
> diff --git a/src/glsl/opt_minmax.cpp b/src/glsl/opt_minmax.cpp
> index 5656059..b987386 100644
> --- a/src/glsl/opt_minmax.cpp
> +++ b/src/glsl/opt_minmax.cpp
> @@ -37,12 +37,10 @@
> #include "glsl_types.h"
> #include "main/macros.h"
>
> -namespace
> -{
> -class minmax_range
> -{
> -public:
> +namespace {
>
> +class minmax_range {
> +public:
> minmax_range(ir_constant *low = NULL, ir_constant *high = NULL)
> {
> range[0] = low;
> @@ -60,60 +58,45 @@ public:
> class ir_minmax_visitor : public ir_rvalue_enter_visitor {
> public:
> ir_minmax_visitor()
> - : progress(false)
> - , valid(true)
> - {
> - }
> -
> - virtual ~ir_minmax_visitor()
> + : progress(false), valid(true)
> {
> }
>
> - 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);
> + bool less_all_components(ir_constant *a, ir_constant *b);
> + ir_constant *smaller_constant(ir_constant *a, ir_constant *b);
> + ir_constant *larger_constant(ir_constant *a, ir_constant *b);
>
> - minmax_range
> - combine_range(minmax_range r0, minmax_range r1, bool ismin);
> + minmax_range combine_range(minmax_range r0, minmax_range r1, bool ismin);
>
> - minmax_range
> - range_intersection(minmax_range r0, minmax_range r1);
> + minmax_range range_intersection(minmax_range r0, minmax_range r1);
>
> - minmax_range
> - get_range(ir_rvalue *rval);
> + minmax_range get_range(ir_rvalue *rval);
>
> - ir_rvalue *
> - prune_expression(ir_expression *expr, minmax_range baserange);
> + ir_rvalue *prune_expression(ir_expression *expr, minmax_range baserange);
>
> - void
> - handle_rvalue(ir_rvalue **rvalue);
> + void handle_rvalue(ir_rvalue **rvalue);
>
> bool progress;
> bool valid;
> };
>
> /*
> - * Returns true if all vector components of `one' are less than of `two'.
> + * Returns true if all vector components of `a' are less than of `b'.
> *
> * 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)
> +ir_minmax_visitor::less_all_components(ir_constant *a, ir_constant *b)
> {
> - assert(one != NULL);
> - assert(two != NULL);
> + assert(a != NULL);
> + assert(b != NULL);
>
> - assert(one->type->base_type == two->type->base_type);
> + assert(a->type->base_type == b->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());
> + 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());
>
> /* No early escape. We need to go through all components and mark the
> * visitor as invalid if comparison yields less for some components and
> @@ -127,34 +110,34 @@ ir_minmax_visitor::less_all_components(ir_constant *one, ir_constant *two)
>
> for (unsigned i = 0, c0 = 0, c1 = 0;
> i < components;
> - c0 += oneinc, c1 += twoinc, ++i) {
> - switch (one->type->base_type) {
> + c0 += a_inc, c1 += b_inc, ++i) {
> + switch (a->type->base_type) {
> case GLSL_TYPE_UINT:
> - if (one->value.u[c0] < two->value.u[c1])
> + if (a->value.u[c0] < b->value.u[c1])
> foundless = true;
> - else if (one->value.u[c0] > two->value.u[c1])
> + else if (a->value.u[c0] > b->value.u[c1])
> foundgreater = true;
> else
> foundequal = true;
> - continue;
> + break;
> case GLSL_TYPE_INT:
> - if (one->value.i[c0] < two->value.i[c1])
> + if (a->value.i[c0] < b->value.i[c1])
> foundless = true;
> - else if (one->value.i[c0] > two->value.i[c1])
> + else if (a->value.i[c0] > b->value.i[c1])
> foundgreater = true;
> else
> foundequal = true;
> - continue;
> + break;
> case GLSL_TYPE_FLOAT:
> - if (one->value.f[c0] < two->value.f[c1])
> + if (a->value.f[c0] < b->value.f[c1])
> foundless = true;
> - else if (one->value.f[c0] > two->value.f[c1])
> + else if (a->value.f[c0] > b->value.f[c1])
> foundgreater = true;
> else
> foundequal = true;
> - continue;
> + break;
> default:
> - assert(!"not reached");
> + unreachable("not reached");
> }
> }
>
> @@ -170,27 +153,27 @@ ir_minmax_visitor::less_all_components(ir_constant *one, ir_constant *two)
> }
>
> ir_constant *
> -ir_minmax_visitor::smaller_constant(ir_constant *one, ir_constant *two)
> +ir_minmax_visitor::smaller_constant(ir_constant *a, ir_constant *b)
> {
> - assert(one != NULL);
> - assert(two != NULL);
> + assert(a != NULL);
> + assert(b != NULL);
>
> - if (less_all_components(one, two))
> - return one;
> + if (less_all_components(a, b))
> + return a;
> else
> - return two;
> + return b;
> }
>
> ir_constant *
> -ir_minmax_visitor::larger_constant(ir_constant *one, ir_constant *two)
> +ir_minmax_visitor::larger_constant(ir_constant *a, ir_constant *b)
> {
> - assert(one != NULL);
> - assert(two != NULL);
> + assert(a != NULL);
> + assert(b != NULL);
>
> - if (less_all_components(one, two))
> - return two;
> + if (less_all_components(a, b))
> + return b;
> else
> - return one;
> + return a;
> }
>
> /* Combines two ranges by doing an element-wise min() / max() depending on the
> @@ -250,17 +233,17 @@ ir_minmax_visitor::range_intersection(minmax_range r0, minmax_range r1)
> 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]);
> + ir_expression *expr = rval->as_expression();
> + if (expr && (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);
> - }
> + return combine_range(r0, r1, expr->operation == ir_binop_min);
> }
>
> - if (ir_constant *c = rval->as_constant()) {
> + ir_constant *c = rval->as_constant();
> + if (c) {
> return minmax_range(c, c);
> }
>
> @@ -314,11 +297,10 @@ ir_minmax_visitor::prune_expression(ir_expression *expr, minmax_range baserange)
> 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);
> - }
> + 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];
> @@ -333,20 +315,19 @@ ir_minmax_visitor::prune_expression(ir_expression *expr, minmax_range baserange)
> 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);
> - }
> + ir_expression *op_expr = expr->operands[i]->as_expression();
> + if (op_expr && (op_expr->operation == ir_binop_min ||
> + op_expr->operation == ir_binop_max)) {
> + limits[1 - i].range[clear] = NULL;
> + minmax_range base = range_intersection(limits[1 - i], baserange);
> + expr->operands[i] = prune_expression(op_expr, base);
> }
> }
>
> return expr;
> }
>
> -ir_rvalue *
> +static ir_rvalue *
> swizzle_if_required(ir_expression *expr,
> ir_rvalue *rval)
> {
> --
> 1.8.5.5
>
> _______________________________________________
> 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