[PATCH 1/3] RISC-V: Use faster hash table on disassembling

[Tsukasa OI <research_trasio@irq.a4lg.com>]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

This commit improves performance on disassembling RISC-V code.
It replaces riscv_hash (in opcodes/riscv-dis.c) with much faster data
structure: a sorted and partitioned hash table.

This is a technique actually used on SPARC architecture
(opcodes/sparc-dis.c) and the author simplified the algorithm even further.
Unlike SPARC, RISC-V's hashed opcode table is not a table to linked lists,
it's just a table, pointing "start" elements in the sorted opcode list
(per hash code) and a global tail.

It is expected to have 20-40% performance improvements when disassembling
linked RISC-V ELF programs using objdump.  That is a significant improvement
and pretty nice for such a small modification
(with about 12KB heap memory allocation on 64-bit environment).

This is not the end.  This structure significantly improves plain binary
file handling (on objdump, "objdump -b binary -m riscv:rv[32|64] -D $FILE").

The author tested on various binary files including random one and big
vmlinux images and confirmed significant performance improvements (>70%
on many cases).  This is partially due to the fact that, disassembling about
one quarter of invalid "instruction" words required iterating over one
thousand opcode entries (348 or more being vector instructions with OP-V,
that can be easily skipped with this new data structure).  Another reason
for this significance is it doesn't have various ELF overhead.

opcodes/ChangeLog:

	* riscv-dis.c (init_riscv_dis_state_for_arch_and_options): Build
	the hash table on the first run.
	(OP_HASH_LEN): Move from riscv_disassemble_insn.
	(OP_HASH_IDX): Move from riscv_disassemble_insn and mask by
	OP_MASK_OP2 == 0x03 for only real 16-bit instructions.
	(riscv_hash): New sorted and partitioned hash table.
	(riscv_opcodes_sorted): New sorted opcode table.
	(compare_opcodes): New function to compare RISC-V opcode entries.
	(build_riscv_opcodes_hash_table): New function to build faster
	hash table to disassemble.
	(riscv_disassemble_insn): Use sorted and partitioned hash table.
