[PATCH 22/28] aarch64: Simplify decode tree generation

Alice Carlotti alice.carlotti@arm.com
Wed Nov 4 18:47:29 GMT 2026


Rewrite the decode tree generation in aarch64-gen.  It is no longer
necessary to store the computed tree for multiple users, so print the
generated decision tree on the fly.  There is no change to the generated
output.


diff --git a/opcodes/aarch64-gen.c b/opcodes/aarch64-gen.c
index 011e96006a91435823d4e2e63a9e3b77b6e3f59d..3c7db05d7932220c140650ee8b35bb54a03a7157 100644
--- a/opcodes/aarch64-gen.c
+++ b/opcodes/aarch64-gen.c
@@ -53,17 +53,6 @@ struct opcode_node
 
 typedef struct opcode_node opcode_node;
 
-/* Node in the decoding tree.  */
-
-struct bittree
-{
-  unsigned int bitno;
-  /* 0, 1, and X (don't care).  */
-  struct bittree *bits[2];
-  /* List of opcodes; only valid for the leaf node.  */
-  opcode_node *list;
-};
-
 /* Allocate and initialize an opcode_node.  */
 static opcode_node*
 new_opcode_node (void)
@@ -343,25 +332,10 @@ print_opcode_nodes (opcode_node *head)
     }
 }
 
-static struct bittree*
-new_bittree_node (void)
-{
-  struct bittree* node;
-  node = malloc (sizeof (struct bittree));
-  if (!node)
-    abort ();
-  node->bitno = -1;
-  node->bits[0] = NULL;
-  node->bits[1] = NULL;
-  return node;
-}
-
-/* The largest number of opcode entries that exist at a leaf node of the
-   decoding decision tree.  The reason that there can be more than one
-   opcode entry is because some opcodes have shared field that is partially
-   constrained and thus cannot be fully isolated using the algorithm
-   here.  */
-static int max_num_opcodes_at_leaf_node = 0;
+/* Record details of the longest chain of opcode entries starting from a leaf of the
+   decoding decision tree.  */
+static int longest_decode_chain_length = 0;
+static int longest_decode_chain_start_index;
 
 /* The mapping used for the switch statement in aarch64_find_next_opcode.  After
    failing to decode an instruction using the opcode at position INDEX in the
@@ -372,17 +346,27 @@ static int max_num_opcodes_at_leaf_node = 0;
    The map will be filled in incrementally by divide_table_1.  */
 static int *next_opcode_map;
 
-/* Given a list of opcodes headed by *OPCODE, try to establish one bit that
+static void __attribute__ ((format (printf, 2, 3)))
+indented_print (unsigned int indent, const char *format, ...)
+{
+  va_list ap;
+  va_start (ap, format);
+  printf ("%*s", (int) indent, "");
+  vprintf (format, ap);
+  va_end (ap);
+}
+
+/* Given a list of opcodes headed by *OPCODES, try to establish one bit that
    is shared by all the opcodes in the list as one of base opcode bits.  If
    such a bit is found, divide the list of the opcodes into two based on the
    value of the bit.
 
-   Store the bit number in BITTREE->BITNO if the division succeeds.  If unable
-   to determine such a bit or there is only one opcode in the list, the list
-   is decided to be undividable and OPCODE will be assigned to BITTREE->LIST.
-
    The function recursively call itself until OPCODE is undividable.
 
+   LIVE_MASK indicates which bits might be relevant for choosing between the
+   remaining opcodes.  Any unset bit in the mask is a position where all
+   remaining opcodes have the same bit value.
+
    N.B. the nature of this algrithm determines that given any value in the
    32-bit space, the computed decision tree will always be able to find one or
    more opcodes entries for it, regardless whether there is a valid instruction
@@ -394,219 +378,129 @@ static int *next_opcode_map;
    in which case call aarch64_opcode_decode to carry out further checks).  */
 
 static void
