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

[Patrick O'Neill]

On 4/13/22 11:11, Palmer Dabbelt wrote:
> On Tue, 12 Apr 2022 22:12:22 PDT (-0700), binutils@sourceware.org wrote:
>> On Wed, Apr 13, 2022 at 08:58:38AM +0800, Kito Cheng via Binutils wrote:
>>> 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 :)
>>
>> You already have an emergency fallback, use an older binutils or
>> revert the patchset.  IMO you do not want two implementations of any
>> given feature.   Doing so just makes it more likely that neither
>> implementation is good.
>
> IMO a key point here is that the hueristics are subtly different, the 
> linear-time algorithm will fail at both forwards and backwards targets 
> where relaxation enables relaxation (as opposed to just failing at the 
> forwards targets, like the old one did).  The theory is that there 
> aren't any pathological cases in the wild, but it's hard to know for 
> sure.  I think it should just be a few lines of code to match the old 
> behavior (ie, just eagerly delete instead of deferring it to after all 
> relocations are processed), but I'm not sure -- the change around 
> alignment handling is tripping me up, as that was unexpected on my end.
>
> That said, there's certainly enough complexity here so I don't think 
> it's a big deal to just only support the new flavor.

If we're only concerned about the backwards targets then it should be
relatively easy to have it evaluate the relaxation deletions
immediately.

There's a challenge in that the current method expects all deletions to
occur one after another with a running tally of deleted bytes. This
causes issues when a deletion depends on a later deletion to clear up
any slack introduced. To solve this, I think it'd be 2 if statements.
One to delete immediately, and one to not depend on a running tally when
deleting immediately.

Regarding the change to alignment/reordered passes, those changes just
defer the deletions related to alignment to one pass at the end. Other
than concerns around correctness, I don't see a reason to keep the old
flavor of alignment around. The old flavor has O(n^2) time complexity
and doesn't change the underlying behavior.