src/compiler/nir/nir_range_analysis.c

   1 /*
   2  * Copyright © 2018 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 DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23 #include <math.h>
  24 #include <float.h>
  25 #include "nir.h"
  26 #include "nir_range_analysis.h"
  27 #include "util/hash_table.h"
  28
  29 /**
  30  * Analyzes a sequence of operations to determine some aspects of the range of
  31  * the result.
  32  */
  33
  34 static bool
  35 is_not_zero(enum ssa_ranges r)
  36 {
  37    return r == gt_zero || r == lt_zero || r == ne_zero;
  38 }
  39
  40 static void *
  41 pack_data(const struct ssa_result_range r)
  42 {
  43    return (void *)(uintptr_t)(r.range | r.is_integral << 8);
  44 }
  45
  46 static struct ssa_result_range
  47 unpack_data(const void *p)
  48 {
  49    const uintptr_t v = (uintptr_t) p;
  50
  51    return (struct ssa_result_range){v & 0xff, (v & 0x0ff00) != 0};
  52 }
  53
  54 static struct ssa_result_range
  55 analyze_constant(const struct nir_alu_instr *instr, unsigned src)
  56 {
  57    uint8_t swizzle[4] = { 0, 1, 2, 3 };
  58
  59    /* If the source is an explicitly sized source, then we need to reset
  60     * both the number of components and the swizzle.
  61     */
  62    const unsigned num_components = nir_ssa_alu_instr_src_components(instr, src);
  63
  64    for (unsigned i = 0; i < num_components; ++i)
  65       swizzle[i] = instr->src[src].swizzle[i];
  66
  67    const nir_load_const_instr *const load =
  68       nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr);
  69
  70    struct ssa_result_range r = { unknown, false };
  71
  72    switch (nir_op_infos[instr->op].input_types[src]) {
  73    case nir_type_float: {
  74       double min_value = DBL_MAX;
  75       double max_value = -DBL_MAX;
  76       bool any_zero = false;
  77       bool all_zero = true;
  78
  79       r.is_integral = true;
  80
  81       for (unsigned i = 0; i < num_components; ++i) {
  82          const double v = nir_const_value_as_float(load->value[swizzle[i]],
  83                                                    load->def.bit_size);
  84
  85          if (floor(v) != v)
  86             r.is_integral = false;
  87
  88          any_zero = any_zero || (v == 0.0);
  89          all_zero = all_zero && (v == 0.0);
  90          min_value = MIN2(min_value, v);
  91          max_value = MAX2(max_value, v);
  92       }
  93
  94       assert(any_zero >= all_zero);
  95       assert(isnan(max_value) || max_value >= min_value);
  96
  97       if (all_zero)
  98          r.range = eq_zero;
  99       else if (min_value > 0.0)
 100          r.range = gt_zero;
 101       else if (min_value == 0.0)
 102          r.range = ge_zero;
 103       else if (max_value < 0.0)
 104          r.range = lt_zero;
 105       else if (max_value == 0.0)
 106          r.range = le_zero;
 107       else if (!any_zero)
 108          r.range = ne_zero;
 109       else
 110          r.range = unknown;
 111
 112       return r;
 113    }
 114
 115    case nir_type_int:
 116    case nir_type_bool: {
 117       int64_t min_value = INT_MAX;
 118       int64_t max_value = INT_MIN;
 119       bool any_zero = false;
 120       bool all_zero = true;
 121
 122       for (unsigned i = 0; i < num_components; ++i) {
 123          const int64_t v = nir_const_value_as_int(load->value[swizzle[i]],
 124                                                   load->def.bit_size);
 125
 126          any_zero = any_zero || (v == 0);
 127          all_zero = all_zero && (v == 0);
 128          min_value = MIN2(min_value, v);
 129          max_value = MAX2(max_value, v);
 130       }
 131
 132       assert(any_zero >= all_zero);
 133       assert(max_value >= min_value);
 134
 135       if (all_zero)
 136          r.range = eq_zero;
 137       else if (min_value > 0)
 138          r.range = gt_zero;
 139       else if (min_value == 0)
 140          r.range = ge_zero;
 141       else if (max_value < 0)
 142          r.range = lt_zero;
 143       else if (max_value == 0)
 144          r.range = le_zero;
 145       else if (!any_zero)
 146          r.range = ne_zero;
 147       else
 148          r.range = unknown;
 149
 150       return r;
 151    }
 152
 153    case nir_type_uint: {
 154       bool any_zero = false;
 155       bool all_zero = true;
 156
 157       for (unsigned i = 0; i < num_components; ++i) {
 158          const uint64_t v = nir_const_value_as_uint(load->value[swizzle[i]],
 159                                                     load->def.bit_size);
 160
 161          any_zero = any_zero || (v == 0);
 162          all_zero = all_zero && (v == 0);
 163       }
 164
 165       assert(any_zero >= all_zero);
 166
 167       if (all_zero)
 168          r.range = eq_zero;
 169       else if (any_zero)
 170          r.range = ge_zero;
 171       else
 172          r.range = gt_zero;
 173
 174       return r;
 175    }
 176
 177    default:
 178       unreachable("Invalid alu source type");
 179    }
 180 }
 181
 182 #ifndef NDEBUG
 183 #define ASSERT_TABLE_IS_COMMUTATIVE(t)                        \
 184    do {                                                       \
 185       for (unsigned r = 0; r < ARRAY_SIZE(t); r++) {          \
 186          for (unsigned c = 0; c < ARRAY_SIZE(t[0]); c++)      \
 187             assert(t[r][c] == t[c][r]);                       \
 188       }                                                       \
 189    } while (false)
 190
 191 #define ASSERT_TABLE_IS_DIAGONAL(t)                           \
 192    do {                                                       \
 193       for (unsigned r = 0; r < ARRAY_SIZE(t); r++)            \
 194          assert(t[r][r] == r);                                \
 195    } while (false)
 196 #else
 197 #define ASSERT_TABLE_IS_COMMUTATIVE(t)
 198 #define ASSERT_TABLE_IS_DIAGONAL(t)
 199 #endif
 200
 201 /**
 202  * Short-hand name for use in the tables in analyze_expression.  If this name
 203  * becomes a problem on some compiler, we can change it to _.
 204  */
 205 #define _______ unknown
 206
 207 /**
 208  * Analyze an expression to determine the range of its result
 209  *
 210  * The end result of this analysis is a token that communicates something
 211  * about the range of values.  There's an implicit grammar that produces
 212  * tokens from sequences of literal values, other tokens, and operations.
 213  * This function implements this grammar as a recursive-descent parser.  Some
 214  * (but not all) of the grammar is listed in-line in the function.
 215  */
 216 static struct ssa_result_range
 217 analyze_expression(const nir_alu_instr *instr, unsigned src,
 218                    struct hash_table *ht)
 219 {
 220    if (nir_src_is_const(instr->src[src].src))
 221       return analyze_constant(instr, src);
 222
 223    if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_alu)
 224       return (struct ssa_result_range){unknown, false};
 225
 226    const struct nir_alu_instr *const alu =
 227        nir_instr_as_alu(instr->src[src].src.ssa->parent_instr);
 228
 229    struct hash_entry *he = _mesa_hash_table_search(ht, alu);
 230    if (he != NULL)
 231       return unpack_data(he->data);
 232
 233    struct ssa_result_range r = {unknown, false};
 234
 235    switch (alu->op) {
 236    case nir_op_b2f32:
 237    case nir_op_b2i32:
 238       r = (struct ssa_result_range){ge_zero, alu->op == nir_op_b2f32};
 239       break;
 240
 241    case nir_op_bcsel: {
 242       const struct ssa_result_range left = analyze_expression(alu, 1, ht);
 243       const struct ssa_result_range right = analyze_expression(alu, 2, ht);
 244
 245       /* If either source is a constant load that is not zero, punt.  The type
 246        * will always be uint regardless of the actual type.  We can't even
 247        * decide if the value is non-zero because -0.0 is 0x80000000, and that
 248        * will (possibly incorrectly) be considered non-zero.
 249        */
 250       /* FINISHME: We could do better, but it would require having the expected
 251        * FINISHME: type passed in.
 252        */
 253       if ((nir_src_is_const(alu->src[1].src) && left.range != eq_zero) ||
 254           (nir_src_is_const(alu->src[2].src) && right.range != eq_zero)) {
 255          return (struct ssa_result_range){unknown, false};
 256       }
 257
 258       r.is_integral = left.is_integral && right.is_integral;
 259
 260       /* le_zero: bcsel(<any>, le_zero, lt_zero)
 261        *        | bcsel(<any>, eq_zero, lt_zero)
 262        *        | bcsel(<any>, le_zero, eq_zero)
 263        *        | bcsel(<any>, lt_zero, le_zero)
 264        *        | bcsel(<any>, lt_zero, eq_zero)
 265        *        | bcsel(<any>, eq_zero, le_zero)
 266        *        | bcsel(<any>, le_zero, le_zero)
 267        *        ;
 268        *
 269        * lt_zero: bcsel(<any>, lt_zero, lt_zero)
 270        *        ;
 271        *
 272        * ge_zero: bcsel(<any>, ge_zero, ge_zero)
 273        *        | bcsel(<any>, ge_zero, gt_zero)
 274        *        | bcsel(<any>, ge_zero, eq_zero)
 275        *        | bcsel(<any>, gt_zero, ge_zero)
 276        *        | bcsel(<any>, eq_zero, ge_zero)
 277        *        ;
 278        *
 279        * gt_zero: bcsel(<any>, gt_zero, gt_zero)
 280        *        ;
 281        *
 282        * ne_zero: bcsel(<any>, ne_zero, gt_zero)
 283        *        | bcsel(<any>, ne_zero, lt_zero)
 284        *        | bcsel(<any>, gt_zero, lt_zero)
 285        *        | bcsel(<any>, gt_zero, ne_zero)
 286        *        | bcsel(<any>, lt_zero, ne_zero)
 287        *        | bcsel(<any>, lt_zero, gt_zero)
 288        *        | bcsel(<any>, ne_zero, ne_zero)
 289        *        ;
 290        *
 291        * eq_zero: bcsel(<any>, eq_zero, eq_zero)
 292        *        ;
 293        *
 294        * All other cases are 'unknown'.
 295        *
 296        * The ranges could be tightened if the range of the first source is
 297        * known.  However, opt_algebraic will (eventually) elminiate the bcsel
 298        * if the condition is known.
 299        */
 300       static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
 301          /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
 302          /* unknown */ { _______, _______, _______, _______, _______, _______, _______ },
 303          /* lt_zero */ { _______, lt_zero, le_zero, ne_zero, _______, ne_zero, le_zero },
 304          /* le_zero */ { _______, le_zero, le_zero, _______, _______, _______, le_zero },
 305          /* gt_zero */ { _______, ne_zero, _______, gt_zero, ge_zero, ne_zero, ge_zero },
 306          /* ge_zero */ { _______, _______, _______, ge_zero, ge_zero, _______, ge_zero },
 307          /* ne_zero */ { _______, ne_zero, _______, ne_zero, _______, ne_zero, _______ },
 308          /* eq_zero */ { _______, le_zero, le_zero, ge_zero, ge_zero, _______, eq_zero },
 309       };
 310
 311       ASSERT_TABLE_IS_COMMUTATIVE(table);
 312       ASSERT_TABLE_IS_DIAGONAL(table);
 313
 314       r.range = table[left.range][right.range];
 315       break;
 316    }
 317
 318    case nir_op_i2f32:
 319    case nir_op_u2f32:
 320       r = analyze_expression(alu, 0, ht);
 321
 322       r.is_integral = true;
 323
 324       if (r.range == unknown && alu->op == nir_op_u2f32)
 325          r.range = ge_zero;
 326
 327       break;
 328
 329    case nir_op_fabs:
 330       r = analyze_expression(alu, 0, ht);
 331
 332       switch (r.range) {
 333       case unknown:
 334       case le_zero:
 335       case ge_zero:
 336          r.range = ge_zero;
 337          break;
 338
 339       case lt_zero:
 340       case gt_zero:
 341       case ne_zero:
 342          r.range = gt_zero;
 343          break;
 344
 345       case eq_zero:
 346          break;
 347       }
 348
 349       break;
 350
 351    case nir_op_fadd: {
 352       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 353       const struct ssa_result_range right = analyze_expression(alu, 1, ht);
 354
 355       r.is_integral = left.is_integral && right.is_integral;
 356
 357       /* ge_zero: ge_zero + ge_zero
 358        *
 359        * gt_zero: gt_zero + eq_zero
 360        *        | gt_zero + ge_zero
 361        *        | eq_zero + gt_zero   # Addition is commutative
 362        *        | ge_zero + gt_zero   # Addition is commutative
 363        *        | gt_zero + gt_zero
 364        *        ;
 365        *
 366        * le_zero: le_zero + le_zero
 367        *
 368        * lt_zero: lt_zero + eq_zero
 369        *        | lt_zero + le_zero
 370        *        | eq_zero + lt_zero   # Addition is commutative
 371        *        | le_zero + lt_zero   # Addition is commutative
 372        *        | lt_zero + lt_zero
 373        *        ;
 374        *
 375        * eq_zero: eq_zero + eq_zero
 376        *
 377        * All other cases are 'unknown'.
 378        */
 379       static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
 380          /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
 381          /* unknown */ { _______, _______, _______, _______, _______, _______, _______ },
 382          /* lt_zero */ { _______, lt_zero, lt_zero, _______, _______, _______, lt_zero },
 383          /* le_zero */ { _______, lt_zero, le_zero, _______, _______, _______, le_zero },
 384          /* gt_zero */ { _______, _______, _______, gt_zero, gt_zero, _______, gt_zero },
 385          /* ge_zero */ { _______, _______, _______, gt_zero, ge_zero, _______, ge_zero },
 386          /* ne_zero */ { _______, _______, _______, _______, _______, ne_zero, ne_zero },
 387          /* eq_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
 388       };
 389
 390       ASSERT_TABLE_IS_COMMUTATIVE(table);
 391       ASSERT_TABLE_IS_DIAGONAL(table);
 392
 393       r.range = table[left.range][right.range];
 394       break;
 395    }
 396
 397    case nir_op_fexp2:
 398       r = (struct ssa_result_range){gt_zero, analyze_expression(alu, 0, ht).is_integral};
 399       break;
 400
 401    case nir_op_fmax: {
 402       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 403       const struct ssa_result_range right = analyze_expression(alu, 1, ht);
 404
 405       r.is_integral = left.is_integral && right.is_integral;
 406
 407       /* gt_zero: fmax(gt_zero, *)
 408        *        | fmax(*, gt_zero)        # Treat fmax as commutative
 409        *        ;
 410        *
 411        * ge_zero: fmax(ge_zero, ne_zero)
 412        *        | fmax(ge_zero, lt_zero)
 413        *        | fmax(ge_zero, le_zero)
 414        *        | fmax(ge_zero, eq_zero)
 415        *        | fmax(ne_zero, ge_zero)  # Treat fmax as commutative
 416        *        | fmax(lt_zero, ge_zero)  # Treat fmax as commutative
 417        *        | fmax(le_zero, ge_zero)  # Treat fmax as commutative
 418        *        | fmax(eq_zero, ge_zero)  # Treat fmax as commutative
 419        *        | fmax(ge_zero, ge_zero)
 420        *        ;
 421        *
 422        * le_zero: fmax(le_zero, lt_zero)
 423        *        | fmax(lt_zero, le_zero)  # Treat fmax as commutative
 424        *        | fmax(le_zero, le_zero)
 425        *        ;
 426        *
 427        * lt_zero: fmax(lt_zero, lt_zero)
 428        *        ;
 429        *
 430        * ne_zero: fmax(ne_zero, lt_zero)
 431        *        | fmax(lt_zero, ne_zero)  # Treat fmax as commutative
 432        *        | fmax(ne_zero, ne_zero)
 433        *        ;
 434        *
 435        * eq_zero: fmax(eq_zero, le_zero)
 436        *        | fmax(eq_zero, lt_zero)
 437        *        | fmax(le_zero, eq_zero)  # Treat fmax as commutative
 438        *        | fmax(lt_zero, eq_zero)  # Treat fmax as commutative
 439        *        | fmax(eq_zero, eq_zero)
 440        *        ;
 441        *
 442        * All other cases are 'unknown'.
 443        */
 444       static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
 445          /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
 446          /* unknown */ { _______, _______, _______, gt_zero, ge_zero, _______, _______ },
 447          /* lt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
 448          /* le_zero */ { _______, le_zero, le_zero, gt_zero, ge_zero, _______, eq_zero },
 449          /* gt_zero */ { gt_zero, gt_zero, gt_zero, gt_zero, gt_zero, gt_zero, gt_zero },
 450          /* ge_zero */ { ge_zero, ge_zero, ge_zero, gt_zero, ge_zero, ge_zero, ge_zero },
 451          /* ne_zero */ { _______, ne_zero, _______, gt_zero, ge_zero, ne_zero, _______ },
 452          /* eq_zero */ { _______, eq_zero, eq_zero, gt_zero, ge_zero, _______, eq_zero }
 453       };
 454
 455       /* Treat fmax as commutative. */
 456       ASSERT_TABLE_IS_COMMUTATIVE(table);
 457       ASSERT_TABLE_IS_DIAGONAL(table);
 458
 459       r.range = table[left.range][right.range];
 460       break;
 461    }
 462
 463    case nir_op_fmin: {
 464       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 465       const struct ssa_result_range right = analyze_expression(alu, 1, ht);
 466
 467       r.is_integral = left.is_integral && right.is_integral;
 468
 469       /* lt_zero: fmin(lt_zero, *)
 470        *        | fmin(*, lt_zero)        # Treat fmin as commutative
 471        *        ;
 472        *
 473        * le_zero: fmin(le_zero, ne_zero)
 474        *        | fmin(le_zero, gt_zero)
 475        *        | fmin(le_zero, ge_zero)
 476        *        | fmin(le_zero, eq_zero)
 477        *        | fmin(ne_zero, le_zero)  # Treat fmin as commutative
 478        *        | fmin(gt_zero, le_zero)  # Treat fmin as commutative
 479        *        | fmin(ge_zero, le_zero)  # Treat fmin as commutative
 480        *        | fmin(eq_zero, le_zero)  # Treat fmin as commutative
 481        *        | fmin(le_zero, le_zero)
 482        *        ;
 483        *
 484        * ge_zero: fmin(ge_zero, gt_zero)
 485        *        | fmin(gt_zero, ge_zero)  # Treat fmin as commutative
 486        *        | fmin(ge_zero, ge_zero)
 487        *        ;
 488        *
 489        * gt_zero: fmin(gt_zero, gt_zero)
 490        *        ;
 491        *
 492        * ne_zero: fmin(ne_zero, gt_zero)
 493        *        | fmin(gt_zero, ne_zero)  # Treat fmin as commutative
 494        *        | fmin(ne_zero, ne_zero)
 495        *        ;
 496        *
 497        * eq_zero: fmin(eq_zero, ge_zero)
 498        *        | fmin(eq_zero, gt_zero)
 499        *        | fmin(ge_zero, eq_zero)  # Treat fmin as commutative
 500        *        | fmin(gt_zero, eq_zero)  # Treat fmin as commutative
 501        *        | fmin(eq_zero, eq_zero)
 502        *        ;
 503        *
 504        * All other cases are 'unknown'.
 505        */
 506       static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
 507          /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
 508          /* unknown */ { _______, lt_zero, le_zero, _______, _______, _______, _______ },
 509          /* lt_zero */ { lt_zero, lt_zero, lt_zero, lt_zero, lt_zero, lt_zero, lt_zero },
 510          /* le_zero */ { le_zero, lt_zero, le_zero, le_zero, le_zero, le_zero, le_zero },
 511          /* gt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
 512          /* ge_zero */ { _______, lt_zero, le_zero, ge_zero, ge_zero, _______, eq_zero },
 513          /* ne_zero */ { _______, lt_zero, le_zero, ne_zero, _______, ne_zero, _______ },
 514          /* eq_zero */ { _______, lt_zero, le_zero, eq_zero, eq_zero, _______, eq_zero }
 515       };
 516
 517       /* Treat fmin as commutative. */
 518       ASSERT_TABLE_IS_COMMUTATIVE(table);
 519       ASSERT_TABLE_IS_DIAGONAL(table);
 520
 521       r.range = table[left.range][right.range];
 522       break;
 523    }
 524
 525    case nir_op_fmul: {
 526       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 527       const struct ssa_result_range right = analyze_expression(alu, 1, ht);
 528
 529       r.is_integral = left.is_integral && right.is_integral;
 530
 531       /* ge_zero: ge_zero * ge_zero
 532        *        | ge_zero * gt_zero
 533        *        | ge_zero * eq_zero
 534        *        | le_zero * lt_zero
 535        *        | lt_zero * le_zero  # Multiplication is commutative
 536        *        | le_zero * le_zero
 537        *        | gt_zero * ge_zero  # Multiplication is commutative
 538        *        | eq_zero * ge_zero  # Multiplication is commutative
 539        *        | a * a              # Left source == right source
 540        *        ;
 541        *
 542        * gt_zero: gt_zero * gt_zero
 543        *        | lt_zero * lt_zero
 544        *        ;
 545        *
 546        * le_zero: ge_zero * le_zero
 547        *        | ge_zero * lt_zero
 548        *        | lt_zero * ge_zero  # Multiplication is commutative
 549        *        | le_zero * ge_zero  # Multiplication is commutative
 550        *        | le_zero * gt_zero
 551        *        ;
 552        *
 553        * lt_zero: lt_zero * gt_zero
 554        *        | gt_zero * lt_zero  # Multiplication is commutative
 555        *        ;
 556        *
 557        * ne_zero: ne_zero * gt_zero
 558        *        | ne_zero * lt_zero
 559        *        | gt_zero * ne_zero  # Multiplication is commutative
 560        *        | lt_zero * ne_zero  # Multiplication is commutative
 561        *        | ne_zero * ne_zero
 562        *        ;
 563        *
 564        * eq_zero: eq_zero * <any>
 565        *          <any> * eq_zero    # Multiplication is commutative
 566        *
 567        * All other cases are 'unknown'.
 568        */
 569       static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
 570          /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
 571          /* unknown */ { _______, _______, _______, _______, _______, _______, eq_zero },
 572          /* lt_zero */ { _______, gt_zero, ge_zero, lt_zero, le_zero, ne_zero, eq_zero },
 573          /* le_zero */ { _______, ge_zero, ge_zero, le_zero, le_zero, _______, eq_zero },
 574          /* gt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
 575          /* ge_zero */ { _______, le_zero, le_zero, ge_zero, ge_zero, _______, eq_zero },
 576          /* ne_zero */ { _______, ne_zero, _______, ne_zero, _______, ne_zero, eq_zero },
 577          /* eq_zero */ { eq_zero, eq_zero, eq_zero, eq_zero, eq_zero, eq_zero, eq_zero }
 578       };
 579
 580       ASSERT_TABLE_IS_COMMUTATIVE(table);
 581
 582       /* x * x => ge_zero */
 583       if (left.range != eq_zero && nir_alu_srcs_equal(alu, alu, 0, 1)) {
 584          /* x * x => ge_zero or gt_zero depending on the range of x. */
 585          r.range = is_not_zero(left.range) ? gt_zero : ge_zero;
 586       } else if (left.range != eq_zero && nir_alu_srcs_negative_equal(alu, alu, 0, 1)) {
 587          /* -x * x => le_zero or lt_zero depending on the range of x. */
 588          r.range = is_not_zero(left.range) ? lt_zero : le_zero;
 589       } else
 590          r.range = table[left.range][right.range];
 591
 592       break;
 593    }
 594
 595    case nir_op_frcp:
 596       r = (struct ssa_result_range){analyze_expression(alu, 0, ht).range, false};
 597       break;
 598
 599    case nir_op_mov:
 600       r = analyze_expression(alu, 0, ht);
 601       break;
 602
 603    case nir_op_fneg:
 604       r = analyze_expression(alu, 0, ht);
 605
 606       switch (r.range) {
 607       case le_zero:
 608          r.range = ge_zero;
 609          break;
 610
 611       case ge_zero:
 612          r.range = le_zero;
 613          break;
 614
 615       case lt_zero:
 616          r.range = gt_zero;
 617          break;
 618
 619       case gt_zero:
 620          r.range = lt_zero;
 621          break;
 622
 623       case ne_zero:
 624       case eq_zero:
 625       case unknown:
 626          /* Negation doesn't change anything about these ranges. */
 627          break;
 628       }
 629
 630       break;
 631
 632    case nir_op_fsat:
 633       r = analyze_expression(alu, 0, ht);
 634
 635       switch (r.range) {
 636       case le_zero:
 637       case lt_zero:
 638          r.range = eq_zero;
 639          r.is_integral = true;
 640          break;
 641
 642       case eq_zero:
 643          assert(r.is_integral);
 644       case gt_zero:
 645       case ge_zero:
 646          /* The fsat doesn't add any information in these cases. */
 647          break;
 648
 649       case ne_zero:
 650       case unknown:
 651          /* Since the result must be in [0, 1], the value must be >= 0. */
 652          r.range = ge_zero;
 653          break;
 654       }
 655       break;
 656
 657    case nir_op_fsign:
 658       r = (struct ssa_result_range){analyze_expression(alu, 0, ht).range, true};
 659       break;
 660
 661    case nir_op_fsqrt:
 662    case nir_op_frsq:
 663       r = (struct ssa_result_range){ge_zero, false};
 664       break;
 665
 666    case nir_op_ffloor: {
 667       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 668
 669       r.is_integral = true;
 670
 671       if (left.is_integral || left.range == le_zero || left.range == lt_zero)
 672          r.range = left.range;
 673       else if (left.range == ge_zero || left.range == gt_zero)
 674          r.range = ge_zero;
 675       else if (left.range == ne_zero)
 676          r.range = unknown;
 677
 678       break;
 679    }
 680
 681    case nir_op_fceil: {
 682       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 683
 684       r.is_integral = true;
 685
 686       if (left.is_integral || left.range == ge_zero || left.range == gt_zero)
 687          r.range = left.range;
 688       else if (left.range == le_zero || left.range == lt_zero)
 689          r.range = le_zero;
 690       else if (left.range == ne_zero)
 691          r.range = unknown;
 692
 693       break;
 694    }
 695
 696    case nir_op_ftrunc: {
 697       const struct ssa_result_range left = analyze_expression(alu, 0, ht);
 698
 699       r.is_integral = true;
 700
 701       if (left.is_integral)
 702          r.range = left.range;
 703       else if (left.range == ge_zero || left.range == gt_zero)
 704          r.range = ge_zero;
 705       else if (left.range == le_zero || left.range == lt_zero)
 706          r.range = le_zero;
 707       else if (left.range == ne_zero)
 708          r.range = unknown;
 709
 710       break;
 711    }
 712
 713    case nir_op_flt:
 714    case nir_op_fge:
 715    case nir_op_feq:
 716    case nir_op_fne:
 717    case nir_op_ilt:
 718    case nir_op_ige:
 719    case nir_op_ieq:
 720    case nir_op_ine:
 721    case nir_op_ult:
 722    case nir_op_uge:
 723       /* Boolean results are 0 or -1. */
 724       r = (struct ssa_result_range){le_zero, false};
 725       break;
 726
 727    default:
 728       r = (struct ssa_result_range){unknown, false};
 729       break;
 730    }
 731
 732    if (r.range == eq_zero)
 733       r.is_integral = true;
 734
 735    _mesa_hash_table_insert(ht, alu, pack_data(r));
 736    return r;
 737 }
 738
 739 #undef _______
 740
 741 struct ssa_result_range
 742 nir_analyze_range(const nir_alu_instr *instr, unsigned src)
 743 {
 744    struct hash_table *ht = _mesa_pointer_hash_table_create(NULL);
 745
 746    const struct ssa_result_range r = analyze_expression(instr, src, ht);
 747
 748    _mesa_hash_table_destroy(ht, NULL);
 749
 750    return r;
 751 }