nir/range-analysis: Rudimentary value range analysis pass

Most integer operations are omitted because dealing with integer
overflow is hard.  There are a few things that could be smarter if there
was a small amount more tracking of ranges of integer types (i.e.,
operands are Boolean, operand values fit in 16 bits, etc.).

The changes to nir_search_helpers.h are included in this patch to
simplify reordering the changes to nir_opt_algebraic.py.

v2: Memoize range analysis results.  Without this, some shaders appear
to get stuck in infinite loops.

v3: Rebase on many months of Mesa changes, including 1-bit Boolean
changes.

v4: Rebase on "nir: Drop imov/fmov in favor of one mov instruction".

v5: Use nir_alu_srcs_equal for detecting (a*a).  Previously just the SSA
value was compared, and this incorrectly matched (a.x*a.y).

v6: Many code improvements including (but not limited to) better names,
more comments, and better use of helper functions.  All suggested by
Caio.  Rework the handling of several opcodes to use a table for mapping
source ranges to a result range.  This change fixed a bug that caused
fmax(gt_zero, ge_zero) to be incorrectly recognized as ge_zero.
Slightly tighten the range of fmul by recognizing that x*x is gt_zero if
x is gt_zero.  Add similar handling for -x*x.

v7: Use _______ in the tables as an alias for unknown.  Suggested by
Caio.

Reviewed-by: Caio Marcelo de Oliveira Filho <caio.oliveira@intel.com>

5 files changed, 753 insertions, 0 deletions

diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
index b3a9a3cc031..b59ce9b737f 100644
--- a/src/compiler/Makefile.sources
+++ b/src/compiler/Makefile.sources
@@ -319,6 +319,8 @@ NIR_FILES = \
 	nir/nir_phi_builder.h \
 	nir/nir_print.c \
 	nir/nir_propagate_invariant.c \
+	nir/nir_range_analysis.c \
+	nir/nir_range_analysis.h \
 	nir/nir_remove_dead_variables.c \
 	nir/nir_repair_ssa.c \
 	nir/nir_search.c \
