[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