From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x102a.google.com (mail-pj1-x102a.google.com [IPv6:2607:f8b0:4864:20::102a]) by sourceware.org (Postfix) with ESMTPS id 31E1E3858D28 for ; Wed, 13 Apr 2022 02:23:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 31E1E3858D28 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=dabbelt.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=dabbelt.com Received: by mail-pj1-x102a.google.com with SMTP id 2so579760pjw.2 for ; Tue, 12 Apr 2022 19:23:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dabbelt-com.20210112.gappssmtp.com; s=20210112; h=date:subject:in-reply-to:cc:from:to:message-id:mime-version :content-transfer-encoding; bh=vrqg1VvIPXj3O0gQUH4oHNjz5TY+V9Eo8+e0B0jnCwQ=; b=qsEGCmQpp1ptUHploDdRmyMrOoMnKhFclKXsabRJUTer9e250ZhXfxZzeo6w3q9n34 32U2q9pmXFtLMny4/ucknbj0qH6bcrvXSyZxXiug5ySPHTCBN7YSdbFlZz5Mpzr0E+9I NBI85iAQJaUh8WIRGY3LD0m/gbGfUDv9gMFPKPVXa7TZwOchRzGXohNfsLafRSqCZ88c HeHVGEVLRfuPgMFlmeB1G28ubdtdfLB5jEe5JaHtHvamSmCoyRZIYStyLW0Xgm20DGGI tj03dMZ4DZTskRCixlsXoKDdS200d71WAa+fypILO2O8l9efAID7P1u1BBAcXHcsQeJZ xx5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:subject:in-reply-to:cc:from:to:message-id :mime-version:content-transfer-encoding; bh=vrqg1VvIPXj3O0gQUH4oHNjz5TY+V9Eo8+e0B0jnCwQ=; b=HK6M3DepVOXpRARU4Qxcbh0xDD0sVlMm3GozH1VMHto0ZRvjaH4R97SVmecU00U40O gKmoTmdnUfjR1nasD32XH8NRikBo8ExFMVPk3kX3tMUNSwoGhsQBWNNpmCPi+4PsNoeY JmHvCBItvYp1DO9XuPkV9EGO5eka206nYW4Ci/EaSjA1J9ITxMb1R/OwjEVvzKQnWUEc esMvLcbCkrGkj9PER6f/GT5xv2VB/cL5XxVyfMhajFxFnqaq7faLn4qzeQ0yvPqkro8Z gMTjJgSHfChNS/j96SN5D9qnaT5SNoPJfiVr/uikdnv82M65SU41TgU1kt3qEDXIBWo7 dscQ== X-Gm-Message-State: AOAM5324vpPgByN2J/UvVlIfiyqHqrWQMX9VVVKvVp3XCV/q5EcB1nqY uHH9iVE7db4a/cnXC+jYbmiNfw== X-Google-Smtp-Source: ABdhPJw7nipkkp5nI5v/AY8vwEzsXHm+NkI0uUumuHlIIZu5lwiFivDx9e8Wce1p89HaWT81ik4XKg== X-Received: by 2002:a17:902:a714:b0:154:6dfe:bba9 with SMTP id w20-20020a170902a71400b001546dfebba9mr40373442plq.124.1649816622138; Tue, 12 Apr 2022 19:23:42 -0700 (PDT) Received: from localhost ([12.3.194.138]) by smtp.gmail.com with ESMTPSA id d21-20020a056a0010d500b004fd9ee64134sm39484621pfu.74.2022.04.12.19.23.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Apr 2022 19:23:41 -0700 (PDT) Date: Tue, 12 Apr 2022 19:23:41 -0700 (PDT) X-Google-Original-Date: Tue, 12 Apr 2022 19:23:39 PDT (-0700) Subject: Re: [PATCH 0/4] RISCV: Improve linker time complexity In-Reply-To: CC: Patrick O'Neill , binutils@sourceware.org, gnu-toolchain@rivosinc.com, Nelson Chu , Jim Wilson From: Palmer Dabbelt To: Kito Cheng Message-ID: Mime-Version: 1.0 (MHng) Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-4.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-List-Received-Date: Wed, 13 Apr 2022 02:23:45 -0000 On Tue, 12 Apr 2022 17:58:38 PDT (-0700), Kito Cheng wrote: > Hi Patrick: > > Thanks for your amazing work! that's really good to see here is O(N) > implementation here, > > And I have a suggestion here is - does it possible to let co-exist with current > implementation and having a command line option to select the linker > relaxation, of course we > could default to using the new implementation, but that gives us an > emergency fallback option to use the old implementation :) I haven't actually looked at the code, but based on the design there should be almost no difference between the two implementations: essentially it's just an extra half-iteration of latency between the deletion and address calculation. In theory it wouldn't be that hard to have a flag that just turns the "mark for deletion" step into an "actually delete" step, which would result in exactly the same behavior we had before, but I'm not sure how that maps to the actual implementation as these patches don't look like I expected them to. I'll try and find some time to sort out why the diff is bigger than I expected it to be. > > Thanks > > > > > > On Wed, Apr 13, 2022 at 12:27 AM Patrick O'Neill wrote: >> >> The current linker has an O(n^2) time complexity when it comes to >> deleting bytes. By deferring the deletion of bytes, we can achieve O(n) >> deletion runtime. >> >> Patrick O'Neill (4): >> RISCV: Add linker relaxation tests >> RISCV: Arrange DELETE pass after .align pass >> RISCV: Implement piecewise deletion >> RISCV: Improve runtime of align directives >> >> bfd/elfnn-riscv.c | 343 ++++++++++++--------- >> ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp | 6 + >> ld/testsuite/ld-riscv-elf/relax-call-1.d | 17 + >> ld/testsuite/ld-riscv-elf/relax-call-1.s | 7 + >> ld/testsuite/ld-riscv-elf/relax-call-2.d | 21 ++ >> ld/testsuite/ld-riscv-elf/relax-call-2.s | 10 + >> ld/testsuite/ld-riscv-elf/relax-call-3.d | 25 ++ >> ld/testsuite/ld-riscv-elf/relax-call-3.s | 13 + >> ld/testsuite/ld-riscv-elf/relax-call-4.d | 19 ++ >> ld/testsuite/ld-riscv-elf/relax-call-4.s | 8 + >> ld/testsuite/ld-riscv-elf/relax-call-5.d | 23 ++ >> ld/testsuite/ld-riscv-elf/relax-call-5.s | 11 + >> ld/testsuite/ld-riscv-elf/relax-call-6.d | 22 ++ >> ld/testsuite/ld-riscv-elf/relax-call-6.s | 11 + >> 14 files changed, 389 insertions(+), 147 deletions(-) >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-1.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-1.s >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-2.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-2.s >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-3.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-3.s >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-4.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-4.s >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-5.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-5.s >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-6.d >> create mode 100644 ld/testsuite/ld-riscv-elf/relax-call-6.s >> >> -- >> 2.25.1 >>