diff --git a/src/compiler/nir/meson.build b/src/compiler/nir/meson.build
index dce8eabaab5..e6b11cb8762 100644
--- a/src/compiler/nir/meson.build
+++ b/src/compiler/nir/meson.build
@@ -198,6 +198,8 @@ files_libnir = files(
   'nir_phi_builder.h',
   'nir_print.c',
   'nir_propagate_invariant.c',
+  'nir_range_analysis.c',
+  'nir_range_analysis.h',
   'nir_remove_dead_variables.c',
   'nir_repair_ssa.c',
   'nir_search.c',
diff --git a/src/compiler/nir/nir_range_analysis.c b/src/compiler/nir/nir_range_analysis.c
new file mode 100644
index 00000000000..8df3558df7a
--- /dev/null
+++ b/src/compiler/nir/nir_range_analysis.c
@@ -0,0 +1,653 @@
+/*
+ * Copyright © 2018 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.
+ */
+#include <math.h>
+#include <float.h>
+#include "nir.h"
+#include "nir_range_analysis.h"
+#include "util/hash_table.h"
+
+/**
+ * Analyzes a sequence of operations to determine some aspects of the range of
+ * the result.
+ */
+
+static bool
+is_not_zero(enum ssa_ranges r)
+{
+   return r == gt_zero || r == lt_zero || r == ne_zero;
+}
+
+static void *
+pack_data(const struct ssa_result_range r)
+{
+   return (void *)(uintptr_t)(r.range | r.is_integral << 8);
+}
+
+static struct ssa_result_range
+unpack_data(const void *p)
+{
+   const uintptr_t v = (uintptr_t) p;
+
+   return (struct ssa_result_range){v & 0xff, (v & 0x0ff00) != 0};
+}
+
+static struct ssa_result_range
+analyze_constant(const struct nir_alu_instr *instr, unsigned src)
+{
+   uint8_t swizzle[4] = { 0, 1, 2, 3 };
+
+   /* If the source is an explicitly sized source, then we need to reset
+    * both the number of components and the swizzle.
+    */
+   const unsigned num_components = nir_ssa_alu_instr_src_components(instr, src);
+
+   for (unsigned i = 0; i < num_components; ++i)
+      swizzle[i] = instr->src[src].swizzle[i];
+
+   const nir_load_const_instr *const load =
+      nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr);
+
+   struct ssa_result_range r = { unknown, false };
+
+   switch (nir_op_infos[instr->op].input_types[src]) {
+   case nir_type_float: {
+      double min_value = DBL_MAX;
+      double max_value = -DBL_MAX;
+      bool any_zero = false;
+      bool all_zero = true;
+
+      r.is_integral = true;
+
+      for (unsigned i = 0; i < num_components; ++i) {
+         const double v = nir_const_value_as_float(load->value[swizzle[i]],
+                                                   load->def.bit_size);
+
+         if (floor(v) != v)
+            r.is_integral = false;
+
+         any_zero = any_zero || (v == 0.0);
+         all_zero = all_zero && (v == 0.0);
+         min_value = MIN2(min_value, v);
+         max_value = MAX2(max_value, v);
+      }
+
+      assert(any_zero >= all_zero);
+      assert(isnan(max_value) || max_value >= min_value);
+
+      if (all_zero)
+         r.range = eq_zero;
+      else if (min_value > 0.0)
+         r.range = gt_zero;
+      else if (min_value == 0.0)
+         r.range = ge_zero;
+      else if (max_value < 0.0)
+         r.range = lt_zero;
+      else if (max_value == 0.0)
+         r.range = le_zero;
+      else if (!any_zero)
+         r.range = ne_zero;
+      else
+         r.range = unknown;
+
+      return r;
+   }
+
+   case nir_type_int:
+   case nir_type_bool: {
+      int64_t min_value = INT_MAX;
+      int64_t max_value = INT_MIN;
+      bool any_zero = false;
+      bool all_zero = true;
+
+      for (unsigned i = 0; i < num_components; ++i) {
+         const int64_t v = nir_const_value_as_int(load->value[swizzle[i]],
+                                                  load->def.bit_size);
+
+         any_zero = any_zero || (v == 0);
+         all_zero = all_zero && (v == 0);
+         min_value = MIN2(min_value, v);
+         max_value = MAX2(max_value, v);
+      }
+
+      assert(any_zero >= all_zero);
+      assert(max_value >= min_value);
+
+      if (all_zero)
+         r.range = eq_zero;
+      else if (min_value > 0)
+         r.range = gt_zero;
+      else if (min_value == 0)
+         r.range = ge_zero;
+      else if (max_value < 0)
+         r.range = lt_zero;
+      else if (max_value == 0)
+         r.range = le_zero;
+      else if (!any_zero)
+         r.range = ne_zero;
+      else
+         r.range = unknown;
+
+      return r;
+   }
+
+   case nir_type_uint: {
+      bool any_zero = false;
+      bool all_zero = true;
+
+      for (unsigned i = 0; i < num_components; ++i) {
+         const uint64_t v = nir_const_value_as_uint(load->value[swizzle[i]],
+                                                    load->def.bit_size);
+
+         any_zero = any_zero || (v == 0);
+         all_zero = all_zero && (v == 0);
+      }
+
+      assert(any_zero >= all_zero);
+
+      if (all_zero)
+         r.range = eq_zero;
+      else if (any_zero)
+         r.range = ge_zero;
+      else
+         r.range = gt_zero;
+
+      return r;
+   }
+
+   default:
+      unreachable("Invalid alu source type");
+   }
+}
+
+#ifndef NDEBUG
+#define ASSERT_TABLE_IS_COMMUTATIVE(t)                        \
+   do {                                                       \
+      for (unsigned r = 0; r < ARRAY_SIZE(t); r++) {          \
+         for (unsigned c = 0; c < ARRAY_SIZE(t[0]); c++)      \
+            assert(t[r][c] == t[c][r]);                       \
+      }                                                       \
+   } while (false)
+
+#define ASSERT_TABLE_IS_DIAGONAL(t)                           \
+   do {                                                       \
+      for (unsigned r = 0; r < ARRAY_SIZE(t); r++)            \
+         assert(t[r][r] == r);                                \
+   } while (false)
+#else
+#define ASSERT_TABLE_IS_COMMUTATIVE(t)
+#define ASSERT_TABLE_IS_DIAGONAL(t)
+#endif
+
+/**
+ * Short-hand name for use in the tables in analyze_expression.  If this name
+ * becomes a problem on some compiler, we can change it to _.
+ */
+#define _______ unknown
+
+/**
+ * Analyze an expression to determine the range of its result
+ *
+ * The end result of this analysis is a token that communicates something
+ * about the range of values.  There's an implicit grammar that produces
+ * tokens from sequences of literal values, other tokens, and operations.
+ * This function implements this grammar as a recursive-descent parser.  Some
+ * (but not all) of the grammar is listed in-line in the function.
+ */
+static struct ssa_result_range
+analyze_expression(const nir_alu_instr *instr, unsigned src,
+                   struct hash_table *ht)
+{
+   if (nir_src_is_const(instr->src[src].src))
+      return analyze_constant(instr, src);
+
+   if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_alu)
+      return (struct ssa_result_range){unknown, false};
+
+   const struct nir_alu_instr *const alu =
+       nir_instr_as_alu(instr->src[src].src.ssa->parent_instr);
+
+   struct hash_entry *he = _mesa_hash_table_search(ht, alu);
+   if (he != NULL)
+      return unpack_data(he->data);
+
+   struct ssa_result_range r = {unknown, false};
+
+   switch (alu->op) {
+   case nir_op_b2f32:
+   case nir_op_b2i32:
+      r = (struct ssa_result_range){ge_zero, alu->op == nir_op_b2f32};
+      break;
+
+   case nir_op_i2f32:
+   case nir_op_u2f32:
+      r = analyze_expression(alu, 0, ht);
+
+      r.is_integral = true;
+
+      if (r.range == unknown && alu->op == nir_op_u2f32)
+         r.range = ge_zero;
+
+      break;
+
+   case nir_op_fabs:
+      r = analyze_expression(alu, 0, ht);
+
+      switch (r.range) {
+      case unknown:
+      case le_zero:
+      case ge_zero:
+         r.range = ge_zero;
+         break;
+
+      case lt_zero:
+      case gt_zero:
+      case ne_zero:
+         r.range = gt_zero;
+         break;
+
+      case eq_zero:
+         break;
+      }
+
+      break;
+
+   case nir_op_fadd: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+      const struct ssa_result_range right = analyze_expression(alu, 1, ht);
+
+      r.is_integral = left.is_integral && right.is_integral;
+
+      /* ge_zero: ge_zero + ge_zero
+       *
+       * gt_zero: gt_zero + eq_zero
+       *        | gt_zero + ge_zero
+       *        | eq_zero + gt_zero   # Addition is commutative
+       *        | ge_zero + gt_zero   # Addition is commutative
+       *        | gt_zero + gt_zero
+       *        ;
+       *
+       * le_zero: le_zero + le_zero
+       *
+       * lt_zero: lt_zero + eq_zero
+       *        | lt_zero + le_zero
+       *        | eq_zero + lt_zero   # Addition is commutative
+       *        | le_zero + lt_zero   # Addition is commutative
+       *        | lt_zero + lt_zero
+       *        ;
+       *
+       * eq_zero: eq_zero + eq_zero
+       *
+       * All other cases are 'unknown'.
+       */
+      static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
+         /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
+         /* unknown */ { _______, _______, _______, _______, _______, _______, _______ },
+         /* lt_zero */ { _______, lt_zero, lt_zero, _______, _______, _______, lt_zero },
+         /* le_zero */ { _______, lt_zero, le_zero, _______, _______, _______, le_zero },
+         /* gt_zero */ { _______, _______, _______, gt_zero, gt_zero, _______, gt_zero },
+         /* ge_zero */ { _______, _______, _______, gt_zero, ge_zero, _______, ge_zero },
+         /* ne_zero */ { _______, _______, _______, _______, _______, ne_zero, ne_zero },
+         /* eq_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
+      };
+
+      ASSERT_TABLE_IS_COMMUTATIVE(table);
+      ASSERT_TABLE_IS_DIAGONAL(table);
+
+      r.range = table[left.range][right.range];
+      break;
+   }
+
+   case nir_op_fexp2:
+      r = (struct ssa_result_range){gt_zero, analyze_expression(alu, 0, ht).is_integral};
+      break;
+
+   case nir_op_fmax: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+      const struct ssa_result_range right = analyze_expression(alu, 1, ht);
+
+      r.is_integral = left.is_integral && right.is_integral;
+
+      /* gt_zero: fmax(gt_zero, *)
+       *        | fmax(*, gt_zero)        # Treat fmax as commutative
+       *        ;
+       *
+       * ge_zero: fmax(ge_zero, ne_zero)
+       *        | fmax(ge_zero, lt_zero)
+       *        | fmax(ge_zero, le_zero)
+       *        | fmax(ge_zero, eq_zero)
+       *        | fmax(ne_zero, ge_zero)  # Treat fmax as commutative
+       *        | fmax(lt_zero, ge_zero)  # Treat fmax as commutative
+       *        | fmax(le_zero, ge_zero)  # Treat fmax as commutative
+       *        | fmax(eq_zero, ge_zero)  # Treat fmax as commutative
+       *        | fmax(ge_zero, ge_zero)
+       *        ;
+       *
+       * le_zero: fmax(le_zero, lt_zero)
+       *        | fmax(lt_zero, le_zero)  # Treat fmax as commutative
+       *        | fmax(le_zero, le_zero)
+       *        ;
+       *
+       * lt_zero: fmax(lt_zero, lt_zero)
+       *        ;
+       *
+       * ne_zero: fmax(ne_zero, lt_zero)
+       *        | fmax(lt_zero, ne_zero)  # Treat fmax as commutative
+       *        | fmax(ne_zero, ne_zero)
+       *        ;
+       *
+       * eq_zero: fmax(eq_zero, le_zero)
+       *        | fmax(eq_zero, lt_zero)
+       *        | fmax(le_zero, eq_zero)  # Treat fmax as commutative
+       *        | fmax(lt_zero, eq_zero)  # Treat fmax as commutative
+       *        | fmax(eq_zero, eq_zero)
+       *        ;
+       *
+       * All other cases are 'unknown'.
+       */
+      static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
+         /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
+         /* unknown */ { _______, _______, _______, gt_zero, ge_zero, _______, _______ },
+         /* lt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
+         /* le_zero */ { _______, le_zero, le_zero, gt_zero, ge_zero, _______, eq_zero },
+         /* gt_zero */ { gt_zero, gt_zero, gt_zero, gt_zero, gt_zero, gt_zero, gt_zero },
+         /* ge_zero */ { ge_zero, ge_zero, ge_zero, gt_zero, ge_zero, ge_zero, ge_zero },
+         /* ne_zero */ { _______, ne_zero, _______, gt_zero, ge_zero, ne_zero, _______ },
+         /* eq_zero */ { _______, eq_zero, eq_zero, gt_zero, ge_zero, _______, eq_zero }
+      };
+
+      /* Treat fmax as commutative. */
+      ASSERT_TABLE_IS_COMMUTATIVE(table);
+      ASSERT_TABLE_IS_DIAGONAL(table);
+
+      r.range = table[left.range][right.range];
+      break;
+   }
+
+   case nir_op_fmin: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+      const struct ssa_result_range right = analyze_expression(alu, 1, ht);
+
+      r.is_integral = left.is_integral && right.is_integral;
+
+      /* lt_zero: fmin(lt_zero, *)
+       *        | fmin(*, lt_zero)        # Treat fmin as commutative
+       *        ;
+       *
+       * le_zero: fmin(le_zero, ne_zero)
+       *        | fmin(le_zero, gt_zero)
+       *        | fmin(le_zero, ge_zero)
+       *        | fmin(le_zero, eq_zero)
+       *        | fmin(ne_zero, le_zero)  # Treat fmin as commutative
+       *        | fmin(gt_zero, le_zero)  # Treat fmin as commutative
+       *        | fmin(ge_zero, le_zero)  # Treat fmin as commutative
+       *        | fmin(eq_zero, le_zero)  # Treat fmin as commutative
+       *        | fmin(le_zero, le_zero)
+       *        ;
+       *
+       * ge_zero: fmin(ge_zero, gt_zero)
+       *        | fmin(gt_zero, ge_zero)  # Treat fmin as commutative
+       *        | fmin(ge_zero, ge_zero)
+       *        ;
+       *
+       * gt_zero: fmin(gt_zero, gt_zero)
+       *        ;
+       *
+       * ne_zero: fmin(ne_zero, gt_zero)
+       *        | fmin(gt_zero, ne_zero)  # Treat fmin as commutative
+       *        | fmin(ne_zero, ne_zero)
+       *        ;
+       *
+       * eq_zero: fmin(eq_zero, ge_zero)
+       *        | fmin(eq_zero, gt_zero)
+       *        | fmin(ge_zero, eq_zero)  # Treat fmin as commutative
+       *        | fmin(gt_zero, eq_zero)  # Treat fmin as commutative
+       *        | fmin(eq_zero, eq_zero)
+       *        ;
+       *
+       * All other cases are 'unknown'.
+       */
+      static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
+         /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
+         /* unknown */ { _______, lt_zero, le_zero, _______, _______, _______, _______ },
+         /* lt_zero */ { lt_zero, lt_zero, lt_zero, lt_zero, lt_zero, lt_zero, lt_zero },
+         /* le_zero */ { le_zero, lt_zero, le_zero, le_zero, le_zero, le_zero, le_zero },
+         /* gt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
+         /* ge_zero */ { _______, lt_zero, le_zero, ge_zero, ge_zero, _______, eq_zero },
+         /* ne_zero */ { _______, lt_zero, le_zero, ne_zero, _______, ne_zero, _______ },
+         /* eq_zero */ { _______, lt_zero, le_zero, eq_zero, eq_zero, _______, eq_zero }
+      };
+
+      /* Treat fmin as commutative. */
+      ASSERT_TABLE_IS_COMMUTATIVE(table);
+      ASSERT_TABLE_IS_DIAGONAL(table);
+
+      r.range = table[left.range][right.range];
+      break;
+   }
+
+   case nir_op_fmul: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+      const struct ssa_result_range right = analyze_expression(alu, 1, ht);
+
+      r.is_integral = left.is_integral && right.is_integral;
+
+      /* ge_zero: ge_zero * ge_zero
+       *        | ge_zero * gt_zero
+       *        | ge_zero * eq_zero
+       *        | le_zero * lt_zero
+       *        | lt_zero * le_zero  # Multiplication is commutative
+       *        | le_zero * le_zero
+       *        | gt_zero * ge_zero  # Multiplication is commutative
+       *        | eq_zero * ge_zero  # Multiplication is commutative
+       *        | a * a              # Left source == right source
+       *        ;
+       *
+       * gt_zero: gt_zero * gt_zero
+       *        | lt_zero * lt_zero
+       *        ;
+       *
+       * le_zero: ge_zero * le_zero
+       *        | ge_zero * lt_zero
+       *        | lt_zero * ge_zero  # Multiplication is commutative
+       *        | le_zero * ge_zero  # Multiplication is commutative
+       *        | le_zero * gt_zero
+       *        ;
+       *
+       * lt_zero: lt_zero * gt_zero
+       *        | gt_zero * lt_zero  # Multiplication is commutative
+       *        ;
+       *
+       * ne_zero: ne_zero * gt_zero
+       *        | ne_zero * lt_zero
+       *        | gt_zero * ne_zero  # Multiplication is commutative
+       *        | lt_zero * ne_zero  # Multiplication is commutative
+       *        | ne_zero * ne_zero
+       *        ;
+       *
+       * eq_zero: eq_zero * <any>
+       *          <any> * eq_zero    # Multiplication is commutative
+       *
+       * All other cases are 'unknown'.
+       */
+      static const enum ssa_ranges table[last_range + 1][last_range + 1] = {
+         /* left\right   unknown  lt_zero  le_zero  gt_zero  ge_zero  ne_zero  eq_zero */
+         /* unknown */ { _______, _______, _______, _______, _______, _______, eq_zero },
+         /* lt_zero */ { _______, gt_zero, ge_zero, lt_zero, le_zero, ne_zero, eq_zero },
+         /* le_zero */ { _______, ge_zero, ge_zero, le_zero, le_zero, _______, eq_zero },
+         /* gt_zero */ { _______, lt_zero, le_zero, gt_zero, ge_zero, ne_zero, eq_zero },
+         /* ge_zero */ { _______, le_zero, le_zero, ge_zero, ge_zero, _______, eq_zero },
+         /* ne_zero */ { _______, ne_zero, _______, ne_zero, _______, ne_zero, eq_zero },
+         /* eq_zero */ { eq_zero, eq_zero, eq_zero, eq_zero, eq_zero, eq_zero, eq_zero }
+      };
+
+      ASSERT_TABLE_IS_COMMUTATIVE(table);
+
+      /* x * x => ge_zero */
+      if (left.range != eq_zero && nir_alu_srcs_equal(alu, alu, 0, 1)) {
+         /* x * x => ge_zero or gt_zero depending on the range of x. */
+         r.range = is_not_zero(left.range) ? gt_zero : ge_zero;
+      } else if (left.range != eq_zero && nir_alu_srcs_negative_equal(alu, alu, 0, 1)) {
+         /* -x * x => le_zero or lt_zero depending on the range of x. */
+         r.range = is_not_zero(left.range) ? lt_zero : le_zero;
+      } else
+         r.range = table[left.range][right.range];
+
+      break;
+   }
+
+   case nir_op_frcp:
+      r = (struct ssa_result_range){analyze_expression(alu, 0, ht).range, false};
+      break;
+
+   case nir_op_mov:
+      r = analyze_expression(alu, 0, ht);
+      break;
+
+   case nir_op_fneg:
+      r = analyze_expression(alu, 0, ht);
+
+      switch (r.range) {
+      case le_zero:
+         r.range = ge_zero;
+         break;
+
+      case ge_zero:
+         r.range = le_zero;
+         break;
+
+      case lt_zero:
+         r.range = gt_zero;
+         break;
+
+      case gt_zero:
+         r.range = lt_zero;
+         break;
+
+      case ne_zero:
+      case eq_zero:
+      case unknown:
+         /* Negation doesn't change anything about these ranges. */
+         break;
+      }
+
+      break;
+
+   case nir_op_fsat:
+      r = (struct ssa_result_range){ge_zero, analyze_expression(alu, 0, ht).is_integral};
+      break;
+
+   case nir_op_fsign:
+      r = (struct ssa_result_range){analyze_expression(alu, 0, ht).range, true};
+      break;
+
+   case nir_op_fsqrt:
+   case nir_op_frsq:
+      r = (struct ssa_result_range){ge_zero, false};
+      break;
+
+   case nir_op_ffloor: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+
+      r.is_integral = true;
+
+      if (left.is_integral || left.range == le_zero || left.range == lt_zero)
+         r.range = left.range;
+      else if (left.range == ge_zero || left.range == gt_zero)
+         r.range = ge_zero;
+      else if (left.range == ne_zero)
+         r.range = unknown;
+
+      break;
+   }
+
+   case nir_op_fceil: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+
+      r.is_integral = true;
+
+      if (left.is_integral || left.range == ge_zero || left.range == gt_zero)
+         r.range = left.range;
+      else if (left.range == le_zero || left.range == lt_zero)
+         r.range = le_zero;
+      else if (left.range == ne_zero)
+         r.range = unknown;
+
+      break;
+   }
+
+   case nir_op_ftrunc: {
+      const struct ssa_result_range left = analyze_expression(alu, 0, ht);
+
+      r.is_integral = true;
+
+      if (left.is_integral)
+         r.range = left.range;
+      else if (left.range == ge_zero || left.range == gt_zero)
+         r.range = ge_zero;
+      else if (left.range == le_zero || left.range == lt_zero)
+         r.range = le_zero;
+      else if (left.range == ne_zero)
+         r.range = unknown;
+
+      break;
+   }
+
+   case nir_op_flt:
+   case nir_op_fge:
+   case nir_op_feq:
+   case nir_op_fne:
+   case nir_op_ilt:
+   case nir_op_ige:
+   case nir_op_ieq:
+   case nir_op_ine:
+   case nir_op_ult:
+   case nir_op_uge:
+      /* Boolean results are 0 or -1. */
+      r = (struct ssa_result_range){le_zero, false};
+      break;
+
+   default:
+      r = (struct ssa_result_range){unknown, false};
+      break;
+   }
+
+   if (r.range == eq_zero)
+      r.is_integral = true;
+
+   _mesa_hash_table_insert(ht, alu, pack_data(r));
+   return r;
+}
+
+#undef _______
+
+struct ssa_result_range
+nir_analyze_range(const nir_alu_instr *instr, unsigned src)
+{
+   struct hash_table *ht = _mesa_pointer_hash_table_create(NULL);
+
+   const struct ssa_result_range r = analyze_expression(instr, src, ht);
+
+   _mesa_hash_table_destroy(ht, NULL);
+
+   return r;
+}
diff --git a/src/compiler/nir/nir_range_analysis.h b/src/compiler/nir/nir_range_analysis.h
new file mode 100644
index 00000000000..240ae74cf6c
--- /dev/null
+++ b/src/compiler/nir/nir_range_analysis.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright © 2018 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.
+ */
+#ifndef _NIR_RANGE_ANALYSIS_H_
+#define _NIR_RANGE_ANALYSIS_H_
+
+enum PACKED ssa_ranges {
+   unknown = 0,
+   lt_zero,
+   le_zero,
+   gt_zero,
+   ge_zero,
+   ne_zero,
+   eq_zero,
+   last_range = eq_zero
+};
+
+struct ssa_result_range {
+   enum ssa_ranges range;
+
+   /** A floating-point value that can only have integer values. */
+   bool is_integral;
+};
+
+extern struct ssa_result_range
+nir_analyze_range(const nir_alu_instr *instr, unsigned src);
+
+#endif /* _NIR_RANGE_ANALYSIS_H_ */
diff --git a/src/compiler/nir/nir_search_helpers.h b/src/compiler/nir/nir_search_helpers.h
index 7c19cd3fdfe..e2a436be6b7 100644
--- a/src/compiler/nir/nir_search_helpers.h
+++ b/src/compiler/nir/nir_search_helpers.h
@@ -29,6 +29,7 @@
 
 #include "nir.h"
 #include "util/bitscan.h"
