From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-sender-0.a4lg.com (mail-sender-0.a4lg.com [IPv6:2401:2500:203:30b:4000:6bfe:4757:0]) by sourceware.org (Postfix) with ESMTPS id BA3763889E2A for ; Sun, 20 Nov 2022 01:09:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BA3763889E2A Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=irq.a4lg.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=irq.a4lg.com Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id E7928300089; Sun, 20 Nov 2022 01:09:00 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=irq.a4lg.com; s=2017s01; t=1668906541; bh=1hdMo+Rh52E9j8/7q5aWzPlJiGOAaU7VsBma9epqZo0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: Mime-Version:Content-Transfer-Encoding; b=Ubp01AkDBT/DWQWyBpHVy61TU9k5/5+SGDNUNj5e/uDG2zTJuSvshin5qCnlgib/w MpX27MtJDlU2lNTS9wnR0b8HRGcJlIS1F7gjsAWyiKWNuKVwYjRgqKQu5oWRebkNM7 Y4CEXWEBRt4ZHbyV65CzAUnFq4MqUpafOWPPe1CU= From: Tsukasa OI To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH 1/3] RISC-V: Use faster hash table on disassembling Date: Sun, 20 Nov 2022 01:08:40 +0000 Message-Id: <7487608537fcd71f322e56d40bfb2cc605cee89a.1668906514.git.research_trasio@irq.a4lg.com> In-Reply-To: References: Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: From: Tsukasa OI 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, } +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