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 105883858439 for ; Mon, 28 Nov 2022 04:46:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 105883858439 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 6C2EE300089; Mon, 28 Nov 2022 04:46:31 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=irq.a4lg.com; s=2017s01; t=1669610791; bh=GBde5aRtOjo1fCwfCTfRok6hVaKN8gP8YXeMYyFpMck=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: Mime-Version:Content-Transfer-Encoding; b=FYZnF5t6ipMzGuYZ4OErHI9p64jcyF4p6SrQNmepT5hmwXpg+8BR79liUECdEqzCI 3311Zq96oEr1w55UkNOkvJFNKrM5eE/mOsJhNbuLPQsKtafUPbH4wsEN7jVX7yAS0K dgGCjMp5CYuKvGPlJ2Af5mDPR08AIGg1HGov4Wts= From: Tsukasa OI To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH v2 0/3] RISC-V: Disassembler Core Optimization 1-1 (Hash table and Caching) Date: Mon, 28 Nov 2022 04:46:19 +0000 Message-Id: In-Reply-To: References: Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,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: Hello, This is the Part 3 of 4-part project to improve disassembler performance drastically: ** this patchset does not apply to master directly. ** This patchset requires following patchset(s) to be applied first: [Changes: v1 -> v2] - Rebased against commit 97f006bc56af: "RISC-V: Better support for long instructions (disassembler)" PATCH 1/3 improves performance on disassembling RISC-V code (which may also possibly contain invalid data). It replaces riscv_hash (on opcodes/ riscv-dis.c) with much faster data structure: 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. PATCH 3/3 takes care of per-instruction instruction support probing problem. By caching which instruction classes are queried already, we no longer have to call riscv_multi_subset_supports function for every instruction. It speeds up the disassembling even further. PATCH 2/3 is not a part of the optimization but a safety net to complement PATCH 1/3. It enables implementing custom instructions that span through multiple major opcodes (such as both CUSTOM_0 and CUSTOM_1 **in a single instruction**) without causing disassembler functionality problems. Note that it has a big performance penalty if a vendor implements such instruction so if such instruction is implemented in the mainline, a separate solution will be required. I benchmarked some of the programs and I usually get 20-50% performance improvements while disassembling code section of compiled RISC-V ELF programs ("objdump -d $FILE"). That is significant and pretty nice for such a small modification (with about 12KB heap memory allocation on 64-bit environment). On libraries and big programs with many debug symbols, the improvements are not that high but this is to be taken care with the next part (the mapping symbol optimization). 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 various binary files including random one and big vmlinux images and I confirmed significant performance improvements (over 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. It also has a great synergy with the commit "RISC-V: One time CSR hash table initialization" and disassembling many CSR instructions is now over 6 times faster (in contrast to only about 30% faster at the patchset part 2). Thanks, Tsukasa Tsukasa OI (3): RISC-V: Use faster hash table on disassembling RISC-V: Fallback on faster hash table RISC-V: Cache instruction support include/opcode/riscv.h | 2 + opcodes/riscv-dis.c | 129 +++++++++++++++++++++++++++++++++++------ 2 files changed, 113 insertions(+), 18 deletions(-) base-commit: 75d9e5b0cfebcce34c855e4c98a956de4d7d7753 -- 2.38.1