nir/opt_bool: Emit instructions for a maximum of minterms

Direct implementation of maximum of minterms.  No attept is made at
factoring, generating XOR, or balancing the expression tree.

Signed-off-by: Ian Romanick <ian.d.romanick@intel.com>

3 files changed, 220 insertions, 0 deletions

diff --git a/src/compiler/nir/nir_opt_minimize_boolean.c b/src/compiler/nir/nir_opt_minimize_boolean.c
index 294575ec90f..01359552f83 100644
--- a/src/compiler/nir/nir_opt_minimize_boolean.c
+++ b/src/compiler/nir/nir_opt_minimize_boolean.c
@@ -28,6 +28,7 @@
 #include "nir_opt_minimize_boolean.h"
 #include "nir_builder.h"
 #include "util/bitset.h"
+#include "mesa/main/imports.h"
 
 #define MAX_VARS 8
 #define MAX_TERMS (1u << MAX_VARS)
@@ -815,6 +816,54 @@ nir_match_boolean_expression(const nir_alu_instr *instr,
    }
 }
 
+/**
+ * Generate instructions that implement the max-of-minterms logic expression
+ */
+nir_ssa_def *
+nir_emit_instructions_for_minterms(struct nir_builder *bld,
+                                   const struct minterm *terms,
+                                   unsigned num_terms,
+                                   const struct boolean_match_state *state)
+{
+   nir_ssa_def *sum_of_products = NULL;
+
+   for (unsigned i = 0; i < num_terms; i++) {
+      nir_ssa_def *minterm = NULL;
+
+      for (unsigned j = 0; j < state->num_variables; j++) {
+         if ((terms[i].mask & (1U << j)) != 0) {
+            if ((terms[i].term & (1U << j)) != 0) {
+               /* The term is expected to be true. */
+               if (minterm != NULL) {
+                  minterm = nir_iand(bld, minterm, state->variables[j].ssa);
+               } else {
+                  minterm = nir_imov(bld, state->variables[j].ssa);
+               }
+            } else {
+               /* The term is expected to be false. */
+               if (minterm != NULL) {
+                  minterm = nir_iand(bld,
+                                     minterm,
+                                     nir_inot(bld, state->variables[j].ssa));
+               } else {
+                  minterm = nir_inot(bld, state->variables[j].ssa);
+               }
+            }
+         }
+      }
+
+      if (minterm != NULL) {
+         if (sum_of_products != NULL) {
+            sum_of_products = nir_ior(bld, sum_of_products, minterm);
+         } else {
+            sum_of_products = minterm;
+         }
+      }
+   }
+
+   return sum_of_products;
+}
+
 static bool
 nir_opt_minimize_boolean_impl(nir_function_impl *impl,
                               bool tautology_or_contradiction_only)