-divide_table_1 (struct bittree *bittree, opcode_node *opcode)
+print_decision_tree_1 (unsigned int indent,
+		       opcode_node *opcodes,
+		       aarch64_insn live_mask)
 {
-  aarch64_insn mask_and;
-  opcode_node *ent;
-  unsigned int bitno;
-  aarch64_insn bitmask;
-  opcode_node list0, list1, **ptr0, **ptr1;
-  static int depth = 0;
+  assert (opcodes != NULL);
 
-  ++depth;
-
-  if (debug)
-    printf ("Enter into depth %d\n", depth);
+  /* PATTERN is only used to generate comment in the code.  */
+  static char pattern[33] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
+  /* Low bits in PATTERN will be printed first which then look as the high
+     bits in comment.  We need to reverse the index to get correct print.  */
+  unsigned int msb = sizeof (pattern) - 2;
 
-  assert (opcode != NULL);
+  opcode_node *node;
 
-  /* Succeed when there is only one opcode left.  */
-  if (!opcode->next)
+  aarch64_insn mask_and = live_mask;
+  aarch64_insn opcode_or = 0;
+  aarch64_insn opcode_and = -1;
+  for (node = opcodes; node; node = node->next)
     {
-      if (debug)
-	{
-	  printf ("opcode isolated:\n");
-	  print_one_opcode_node (opcode);
-	}
-      goto divide_table_1_finish;
+      mask_and &= node->mask;
+      opcode_or |= node->opcode;
+      opcode_and &= node->opcode;
     }
 
- divide_table_1_try_again:
-  mask_and = -1;
-  ent = opcode;
-  while (ent)
+  /* Any bit values that are never one or never zero aren't discriminating.  */
+  mask_and &= (opcode_or & ~opcode_and);
+  if (!mask_and)
     {
-      mask_and &= ent->mask;
-      ent = ent->next;
-    }
+      /* No usable bits, so this will be a leaf.  */
+      indented_print (indent, "/* 33222222222211111111110000000000\n");
+      indented_print (indent, "   10987654321098765432109876543210\n");
+      indented_print (indent, "   %s.  */\n", pattern);
+      indented_print (indent, "return %s;\n",
+		      opcode_node_labels[opcodes->index]);
 
-  if (debug)
-    printf ("mask and result: %08x\n", (unsigned int)mask_and);
+      /* If there's more than one opcode remaining, chain them together in
+	 next_opcode_map.  */
+      unsigned int chain_length = 1;
+      for (node = opcodes; node->next; node = node->next)
+	next_opcode_map[node->index] = node->next->index;
+      free_opcode_list (opcodes);
 
-  /* If no more bit to look into, we have to accept the reality then.  */
-  if (!mask_and)
-    {
-      int i;
-      opcode_node *ptr;
-      if (debug)
+      if (chain_length > longest_decode_chain_length)
 	{
-	  ptr = opcode;
-	  printf ("Isolated opcode group:\n");
-	  do {
-	      print_one_opcode_node (ptr);
-	      ptr = ptr->next;
-	  } while (ptr);
+	  longest_decode_chain_length = chain_length;
+	  longest_decode_chain_start_index = opcodes->index;
 	}
-      /* Count the number of opcodes.  */
-      for (i = 0, ptr = opcode; ptr; ++i)
-	ptr = ptr->next;
-      if (i > max_num_opcodes_at_leaf_node)
-	max_num_opcodes_at_leaf_node = i;
-      goto divide_table_1_finish;
+      return;
     }
 
-  /* Pick up the right most bit that is 1.  */
-  bitno = 0;
+  /* We've found some usable bits.  Pick the least significant one.  */
+  unsigned int bitno = 0;
   while (!(mask_and & (1 << bitno)))
     ++bitno;
-  bitmask = (1 << bitno);
 
-  if (debug)
-    printf ("use bit %d\n", bitno);
-
-  /* Record in the bittree.  */
-  bittree->bitno = bitno;
-
-  /* Get two new opcode lists; adjust their masks.  */
-  list0.next = NULL;
-  list1.next = NULL;
-  ptr0 = &list0.next;
-  ptr1 = &list1.next;
-  ent = opcode;
-  while (ent)
+  aarch64_insn bitmask = (1 << bitno);
+  live_mask &= ~bitmask;
+
+  /* Split the list in two, according to the value of the chosen bit.  */
+  opcode_node *list0;
+  opcode_node *list1;
+  opcode_node **tail0 = &list0;
+  opcode_node **tail1 = &list1;
+
+  for (node = opcodes; node; node = node->next)
     {
-      if (ent->opcode & bitmask)
+      if ((node->opcode & bitmask) == 0)
 	{
-	  ent->mask &= (~bitmask);
-	  *ptr1 = ent;
-	  ent = ent->next;
-	  (*ptr1)->next = NULL;
-	  ptr1 = &(*ptr1)->next;
+	  *tail0 = node;
+	  tail0 = &node->next;
 	}
       else
 	{
-	  ent->mask &= (~bitmask);
-	  *ptr0 = ent;
-	  ent = ent->next;
-	  (*ptr0)->next = NULL;
-	  ptr0 = &(*ptr0)->next;
+	  *tail1 = node;
+	  tail1 = &node->next;
 	}
     }
+  *tail0 = NULL;
+  *tail1 = NULL;
 
-  /* If BITNO can NOT divide the opcode group, try next bit.  */
-  if (list0.next == NULL)
-    {
-      opcode = list1.next;
-      goto divide_table_1_try_again;
-    }
-  else if (list1.next == NULL)
-    {
-      opcode = list0.next;
-      goto divide_table_1_try_again;
-    }
-
-  /* Further divide.  */
-  bittree->bits[0] = new_bittree_node ();
-  bittree->bits[1] = new_bittree_node ();
-  divide_table_1 (bittree->bits[0], list0.next);
-  divide_table_1 (bittree->bits[1], list1.next);
-
- divide_table_1_finish:
   if (debug)
-    printf ("Leave from depth %d\n", depth);
-  --depth;
-
-  if (!bittree->bits[0])
-    {
-      /* Record the opcode entries on this leaf node.  */
-      bittree->list = opcode;
-      for (opcode_node *node = opcode; node->next; node = node->next)
-	next_opcode_map[node->index] = node->next->index;
-    }
-
-  return;
-}
-
-/* Call divide_table_1 to divide the all the opcodes and thus create the
-   decoding decision tree.  */
-static struct bittree *
-divide_table (opcode_node *head)
-{
-  /* Allocate and initialise next_opcode_map.  */
-  unsigned count = sizeof (aarch64_opcode_table) / sizeof (aarch64_opcode);
-  next_opcode_map = malloc (count * sizeof (int));
-  for (int i = 0; i < count; i++)
-    next_opcode_map[i] = -1;
-
-  struct bittree *bittree = new_bittree_node ();
-  divide_table_1 (bittree, head);
-  return bittree;
-}
-
-static void __attribute__ ((format (printf, 2, 3)))
-indented_print (unsigned int indent, const char *format, ...)
-{
-  va_list ap;
-  va_start (ap, format);
-  printf ("%*s", (int) indent, "");
-  vprintf (format, ap);
-  va_end (ap);
-}
-
-/* N.B. read the comment above divide_table_1 for the reason why the generated
-   decision tree function never returns NULL.  */
-
-static void
-print_decision_tree_1 (unsigned int indent, struct bittree* bittree)
-{
-  /* PATTERN is only used to generate comment in the code.  */
-  static char pattern[33] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
-  /* Low bits in PATTERN will be printed first which then look as the high
-     bits in comment.  We need to reverse the index to get correct print.  */
-  unsigned int msb = sizeof (pattern) - 2;
-  assert (bittree != NULL);
-
-  /* Leaf node located.  */
-  if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
     {
-      assert (bittree->list != NULL);
-      indented_print (indent, "/* 33222222222211111111110000000000\n");
-      indented_print (indent, "   10987654321098765432109876543210\n");
-      indented_print (indent, "   %s.  */\n", pattern);
-      indented_print (indent, "return %s;\n",
-		      opcode_node_labels[bittree->list->index]);
-      return;
+      printf ("List 0\n");
+      print_opcode_nodes (list0);
+      printf ("List 1\n");
+      print_opcode_nodes (list1);
     }
 
-  /* Walk down the decoder tree.  */
-  indented_print (indent, "if (((word >> %d) & 0x1) == 0)\n", bittree->bitno);
+  /* Walk down the decoder tree, and recurse.  */
+  indented_print (indent, "if (((word >> %d) & 0x1) == 0)\n", bitno);
   indented_print (indent, "  {\n");
-  pattern[msb - bittree->bitno] = '0';
-  print_decision_tree_1 (indent + 4, bittree->bits[0]);
+  pattern[msb - bitno] = '0';
+  print_decision_tree_1 (indent + 4, list0, live_mask);
   indented_print (indent, "  }\n");
   indented_print (indent, "else\n");
   indented_print (indent, "  {\n");
-  pattern[msb - bittree->bitno] = '1';
-  print_decision_tree_1 (indent + 4, bittree->bits[1]);
+  pattern[msb - bitno] = '1';
+  print_decision_tree_1 (indent + 4, list1, live_mask);
   indented_print (indent, "  }\n");
-  pattern[msb - bittree->bitno] = 'x';
+  pattern[msb - bitno] = 'x';
 }
 
 /* Generate aarch64_opcode_lookup in C code to the standard output.  */
 
 static void
