[PATCH 4/4] x86: move operand_types[] out of struct insn_template

Most insns have fewer than 5 operands, so the extra slots are wasted
there. Many insns also have identical operand combinations, so there is a
lot of redundancy as well. Introduce a separate array holding all the
operand combinations, but before adding new sets check whether the same
set was seen before. Put the index into the new array into the struct
insn_template instances.

At the time of writing we're going down from 22,880 i386_operand_type
instances (of which 10,006 are actually used) to just 770.
---
Note: When merging operands directly while parsing, their amount went down
      to only 934.

With the re-use of i386-mnem.h here we may want to rename it (to e.g.
i386-defs.h).

Subsequently we could consider to fold mnem_off and operand_ref into a
single 32-bit field, as for both 16 bits (for the latter even fewer) are
going to be sufficient for quite some time.

Subsequently we could do the same to the CPU specifiers, perhaps to also
do away again with the distinction between i386_cpu_flags and
i386_cpu_attr (accepting the somewhat bigger data size, but which then
wouldn't grow with every addition of a new template). Doing so may then
also pave the road towards more complex combinations of CPU specifiers
(we're already in trouble expressing some, and ACE looks to be making the
situation worse).

--- a/gas/config/tc-i386.c
+++ b/gas/config/tc-i386.c
@@ -1376,6 +1376,8 @@ static htab_t op_hash;
 /* Hash table for register lookup.  */
 static htab_t reg_hash;
 
+#include "opcodes/i386-tbl.h"
+
 #if (defined (OBJ_ELF) || defined (OBJ_MACH_O) || defined (TE_PE))
 static const struct
 {
@@ -2551,7 +2553,7 @@ operand_type_check (i386_operand_type t,
 static INLINE const i386_operand_type *
 get_operand_types (const insn_template *t)
 {
-  return t->operand_types;
+  return &i386_operand_types[t->operand_ref];
 }
 
 /* Return 1 if there is no conflict in 8bit/16bit/32bit/64bit size
@@ -3647,8 +3649,6 @@ i386_mach (void)
     as_fatal (_("unknown architecture"));
 }
 
-#include "opcodes/i386-tbl.h"
-
 static void
 op_lookup (const char *mnemonic)
 {
--- a/opcodes/i386-gen.c
+++ b/opcodes/i386-gen.c
@@ -621,6 +621,17 @@ static bitfield operand_types[] =
 #endif
 };
 
+/* Class and instance are small non-negative numbers, while the other fields
+   have boolean type.  Use the smallest available type for latching the values
+   out of struct bitfield.  */
+typedef unsigned char opval_t;
+
+/* Number of opval_t in a single operand representation.  */
+#define OPVAL_COUNT (2 + ARRAY_SIZE (operand_types))
+
+static const opval_t **operands[MAX_OPERANDS + 1];
+static unsigned int nr_operands[MAX_OPERANDS + 1];
+
 static const char *filename;
 static i386_cpu_flags active_cpu_flags;
 static int active_isstring;
@@ -1386,7 +1397,7 @@ output_operand_type (FILE *table, enum o
   fprintf (table, "%d } }", types[i].value);
 }
 
-static void
+static const opval_t *
 process_i386_operand_type (FILE *table, char *op, enum stage stage,
 			   const char *indent, int lineno)
 {
@@ -1449,8 +1460,35 @@ process_i386_operand_type (FILE *table,
 	  set_bitfield("Disp32", types, 1, ARRAY_SIZE (types), lineno);
 	}
     }
+
+  if (!table)
+    {
+      opval_t *op = XNEWVEC (opval_t, OPVAL_COUNT);
+
+      op[0] = class;
+      op[1] = instance;
+
+      /* Check for no truncation.  */
+      if (op[0] != class || op[1] != instance)
+	fail ("%s: %d: class (%u) or instance (%u) out of range\n",
+	      filename, lineno);
+
+      for (unsigned int i = 0; i < ARRAY_SIZE (types); ++i)
+	{
+	  op[i + 2] = types[i].value;
+
+	  /* Check for no truncation.  */
+	  if (op[i + 2] != types[i].value)
+	    fail ("%s: %d: `%s' value out of range: %d\n",
+		  filename, lineno, types[i].name, types[i].value);
+	}
+
+      return op;
+    }
+
   output_operand_type (table, class, instance, types, ARRAY_SIZE (types),
 		       stage, indent);
+  return NULL;
 }
 
 static char *mkident (const char *mnem)
@@ -1467,13 +1505,53 @@ static char *mkident (const char *mnem)
   return ident;
 }
 
+static unsigned int
+get_opref (const opval_t *op[], unsigned int nr, bool parse)
+{
+  static unsigned int slots_operands[MAX_OPERANDS + 1];
+  unsigned int i, lst, step;
+
+  /* While parsing templates, insert into the respective list.  In this phase
+     also only consider whole groups of operands for merging.
+
+     On the final merging pass everything goes onto the MAX_OPERANDS list.  */
+  if (parse)
+    lst = step = nr;
+  else
+    lst = MAX_OPERANDS, step = 1;
+
+  /* Brute force lookup for now.  */
+  for (unsigned int ref = 0; ref + nr <= nr_operands[lst]; ref += step)
+    {
+      for (i = 0; i < nr; ++i)
+	if (memcmp (operands[lst][ref + i], op[i], OPVAL_COUNT))
+	  break;
+      if (i == nr)
+	{
+	  while (i--)
+	    free ((void *)op[i]);
+	  return ref;
+	}
+    }
+
+  if (nr_operands[lst] + nr > slots_operands[lst])
+    operands[lst] = XRESIZEVEC (const opval_t *, operands[lst],
+				slots_operands[lst] += 16 * nr);
+
+  for (i = 0; i < nr; ++i)
+    operands[lst][nr_operands[lst]++] = op[i];
+
+  return nr_operands[lst] - nr;
+}
+
 static void
 output_i386_opcode (FILE *table, const char *name, char *str,
 		    char *last, int lineno)
 {
-  unsigned int i, length, prefix = 0, space = 0;
+  unsigned int i, length, prefix = 0, space = 0, ref;
   char *base_opcode, *extension_opcode, *end, *ident;
   char *cpu_flags, *opcode_modifier, *operand_types [MAX_OPERANDS];
+  const opval_t *op [MAX_OPERANDS];
   unsigned long long opcode;
 
   /* Find base_opcode.  */
@@ -1578,25 +1656,29 @@ output_i386_opcode (FILE *table, const c
 
   process_i386_cpu_flag (table, cpu_flags, NULL, ",", "    ", lineno, CpuMax);
 
-  fprintf (table, "    { ");
-
   for (i = 0; i < ARRAY_SIZE (operand_types); i++)
     {
       if (!operand_types[i])
-	{
-	  if (i == 0)
-	    process_i386_operand_type (table, "0", stage_opcodes, "\t  ",
-				       lineno);
-	  break;
-	}
+	break;
 
-      if (i != 0)
-	fprintf (table, ",\n      ");
+      op[i] = process_i386_operand_type (NULL, operand_types[i], stage_opcodes,
+					 NULL, lineno);
+    }
 
-      process_i386_operand_type (table, operand_types[i], stage_opcodes,
-				 "\t  ", lineno);
+  if (i == 0)
+    {
+      fprintf (table, "    0 },\n");
+      return;
     }
-  fprintf (table, " } },\n");
+
+  ref = get_opref (op, i, true);
+  /* The MAX_OPERANDS list won't further be altered, so the reference can be
+     recorded directly.  All other lists will be merged into the main list
+     later, and the reference to store will be known only then.  */
+  if (i == MAX_OPERANDS)
+    fprintf (table, "    %u },\n", ref);
+  else
+    fprintf (table, "    OPREF_%u_%u },\n", i, ref);
 }
 
 struct opcode_hash_entry
@@ -2118,10 +2200,41 @@ process_i386_opcodes (FILE *table)
     }
 
   fprintf (table, "  \"\\0\"\".insn\"\n");
-  fprintf (fp, "#define MN__insn %#x\n", offs + 1);
+  fprintf (fp, "#define MN__insn %#x\n\n", offs + 1);
 
   fprintf (table, ";\n");
 
+  for (i = MAX_OPERANDS - 1; i > 0; --i)
+    {
+      for (j = 0, nr = nr_operands[i]; j < nr; j += i)
+	{
+	  unsigned int ref = get_opref (&operands[i][j], i, false);
+
+	  fprintf (fp, "#define OPREF_%u_%u %u\n", i, j, ref);
+	}
+    }
+
+  fprintf (table, "\n/* i386 operand types table.  */\n\n");
+  fprintf (table, "static const i386_operand_type i386_operand_types[] =\n{\n");
+
+  for (i = 0; i < nr_operands[MAX_OPERANDS]; ++i)
+    {
+      const opval_t *op = operands[MAX_OPERANDS][i];
+      bitfield types[ARRAY_SIZE (operand_types)] = { [0] = { .name = NULL } };
+
+      fprintf (table, "  ");
+
+      for (j = 0; j < ARRAY_SIZE (types); ++j)
+	types[j].value = op[j + 2];
+
+      output_operand_type (table, op[0], op[1], types, ARRAY_SIZE (types),
+			   stage_opcodes, "      ");
+
+      fprintf (table, ",\n");
+    }
+
+  fprintf (table, "};\n");
+
   fclose (fp);
 }
 
--- a/opcodes/i386-opc.h
+++ b/opcodes/i386-opc.h
@@ -1104,11 +1104,11 @@ typedef struct insn_template
   /* cpu feature attributes */
   i386_cpu_attr cpu, cpu_any;
 
-  /* operand_types[i] describes the type of operand i.  This is made
-     by OR'ing together all of the possible type masks.  (e.g.
+  /* i386_operand_types[operand_ref + i] describes the type of operand i.
+     This is made by OR'ing together all of the possible type masks.  (e.g.
      'operand_types[i] = Reg|Imm' specifies that operand i can be
      either a register or an immediate operand.  */
-  i386_operand_type operand_types[MAX_OPERANDS];
+  unsigned int operand_ref;
 }
 insn_template;