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

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

[Tsukasa OI]

Hello,

This patchset intends to improve performance on disassembling RISC-V
code (which may possibly contain invalid data).  It replaces riscv_hash
(on opcodes/riscv-dis.c) with much faster data structure: sorted and
partitioned hash table.

Tracker on GitHub:
<https://github.com/a4lg/binutils-gdb/wiki/riscv_dis_opts_hashtable>

    Sidenote:
    I started listing my Binutils submissions on my GitHub Wiki:
    <https://github.com/a4lg/binutils-gdb/wiki/Patch-Queue>
    hoping that current status and conflicting patches are clear.

***WARNING***

This patchset conflicts with following patchset(s):
-   <https://sourceware.org/pipermail/binutils/2022-June/121441.html>
    (Tracker: <https://github.com/a4lg/binutils-gdb/wiki/riscv_dis_generics>)
If either of them is merged, I will submit rebased patchset.



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

I benchmarked some of the programs and I measure somewhat between 2%
to 10% performance increase while disassembling code section of RISC-V
ELF files (objdump -d $FILE).  That is not significant but not bad for
such a small modification (with ~ 11KB 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).  I tested on a big vmlinux image with debug symbols and I got
over 50% performance boost.  This is due to the fact that, disassembling
about one quarter of invalid "instruction" words required iterating over
one thousand opcode entries (>= 348 being vector instructions with OP-V,
that can be easily skipped with this new data structure).

Thanks,
Tsukasa




Tsukasa OI (1):
  RISC-V: Use faster hash table on disassembling

 opcodes/riscv-dis.c | 214 ++++++++++++++++++++++++++++----------------
 1 file changed, 136 insertions(+), 78 deletions(-)


base-commit: d2acd4b0c5bab349aaa152d60268bc144634a844
-- 
2.34.1

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

[Tsukasa OI]

This commit replaces riscv_hash with sorted and partitioned hash table
for faster disassembling (general idea is based on SPARC architecture
implementation).  It expects around 2%-10% performance improvement on
regular RISC-V code area and 50% or more on entire area of large binary
files (including but not limited to RISC-V code).

opcodes/ChangeLog:

	* riscv-dis.c (OP_HASH_IDX): Move out from
	riscv_disassemble_insn.
	(compare_opcodes, OP_HASH_LEN): New helpers.
	(riscv_hash, riscv_opcodes_sorted): New.
	(build_hash_table): New hash table building function.
	(riscv_disassemble_insn): Use faster hash table.  Split match
	and print steps.
---
 opcodes/riscv-dis.c | 214 ++++++++++++++++++++++++++++----------------
 1 file changed, 136 insertions(+), 78 deletions(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index 164fd209dbd..d8c16583ba1 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -564,6 +564,63 @@ print_insn_args (const char *oparg, insn_t l, bfd_vma pc, disassemble_info *info
     }
 }
 
+/* Build a hash table for disassembler to shorten the search time.
+   We sort pointers to riscv_opcodes entries to be even faster.  */
+
+#define OP_HASH_LEN (OP_MASK_OP + 1)
+#define OP_HASH_IDX(i) ((i) & (riscv_insn_length (i) == 2 ? 0x3 : OP_MASK_OP))
+static const struct riscv_opcode **riscv_hash[OP_HASH_LEN + 1];
+static const struct riscv_opcode **riscv_opcodes_sorted;
+
+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;
+  insn_t ai = OP_HASH_IDX (a->match);
+  insn_t bi = OP_HASH_IDX (b->match);
+  if (ai < bi)
+    return -1;
+  if (ai > bi)
+    return +1;
+  /* Stable sort (on riscv_opcodes entry order) is required.  */
+  if (a < b)
+    return -1;
+  if (a > b)
+    return +1;
+  return 0;
+}
+
+static void
+build_hash_table (void)
+{
+  const struct riscv_opcode *op;
+  const struct riscv_opcode **pop, **pop_end;
+  size_t len = 0, i;
+
+  /* Sort pointers to riscv_opcodes entries (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 (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;
+}
+
 /* 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
@@ -572,21 +629,15 @@ 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 *op;
+  const struct riscv_opcode **pop, **pop_end;
+  const struct riscv_opcode *op, *matched_op;
   static bool init = 0;
-  static const struct riscv_opcode *riscv_hash[OP_MASK_OP + 1];
   struct riscv_private_data *pd;
   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)
+  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;
-
+      build_hash_table ();
       init = 1;
     }
 
@@ -623,82 +674,89 @@ riscv_disassemble_insn (bfd_vma memaddr, insn_t word, disassemble_info *info)
   info->target = 0;
   info->target2 = 0;
 
-  op = riscv_hash[OP_HASH_IDX (word)];
-  if (op != NULL)
+  /* If XLEN is not known, get its value from the ELF class.  */
+  if (info->mach == bfd_mach_riscv64)
+    xlen = 64;
+  else if (info->mach == bfd_mach_riscv32)
+    xlen = 32;
+  else if (info->section != NULL)
     {
-      /* If XLEN is not known, get its value from the ELF class.  */
-      if (info->mach == bfd_mach_riscv64)
-	xlen = 64;
-      else if (info->mach == bfd_mach_riscv32)
-	xlen = 32;
-      else if (info->section != NULL)
-	{
-	  Elf_Internal_Ehdr *ehdr = elf_elfheader (info->section->owner);
-	  xlen = ehdr->e_ident[EI_CLASS] == ELFCLASS64 ? 64 : 32;
-	}
+      Elf_Internal_Ehdr *ehdr = elf_elfheader (info->section->owner);
+      xlen = ehdr->e_ident[EI_CLASS] == ELFCLASS64 ? 64 : 32;
+    }
+
+  matched_op = NULL;
+  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;
+      /* Is this a pseudo-instruction and may we print it as such?  */
+      if (no_aliases && (op->pinfo & INSN_ALIAS))
+	continue;
+      /* Is this instruction restricted to a certain value of XLEN?  */
+      if ((op->xlen_requirement != 0) && (op->xlen_requirement != xlen))
+	continue;
+
+      if (!riscv_multi_subset_supports (&riscv_rps_dis, op->insn_class))
+	continue;
+
+      matched_op = op;
+      break;
+    }
+
+  /* There is a match.  */
+  if (matched_op != NULL)
+    {
+      op = matched_op;
 
-      /* If arch has ZFINX flags, use gpr for disassemble.  */
-      if(riscv_subset_supports (&riscv_rps_dis, "zfinx"))
+      /* If arch has Zfinx extension, use GPR to disassemble.  */
+      if (riscv_subset_supports (&riscv_rps_dis, "zfinx"))
 	riscv_fpr_names = riscv_gpr_names;
 
-      for (; op->name; op++)
-	{
-	  /* Does the opcode match?  */
-	  if (! (op->match_func) (op, word))
-	    continue;
-	  /* Is this a pseudo-instruction and may we print it as such?  */
-	  if (no_aliases && (op->pinfo & INSN_ALIAS))
-	    continue;
-	  /* Is this instruction restricted to a certain value of XLEN?  */
-	  if ((op->xlen_requirement != 0) && (op->xlen_requirement != xlen))
-	    continue;
-
-	  if (!riscv_multi_subset_supports (&riscv_rps_dis, op->insn_class))
-	    continue;
-
-	  /* It's a match.  */
-	  (*info->fprintf_styled_func) (info->stream, dis_style_mnemonic,
-					"%s", op->name);
-	  print_insn_args (op->args, word, memaddr, info);
-
-	  /* Try to disassemble multi-instruction addressing sequences.  */
-	  if (pd->print_addr != (bfd_vma)-1)
-	    {
-	      info->target = pd->print_addr;
-	      (*info->fprintf_styled_func)
-		(info->stream, dis_style_comment_start, " # ");
-	      (*info->print_address_func) (info->target, info);
-	      pd->print_addr = -1;
-	    }
+      (*info->fprintf_styled_func) (info->stream, dis_style_mnemonic,
+				    "%s", op->name);
+      print_insn_args (op->args, word, memaddr, info);
 
-	  /* Finish filling out insn_info fields.  */
-	  switch (op->pinfo & INSN_TYPE)
-	    {
-	    case INSN_BRANCH:
-	      info->insn_type = dis_branch;
-	      break;
-	    case INSN_CONDBRANCH:
-	      info->insn_type = dis_condbranch;
-	      break;
-	    case INSN_JSR:
-	      info->insn_type = dis_jsr;
-	      break;
-	    case INSN_DREF:
-	      info->insn_type = dis_dref;
-	      break;
-	    default:
-	      break;
-	    }
+      /* Try to disassemble multi-instruction addressing sequences.  */
+      if (pd->print_addr != (bfd_vma) - 1)
+	{
+	  info->target = pd->print_addr;
+	  (*info->fprintf_styled_func)
+	    (info->stream, dis_style_comment_start, " # ");
+	  (*info->print_address_func) (info->target, info);
+	  pd->print_addr = -1;
+	}
 
-	  if (op->pinfo & INSN_DATA_SIZE)
-	    {
-	      int size = ((op->pinfo & INSN_DATA_SIZE)
-			  >> INSN_DATA_SIZE_SHIFT);
-	      info->data_size = 1 << (size - 1);
-	    }
+      /* Finish filling out insn_info fields.  */
+      switch (op->pinfo & INSN_TYPE)
+	{
+	case INSN_BRANCH:
+	  info->insn_type = dis_branch;
+	  break;
+	case INSN_CONDBRANCH:
+	  info->insn_type = dis_condbranch;
+	  break;
+	case INSN_JSR:
+	  info->insn_type = dis_jsr;
+	  break;
+	case INSN_DREF:
+	  info->insn_type = dis_dref;
+	  break;
+	default:
+	  break;
+	}
 
-	  return insnlen;
+      if (op->pinfo & INSN_DATA_SIZE)
+	{
+	  int size = ((op->pinfo & INSN_DATA_SIZE) >> INSN_DATA_SIZE_SHIFT);
+	  info->data_size = 1 << (size - 1);
 	}
+
+      return insnlen;
     }
 
   /* We did not find a match, so just print the instruction bits.  */
-- 
2.34.1

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

[Tsukasa OI]

This patch is postponed because I will merge this into a larger patchset
with general core disassembler improvements.

Thanks,
Tsukasa

On 2022/07/09 12:49, Tsukasa OI wrote:
> Hello,
> 
> This patchset intends to improve performance on disassembling RISC-V
> code (which may possibly contain invalid data).  It replaces riscv_hash
> (on opcodes/riscv-dis.c) with much faster data structure: sorted and
> partitioned hash table.
> 
> Tracker on GitHub:
> <https://github.com/a4lg/binutils-gdb/wiki/riscv_dis_opts_hashtable>
> 
>     Sidenote:
>     I started listing my Binutils submissions on my GitHub Wiki:
>     <https://github.com/a4lg/binutils-gdb/wiki/Patch-Queue>
>     hoping that current status and conflicting patches are clear.
> 
> ***WARNING***
> 
> This patchset conflicts with following patchset(s):
> -   <https://sourceware.org/pipermail/binutils/2022-June/121441.html>
>     (Tracker: <https://github.com/a4lg/binutils-gdb/wiki/riscv_dis_generics>)
> If either of them is merged, I will submit rebased patchset.
> 
> 
> 
> This is a technique actually used on SPARC architecture
> (opcodes/sparc-dis.c) and I simplified the algorithm even further.
> Unlike SPARC, RISC-V hashed opcode table is not a table to linked lists,
> it's just a table, pointing to "start" elements of the sorted opcode
> list (sorted by hash code) plus global tail.
> 
> I benchmarked some of the programs and I measure somewhat between 2%
> to 10% performance increase while disassembling code section of RISC-V
> ELF files (objdump -d $FILE).  That is not significant but not bad for
> such a small modification (with ~ 11KB 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).  I tested on a big vmlinux image with debug symbols and I got
> over 50% performance boost.  This is due to the fact that, disassembling
> about one quarter of invalid "instruction" words required iterating over
> one thousand opcode entries (>= 348 being vector instructions with OP-V,
> that can be easily skipped with this new data structure).
> 
> Thanks,
> Tsukasa
> 
> 
> 
> 
> Tsukasa OI (1):
>   RISC-V: Use faster hash table on disassembling
> 
>  opcodes/riscv-dis.c | 214 ++++++++++++++++++++++++++++----------------
>  1 file changed, 136 insertions(+), 78 deletions(-)
> 
> 
> base-commit: d2acd4b0c5bab349aaa152d60268bc144634a844