-print_decision_tree (struct bittree* bittree)
+print_decision_tree (opcode_node *opcodes)
 {
   if (debug)
     printf ("Enter print_decision_tree\n");
 
+  /* Allocate and initialise next_opcode_map.  */
+  unsigned count = sizeof (aarch64_opcode_table) / sizeof (aarch64_opcode);
+  next_opcode_map = malloc (count * sizeof (int));
+  for (int i = 0; i < count; i++)
+    next_opcode_map[i] = -1;
+
   printf ("/* Called by aarch64_opcode_lookup.  */\n\n");
 
   printf ("static enum aarch64_opcode_idx\n");
   printf ("aarch64_opcode_lookup_1 (uint32_t word)\n");
   printf ("{\n");
 
-  print_decision_tree_1 (2, bittree);
+  print_decision_tree_1 (2, opcodes, -1);
 
   printf ("}\n\n");
 
@@ -619,12 +513,17 @@ print_decision_tree (struct bittree* bittree)
   printf ("{\n");
   printf ("  return aarch64_opcode_table + aarch64_opcode_lookup_1 (word);\n");
   printf ("}\n");
+
+  if (debug)
+    printf ("Longest decode chain is length %d, starting from %s\n",
+	    longest_decode_chain_length,
+	    opcode_node_labels[longest_decode_chain_start_index]);
 }
 
 /* Generate aarch64_find_next_opcode in C code to the standard output.  */
 
 static void
