[PATCH 23/28] aarch64: Support partial splits in the decode tree
Alice Carlotti
alice.carlotti@arm.com
Wed Nov 4 18:47:47 GMT 2026
When it isn't possible to split an entire group of opcodes with a
single bit, we might still be able to split part of the list before
chaining both halves into the remaining unsplit tail.
For example, hint instructions could be handled by setting aside the
parent 'hint #<imm>' opcode and using the decode tree to find the
closest matching hint, with each hint opcode mapping directly to the
'hint #<imm>' opcode in aarch64_find_next_opcode. This could turn a
linear scan into a binary search of this encoding space. The binary
search doesn't apply to aliases at the moment, but a future change will
enable this.
Partial splits are temporarily disabled in this patch, to verify that
the generated code remains otherwise unchanged.
diff --git a/opcodes/aarch64-gen.c b/opcodes/aarch64-gen.c
index 3c7db05d7932220c140650ee8b35bb54a03a7157..9b80628b2ff19623fb97b17f24d7c9befdf34a90 100644
--- a/opcodes/aarch64-gen.c
+++ b/opcodes/aarch64-gen.c
@@ -380,7 +380,8 @@ indented_print (unsigned int indent, const char *format, ...)
static void
print_decision_tree_1 (unsigned int indent,
opcode_node *opcodes,
- aarch64_insn live_mask)
+ aarch64_insn live_mask,
+ unsigned int chain_length)
{
assert (opcodes != NULL);
@@ -397,34 +398,73 @@ print_decision_tree_1 (unsigned int indent,
aarch64_insn opcode_and = -1;
for (node = opcodes; node; node = node->next)
{
+ if (!(mask_and & node->mask))
+ break;
mask_and &= node->mask;
opcode_or |= node->opcode;
opcode_and &= node->opcode;
}
- /* Any bit values that are never one or never zero aren't discriminating. */
- mask_and &= (opcode_or & ~opcode_and);
- if (!mask_and)
+ opcode_node *blocked_node = node;
+
+ if (blocked_node)
{
- /* 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 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)
+ /* Temporarily force blocked_node to the first opcode, to match the
+ existing generated code. */
+ blocked_node = opcodes;
+
+ /* No usable bits can fully split the remaining opcodes. If there are
+ any more opcodes after node, chain them together now. */
+ chain_length++;
+ for (node = blocked_node; node->next; node = node->next, chain_length++)
next_opcode_map[node->index] = node->next->index;
- free_opcode_list (opcodes);
- if (chain_length > longest_decode_chain_length)
+ if (blocked_node == opcodes)
+ {
+ /* No usable bits can eliminate the first opcode value, 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]);
+ free_opcode_list (opcodes);
+ if (chain_length > longest_decode_chain_length)
+ {
+ longest_decode_chain_length = chain_length;
+ longest_decode_chain_start_index = opcodes->index;
+ }
+ return;
+ }
+
+ /* We can still do a partial split. Any earlier nodes will need to chain
+ to blocked_node. Link them directly for now, but this may be
+ overridden at a deeper recursion level. */
+ for (node = opcodes; ; node = node->next)
{
- longest_decode_chain_length = chain_length;
- longest_decode_chain_start_index = opcodes->index;
+ next_opcode_map[node->index] = blocked_node->index;
+ if (node->next == blocked_node)
+ {
+ /* Truncate the remaining opcodes list here. */
+ node->next = NULL;
+ free_opcode_list (blocked_node);
+ break;
+ }
}
+ }
+
+ /* Any bits that are always one or zero in the remaining opcodes aren't
+ usable. */
+ live_mask &= ~(mask_and & (opcode_and | ~opcode_or));
+
+ /* Check whether any of the masked bits split the remaining opcodes into
+ two nonempty lists. */
+ mask_and &= (opcode_or & ~opcode_and);
+ if (!mask_and)
+ {
+ /* None of our selected bits work, so recurse to look for an earlier
+ blocking node (with these bits removed from live_mask). */
+ print_decision_tree_1 (indent, opcodes, live_mask, chain_length);
return;
}
@@ -470,12 +510,12 @@ print_decision_tree_1 (unsigned int indent,
indented_print (indent, "if (((word >> %d) & 0x1) == 0)\n", bitno);
indented_print (indent, " {\n");
pattern[msb - bitno] = '0';
- print_decision_tree_1 (indent + 4, list0, live_mask);
+ print_decision_tree_1 (indent + 4, list0, live_mask, chain_length);
indented_print (indent, " }\n");
indented_print (indent, "else\n");
indented_print (indent, " {\n");
pattern[msb - bitno] = '1';
- print_decision_tree_1 (indent + 4, list1, live_mask);
+ print_decision_tree_1 (indent + 4, list1, live_mask, chain_length);
indented_print (indent, " }\n");
pattern[msb - bitno] = 'x';
}
@@ -500,7 +540,7 @@ print_decision_tree (opcode_node *opcodes)
printf ("aarch64_opcode_lookup_1 (uint32_t word)\n");
printf ("{\n");
- print_decision_tree_1 (2, opcodes, -1);
+ print_decision_tree_1 (2, opcodes, -1, 0);
printf ("}\n\n");
More information about the Binutils
mailing list