From patchwork Sun Nov 20 01:10:06 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tsukasa OI X-Patchwork-Id: 1958 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp928122wrr; Sat, 19 Nov 2022 17:10:40 -0800 (PST) X-Google-Smtp-Source: AA0mqf7f8blg1O2Z381BgaaBq3EoR2671rShuU8vinASygXjHG70VdsmGfji7fZ4Cxi6ZZp8UHsT X-Received: by 2002:a17:906:8419:b0:7a3:28c7:5835 with SMTP id n25-20020a170906841900b007a328c75835mr11413178ejx.32.1668906640593; Sat, 19 Nov 2022 17:10:40 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668906640; cv=none; d=google.com; s=arc-20160816; b=mujpGqoMmBwQErHfiienVqlR6pJO/V95XTC84fkErxosdzmkG3Xfb4P51hlOrfejk2 7gBz514Z9Sv6wB9TVpShFumWtmyzycXo+qw2Z+tEUugUCb/qG86ZXQcJZ6IwtbtB37Jp JawU+qEX7pGYHxxngkF+YiVXiw/otYbboDUEl8NEPIE5kqlHtakc5pjJkZABraFwRD9k i0MHRHbOGBGV+ju3xhQslw5jaR+ufbgo9MwawW/oCYPPdJjxVRD6qJu6Xy2OEN4EMbWC EnAA4onARi7LzjRKtK0NfUA1bVxq4Dv+LRiJUhPzwZ08BoLL1jNmIQlqU4IMU/CYz0Vw 3EZA== 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=EEXLNCg+ut1LrlEjppQiysyUDV7/cbJDGsRuXMg74wA=; b=wN7sf61mhqKSIVaM+Vrwa39Fe9HiiwdSQEXvwYPI4uk5aB2EmITB54xlz1lrv30y6d YXdZXEEkyLlUQrj7Hw5KfVD2f4POD3vQ4rPMes4mw1nzIlRlYVHRLVJGWhWPrY4Hhgqb oil81vD53wUcoBN2eRQU48+MxHCHIK8kTYCqan/XBd/HbDk6SUD6VXGDFojd7Ytv0GVb vVhQg41P36aQPa780sbSignER4mkCrYXeZCeJaVMbA0Ynw+ZINnK608g2/vloDNKQvFq jUvWIm0FPKItnR1XxoIOXAWLhcOpJoZid+PBirkrEi90LXA9bmA8fgILbTWqJ8j2844a jmeQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=VEsrZ4Or; 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 xb1-20020a170907070100b007aee7ca1161si761488ejb.711.2022.11.19.17.10.40 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Nov 2022 17:10:40 -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=VEsrZ4Or; 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 605D8388B686 for ; Sun, 20 Nov 2022 01:10:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 605D8388B686 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1668906634; bh=EEXLNCg+ut1LrlEjppQiysyUDV7/cbJDGsRuXMg74wA=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=VEsrZ4Orhvj36k06D6AtAwVyLVxsx6AOcV8oahBNh2Iw03LnZkjUNTTZpdACf5wvq tPPyRged8duFCI6YPV4s0Zi+4vBg7SWuRHxduQ81bwXvalFPb8wSmyl0oC53YYtg+1 AArY4J17gy+nmiJJtFpBGWEHVx7+lngUrhsJbf2M= 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 6AC083889E3F for ; Sun, 20 Nov 2022 01:10:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6AC083889E3F Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id B7007300089; Sun, 20 Nov 2022 01:10:10 +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-2 (Mapping symbols) Date: Sun, 20 Nov 2022 01:10:06 +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?1749975449696505745?= X-GMAIL-MSGID: =?utf-8?q?1749975449696505745?= Hello, This is the Part 4 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: Following is basically a copy from the PATCH 3/3 commit message. For ELF files with many symbols and/or sections (static libraries, partially linked files [e.g. vmlinux.o] or large object files), the disassembler is drastically slowed down by looking up the suitable mapping symbol. This is caused by the fact that: - It used an inefficient linear search to find the suitable mapping symbol - symtab_pos is not always a good hint for forward linear search and - The symbol table accessible by the disassembler is sorted by address and then section (not section, then address). They sometimes force O(n^2) mapping symbol search time while searching for the suitable mapping symbol for given address. This commit implements: - A binary search to look up suitable mapping symbol (O(log(n)) time per a lookup call, O(n) time on initialization), - Separate mapping symbol table, sorted by section and then address (unless the section to disassemble is NULL), - A very short linear search, even faster than binary search, when disassembling consecutive addresses (usually traverses only 1 or 2 symbols, O(n) on the worst case but this is only expected on adversarial samples) and - Efficient tracking of mapping symbols with ISA string (by propagating arch field of "$x+(arch)" to succeeding "$x" symbols). It also changes when the disassembler reuses the last mapping symbol. This commit only uses the last disassembled address to determine whether the last mapping symbol should be reused. This commit doesn't improve the disassembler performance much on regular programs in general. However, it expects >50% disassembler performance improvements on some files that "RISC-V: Use faster hash table on disassembling" was not effective enough. On bigger libraries, following numbers are observed during the benchmark: - x 2.13 - 2.22 : Static library : Newlib (libc.a) - x 5.67 - 6.09 : Static library : GNU libc (libc.a) - x 11.72 - 12.04 : Shared library : OpenSSL (libcrypto.so) - x 96.29 : Shared library : LLVM 14 (libLLVM-14.so) Thanks, Tsukasa Tsukasa OI (3): RISC-V: Easy optimization on riscv_search_mapping_symbol RISC-V: Per-section private data initialization RISC-V: Optimized search on mapping symbols opcodes/disassemble.c | 1 + opcodes/disassemble.h | 2 + opcodes/riscv-dis.c | 443 +++++++++++++++++++++++++++++------------- 3 files changed, 311 insertions(+), 135 deletions(-) base-commit: 844db363911065a3b5f0c5e4601f89ee1d7360c5