-print_find_next_opcode (struct bittree* bittree)
+print_find_next_opcode ()
 {
   if (debug)
     printf ("Enter print_find_next_opcode\n");
@@ -657,39 +556,6 @@ print_find_next_opcode (struct bittree* bittree)
   printf ("}\n");
 }
 
-/* Release the dynamic memory resource allocated for the generation of the
-   decoder tree.  */
-
-static void
-release_resource_decoder_tree (struct bittree* bittree)
-{
-  assert (bittree != NULL);
-
-  /* Leaf node located.  */
-  if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
-    {
-      assert (bittree->list != NULL);
-      /* Free opcode_nodes.  */
-      opcode_node *list = bittree->list;
-      while (list != NULL)
-	{
-	  opcode_node *next = list->next;
-	  free (list);
-	  list = next;
-	}
-      /* Free the tree node.  */
-      free (bittree);
-      return;
-    }
-
-  /* Walk down the decoder tree.  */
-  release_resource_decoder_tree (bittree->bits[0]);
-  release_resource_decoder_tree (bittree->bits[1]);
-
-  /* Free the tree node.  */
-  free (bittree);
-}
-
 /* Generate aarch64_find_real_opcode in C code to the standard output.
    TABLE points to the alias info table, while NUM indicates the number of
    entries in the table.  */
@@ -775,15 +641,6 @@ print_find_next_alias_opcode (opcode_node *has_alias_list,
   printf ("  return aarch64_opcode_table + value;\n");
   printf ("}\n");
 }
-
-/* As a debugging utility, print out the result of the table division, although
-   it is not doing much this moment.  */
-static void
-print_divide_result (const struct bittree *bittree ATTRIBUTE_UNUSED)
-{
-  printf ("max_num_opcodes_at_leaf_node: %d\n", max_num_opcodes_at_leaf_node);
-  return;
-}
 
 /* Structure to help generate the operand table.  */
 struct operand
@@ -1323,13 +1180,9 @@ main (int argc, char **argv)
 	  print_opcode_nodes (tree_opcodes);
 	  print_opcode_nodes (alias_opcodes);
 	}
-      struct bittree *decoder_tree = divide_table (tree_opcodes);
-      if (debug)
-	print_divide_result (decoder_tree);
 
-      print_decision_tree (decoder_tree);
-      release_resource_decoder_tree (decoder_tree);
-      print_find_next_opcode (decoder_tree);
+      print_decision_tree (tree_opcodes);
+      print_find_next_opcode ();
       free (next_opcode_map);
 
       /* print_find_next_alias_opcode modifies the indices in has_alias_list


More information about the Binutils mailing list