From patchwork Sun Apr 9 22:55:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 81328 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp1571347vqo; Sun, 9 Apr 2023 15:55:29 -0700 (PDT) X-Google-Smtp-Source: AKy350Y0ltozJHQhGhIhO/I/itZlMGBEb8bCXLr3H9tuMX/cTwh3z5bI+2WL6lh83aWRRwp/UhLI X-Received: by 2002:a17:907:6d90:b0:8aa:c090:a9ef with SMTP id sb16-20020a1709076d9000b008aac090a9efmr6625856ejc.55.1681080929100; Sun, 09 Apr 2023 15:55:29 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1681080929; cv=none; d=google.com; s=arc-20160816; b=ZIGIi2EoUXxNTAEn3dF1bO3zbf+OO48PjFJcYYGuWl6CGj/+VS547d4FiORx2Af3AH asKu26gesw7c+T08PUFuzJs1lUASq1acXUoSv9iJZmlxYI7jm+8+AY2Oc7HYi2Vnu+ir nvEAX4gSvZ5ASyRGN/i0NzM75VAQnvBGSNT7VUBxit/8/bDtgIfmIS+NiAwiak4NawcS 3rm+CoV3cppVLPHPivXf22Waizb+WNVn0XnWMIooxTsWuL6XFpmpdymokq/SLuvfhmUF Dd+5q2cMIIqHVZmAAZM2V0BiY0bmVX0ZQDH2CQRClveTKe8h0obwulmqMvHb4M6xxzLN 9wsA== 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:subject:to :content-language:user-agent:mime-version:date:message-id :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=juKmBplkecEOC8EURZkgOB5k8PqENS2u3KUAQHMdPhc=; b=cNhLWB8sqIEgm86Z7M27DS0o3hTiI4H/G/+bS/YFesfVUPpg5hDOzqfdBO5tj89xBJ ES1gHSmhWwOK1KQd1EeEISmz36uBAoAmNBti8o7LXhf9mejyALGiDCsHz5J9tmOkJLth 7M/GFmqfljFDOJMDh14U3nNjDYXQG7BuNYdTqoBM4h840moWtCiWSt9bR7YUcymiNQWj xFeskAAiSW8XdZAxsDbgXvNFAhoxc8eTPujboPMPgq0PEZmc1QRycziSVFB7pH6Uc4nO 4X3qGIGQBXY+CY+DUp/B065awCvaJjsoYqDY/3o/9HbIN84G/vvc+Dhmu+Udxw42hLeQ 9cDA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=QA51Qx5s; 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 hv22-20020a17090760d600b0093138e5a851si8411855ejc.344.2023.04.09.15.55.28 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 09 Apr 2023 15:55:29 -0700 (PDT) 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=QA51Qx5s; 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 B38003858C36 for ; Sun, 9 Apr 2023 22:55:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B38003858C36 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1681080927; bh=juKmBplkecEOC8EURZkgOB5k8PqENS2u3KUAQHMdPhc=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=QA51Qx5sFNH3DhjDoxECdu7hpN9wT7m7yc+e1OetIa8hXzX8FAN81FG3j8a/eXxQ2 Zp3qub2msL4+Q7NKzVhRqcpgVEJxLUaOdv4YHziIxPRIurPncOH6ENB/n039XXkfXu HWb45MjUPDB+HLjhhwUpHHEtzJZ8AMV0jH5nwUpM= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from mail-qv1-xf35.google.com (mail-qv1-xf35.google.com [IPv6:2607:f8b0:4864:20::f35]) by sourceware.org (Postfix) with ESMTPS id 0BB973858D28 for ; Sun, 9 Apr 2023 22:55:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0BB973858D28 Received: by mail-qv1-xf35.google.com with SMTP id u4so2415050qvj.10 for ; Sun, 09 Apr 2023 15:55:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1681080916; h=subject:from:to:content-language:user-agent:mime-version:date :message-id:sender:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=juKmBplkecEOC8EURZkgOB5k8PqENS2u3KUAQHMdPhc=; b=oI8LlnDa41Eb28+J5mwXF8MbxMvSPj0Hegq45+ChxWsHWG6stsBiWJ6vmCeBE7oBJi NBg98UHphtRQQSE/+MBMoIepETW+CNcYP0IbeHHfUNpBLWpTzZIJAx5aWFYRhVbxu6uC fASHIagcfhBp3FpL9Cr5bLmkM3Tk8goMh0YKbz2nYdPBI4bhuxMS+Pcnq6q3u768HONY ZNzs6jp575+LASbiqUJnGsou9+3wok8SCbZVFKtJGNBP3DGtvD+K7YDhLTSKrefiT/1s dCDhU9Cw8oF3YtY55fmJcXmqu9Yi+YGw8eqY3AXUOO5vCK+K/b3Gn6jg4/vKW7z/SnWG olPA== X-Gm-Message-State: AAQBX9f/GzmnZiq6VFJq+ZwrgLkPTWhOISbE/3upq6Ry05B93O25+6iC jKzWXm0djsSoZZUKKX8drrg= X-Received: by 2002:ad4:4ee3:0:b0:5e9:8487:3957 with SMTP id dv3-20020ad44ee3000000b005e984873957mr12210088qvb.7.1681080915650; Sun, 09 Apr 2023 15:55:15 -0700 (PDT) Received: from ?IPV6:2601:19c:527f:bfd0:cb20:e74:ead7:4cfe? ([2601:19c:527f:bfd0:cb20:e74:ead7:4cfe]) by smtp.googlemail.com with ESMTPSA id j9-20020a0cc349000000b005dd8b9345b9sm3032643qvi.81.2023.04.09.15.55.14 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 09 Apr 2023 15:55:15 -0700 (PDT) Message-ID: <745eb337-facd-244a-bd02-d9b8b1f653a5@acm.org> Date: Sun, 9 Apr 2023 18:55:13 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.9.1 Content-Language: en-US To: Nick Clifton , binutils Subject: bfd: optimize bfd_elf_hash X-Spam-Status: No, score=-3037.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, RCVD_IN_DNSWL_NONE, 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: Nathan Sidwell via Binutils From: Nathan Sidwell Reply-To: Nathan Sidwell 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?1762741116091104562?= X-GMAIL-MSGID: =?utf-8?q?1762741116091104562?= I happened to be poking at llvm's implementation of the sysv hash and notice binutils' version had similar optimization issues. neither gcc nor llvm can spot these xforms, and the if (...) at least obscures the data flow IMHO anyway. The bfd_elf_hash loop is taken straight from the sysV document, but it is poorly optimized. This refactoring removes about 5 x86 insns from the 15 insn loop. 1) The if (..) is meaningless -- we're xoring with that value, and of course xor 0 is a nop. On x86 (at least) we actually compute the xor'd value and then cmov. Removing the if test removes the cmov. 2) The 'h ^ g' to clear the top 4 bits is not needed, as those 4 bits will be shifted out in the next iteration. All we need to do is sink a mask of those 4 bits out of the loop. 3) anding with 0xf0 after shifting by 24 bits can allow betterin encoding on RISC ISAs than masking with '0xf0 << 24' before shifting. RISC ISAs often require materializing larger constants. nathan From 4fc6668fcbee2945d79b40f51cdcaeac78f08aa3 Mon Sep 17 00:00:00 2001 From: Nathan Sidwell Date: Sun, 9 Apr 2023 18:44:07 -0400 Subject: [PATCH] bfd: optimize bfd_elf_hash The bfd_elf_hash loop is taken straight from the sysV document, but it is poorly optimized. This refactoring removes about 5 x86 insns from the 15 insn loop. 1) The if (..) is meaningless -- we're xoring with that value, and of course xor 0 is a nop. On x86 (at least) we actually compute the xor'd value and then cmov. Removing the if test removes the cmov. 2) The 'h ^ g' to clear the top 4 bits is not needed, as those 4 bits will be shifted out in the next iteration. All we need to do is sink a mask of those 4 bits out of the loop. 3) anding with 0xf0 after shifting by 24 bits can allow betterin encoding on RISC ISAs than masking with '0xf0 << 24' before shifting. RISC ISAs often require materializing larger constants. bfd/ * elf.c (bfd_elf_hash): Refactor to optimize loop. (bfd_elf_gnu_hash): Refactor to use 32-bit type. --- bfd/elf.c | 31 +++++++++++-------------------- 1 file changed, 11 insertions(+), 20 deletions(-) diff --git a/bfd/elf.c b/bfd/elf.c index 87ec1623313..bda83469edd 100644 --- a/bfd/elf.c +++ b/bfd/elf.c @@ -196,23 +196,15 @@ _bfd_elf_swap_versym_out (bfd *abfd, unsigned long bfd_elf_hash (const char *namearg) { - const unsigned char *name = (const unsigned char *) namearg; - unsigned long h = 0; - unsigned long g; - int ch; + uint32_t h = 0; - while ((ch = *name++) != '\0') + for (const unsigned char *name = (const unsigned char *) namearg; + *name; name++) { - h = (h << 4) + ch; - if ((g = (h & 0xf0000000)) != 0) - { - h ^= g >> 24; - /* The ELF ABI says `h &= ~g', but this is equivalent in - this case and on some machines one insn instead of two. */ - h ^= g; - } + h = (h << 4) + *name; + h ^= (h >> 24) & 0xf0; } - return h & 0xffffffff; + return h & 0x0fffffff; } /* DT_GNU_HASH hash function. Do not change this function; you will @@ -221,13 +213,12 @@ bfd_elf_hash (const char *namearg) unsigned long bfd_elf_gnu_hash (const char *namearg) { - const unsigned char *name = (const unsigned char *) namearg; - unsigned long h = 5381; - unsigned char ch; + uint32_t h = 5381; - while ((ch = *name++) != '\0') - h = (h << 5) + h + ch; - return h & 0xffffffff; + for (const unsigned char *name = (const unsigned char *) namearg; + *name; name++) + h = (h << 5) + h + *name; + return h; } /* Create a tdata field OBJECT_SIZE bytes in length, zeroed out and with -- 2.39.2