LoongArch: Batch-delete bytes at the end of each relax trip

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>

0 files changed, 0 insertions, 0 deletions