[PATCH 2/4] genopinit: Group optab patterns by condition

From: Kyrylo Tkachov <[email protected]>

insn-opinit.cc initializes one Boolean value for every optab pattern.
Many assignments use the same target condition.  The repeated assignments
make the generated file expensive to optimize and produce a large initializer
function.  A measured AArch64 file has 3,412 patterns but only 128 exact
conditions.  A measured RISC-V file has 14,984 patterns but only 963 exact
conditions.

Record an index for each exact condition string while genopinit reads the
machine description.  Emit one representative HAVE_* value per condition
and a compact pattern-to-condition map.  Initialize pat_enable with one
sequential loop.  Use unsigned char or unsigned short when their ISO C minimum
ranges hold all condition indices.  Otherwise use unsigned int, which holds
every GCC vec index on a supported host.

For example, these four AArch64 HAVE_* macros all expand to TARGET_SVE.
A shortened part of the old initializer is:

  ena[1021] = HAVE_while_ultsivnx16bi; /* TARGET_SVE */
  ena[1022] = HAVE_while_ultdivnx16bi; /* TARGET_SVE */
  ena[1023] = HAVE_while_ultsivnx8bi;  /* TARGET_SVE */
  ena[1024] = HAVE_while_ultdivnx8bi;  /* TARGET_SVE */

The new initializer contains four one-byte condition indices and one
representative TARGET_SVE expression:

  static const unsigned char pat_condition[NUM_OPTAB_PATTERNS] = {
    /* ... */ 9, 9, 9, 9, /* ... */
  };

  void
  init_all_optabs (struct target_optabs *optabs)
  {
    const bool condition_values[] = {
      /* ... */
      !!HAVE_movvnx32bi, /* TARGET_SVE, condition 9 */
      /* ... */
    };
    for (unsigned int i = 0; i < NUM_OPTAB_PATTERNS; ++i)
      optabs->pat_enable[i] = condition_values[pat_condition[i]];
  }

The initializer therefore contains one TARGET_SVE expression for these four
patterns instead of four copies.  The same reduction applies to every shared
condition.

The condition values remain local to init_all_optabs, so each call evaluates
them for the current target options.  Each pat_enable entry also remains
independent for swap_optab_enable.

On AArch64, direct compilation of insn-opinit.cc takes about 94% less wall
time and 64% less peak memory.  On x86_64, it takes about 34% less wall time
and 19% less peak memory.  The AArch64 initializer text is about 95% smaller.
The x86_64 initializer text is about 77% smaller.

Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* genopinit.cc (pattern_info): New.
	(patterns): Use pattern_info.
	(condition_map, condition_representatives): New.
	(gen_insn): Record the condition index for each pattern.
	(pattern_cmp): Use pattern_info.
	(main): Emit one value per condition, a compact condition map, and one
	initialization loop.

Suggested-by: Tamar Christina <[email protected]>
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/genopinit.cc | 98 +++++++++++++++++++++++++++---------------------
 1 file changed, 55 insertions(+), 43 deletions(-)

