From patchwork Fri Nov 25 16:44:23 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Matz X-Patchwork-Id: 2242 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp4151888wrr; Fri, 25 Nov 2022 08:44:34 -0800 (PST) X-Google-Smtp-Source: AA0mqf4jRGw4jPwv09IVpf712NDu/6MxRi3q8uWib5BAN21mAJYlqxXzZT8cKvc9ykeox1gfUc22 X-Received: by 2002:a17:906:f858:b0:78d:b654:8af9 with SMTP id ks24-20020a170906f85800b0078db6548af9mr25843596ejb.660.1669394674403; Fri, 25 Nov 2022 08:44:34 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1669394674; cv=none; d=google.com; s=arc-20160816; b=Q0n7ReBqvNbcJGvghIHwYNWfyzAmI6Hf+kJfedWPYwzTy3h0pQXe2WT5iv/zdhizik LH+9wtZbpCjej7JSO/JAPK3UiwDVOcGbg4aAG2dSg1o3H3zCq/tYV/DNVRTVlDrazGNG s58juXdvcyXIUEHZjtN8Nj8EzeoKZWDq390V7Ho0jtUIzu3tf8sbzbZ51JRPobELJ9yC iAOhGqp11fbewHWr9K0bCExmMj+uAm6CkOWmcoyoivJbSowYcmdj3vNggYVU/drF5ejq S1mTSGMQ1xLv9jIw+RztGrAUHwwTFBbN+S+PzqWmfmV/bF2Uhiwt5JQ6PP2v+a9+bQV8 NpBg== 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:mime-version :user-agent:message-id:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=d+gx9wyJMaoCVxWUO6RjlmI/VC/jfTqhPH9ribFVyL4=; b=RS/93foTAIb7SlTZq6oNpl9D2Dq+rULLEm2nKfkgOSN8NncOj8WbIPBNYSh1Jtbkb7 ldrvuH6z7WGuyk+xdiKNVjpNEV+6N6O/UwvGYEbgRQp4c20ASMiDq+XZBh0Ogd//Z5w0 WiMIC6sxbuflrsEeq4YQqJX7zDhcjiKLeG1mpLifq3E0JJwsKsieDCnyXuxDEKhHscJA rsHtJDSYPsl455ue2/at9tETvgy6PS/KOis19tweo52DPNQY20zXMJvmhAAkWruGlRLe Mv97CXeYZbjPa4KlKkzkjLJ2CygpB/lLHJzRuh6OOgYgzIfV9TEtHBIHPa6jYHxCdnp9 CNYA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=sQesD6oV; 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 dp16-20020a170906c15000b007adb388df38si4163121ejc.706.2022.11.25.08.44.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Nov 2022 08:44:34 -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=sQesD6oV; 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 30A5F384EF79 for ; Fri, 25 Nov 2022 16:44:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 30A5F384EF79 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669394673; bh=d+gx9wyJMaoCVxWUO6RjlmI/VC/jfTqhPH9ribFVyL4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=sQesD6oVAfGMHMy4AawotTCK2HCWQFn7TVn+fbCdyFFuBuU3LZgtT2BsqofWh+33L U6W7v9PmIc7dlxYyVBU1g9NNx62YnFm/h0E2lcYd4gAJhWH04EfPfzCRtS9oOioBgo +5o46A86r3k7nLfrbqnUnk875n5zPjAy7HSBgZKo= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id AD7C0384EF72 for ; Fri, 25 Nov 2022 16:44:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AD7C0384EF72 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id E9BF21FD81 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id E569C2C141 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Received: by wotan.suse.de (Postfix, from userid 10510) id DDCE46586; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by wotan.suse.de (Postfix) with ESMTP id DBF1A6238 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Date: Fri, 25 Nov 2022 16:44:23 +0000 (UTC) To: binutils@sourceware.org Subject: [PATCH 0/8] ld: Speed up section selection Message-ID: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, 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: Michael Matz via Binutils From: Michael Matz Reply-To: Michael Matz 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?1750487190405558405?= X-GMAIL-MSGID: =?utf-8?q?1750487190405558405?= Hello, so this series rewrites how ld selects sections, i.e. how the globs inside linker scripts are evaluated. My speed testcase is always linking cc1, a reasonably sized c++ program with many input files and sections (due to templates and section groups). I will use x86-64. The characteristics of that testcase are: * 674 input files * 300050 input sections * 129 wild statements in the linker script * 179 section selecttors in these wild statements (not all of them globs) With an -O2 build ld.bfd we start with this before the series: overall link time: 4.2823 +- 0.0188 seconds time elapsed ( +- 0.44% ) relevant pieces of the profile (overall this has 16900 samples): percentage Samples program shared object symbol name 5.82% 937 ld-new ld-new walk_wild_section_specs3_wild2 4.45% 718 ld-new ld-new walk_wild_section_specs1_wild1 2.97% 480 ld-new ld-new walk_wild_section_specs2_wild1 1.97% 317 ld-new ld-new walk_wild_section_general 0.85% 137 ld-new ld-new match_simple_wild After the series this will be: overall link time: 3.62733 +- 0.00779 seconds time elapsed ( +- 0.21% ) relevant pieces of the profile (overall this has 14244 samples): percentage Samples program shared object symbol name 0.67% 97 ld-new ld-new resolve_wild_sections.part.0 Yep, that's it, 97 samples remain from the initial 2500 samples for the whole of section selection. I have further patches that speedup GNU ld, but this series is only about the section selection process, which is the second top-most profile entry and the only code taking considerable time that isn't in libbfd. The way the series works is to first reshuffle the order of the overall loop structure matching all sections against all wild statements. Then we can memoize these results (which needs some adjustments), then we can use a prefix tree to quickly rule out possible matches, and then we cleaup. For review purpose I decided to not merge together some of the patches in the series. In particular it adds some interface into libbfd (in 2/8) that gets removed again later (in 7/8). Also the patches adding functionality often only comment out the old variants that are then only removed in a later patch. I think in this case that makes it easier to review (I looked at the overall squashed patch and it's quite confusing). I will also have a question in 4/8 whose answer might make the bfd change useful, so that it wouldn't have to be removed. I've tested the whole series without regression on all of Alans targets (158 of them). So, okay for master? :) Ciao, Michael. Michael Matz (8): section-select: Lazily resolve section matches section-select: Deal with sections added late section-select: Implement a prefix-tree section-select: Completely rebuild matches section-select: Remove unused code section-select: Cleanup section-select: Remove bfd_max_section_id again section-select: Fix exclude-file-3 ld/ldlang.c | 672 +++++++++------------ ld/ldlang.h | 13 +- ld/testsuite/ld-scripts/exclude-file-3.map | 4 +- 3 files changed, 295 insertions(+), 394 deletions(-)