diff --git a/src/compiler/nir/nir_opt_minimize_boolean.h b/src/compiler/nir/nir_opt_minimize_boolean.h
index 296a93e8be0..e6142f8dbff 100644
--- a/src/compiler/nir/nir_opt_minimize_boolean.h
+++ b/src/compiler/nir/nir_opt_minimize_boolean.h
@@ -68,6 +68,10 @@ bool nir_remove_unused_variables_from_minterms(struct minterm *terms,
 bool nir_match_boolean_expression(const nir_alu_instr *instr,
                                   struct boolean_match_state *state);
 
+nir_ssa_def *nir_emit_instructions_for_minterms(struct nir_builder *bld,
+                                                const struct minterm *terms,
+                                                unsigned num_terms,
+                                                const struct boolean_match_state *s);
 
 bool nir_opt_boolean_tautology_or_contradiction(nir_shader *shader);
 
diff --git a/src/compiler/nir/tests/opt_minimize_boolean_test.cpp b/src/compiler/nir/tests/opt_minimize_boolean_test.cpp
index 0f94ab63640..daa8bf739a6 100644
--- a/src/compiler/nir/tests/opt_minimize_boolean_test.cpp
+++ b/src/compiler/nir/tests/opt_minimize_boolean_test.cpp
@@ -1296,3 +1296,170 @@ ZERO_SRCS_BOOL_BINOP(ilt)
 ZERO_SRCS_BOOL_BINOP(ige)
 ZERO_SRCS_BOOL_BINOP(ult)
 ZERO_SRCS_BOOL_BINOP(uge)
+
+/*****************************************************************************/
+
+class emit_instructions_for_minterms_test : public ::testing::Test {
+protected:
+   emit_instructions_for_minterms_test()
+   {
+      static const nir_shader_compiler_options options = { };
+      nir_builder_init_simple_shader(&bld, NULL, MESA_SHADER_VERTEX, &options);
+
+      memset(&state, 0, sizeof(state));
+
+      one = nir_imm_float(&bld, 1.0f);
+      two = nir_imm_float(&bld, 2.0f);
+      three = nir_imm_float(&bld, 3.0f);
+      cmp1 = nir_feq(&bld, one, two);
+      cmp2 = nir_feq(&bld, one, two);
+   }
+
+   ~emit_instructions_for_minterms_test()
+   {
+      ralloc_free(bld.shader);
+   }
+
+   static int cmp_minterm(const void *_a, const void *_b)
+   {
+      const struct minterm *a = (const struct minterm *) _a;
+      const struct minterm *b = (const struct minterm *) _b;
+
+      return a->term == b->term ? a->mask - b->mask : a->term - b->term;
+   }
+
+   void canonicalize_result(struct minterm *m, unsigned num)
+   {
+      qsort(m, num, sizeof(struct minterm), cmp_minterm);
+   }
+
+   void do_test(const struct minterm *t, unsigned num_t)
+   {
+      nir_ssa_def *const result =
+         nir_emit_instructions_for_minterms(&bld, t, num_t, &state);
+
+      ASSERT_NE((void *)0, result);
+
+      const bool match =
+         nir_match_boolean_expression(nir_instr_as_alu(result->parent_instr),
+                                      &state);
+
+      ASSERT_TRUE(match);
+
+      const struct nir_src src = nir_src_for_ssa(result);
+      uint8_t terms[256];
+      const unsigned num_terms = nir_evaluate_truth_table(&src, &state, terms);
+
+      struct minterm final_minterms[256];
+
+      const unsigned count =
+         nir_quine_mccluskey(state.num_variables, num_terms, terms, final_minterms);
+
+      canonicalize_result(final_minterms, count);
+
+      EXPECT_EQ(num_t, count);
+
+      for (unsigned i = 0; i < count && i < num_t; i++) {
+         EXPECT_EQ(t[i].term, final_minterms[i].term);
+         EXPECT_EQ(t[i].mask, final_minterms[i].mask);
+      }
+   }
+
+   struct nir_builder bld;
+   struct boolean_match_state state;
+
+   nir_ssa_def *one;
+   nir_ssa_def *two;
+   nir_ssa_def *three;
+   nir_ssa_def *cmp1;
+   nir_ssa_def *cmp2;
+};
+
+/* There are no single variable tests.  Anything with a single variable is a
+ * tautology, a contradiction, or not a Boolean expression.
+ */
+
+TEST_F(emit_instructions_for_minterms_test, AB)
+{
+   static const struct minterm t[] = { { 3, 3 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, aB)
+{
+   static const struct minterm t[] = { { 2, 3 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, Ab)
+{
+   static const struct minterm t[] = { { 1, 3 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, ab)
+{
+   static const struct minterm t[] = { { 0, 3 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, A_B)
+{
+   static const struct minterm t[] = { { 1, 1 }, { 2, 2 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, Ab_aB)
+{
+   static const struct minterm t[] = { { 1, 3 }, { 2, 3 } };
+
+   state.num_variables = 2;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+
+   do_test(t, ARRAY_SIZE(t));
+}
+
+TEST_F(emit_instructions_for_minterms_test, aD_AB_ACd)
+{
+   /* This test catches certain kinds of problems when factoring out a common
+    * term.  This should be A(B+C) + bc, but you might get A(B+C+bc).
+    */
+   static const struct minterm t[] = { { 3, 3 }, { 5, 1+4+8 }, { 8, 9 } };
+
+   nir_ssa_def *cmp3 = nir_ine(&bld, one, three);
+   nir_ssa_def *cmp4 = nir_ine(&bld, two, three);
+
+   state.num_variables = 4;
+   state.variables[0] = nir_src_for_ssa(cmp1);
+   state.variables[1] = nir_src_for_ssa(cmp2);
+   state.variables[2] = nir_src_for_ssa(cmp3);
+   state.variables[3] = nir_src_for_ssa(cmp4);
+
+   do_test(t, ARRAY_SIZE(t));
+}