src/glsl/opt_minmax.cpp

   1 /*
   2  * Copyright © 2014 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 /**
  25  * \file opt_minmax.cpp
  26  *
  27  * Drop operands from an expression tree of only min/max operations if they
  28  * can be proven to not contribute to the final result.
  29  *
  30  * The algorithm is similar to alpha-beta pruning on a minmax search.
  31  */
  32
  33 #include "ir.h"
  34 #include "ir_visitor.h"
  35 #include "ir_rvalue_visitor.h"
  36 #include "ir_optimization.h"
  37 #include "ir_builder.h"
  38 #include "program/prog_instruction.h"
  39 #include "glsl_types.h"
  40 #include "main/macros.h"
  41
  42 using namespace ir_builder;
  43
  44 namespace {
  45
  46 enum compare_components_result {
  47    LESS,
  48    LESS_OR_EQUAL,
  49    EQUAL,
  50    GREATER_OR_EQUAL,
  51    GREATER,
  52    MIXED
  53 };
  54
  55 class minmax_range {
  56 public:
  57    minmax_range(ir_constant *low = NULL, ir_constant *high = NULL)
  58    {
  59       this->low = low;
  60       this->high = high;
  61    }
  62
  63    /* low is the lower limit of the range, high is the higher limit. NULL on
  64     * low means negative infinity (unlimited) and on high positive infinity
  65     * (unlimited). Because of the two interpretations of the value NULL,
  66     * arbitrary comparison between ir_constants is impossible.
  67     */
  68    ir_constant *low;
  69    ir_constant *high;
  70 };
  71
  72 class ir_minmax_visitor : public ir_rvalue_enter_visitor {
  73 public:
  74    ir_minmax_visitor()
  75       : progress(false)
  76    {
  77    }
  78
  79    ir_rvalue *prune_expression(ir_expression *expr, minmax_range baserange);
  80
  81    void handle_rvalue(ir_rvalue **rvalue);
  82
  83    bool progress;
  84 };
  85
  86 /*
  87  * Returns LESS if all vector components of `a' are strictly lower than of `b',
  88  * GREATER if all vector components of `a' are strictly greater than of `b',
  89  * MIXED if some vector components of `a' are strictly lower than of `b' while
  90  * others are strictly greater, or EQUAL otherwise.
  91  */
  92 static enum compare_components_result
  93 compare_components(ir_constant *a, ir_constant *b)
  94 {
  95    assert(a != NULL);
  96    assert(b != NULL);
  97
  98    assert(a->type->base_type == b->type->base_type);
  99
 100    unsigned a_inc = a->type->is_scalar() ? 0 : 1;
 101    unsigned b_inc = b->type->is_scalar() ? 0 : 1;
 102    unsigned components = MAX2(a->type->components(), b->type->components());
 103
 104    bool foundless = false;
 105    bool foundgreater = false;
 106    bool foundequal = false;
 107
 108    for (unsigned i = 0, c0 = 0, c1 = 0;
 109         i < components;
 110         c0 += a_inc, c1 += b_inc, ++i) {
 111       switch (a->type->base_type) {
 112       case GLSL_TYPE_UINT:
 113          if (a->value.u[c0] < b->value.u[c1])
 114             foundless = true;
 115          else if (a->value.u[c0] > b->value.u[c1])
 116             foundgreater = true;
 117          else
 118             foundequal = true;
 119          break;
 120       case GLSL_TYPE_INT:
 121          if (a->value.i[c0] < b->value.i[c1])
 122             foundless = true;
 123          else if (a->value.i[c0] > b->value.i[c1])
 124             foundgreater = true;
 125          else
 126             foundequal = true;
 127          break;
 128       case GLSL_TYPE_FLOAT:
 129          if (a->value.f[c0] < b->value.f[c1])
 130             foundless = true;
 131          else if (a->value.f[c0] > b->value.f[c1])
 132             foundgreater = true;
 133          else
 134             foundequal = true;
 135          break;
 136       default:
 137          unreachable("not reached");
 138       }
 139    }
 140
 141    if (foundless && foundgreater) {
 142       /* Some components are strictly lower, others are strictly greater */
 143       return MIXED;
 144    }
 145
 146    if (foundequal) {
 147        /* It is not mixed, but it is not strictly lower or greater */
 148       if (foundless)
 149          return LESS_OR_EQUAL;
 150       if (foundgreater)
 151          return GREATER_OR_EQUAL;
 152       return EQUAL;
 153    }
 154
 155    /* All components are strictly lower or strictly greater */
 156    return foundless ? LESS : GREATER;
 157 }
 158
 159 static ir_constant *
 160 combine_constant(bool ismin, ir_constant *a, ir_constant *b)
 161 {
 162    void *mem_ctx = ralloc_parent(a);
 163    ir_constant *c = a->clone(mem_ctx, NULL);
 164    for (unsigned i = 0; i < c->type->components(); i++) {
 165       switch (c->type->base_type) {
 166       case GLSL_TYPE_UINT:
 167          if ((ismin && b->value.u[i] < c->value.u[i]) ||
 168              (!ismin && b->value.u[i] > c->value.u[i]))
 169             c->value.u[i] = b->value.u[i];
 170          break;
 171       case GLSL_TYPE_INT:
 172          if ((ismin && b->value.i[i] < c->value.i[i]) ||
 173              (!ismin && b->value.i[i] > c->value.i[i]))
 174             c->value.i[i] = b->value.i[i];
 175          break;
 176       case GLSL_TYPE_FLOAT:
 177          if ((ismin && b->value.f[i] < c->value.f[i]) ||
 178              (!ismin && b->value.f[i] > c->value.f[i]))
 179             c->value.f[i] = b->value.f[i];
 180          break;
 181       default:
 182          assert(!"not reached");
 183       }
 184    }
 185    return c;
 186 }
 187
 188 static ir_constant *
 189 smaller_constant(ir_constant *a, ir_constant *b)
 190 {
 191    assert(a != NULL);
 192    assert(b != NULL);
 193
 194    enum compare_components_result ret = compare_components(a, b);
 195    if (ret == MIXED)
 196       return combine_constant(true, a, b);
 197    else if (ret < EQUAL)
 198       return a;
 199    else
 200       return b;
 201 }
 202
 203 static ir_constant *
 204 larger_constant(ir_constant *a, ir_constant *b)
 205 {
 206    assert(a != NULL);
 207    assert(b != NULL);
 208
 209    enum compare_components_result ret = compare_components(a, b);
 210    if (ret == MIXED)
 211       return combine_constant(false, a, b);
 212    else if (ret < EQUAL)
 213       return b;
 214    else
 215       return a;
 216 }
 217
 218 /* Combines two ranges by doing an element-wise min() / max() depending on the
 219  * operation.
 220  */
 221 static minmax_range
 222 combine_range(minmax_range r0, minmax_range r1, bool ismin)
 223 {
 224    minmax_range ret;
 225
 226    if (!r0.low) {
 227       ret.low = ismin ? r0.low : r1.low;
 228    } else if (!r1.low) {
 229       ret.low = ismin ? r1.low : r0.low;
 230    } else {
 231       ret.low = ismin ? smaller_constant(r0.low, r1.low) :
 232          larger_constant(r0.low, r1.low);
 233    }
 234
 235    if (!r0.high) {
 236       ret.high = ismin ? r1.high : r0.high;
 237    } else if (!r1.high) {
 238       ret.high = ismin ? r0.high : r1.high;
 239    } else {
 240       ret.high = ismin ? smaller_constant(r0.high, r1.high) :
 241          larger_constant(r0.high, r1.high);
 242    }
 243
 244    return ret;
 245 }
 246
 247 /* Returns a range so that lower limit is the larger of the two lower limits,
 248  * and higher limit is the smaller of the two higher limits.
 249  */
 250 static minmax_range
 251 range_intersection(minmax_range r0, minmax_range r1)
 252 {
 253    minmax_range ret;
 254
 255    if (!r0.low)
 256       ret.low = r1.low;
 257    else if (!r1.low)
 258       ret.low = r0.low;
 259    else
 260       ret.low = larger_constant(r0.low, r1.low);
 261
 262    if (!r0.high)
 263       ret.high = r1.high;
 264    else if (!r1.high)
 265       ret.high = r0.high;
 266    else
 267       ret.high = smaller_constant(r0.high, r1.high);
 268
 269    return ret;
 270 }
 271
 272 static minmax_range
 273 get_range(ir_rvalue *rval)
 274 {
 275    ir_expression *expr = rval->as_expression();
 276    if (expr && (expr->operation == ir_binop_min ||
 277                 expr->operation == ir_binop_max)) {
 278       minmax_range r0 = get_range(expr->operands[0]);
 279       minmax_range r1 = get_range(expr->operands[1]);
 280       return combine_range(r0, r1, expr->operation == ir_binop_min);
 281    }
 282
 283    ir_constant *c = rval->as_constant();
 284    if (c) {
 285       return minmax_range(c, c);
 286    }
 287
 288    return minmax_range();
 289 }
 290
 291 /**
 292  * Prunes a min/max expression considering the base range of the parent
 293  * min/max expression.
 294  *
 295  * @param baserange the range that the parents of this min/max expression
 296  * in the min/max tree will clamp its value to.
 297  */
 298 ir_rvalue *
 299 ir_minmax_visitor::prune_expression(ir_expression *expr, minmax_range baserange)
 300 {
 301    assert(expr->operation == ir_binop_min ||
 302           expr->operation == ir_binop_max);
 303
 304    bool ismin = expr->operation == ir_binop_min;
 305    minmax_range limits[2];
 306
 307    /* Recurse to get the ranges for each of the subtrees of this
 308     * expression. We need to do this as a separate step because we need to
 309     * know the ranges of each of the subtrees before we prune either one.
 310     * Consider something like this:
 311     *
 312     *        max
 313     *     /       \
 314     *    max     max
 315     *   /   \   /   \
 316     *  3    a   b    2
 317     *
 318     * We would like to prune away the max on the bottom-right, but to do so
 319     * we need to know the range of the expression on the left beforehand,
 320     * and there's no guarantee that we will visit either subtree in a
 321     * particular order.
 322     */
 323    for (unsigned i = 0; i < 2; ++i)
 324       limits[i] = get_range(expr->operands[i]);
 325
 326    for (unsigned i = 0; i < 2; ++i) {
 327       bool is_redundant = false;
 328
 329       enum compare_components_result cr = LESS;
 330       if (ismin) {
 331          /* If this operand will always be greater than the other one, it's
 332           * redundant.
 333           */
 334          if (limits[i].low && limits[1 - i].high) {
 335                cr = compare_components(limits[i].low, limits[1 - i].high);
 336             if (cr >= EQUAL && cr != MIXED)
 337                is_redundant = true;
 338          }
 339          /* If this operand is always greater than baserange, then even if
 340           * it's smaller than the other one it'll get clamped, so it's
 341           * redundant.
 342           */
 343          if (!is_redundant && limits[i].low && baserange.high) {
 344             cr = compare_components(limits[i].low, baserange.high);
 345             if (cr >= EQUAL && cr != MIXED)
 346                is_redundant = true;
 347          }
 348       } else {
 349          /* If this operand will always be lower than the other one, it's
 350           * redundant.
 351           */
 352          if (limits[i].high && limits[1 - i].low) {
 353             cr = compare_components(limits[i].high, limits[1 - i].low);
 354             if (cr <= EQUAL)
 355                is_redundant = true;
 356          }
 357          /* If this operand is always lower than baserange, then even if
 358           * it's greater than the other one it'll get clamped, so it's
 359           * redundant.
 360           */
 361          if (!is_redundant && limits[i].high && baserange.low) {
 362             cr = compare_components(limits[i].high, baserange.low);
 363             if (cr <= EQUAL)
 364                is_redundant = true;
 365          }
 366       }
 367
 368       if (is_redundant) {
 369          progress = true;
 370
 371          /* Recurse if necessary. */
 372          ir_expression *op_expr = expr->operands[1 - i]->as_expression();
 373          if (op_expr && (op_expr->operation == ir_binop_min ||
 374                          op_expr->operation == ir_binop_max)) {
 375             return prune_expression(op_expr, baserange);
 376          }
 377
 378          return expr->operands[1 - i];
 379       } else if (cr == MIXED) {
 380          /* If we have mixed vector operands, we can try to resolve the minmax
 381           * expression by doing a component-wise minmax:
 382           *
 383           *             min                          min
 384           *           /    \                       /    \
 385           *         min     a       ===>        [1,1]    a
 386           *       /    \
 387           *    [1,3]   [3,1]
 388           *
 389           */
 390          ir_constant *a = expr->operands[0]->as_constant();
 391          ir_constant *b = expr->operands[1]->as_constant();
 392          if (a && b)
 393             return combine_constant(ismin, a, b);
 394       }
 395    }
 396
 397    /* Now recurse to operands giving them the proper baserange. The baserange
 398     * to pass is the intersection of our baserange and the other operand's
 399     * limit with one of the ranges unlimited. If we can't compute a valid
 400     * intersection, we use the current baserange.
 401     */
 402    for (unsigned i = 0; i < 2; ++i) {
 403       ir_expression *op_expr = expr->operands[i]->as_expression();
 404       if (op_expr && (op_expr->operation == ir_binop_min ||
 405                       op_expr->operation == ir_binop_max)) {
 406          /* We can only compute a new baserange for this operand if we managed
 407           * to compute a valid range for the other operand.
 408           */
 409          if (ismin)
 410             limits[1 - i].low = NULL;
 411          else
 412             limits[1 - i].high = NULL;
 413          minmax_range base = range_intersection(limits[1 - i], baserange);
 414          expr->operands[i] = prune_expression(op_expr, base);
 415       }
 416    }
 417
 418    /* If we got here we could not discard any of the operands of the minmax
 419     * expression, but we can still try to resolve the expression if both
 420     * operands are constant. We do this after the loop above, to make sure
 421     * that if our operands are minmax expressions we have tried to prune them
 422     * first (hopefully reducing them to constants).
 423     */
 424    ir_constant *a = expr->operands[0]->as_constant();
 425    ir_constant *b = expr->operands[1]->as_constant();
 426    if (a && b)
 427       return combine_constant(ismin, a, b);
 428
 429    return expr;
 430 }
 431
 432 static ir_rvalue *
 433 swizzle_if_required(ir_expression *expr, ir_rvalue *rval)
 434 {
 435    if (expr->type->is_vector() && rval->type->is_scalar()) {
 436       return swizzle(rval, SWIZZLE_XXXX, expr->type->vector_elements);
 437    } else {
 438       return rval;
 439    }
 440 }
 441
 442 void
 443 ir_minmax_visitor::handle_rvalue(ir_rvalue **rvalue)
 444 {
 445    if (!*rvalue)
 446       return;
 447
 448    ir_expression *expr = (*rvalue)->as_expression();
 449    if (!expr || (expr->operation != ir_binop_min &&
 450                  expr->operation != ir_binop_max))
 451       return;
 452
 453    ir_rvalue *new_rvalue = prune_expression(expr, minmax_range());
 454    if (new_rvalue == *rvalue)
 455       return;
 456
 457    /* If the expression type is a vector and the optimization leaves a scalar
 458     * as the result, we need to turn it into a vector.
 459     */
 460    *rvalue = swizzle_if_required(expr, new_rvalue);
 461
 462    progress = true;
 463 }
 464
 465 }
 466
 467 bool
 468 do_minmax_prune(exec_list *instructions)
 469 {
 470    ir_minmax_visitor v;
 471
 472    visit_list_elements(&v, instructions);
 473
 474    return v.progress;
 475 }