---
 opcodes/riscv-dis.c | 93 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 76 insertions(+), 17 deletions(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index 328a34501549..a4a74e5733a5 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -162,6 +162,8 @@ set_riscv_dis_arch_context (riscv_dis_arch_context_t *context,
 }
 \f
 
+static void build_riscv_opcodes_hash_table (void);
+
 /* Guess and update current XLEN.  */
 
 static void
@@ -205,6 +207,12 @@ init_riscv_dis_state_for_arch (void)
 static void
 init_riscv_dis_state_for_arch_and_options (void)
 {
+  static bool init = false;
+  if (!init)
+    {
+      build_riscv_opcodes_hash_table ();
+      init = true;
+    }
   /* If the architecture string is changed, update XLEN.  */
   if (is_arch_changed)
     update_riscv_dis_xlen (NULL);
@@ -818,6 +826,69 @@ print_insn_args (const char *oparg, insn_t l, bfd_vma pc, disassemble_info *info
     }
 }
 
+/* Build a hash table for the disassembler to shorten the search time.
+   We sort riscv_opcodes entry pointers for further performance.
+   Hash index is computed by masking the instruction with...
+   - 0x03 (OP_MASK_OP2) for real 16-bit instructions
+   - 0x7f (OP_MASK_OP)  for all other instructions.  */
+
+#define OP_HASH_LEN (OP_MASK_OP + 1)
+#define OP_HASH_IDX(i)                                                        \
+  ((i) & (((i & OP_MASK_OP2) != OP_MASK_OP2) ? OP_MASK_OP2 : OP_MASK_OP))
+static const struct riscv_opcode **riscv_hash[OP_HASH_LEN + 1];
+static const struct riscv_opcode **riscv_opcodes_sorted;
+
+/* Compare two riscv_opcode* objects to sort by hash index.  */
+
+static int
+compare_opcodes (const void *ap, const void *bp)
+{
+  const struct riscv_opcode *a = *(const struct riscv_opcode **) ap;
+  const struct riscv_opcode *b = *(const struct riscv_opcode **) bp;
+  int ai = (int) OP_HASH_IDX (a->match);
+  int bi = (int) OP_HASH_IDX (b->match);
+  if (ai != bi)
+    return ai - bi;
+  /* Stable sort (on riscv_opcodes entry order) is required.  */
+  if (a < b)
+    return -1;
+  if (a > b)
+    return +1;
+  return 0;
+}
+
+/* Build riscv_opcodes-based hash table.  */
+
+static void
+build_riscv_opcodes_hash_table (void)
+{
+  const struct riscv_opcode *op;
+  const struct riscv_opcode **pop, **pop_end;
+  size_t len = 0;
+
+  /* Sort riscv_opcodes entry pointers (except macros).  */
+  for (op = riscv_opcodes; op->name; op++)
+    if (op->pinfo != INSN_MACRO)
+      len++;
+  riscv_opcodes_sorted = xcalloc (len, sizeof (struct riscv_opcode *));
+  pop_end = riscv_opcodes_sorted;
+  for (op = riscv_opcodes; op->name; op++)
+    if (op->pinfo != INSN_MACRO)
+      *pop_end++ = op;
+  qsort (riscv_opcodes_sorted, len, sizeof (struct riscv_opcode *),
+	 compare_opcodes);
+
+  /* Initialize faster hash table.  */
+  pop = riscv_opcodes_sorted;
+  for (unsigned i = 0; i < OP_HASH_LEN; i++)
+    {
+      riscv_hash[i] = pop;
+      while (pop != pop_end && OP_HASH_IDX ((*pop)->match) == i)
+	pop++;
+    }
+  riscv_hash[OP_HASH_LEN] = pop_end;
+}
+
 /* Print the RISC-V instruction at address MEMADDR in debugged memory,
    on using INFO.  Returns length of the instruction, in bytes.
    BIGENDIAN must be 1 if this is big-endian code, 0 if
@@ -826,24 +897,11 @@ print_insn_args (const char *oparg, insn_t l, bfd_vma pc, disassemble_info *info
 static int
 riscv_disassemble_insn (bfd_vma memaddr, insn_t word, disassemble_info *info)
 {
+  const struct riscv_opcode **pop, **pop_end;
   const struct riscv_opcode *op, *matched_op;
-  static bool init = false;
-  static const struct riscv_opcode *riscv_hash[OP_MASK_OP + 1];
   struct riscv_private_data *pd = info->private_data;
   int insnlen;
 
-#define OP_HASH_IDX(i) ((i) & (riscv_insn_length (i) == 2 ? 0x3 : OP_MASK_OP))
-
-  /* Build a hash table to shorten the search time.  */
-  if (! init)
-    {
-      for (op = riscv_opcodes; op->name; op++)
-	if (!riscv_hash[OP_HASH_IDX (op->match)])
-	  riscv_hash[OP_HASH_IDX (op->match)] = op;
-
-      init = true;
-    }
-
   insnlen = riscv_insn_length (word);
 
   /* RISC-V instructions are always little-endian.  */
@@ -861,10 +919,11 @@ riscv_disassemble_insn (bfd_vma memaddr, insn_t word, disassemble_info *info)
   info->target2 = 0;
 
   matched_op = NULL;
-  op = riscv_hash[OP_HASH_IDX (word)];
-
-  for (; op && op->name; op++)
+  pop     = riscv_hash[OP_HASH_IDX (word)];
+  pop_end = riscv_hash[OP_HASH_IDX (word) + 1];
+  for (; pop != pop_end; pop++)
     {
+      op = *pop;
       /* Does the opcode match?  */
       if (!(op->match_func) (op, word))
 	continue;
-- 
2.38.1