From patchwork Sun Nov 20 01:08:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tsukasa OI X-Patchwork-Id: 1957 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp927724wrr; Sat, 19 Nov 2022 17:09:14 -0800 (PST) X-Google-Smtp-Source: AA0mqf7kvZBgwyPBxpS5qli/8JxkNQ6yaLOxc5MpuIApx++soA0NTqeyqpebMcFiO9gudZOB6Zrq X-Received: by 2002:a17:906:c1d0:b0:7b4:64d3:e6f4 with SMTP id bw16-20020a170906c1d000b007b464d3e6f4mr3494377ejb.594.1668906554057; Sat, 19 Nov 2022 17:09:14 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668906554; cv=none; d=google.com; s=arc-20160816; b=UzqxM+E2Lw3S9KW7D3rjYj7ZQuUXKFk99bOw8ff0Wp7FNB1qWbtLvS3DmWgx0Pea/e tq/2Sw/dQamm7Va1ZDF4SBn2233RcphGoEtmPZQcNWFLt6VKtgBZL8hoNJurflmMy19I ZnKenGI/cBiycj0rJv7vIOQFhZpDe5kfv3DI9V+lrKH92QeQUtikHzwKykvmOFm89ErU vZoBSLKE6YFV22HFsKEigVVEQbjPCzh7A6OfAHlLdxad6EhZcBfgkJxPYa1yNOIeJvJ0 51orGWWengvmCBvmL292jQUow6WGTzT6aoEp/jkY2ZQffC4LowtWu5RayqfL7rY3G3X8 VKiQ== 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:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=g7IwTUcyVshgP7j7pbuk3QRUMtPJthbrhR5608mY3+g=; b=NclqEN1e14WBupDnUlrhQgKhPWuDmUFMPrWrBZUrCtbuMf6NQnf3fYIvDd8wAkIAu6 Bfbn+AYANzL+Vg4vpH4yLmYvbVc6gXVZJcbnwird2zpmolf5gIE61GESDhNQQMXmvH/e z4bf/0xPfYRPZGJ6YubHsoWcH5o/HaudExrz71D4iqxRU+MoQtxhJI0fGK1UNsuCrWBT +z15sCgGL+5OzQgsKRm/BPg1GEJbWDHU7mjglN0I/3EOMQsTsgl5bpV1h6R3/DiodFby tr/RKwpNXbaGliW2xasJJSst/1hEH5mBuBsGD0pOIHUa+nT/1KUWtZrTOYVW0dkx8KAu GIbA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=u+hAZXSb; 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 fj10-20020a0564022b8a00b00461f7a83e58si5686651edb.46.2022.11.19.17.09.13 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Nov 2022 17:09:14 -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=u+hAZXSb; 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 2ABA63889E37 for ; Sun, 20 Nov 2022 01:09:12 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2ABA63889E37 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1668906552; bh=g7IwTUcyVshgP7j7pbuk3QRUMtPJthbrhR5608mY3+g=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=u+hAZXSb9eJz5afcCxpV7FMPDDq1dI4w/XTK2hcpb+erne0kohfRwbFxDtlVKMim9 7D5a+wjS6dbSMXx3gl0ezZr22yo67OKZlWXXgCclTxk56v5SPmbKVtpZ6Vn9RmC17r /X3eESjo0jiwPvrkppo+6igiNzwgRmbkSD7UXY8M= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org 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 0988C3889E1C for ; Sun, 20 Nov 2022 01:08:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0988C3889E1C Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id 6690E300089; Sun, 20 Nov 2022 01:08:50 +0000 (UTC) To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH 0/3] RISC-V: Disassembler Core Optimization 1-1 (Hash table and Caching) Date: Sun, 20 Nov 2022 01:08:39 +0000 Message-Id: Mime-Version: 1.0 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 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?1749975358940566925?= X-GMAIL-MSGID: =?utf-8?q?1749975358940566925?= 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: 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: f3fcf98b44621fb8768cf11121d3fd77089bca5b