[PATCH 0/4] RISCV: Improve linker time complexity

[Kito Cheng]

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 <patrick@rivosinc.com> 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
>