[PATCH v4] LoongArch: Batch-delete bytes at the end of each relax trip

[Lulu Cai]

Thanks for your contribution, the patch has been applied.

On 6/17/25 4:12 PM, WANG Xuerui wrote:
> From: WANG Xuerui <git@xen0n.name>
>
> Previously, memmove and reloc/symbol adjustments happened at each
> loongarch_relax_delete_bytes() call, which is O(n^2) time complexity and
> leads to unacceptable (multiple hours) linking times for certain inputs
> with huge number of relaxable sites -- see the linked issue for details.
>
> To get rid of the quadratic behavior, defer all delete ops to the end of
> each relax trip, with the buffer implemented with the splay tree from
> libiberty. The individual relaxation handlers are converted to handle
> symbol values and relocation offsets as if all preceding deletions
> actually happened, by querying a cumulative offset from the splay tree;
> the accesses should be efficient because they are mostly sequential
> during a relaxation trip. The exact relaxation behavior remains largely
> unchanged.
>
> Example running times before and after the change with the test case in
> the linked issue (mypy transpiled C), cross-linking on Threadripper
> 3990X:
> Before: 4192.80s user 1.09s system 98% cpu 1:10:53.52 total
> After:  1.76s user 0.74s system 98% cpu 2.539 total - ~1/2382 the time!
>
> Also tested with binutils (bootstrapping self), CPython 3.14 and LLVM
> 20.1.6; all passed the respective test suites.
>
> Link: https://github.com/loongson-community/discussions/issues/56
> Signed-off-by: WANG Xuerui <git@xen0n.name>
> ---
>
> Changes from v3:
>
> - Fixed loongarch_relax_perform_deletes's illustration and made it more
>    understandable with more comments.
>
> Changes from v2:
>
> - Fixed coding style issues as suggested by @mengqinggang. (The ASCII
>    art is causing some false positives from the check script.)
>
> Changes from v1:
>
> - Fixed symbol size adjustment to account for multiple deletions within
>    symbol range
> - Minor wording tweaks
>
>