From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com [IPv6:2a00:1450:4864:20::62b]) by sourceware.org (Postfix) with ESMTPS id 9CF513858D28 for ; Wed, 13 Apr 2022 00:58:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9CF513858D28 Received: by mail-ej1-x62b.google.com with SMTP id g18so827875ejc.10 for ; Tue, 12 Apr 2022 17:58:50 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=05iPMqg9hUCceX6cwTquzLZrS3smB3nw5wKJ6+gZNcs=; b=OLoYi+fdQ0Ar+5WRTOq4zTgB7+K+ofuUnx7HNVdpJ9z6DPasaQB5nWzWMI5lEAK/zS eMcVquhsOXNR1SaBaMiyXI8e0WTuv4bQ00qyybsPAp1fgonojFdEZCt49dsjM4/WLQxZ If6NwbfTFpQJLSY6Yn8e6OuQH+DhQu1Dnn+1CVzHdLbKNruvDBZ4fOUoNBmdJomWAnZG Dvr8QBp7w4OCTAlBrRkrzqBuUCHTQyI59A4IQgqkHC72k8+ckZTFHhzkFU7I/nSlqvSK l3uUpMXh/HGdZBF3rsLakcp0GGiYJgki8YYOE9KebrmnFkFGRBzt4ICOtDyQu057Bc+5 Hacg== X-Gm-Message-State: AOAM533w9D6ECBZReaceH9N1t+ZzvXHeBzC9zk2laVi4z8gsulEo/x9v Et6us1OtA7ZxBkRLUjOZgsyjVicB4xMIVke0W+6OIVBc X-Google-Smtp-Source: ABdhPJwC9TzA1I1Bsy0pa7xUnqQl9/d87HLUnm0gFACJnWrKXH9bhx2xGIcmKZnYNsc6dwJHiCoGyOXwRhv/mgLIcv4= X-Received: by 2002:a17:907:3f1a:b0:6e8:b17c:e353 with SMTP id hq26-20020a1709073f1a00b006e8b17ce353mr5199019ejc.626.1649811529231; Tue, 12 Apr 2022 17:58:49 -0700 (PDT) MIME-Version: 1.0 References: <20220412162601.146507-1-patrick@rivosinc.com> In-Reply-To: <20220412162601.146507-1-patrick@rivosinc.com> From: Kito Cheng Date: Wed, 13 Apr 2022 08:58:38 +0800 Message-ID: Subject: Re: [PATCH 0/4] RISCV: Improve linker time complexity To: "Patrick O'Neill" Cc: Binutils , gnu-toolchain@rivosinc.com, Palmer Dabbelt , Nelson Chu , Jim Wilson Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, 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 00:58:52 -0000 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 :) 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 >