From patchwork Mon Nov 28 04:46:20 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tsukasa OI X-Patchwork-Id: 26504 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp5434001wrr; Sun, 27 Nov 2022 20:50:56 -0800 (PST) X-Google-Smtp-Source: AA0mqf5KZnZgodxLHGKpxJ8kntIp6VMv9leQTdgJqep0BB2xaExMS8GIvjOYyHHaB/VfxXnIyDNh X-Received: by 2002:a17:906:a1a:b0:79e:9aea:7b60 with SMTP id w26-20020a1709060a1a00b0079e9aea7b60mr42532375ejf.444.1669611055959; Sun, 27 Nov 2022 20:50:55 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1669611055; cv=none; d=google.com; s=arc-20160816; b=KnECB5RvDRnfr/qyfRMUbuGyXG/rUTvAzZ/laKvmpF83U4OJw5y6/t0F0FjHFa6+dD bo+++YvF30vZ6cF10i18v1GqwzqpjoCacyZS2GtTZr7qpFT6DpJNLAN+qzGoSSyHqzRd LBih9YsCJBv/3YKtXok+JBGBzA3cvM6gJrfyOeTaBk1LFLE334hZOW+h0kRjsN9z95Yk Et/zNBg/f3qpijMaIzLkEfFy7SJuESMkZS0PSY/oncn2MPeg5CWXGyjmzG29OcAEk4U6 mI//1h9ompRS47d0/OL4n+yIRwrQ1mKFl8eHl/SCC88LUsYM4g+jMPIqS8uUW9N+4XN3 dPYQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=6ubdNv2FHyn2o3FdlwNLQjAwm8fG7IlpDuaQxIPSO6I=; b=UOjSYyvtjjqTomPf4yKFbr9mUX8ZxjHnxAp0rJiweICbRsclY9C60P9aklNi+olQqC dLs+0evgw7aHo7Jg7OYWwUC6zbHhmnIRaHl2YlZFuSv4Up06hr7Kd4Y7xh2QmOLEmQs/ mTK9xf7IeqcY0mevY02s6U2vUjrVw5pusQluwTchB1dChNWoCG2qi+o53fb5uXi5NxcL BHml8tJOD/hc8ndwCatcZGZWw+HXh96RsF3Yn9w606flNW34MV39OheMlSHr/070HtY1 2kXpJDEEzBagEfiYWQUsYFwluAMdz0HFCH7A9CZftrTB6ddkEXT5WzQbh5ajiGlPfhmj 8N8g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=X9WYrU8v; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id xb4-20020a170907070400b007be1ba9fba1si4150371ejb.948.2022.11.27.20.50.55 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 27 Nov 2022 20:50:55 -0800 (PST) Received-SPF: pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=X9WYrU8v; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E62E139540AE for ; Mon, 28 Nov 2022 04:47:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E62E139540AE DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669610861; bh=6ubdNv2FHyn2o3FdlwNLQjAwm8fG7IlpDuaQxIPSO6I=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=X9WYrU8vUs6UnDXsziV6fPwRvO65QBKUBcVJSwVziIIMOk/anF72+to80GcK2vaaJ GhpPiEcsaWrCNZr6bADp2GwaS+ba6aCUk3rKR7ZkyunA8W9tAiIJDzxsBkH7ppN+Dq lBR73PR6K7dLSG/0NfLa4nayPmOFzAlNtXe+Gyfo= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from mail-sender-0.a4lg.com (mail-sender.a4lg.com [153.120.152.154]) by sourceware.org (Postfix) with ESMTPS id 90C9E38A816C for ; Mon, 28 Nov 2022 04:46:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 90C9E38A816C Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id E78F4300089; Mon, 28 Nov 2022 04:46:41 +0000 (UTC) To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH v2 1/3] RISC-V: Use faster hash table on disassembling Date: Mon, 28 Nov 2022 04:46:20 +0000 Message-Id: In-Reply-To: References: Mime-Version: 1.0 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 X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Tsukasa OI via Binutils From: Tsukasa OI Reply-To: Tsukasa OI Errors-To: binutils-bounces+ouuuleilei=gmail.com@sourceware.org Sender: "Binutils" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749975462541234034?= X-GMAIL-MSGID: =?utf-8?q?1750714082748811370?= 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 b9309c092b17..4267b3ccf88c 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 @@ -829,24 +900,11 @@ riscv_disassemble_insn (bfd_vma memaddr, const bfd_byte *packet, 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. */ @@ -864,10 +922,11 @@ riscv_disassemble_insn (bfd_vma memaddr, 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; From patchwork Mon Nov 28 04:46:21 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tsukasa OI X-Patchwork-Id: 26507 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp5434561wrr; Sun, 27 Nov 2022 20:53:17 -0800 (PST) X-Google-Smtp-Source: AA0mqf4PXgIKVRA1ED8Z+P/7h9nYK/lgtK/nkxzPeK/uoeBCQQuMk6fP1xvleXNFKSEdH5fOk95f X-Received: by 2002:a17:907:989a:b0:7c0:7bd1:6436 with SMTP id ja26-20020a170907989a00b007c07bd16436mr472462ejc.718.1669611197793; Sun, 27 Nov 2022 20:53:17 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1669611197; cv=none; d=google.com; s=arc-20160816; b=MgFD+XW0ocS99iHx8SYSPj/q5dAZt5btWHEW7yEpKQ5t1sr0uWYrPXDCEIIq5hT/tT t0RP0lndERyQzvmO9rnvG32vfpVlrZZj9TtQNROM0riTkgvKvWtiTJcFkvASEpAffXfm 3vNb9XQOU97duhN/IMJfpX6wdibz+Rls+XBSU8hdkPzUfmw3Fl29Fj3zVrZ4lUEsr+EO vQsrj2arhjlf5qFjsh02Y3NKG34zn+XpLld733C47TExXW1g3YeqmfsknUzw7XSZwQY4 8WiGMNAWhWnjqOQQ10+Uvvn5lDjIYMA9zBHFniDR0PgOqyLIjErB9RQ5ncEmDz0Z05BN wmDw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=zh9rrwnRKAtXrMQT/3bew/O1ECNls1asgUv3xr5yOXo=; b=fMsVIYcJ4TTZN4WumV7EkrXgGlwGMl5sdr/GN+73pNWU1n2MQPcMuoa+pbNAFHoi63 pH9/EL4AflwWIwNRfsXhmHwWbC2Y557ElHAyzSyU4g0KuaYE6HdpF5OLBz4hMU1fAW3s U/C7LzCBrOQFa0MKp0n8w0zh4oI5dYwnvBI7kmxVzNde9DM2d+qOKPOriFl/pCI1syGd vUvpq/oDs3nVGfS9/DAHYuNtNWdmY1mWd62nZO+RlzJCsyHvQW5sDUm+RiJV9gqt1k8I LpfBrgF4LFvo4mWp6q6X5a9lkstFk50UhZeUOmVdfRzlFpS2Fzc4rfMpRF/23gq/8voO pJoQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=c6enmDg6; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id qk12-20020a1709077f8c00b0078dfe6dc4d2si9436234ejc.33.2022.11.27.20.53.17 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 27 Nov 2022 20:53:17 -0800 (PST) Received-SPF: pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=c6enmDg6; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A4294395B075 for ; Mon, 28 Nov 2022 04:48:45 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A4294395B075 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669610925; bh=zh9rrwnRKAtXrMQT/3bew/O1ECNls1asgUv3xr5yOXo=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=c6enmDg6EcwdXFHLs1Cm2kanK2YsmMMaW2c0EGHKQglw0sIiT+x/Va88QJ/VOCmFz CMJEFq/DeALsBPZa8wyNB0mUG+fXli2UrZemzcqk5y8VTIQ2I56j2lzhfK2upjo5aS aSVliJ/Lqag2G3T9tLtk0clI1REyddefsMRZmIlI= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from mail-sender-0.a4lg.com (mail-sender.a4lg.com [153.120.152.154]) by sourceware.org (Postfix) with ESMTPS id 223D7384F498 for ; Mon, 28 Nov 2022 04:46:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 223D7384F498 Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id 725F8300089; Mon, 28 Nov 2022 04:46:52 +0000 (UTC) To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH v2 2/3] RISC-V: Fallback on faster hash table Date: Mon, 28 Nov 2022 04:46:21 +0000 Message-Id: <0cd0bbfa70f83db276facb842b9a7bca1aaa77a6.1669610780.git.research_trasio@irq.a4lg.com> In-Reply-To: References: Mime-Version: 1.0 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 X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Tsukasa OI via Binutils From: Tsukasa OI Reply-To: Tsukasa OI Errors-To: binutils-bounces+ouuuleilei=gmail.com@sourceware.org Sender: "Binutils" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749975387644190681?= X-GMAIL-MSGID: =?utf-8?q?1750714231443187198?= From: Tsukasa OI Although it does not have a problem on current GNU Binutils implementation, if the custom vendor implements an instruction which spans across multiple major opcodes (e.g. uses both CUSTOM_0 and CUSTOM_1 in a *single* custom instruction), the original assumption of the sorted hash table breaks. In this case, this commit enables the fallback mode to disable all optimizations except filtering macros out. Note that, if a such instruction (that disables this disassembler optimization) is upstreamed to Binutils, a separate solution will be required to avoid major performance degradation when such instruction is not used. The intent of this commit is to make a room for custom vendors to implement such instructions in *their* tree without causing disassembler problems. opcodes/ChangeLog: * riscv-dis.c (is_riscv_hash_fallback) New. (build_riscv_opcodes_hash_table): If an instruction spans across multiple major opcodes, enable fallback mode and disable sorting. (riscv_disassemble_insn): If the fallback mode is enabled, scan through all instructions instead of scanning only instruction entries matching the hash value. --- opcodes/riscv-dis.c | 31 ++++++++++++++++++++++++++----- 1 file changed, 26 insertions(+), 5 deletions(-) diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c index 4267b3ccf88c..3f6cbf5a3680 100644 --- a/opcodes/riscv-dis.c +++ b/opcodes/riscv-dis.c @@ -838,6 +838,9 @@ print_insn_args (const char *oparg, insn_t l, bfd_vma pc, disassemble_info *info static const struct riscv_opcode **riscv_hash[OP_HASH_LEN + 1]; static const struct riscv_opcode **riscv_opcodes_sorted; +/* Whether the fallback should be used. */ +static bool is_riscv_hash_fallback = false; + /* Compare two riscv_opcode* objects to sort by hash index. */ static int @@ -868,15 +871,25 @@ build_riscv_opcodes_hash_table (void) /* Sort riscv_opcodes entry pointers (except macros). */ for (op = riscv_opcodes; op->name; op++) - if (op->pinfo != INSN_MACRO) + { + if (op->pinfo == INSN_MACRO) + continue; len++; + if (is_riscv_hash_fallback) + continue; + if (OP_HASH_IDX (op->match) < OP_MASK_OP2 + ? (op->mask & OP_MASK_OP2) != OP_MASK_OP2 + : (op->mask & OP_MASK_OP) != OP_MASK_OP) + is_riscv_hash_fallback = true; + } 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); + if (!is_riscv_hash_fallback) + qsort (riscv_opcodes_sorted, len, sizeof (struct riscv_opcode *), + compare_opcodes); /* Initialize faster hash table. */ pop = riscv_opcodes_sorted; @@ -922,8 +935,16 @@ riscv_disassemble_insn (bfd_vma memaddr, info->target2 = 0; matched_op = NULL; - pop = riscv_hash[OP_HASH_IDX (word)]; - pop_end = riscv_hash[OP_HASH_IDX (word) + 1]; + if (!is_riscv_hash_fallback) + { + pop = riscv_hash[OP_HASH_IDX (word)]; + pop_end = riscv_hash[OP_HASH_IDX (word) + 1]; + } + else + { + pop = riscv_hash[0]; + pop_end = riscv_hash[OP_HASH_LEN]; + } for (; pop != pop_end; pop++) { op = *pop; From patchwork Mon Nov 28 04:46:22 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tsukasa OI X-Patchwork-Id: 26501 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp5433751wrr; Sun, 27 Nov 2022 20:49:48 -0800 (PST) X-Google-Smtp-Source: AA0mqf5bpikhcePU4ogT54irnFJfC0konTBYfuUwD+JcJb/GieVUoMy0M+8chf0Rc19otYfWQN2n X-Received: by 2002:a17:906:f752:b0:7b9:b2f1:f382 with SMTP id jp18-20020a170906f75200b007b9b2f1f382mr21243748ejb.187.1669610988322; Sun, 27 Nov 2022 20:49:48 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1669610988; cv=none; d=google.com; s=arc-20160816; b=Z5e0puBX/rP1D8o5bHRrkHKTM93QVo+EpYbknwnMluN1iU+0vTz8SBnGCBPHBIp/rb 9r4BEyIVLc6UM6iaEYBLIP2v+WZ/a0sMcqBShXKC6OGI5R46AKUeWtepM8Zvmj7ableJ fzxL9OpZjWIR5ObcoojqmwSlgy3T+mCguTIWHPh3V2PepC9nIDXxs4SHE8TPX6j1Ccc6 g4MUmNythiCAoEg5REzoUR4sF9K2Cp6niHNwCwBeihyRMIeWUbf3ujfLHbBt9YBKgRZa P4797LgvRC97daMa8L32DrcjeFwQwI5C/0oB5K0uFP/cLfv9bYWt01XiviSC9YFMIQVB IDzg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=JVzDjZjhe1MCTdrgk365qrWSpe41y7+h8heM/Y3//UI=; b=u4BzWp+fH7Mtz9V7N6bqF0xoz0NYiW0wqEgYtZgjQhrVAlNrt64PQju/xRoaUVaED1 YChXrvClrlkk8n6AZEQbEkvjHwt+BkT8pWiv9MKPcSYzWRlHN4vUMX17Y0eRSIid8qFJ YUsz14Fmu23z5rsrv4mB+CPztRR3GO0UPXMIGqe81Rb8Bg73XhdAALOM41sPW/hal+b3 5gKXTFW+mjhd3Tp86YJmxAsWMQwZJIMhP5XalyknfP56jgNpRAQiXR5DFoAMLrRXx5s1 aUdRdhZoEV5/2EzrSLjs4CfFO97hgRvXbFq8OtqxtGB/yZM1QbBBM0LLfEweyj+WWQNc fOZQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b="Skg/6AdY"; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id z10-20020a05640235ca00b0046aeca41c55si4848235edc.212.2022.11.27.20.49.48 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 27 Nov 2022 20:49:48 -0800 (PST) Received-SPF: pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b="Skg/6AdY"; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 175F43942024 for ; Mon, 28 Nov 2022 04:47:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 175F43942024 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669610833; bh=JVzDjZjhe1MCTdrgk365qrWSpe41y7+h8heM/Y3//UI=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=Skg/6AdY7Xj5EXRcujIutGl9QLvjV2MEl5CvCCpcEE0x+xyqc2PcGdmHnmnL4r2pe Mwzkuf1H0SeABjauRbWjAwI+qWTVMWtyZpfUEDgmrRx4acySvoW6M0ujKJ/cTcfU/I NTM4gibycNKQs6tyHUPGgMSCNWcU8KoPXKpZxRG4= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from mail-sender-0.a4lg.com (mail-sender.a4lg.com [153.120.152.154]) by sourceware.org (Postfix) with ESMTPS id AD623384F6E2 for ; Mon, 28 Nov 2022 04:47:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AD623384F6E2 Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id F1E06300089; Mon, 28 Nov 2022 04:47:02 +0000 (UTC) To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH v2 3/3] RISC-V: Cache instruction support Date: Mon, 28 Nov 2022 04:46:22 +0000 Message-Id: <5b561967091a59d0052bd717d1b9f3e31ef841cc.1669610780.git.research_trasio@irq.a4lg.com> In-Reply-To: References: Mime-Version: 1.0 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 X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Tsukasa OI via Binutils From: Tsukasa OI Reply-To: Tsukasa OI Errors-To: binutils-bounces+ouuuleilei=gmail.com@sourceware.org Sender: "Binutils" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749975589075947301?= X-GMAIL-MSGID: =?utf-8?q?1750714011444627998?= From: Tsukasa OI Calling riscv_subset_supports repeatedly harms the performance in a measurable way (about 3-13% in total on the most cases). As a simple solution, this commit now caches instruction class support (whether specific instruction class is supported) as a signed char array. It is expected to have 5-7% performance improvements when disassembling linked RISC-V ELF programs using objdump but this is particularly effective with programs with many CSR instructions (up to ~42% on the author's PC). include/ChangeLog: * opcode/riscv.h (enum riscv_insn_class): Add NUM_INSN_CLASSES. opcodes/ChangeLog: * riscv-dis.c (riscv_insn_support_cache) New. (init_riscv_dis_state_for_arch): Clear the instruction support cache. (riscv_disassemble_insn): Cache the instruction support. --- include/opcode/riscv.h | 2 ++ opcodes/riscv-dis.c | 15 ++++++++++++++- 2 files changed, 16 insertions(+), 1 deletion(-) diff --git a/include/opcode/riscv.h b/include/opcode/riscv.h index c3cbde600cb0..6a029a1034e1 100644 --- a/include/opcode/riscv.h +++ b/include/opcode/riscv.h @@ -422,6 +422,8 @@ enum riscv_insn_class INSN_CLASS_XTHEADMEMIDX, INSN_CLASS_XTHEADMEMPAIR, INSN_CLASS_XTHEADSYNC, + + NUM_INSN_CLASSES, }; /* This structure holds information for a particular instruction. */ diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c index 3f6cbf5a3680..eb3e64816bf6 100644 --- a/opcodes/riscv-dis.c +++ b/opcodes/riscv-dis.c @@ -107,6 +107,9 @@ static bool no_aliases = false; /* If set, disassemble with numeric register names. */ static bool is_numeric = false; + +/* Instruction support cache. */ +static signed char riscv_insn_support_cache[NUM_INSN_CLASSES]; /* Set current disassembler context (dis_arch_context_current). @@ -200,6 +203,9 @@ static void init_riscv_dis_state_for_arch (void) { is_arch_changed = true; + /* Clear instruction support cache. */ + for (size_t i = 0; i < NUM_INSN_CLASSES; i++) + riscv_insn_support_cache[i] = 0; } /* Initialization (for arch and options). */ @@ -958,7 +964,14 @@ riscv_disassemble_insn (bfd_vma memaddr, if ((op->xlen_requirement != 0) && (op->xlen_requirement != xlen)) continue; /* Is this instruction supported by the current architecture? */ - if (!riscv_multi_subset_supports (&riscv_rps_dis, op->insn_class)) + if (riscv_insn_support_cache[op->insn_class] == 0) + { + riscv_insn_support_cache[op->insn_class] + = riscv_multi_subset_supports (&riscv_rps_dis, op->insn_class) + ? +1 + : -1; + } + if (riscv_insn_support_cache[op->insn_class] < 0) continue; matched_op = op;