+#include "nir_range_analysis.h"
 #include <math.h>
 
 static inline bool
@@ -324,4 +325,52 @@ no_unsigned_wrap(nir_alu_instr *instr)
    return instr->no_unsigned_wrap;
 }
 
+static inline bool
+is_integral(nir_alu_instr *instr, unsigned src,
+            UNUSED unsigned num_components, UNUSED const uint8_t *swizzle)
+{
+   const struct ssa_result_range r = nir_analyze_range(instr, src);
+
+   return r.is_integral;
+}
+
+#define RELATION(r)                                                     \
+static inline bool                                                      \
+is_ ## r (nir_alu_instr *instr, unsigned src,                           \
+          UNUSED unsigned num_components, UNUSED const uint8_t *swizzle) \
+{                                                                       \
+   const struct ssa_result_range v = nir_analyze_range(instr, src);     \
+   return v.range == r;                                                 \
+}
+
+RELATION(lt_zero)
+RELATION(le_zero)
+RELATION(gt_zero)
+RELATION(ge_zero)
+RELATION(ne_zero)
+
+static inline bool
+is_not_negative(nir_alu_instr *instr, unsigned src,
+                UNUSED unsigned num_components, UNUSED const uint8_t *swizzle)
+{
+   const struct ssa_result_range v = nir_analyze_range(instr, src);
+   return v.range == ge_zero || v.range == gt_zero || v.range == eq_zero;
+}
+
+static inline bool
+is_not_positive(nir_alu_instr *instr, unsigned src,
+                UNUSED unsigned num_components, UNUSED const uint8_t *swizzle)
+{
+   const struct ssa_result_range v = nir_analyze_range(instr, src);
+   return v.range == le_zero || v.range == lt_zero || v.range == eq_zero;
+}
+
+static inline bool
+is_not_zero(nir_alu_instr *instr, unsigned src,
+            UNUSED unsigned num_components, UNUSED const uint8_t *swizzle)
+{
+   const struct ssa_result_range v = nir_analyze_range(instr, src);
+   return v.range == lt_zero || v.range == gt_zero || v.range == ne_zero;
+}
+
 #endif /* _NIR_SEARCH_ */