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

[Palmer Dabbelt]

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 <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
>>