diff --git a/gcc/genopinit.cc b/gcc/genopinit.cc
index 62eaf5bd378..77aaa6a858e 100644
--- a/gcc/genopinit.cc
+++ b/gcc/genopinit.cc
@@ -35,22 +35,45 @@ static const char * const rtx_upname[] = {
 
 #undef DEF_RTL_EXPR
 
+struct pattern_info : optab_pattern
+{
+  unsigned int condition_index;
+};
+
 /* Vector in which to collect insns that match.  */
-static vec<optab_pattern> patterns;
+static vec<pattern_info> patterns;
+
+/* Maps each condition to its index in CONDITION_REPRESENTATIVES.  */
+static hash_map<nofree_string_hash, unsigned int> condition_map;
+
+/* One representative optab pattern name for each unique condition.  */
+static vec<const char *> condition_representatives;
 
 static void
 gen_insn (md_rtx_info *info)
 {
-  optab_pattern p;
+  pattern_info p;
   if (find_optab (&p, XSTR (info->def, 0)))
-    patterns.safe_push (p);
+    {
+      const char *condition = get_c_test (info->def);
+      bool existed;
+      unsigned int &condition_index
+	= condition_map.get_or_insert (condition, &existed);
+      if (!existed)
+	{
+	  condition_index = condition_representatives.length ();
+	  condition_representatives.safe_push (p.name);
+	}
+      p.condition_index = condition_index;
+      patterns.safe_push (p);
+    }
 }
 
 static int
 pattern_cmp (const void *va, const void *vb)
 {
-  const optab_pattern *a = (const optab_pattern *)va;
-  const optab_pattern *b = (const optab_pattern *)vb;
+  const pattern_info *a = (const pattern_info *)va;
+  const pattern_info *b = (const pattern_info *)vb;
   return a->sort_num - b->sort_num;
 }
 
@@ -178,7 +201,7 @@ main (int argc, const char **argv)
 {
   FILE *h_file, *s_file;
   unsigned int i, j, n, last_kind[5];
-  optab_pattern *p;
+  pattern_info *p;
 
   progname = "genopinit";
 
@@ -367,44 +390,33 @@ main (int argc, const char **argv)
     fprintf (s_file, "  { %#08x, CODE_FOR_%s },\n", p->sort_num, p->name);
   fprintf (s_file, "};\n\n");
 
-  /* Some targets like riscv have a large number of patterns.  In order to
-     prevent pathological situations in dataflow analysis split the init
-     function into separate ones that initialize 1000 patterns each.  */
-
-  const int patterns_per_function = 1000;
-
-  if (patterns.length () > patterns_per_function)
-    {
-      unsigned num_init_functions
-	= patterns.length () / patterns_per_function + 1;
-      for (i = 0; i < num_init_functions; i++)
-	{
-	  fprintf (s_file, "static void\ninit_optabs_%02d "
-		   "(struct target_optabs *optabs)\n{\n", i);
-	  fprintf (s_file, "  bool *ena = optabs->pat_enable;\n");
-	  unsigned start = i * patterns_per_function;
-	  unsigned end = MIN (patterns.length (),
-			      (i + 1) * patterns_per_function);
-	  for (j = start; j < end; ++j)
-	    fprintf (s_file, "  ena[%u] = HAVE_%s;\n", j, patterns[j].name);
-	  fprintf (s_file, "}\n\n");
-	}
-
-      fprintf (s_file, "void\ninit_all_optabs "
-	       "(struct target_optabs *optabs)\n{\n");
-      for (i = 0; i < num_init_functions; ++i)
-	fprintf (s_file, "  init_optabs_%02d (optabs);\n", i);
-      fprintf (s_file, "}\n\n");
-    }
+  /* Base the first two limits on the minimum ranges required by ISO C.  The
+     host that compiles the generated file can differ from the machine that
+     runs this generator.  GCC hosts have at least 32-bit int, while vec has
+     a 31-bit capacity, so unsigned int holds all remaining indices.  */
+  const char *condition_index_type;
+  if (condition_representatives.length () <= 256)
+    condition_index_type = "unsigned char";
+  else if (condition_representatives.length () <= 65536)
+    condition_index_type = "unsigned short";
   else
-    {
-      fprintf (s_file, "void\ninit_all_optabs "
-	       "(struct target_optabs *optabs)\n{\n");
-      fprintf (s_file, "  bool *ena = optabs->pat_enable;\n");
-      for (i = 0; patterns.iterate (i, &p); ++i)
-	fprintf (s_file, "  ena[%u] = HAVE_%s;\n", i, p->name);
-      fprintf (s_file, "}\n\n");
-    }
+    condition_index_type = "unsigned int";
+  fprintf (s_file, "static const %s "
+	   "pat_condition[NUM_OPTAB_PATTERNS] = {\n", condition_index_type);
+  for (i = 0; patterns.iterate (i, &p); ++i)
+    fprintf (s_file, "  %u,\n", p->condition_index);
+  fprintf (s_file, "};\n\n");
+
+  fprintf (s_file, "void\ninit_all_optabs "
+	   "(struct target_optabs *optabs)\n{\n"
+	   "  const bool condition_values[] = {\n");
+  for (i = 0; i < condition_representatives.length (); ++i)
+    fprintf (s_file, "    !!HAVE_%s,\n", condition_representatives[i]);
+  fprintf (s_file,
+	   "  };\n"
+	   "  for (unsigned int i = 0; i < NUM_OPTAB_PATTERNS; ++i)\n"
+	   "    optabs->pat_enable[i] = condition_values[pat_condition[i]];\n"
+	   "}\n\n");
 
   fprintf (s_file,
 	   "/* Returns TRUE if the target supports any of the partial vector\n"
-- 
2.50.1 (Apple Git-155)