[PATCH v2 0/5] RISCV: Improve linker time complexity

[Patrick O'Neill]

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.

There is a pathological case that could cause this to have worse
performance, so the --no-defer-deletion flag is added to allow users
to opt-out.

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
  RISCV: Add --defer-deletion flag

 bfd/elfnn-riscv.c                          | 212 ++++++++++++++-------
 include/bfdlink.h                          |   4 +
 ld/ld.texi                                 |  10 +
 ld/ldlex.h                                 |   2 +
 ld/lexsup.c                                |  10 +
 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 ++
 18 files changed, 363 insertions(+), 68 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