From: Patrick O'Neill <patrick@rivosinc.com>
To: binutils@sourceware.org, nelson.chu@sifive.com
Cc: gnu-toolchain@rivosinc.com, jim.wilson.gcc@gmail.com,
palmer@rivosinc.com, andrew@sifive.com, kito.cheng@gmail.com,
Patrick O'Neill <patrick@rivosinc.com>
Subject: [PATCH v3 0/3] RISCV: Improve linker time complexity
Date: Fri, 27 May 2022 14:20:02 -0700 [thread overview]
Message-ID: <20220527212005.30709-1-patrick@rivosinc.com> (raw)
In-Reply-To: <20220502135048.1392596-1-patrick@rivosinc.com>
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.
There is a pathological case that could cause this to have worse
performance, so the --no-defer-deletion flag is added to allow users
to opt-out.
Patrick O'Neill (3):
RISCV: Add linker relaxation tests
RISCV: Implement piecewise deletion
RISCV: Add --defer-deletion flag
bfd/elfnn-riscv.c | 193 ++++++++++++++++-----
include/bfdlink.h | 4 +
ld/ld.texi | 10 ++
ld/ldlex.h | 2 +
ld/lexsup.c | 10 ++
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 ++
18 files changed, 366 insertions(+), 46 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
next prev parent reply other threads:[~2022-05-27 21:20 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-04-12 16:25 [PATCH 0/4] " Patrick O'Neill
2022-04-12 16:25 ` [PATCH 1/4] RISCV: Add linker relaxation tests Patrick O'Neill
2022-04-12 16:25 ` [PATCH 2/4] RISCV: Arrange DELETE pass after .align pass Patrick O'Neill
2022-04-12 16:26 ` [PATCH 3/4] RISCV: Implement piecewise deletion Patrick O'Neill
2022-04-12 16:26 ` [PATCH 4/4] RISCV: Improve runtime of align directives Patrick O'Neill
2022-04-13 0:58 ` [PATCH 0/4] RISCV: Improve linker time complexity Kito Cheng
2022-04-13 2:23 ` Palmer Dabbelt
2022-04-13 5:12 ` Alan Modra
2022-04-13 18:11 ` Palmer Dabbelt
2022-04-25 17:26 ` Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 0/5] " Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 1/5] RISCV: Add linker relaxation tests Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 2/5] RISCV: Arrange DELETE pass after .align pass Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 3/5] RISCV: Implement piecewise deletion Patrick O'Neill
2022-05-20 10:48 ` Nelson Chu
2022-05-20 17:36 ` Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 4/5] RISCV: Improve runtime of align directives Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 5/5] RISCV: Add --defer-deletion flag Patrick O'Neill
2022-05-27 21:20 ` Patrick O'Neill [this message]
2022-05-27 21:20 ` [PATCH v3 1/3] RISCV: Add linker relaxation tests Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 2/3] RISCV: Implement piecewise deletion Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 3/3] RISCV: Add --defer-deletion flag Patrick O'Neill
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220527212005.30709-1-patrick@rivosinc.com \
--to=patrick@rivosinc.com \
--cc=andrew@sifive.com \
--cc=binutils@sourceware.org \
--cc=gnu-toolchain@rivosinc.com \
--cc=jim.wilson.gcc@gmail.com \
--cc=kito.cheng@gmail.com \
--cc=nelson.chu@sifive.com \
--cc=palmer@rivosinc.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).