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

[PATCH 0/4] 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.

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

[PATCH 1/4] RISCV: Add linker relaxation tests

[Patrick O'Neill]

Add basic tests for the behavior of relaxing function calls.
This covers behavior like relaxing a call, not relaxing a call, and
relaxing a call that is enabled by relaxing another call.

2022-04-11 Patrick O'Neill <patrick@rivosinc.com>

	* ld-riscv-elf.exp: Add testcases.
	* relax-call-1.d: Add new testcase.
	* relax-call-1.s: Likewise.
	* relax-call-2.d: Likewise.
	* relax-call-2.s: Likewise.
	* relax-call-3.d: Likewise.
	* relax-call-3.s: Likewise.
	* relax-call-4.d: Likewise.
	* relax-call-4.s: Likewise.
	* relax-call-5.d: Likewise.
	* relax-call-5.s: Likewise.
	* relax-call-6.d: Likewise.
	* relax-call-6.s: Likewise.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
 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 ++++++++++
 13 files changed, 193 insertions(+)
 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

diff --git a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
index 272424b33e..60f7cc5f20 100644
--- a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
+++ b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
@@ -119,6 +119,12 @@ proc run_relax_twice_test {} {
 }
 
 if [istarget "riscv*-*-*"] {
+    run_dump_test "relax-call-1"
+    run_dump_test "relax-call-2"
+    run_dump_test "relax-call-3"
+    run_dump_test "relax-call-4"
+    run_dump_test "relax-call-5"
+    run_dump_test "relax-call-6"
     run_dump_test "align-small-region"
     run_dump_test "call-relax"
     run_dump_test "pcgp-relax-01"
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.d b/ld/testsuite/ld-riscv-elf/relax-call-1.d
new file mode 100644
index 0000000000..3e7bfb500c
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.d
@@ -0,0 +1,17 @@
+#source: relax-call-1.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.s b/ld/testsuite/ld-riscv-elf/relax-call-1.s
new file mode 100644
index 0000000000..7b81e28f99
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.s
@@ -0,0 +1,7 @@
+	.text
+foo:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.d b/ld/testsuite/ld-riscv-elf/relax-call-2.d
new file mode 100644
index 0000000000..7481bea8c1
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.d
@@ -0,0 +1,21 @@
+#source: relax-call-2.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.s b/ld/testsuite/ld-riscv-elf/relax-call-2.s
new file mode 100644
index 0000000000..7f5844a678
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.s
@@ -0,0 +1,10 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.d b/ld/testsuite/ld-riscv-elf/relax-call-3.d
new file mode 100644
index 0000000000..5c49222e05
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.d
@@ -0,0 +1,25 @@
+#source: relax-call-3.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.*<baz>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*jal.* <baz>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.s b/ld/testsuite/ld-riscv-elf/relax-call-3.s
new file mode 100644
index 0000000000..66e7c02ca1
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.s
@@ -0,0 +1,13 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+baz:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	call	baz
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.d b/ld/testsuite/ld-riscv-elf/relax-call-4.d
new file mode 100644
index 0000000000..09e939ca9b
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.d
@@ -0,0 +1,19 @@
+#source: relax-call-4.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.s b/ld/testsuite/ld-riscv-elf/relax-call-4.s
new file mode 100644
index 0000000000..44eed0bc12
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.s
@@ -0,0 +1,8 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048570
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.d b/ld/testsuite/ld-riscv-elf/relax-call-5.d
new file mode 100644
index 0000000000..d9f44e5f8a
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.d
@@ -0,0 +1,23 @@
+#source: relax-call-5.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.s b/ld/testsuite/ld-riscv-elf/relax-call-5.s
new file mode 100644
index 0000000000..5605fb14e7
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048566
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.d b/ld/testsuite/ld-riscv-elf/relax-call-6.d
new file mode 100644
index 0000000000..c385ccb551
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.d
@@ -0,0 +1,22 @@
+#source: relax-call-6.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <bar>
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.s b/ld/testsuite/ld-riscv-elf/relax-call-6.s
new file mode 100644
index 0000000000..6df73e108f
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048560
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	bar
+	call	foo
+	jr	ra
-- 
2.25.1

[PATCH 2/4] RISCV: Arrange DELETE pass after .align pass

[Patrick O'Neill]

By moving the deletion pass after the align pass, the linker can touch
each byte once via piecewise deletion. Otherwise, it may need to move
the same bytes twice.

2022-04-11 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c (_bfd_riscv_relax_align): Count to-be-deleted
	  bytes so the alignments are still accurate.
	* elfnn-riscv.c (_bfd_riscv_relax_section): Move DELETE pass
	  after ALIGN pass.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This gives us an O(n^2) runtime when the align pass counts the number of 
deleted bytes preceding it, but this will be fixed in Patch 4/4.
---
 bfd/elfnn-riscv.c | 45 +++++++++++++++++++++++++++++----------------
 1 file changed, 29 insertions(+), 16 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 8f9f0d8a86..17f9607744 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4435,7 +4435,7 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 static bool
 _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			asection *sym_sec,
-			struct bfd_link_info *link_info,
+			struct bfd_link_info *link_info ATTRIBUTE_UNUSED,
 			Elf_Internal_Rela *rel,
 			bfd_vma symval,
 			bfd_vma max_alignment ATTRIBUTE_UNUSED,
@@ -4449,6 +4449,18 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   while (alignment <= rel->r_addend)
     alignment *= 2;
 
+  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
+  for (unsigned int i = 0; i < sec->reloc_count; i++)
+    {
+      Elf_Internal_Rela *reloc = relocs + i;
+      /* Ignore annotations after this alignment directive.  */
+      if (reloc == rel)
+	break;
+      /* Account for to-be-deleted bytes  */
+      else if (ELFNN_R_TYPE (reloc->r_info) == R_RISCV_DELETE)
+	symval -= reloc->r_addend;
+    }
+
   symval -= rel->r_addend;
   bfd_vma aligned_addr = ((symval - 1) & ~(alignment - 1)) + alignment;
   bfd_vma nop_bytes = aligned_addr - symval;
@@ -4468,12 +4480,12 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
       return false;
     }
 
-  /* Delete the reloc.  */
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
-
-  /* If the number of NOPs is already correct, there's nothing to do.  */
+  /* If the number of NOPs is already correct, delete the reloc.  */
   if (nop_bytes == rel->r_addend)
-    return true;
+    {
+      rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
+      return true;
+    }
 
   /* Write as many RISC-V NOPs as we need.  */
   for (pos = 0; pos < (nop_bytes & -4); pos += 4)
@@ -4483,10 +4495,11 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   if (nop_bytes % 4 != 0)
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
-  /* Delete the excess bytes.  */
-  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + nop_bytes,
-				   rel->r_addend - nop_bytes, link_info,
-				   NULL);
+  /* Mark the excess bytes for deletion.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+  rel->r_addend = rel->r_addend - nop_bytes;
+  rel->r_offset = rel->r_offset + nop_bytes;
+  return true;
 }
 
 /* Relax PC-relative references to GP-relative references.  */
@@ -4677,8 +4690,8 @@ bfd_elfNN_riscv_set_data_segment_info (struct bfd_link_info *info,
 /* Relax a section.
 
    Pass 0: Shortens code sequences for LUI/CALL/TPREL/PCREL relocs.
-   Pass 1: Deletes the bytes that PCREL relaxation in pass 0 made obsolete.
-   Pass 2: Which cannot be disabled, handles code alignment directives.  */
+   Pass 1: Which cannot be disabled, handles code alignment directives.
+   Pass 2: Handle DELETE directives.  */
 
 static bool
 _bfd_riscv_relax_section (bfd *abfd, asection *sec,
@@ -4697,7 +4710,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
   *again = false;
 
   if (bfd_link_relocatable (info)
-      || sec->sec_flg0
+      || (sec->sec_flg0 && info->relax_pass == 0)
       || (sec->flags & SEC_RELOC) == 0
       || sec->reloc_count == 0
       || (info->disable_target_specific_optimizations
@@ -4771,10 +4784,10 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (info->relax_pass == 1 && type == R_RISCV_DELETE)
-	relax_func = _bfd_riscv_relax_delete;
-      else if (info->relax_pass == 2 && type == R_RISCV_ALIGN)
+      else if (info->relax_pass == 1 && type == R_RISCV_ALIGN)
 	relax_func = _bfd_riscv_relax_align;
+      else if (info->relax_pass == 2 && type == R_RISCV_DELETE)
+	relax_func = _bfd_riscv_relax_delete;
       else
 	continue;
 
-- 
2.25.1

[PATCH 3/4] RISCV: Implement piecewise deletion

[Patrick O'Neill]

Rather than deleting bytes immediately, we can first mark the bytes for
deletion. Then, using piecewise deletion, we reduce the runtime from
O(n^2) to O(n).

By moving the logic from the riscv_relax_delete_bytes function into the
RISCV_DELETE reloc handler, we can delete the bytes in a piecewise
manner.

2022-04-11 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c: Move deletion logic into DELETE reloc handler
	  and replace with DELETE reloc creation logic.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This change overwrites the R_RISCV_RELAX with a R_RISCV_DELETE reloc
when a relaxation wants to delete bytes. If it was going to delete a
reloc, we use that reloc rather than deleting it.
---
 bfd/elfnn-riscv.c | 302 +++++++++++++++++++++++++---------------------
 1 file changed, 167 insertions(+), 135 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 17f9607744..5ebf7fe578 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4057,117 +4057,14 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
 /* Delete some bytes from a section while relaxing.  */
 
 static bool
-riscv_relax_delete_bytes (bfd *abfd,
-			  asection *sec,
-			  bfd_vma addr,
+riscv_relax_delete_bytes (bfd_vma addr,
 			  size_t count,
-			  struct bfd_link_info *link_info,
-			  riscv_pcgp_relocs *p)
+			  Elf_Internal_Rela *rel)
 {
-  unsigned int i, symcount;
-  bfd_vma toaddr = sec->size;
-  struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (abfd);
-  Elf_Internal_Shdr *symtab_hdr = &elf_tdata (abfd)->symtab_hdr;
-  unsigned int sec_shndx = _bfd_elf_section_from_bfd_section (abfd, sec);
-  struct bfd_elf_section_data *data = elf_section_data (sec);
-  bfd_byte *contents = data->this_hdr.contents;
-
-  /* Actually delete the bytes.  */
-  sec->size -= count;
-  memmove (contents + addr, contents + addr + count, toaddr - addr - count);
-
-  /* Adjust the location of all of the relocs.  Note that we need not
-     adjust the addends, since all PC-relative references must be against
-     symbols, which we will adjust below.  */
-  for (i = 0; i < sec->reloc_count; i++)
-    if (data->relocs[i].r_offset > addr && data->relocs[i].r_offset < toaddr)
-      data->relocs[i].r_offset -= count;
-
-  /* Adjust the hi_sec_off, and the hi_addr of any entries in the pcgp relocs
-     table for which these values occur after the deleted bytes.  */
-  if (p)
-    riscv_update_pcgp_relocs (p, sec, addr, count);
-
-  /* Adjust the local symbols defined in this section.  */
-  for (i = 0; i < symtab_hdr->sh_info; i++)
-    {
-      Elf_Internal_Sym *sym = (Elf_Internal_Sym *) symtab_hdr->contents + i;
-      if (sym->st_shndx == sec_shndx)
-	{
-	  /* If the symbol is in the range of memory we just moved, we
-	     have to adjust its value.  */
-	  if (sym->st_value > addr && sym->st_value <= toaddr)
-	    sym->st_value -= count;
-
-	  /* If the symbol *spans* the bytes we just deleted (i.e. its
-	     *end* is in the moved bytes but its *start* isn't), then we
-	     must adjust its size.
-
-	     This test needs to use the original value of st_value, otherwise
-	     we might accidentally decrease size when deleting bytes right
-	     before the symbol.  But since deleted relocs can't span across
-	     symbols, we can't have both a st_value and a st_size decrease,
-	     so it is simpler to just use an else.  */
-	  else if (sym->st_value <= addr
-		   && sym->st_value + sym->st_size > addr
-		   && sym->st_value + sym->st_size <= toaddr)
-	    sym->st_size -= count;
-	}
-    }
-
-  /* Now adjust the global symbols defined in this section.  */
-  symcount = ((symtab_hdr->sh_size / sizeof (ElfNN_External_Sym))
-	      - symtab_hdr->sh_info);
-
-  for (i = 0; i < symcount; i++)
-    {
-      struct elf_link_hash_entry *sym_hash = sym_hashes[i];
-
-      /* The '--wrap SYMBOL' option is causing a pain when the object file,
-	 containing the definition of __wrap_SYMBOL, includes a direct
-	 call to SYMBOL as well. Since both __wrap_SYMBOL and SYMBOL reference
-	 the same symbol (which is __wrap_SYMBOL), but still exist as two
-	 different symbols in 'sym_hashes', we don't want to adjust
-	 the global symbol __wrap_SYMBOL twice.
-
-	 The same problem occurs with symbols that are versioned_hidden, as
-	 foo becomes an alias for foo@BAR, and hence they need the same
-	 treatment.  */
-      if (link_info->wrap_hash != NULL
-	  || sym_hash->versioned != unversioned)
-	{
-	  struct elf_link_hash_entry **cur_sym_hashes;
-
-	  /* Loop only over the symbols which have already been checked.  */
-	  for (cur_sym_hashes = sym_hashes; cur_sym_hashes < &sym_hashes[i];
-	       cur_sym_hashes++)
-	    {
-	      /* If the current symbol is identical to 'sym_hash', that means
-		 the symbol was already adjusted (or at least checked).  */
-	      if (*cur_sym_hashes == sym_hash)
-		break;
-	    }
-	  /* Don't adjust the symbol again.  */
-	  if (cur_sym_hashes < &sym_hashes[i])
-	    continue;
-	}
-
-      if ((sym_hash->root.type == bfd_link_hash_defined
-	   || sym_hash->root.type == bfd_link_hash_defweak)
-	  && sym_hash->root.u.def.section == sec)
-	{
-	  /* As above, adjust the value if needed.  */
-	  if (sym_hash->root.u.def.value > addr
-	      && sym_hash->root.u.def.value <= toaddr)
-	    sym_hash->root.u.def.value -= count;
-
-	  /* As above, adjust the size if needed.  */
-	  else if (sym_hash->root.u.def.value <= addr
-		   && sym_hash->root.u.def.value + sym_hash->size > addr
-		   && sym_hash->root.u.def.value + sym_hash->size <= toaddr)
-	    sym_hash->size -= count;
-	}
-    }
+  /* Mark bytes for deletion.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+  rel->r_offset = addr;
+  rel->r_addend = count;
 
   return true;
 }
@@ -4177,7 +4074,7 @@ typedef bool (*relax_func_t) (bfd *, asection *, asection *,
 			      Elf_Internal_Rela *,
 			      bfd_vma, bfd_vma, bfd_vma, bool *,
 			      riscv_pcgp_relocs *,
-			      bool undefined_weak);
+			      bool undefined_weak, bfd_vma *);
 
 /* Relax AUIPC + JALR into JAL.  */
 
@@ -4190,7 +4087,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
 		       bfd_vma reserve_size ATTRIBUTE_UNUSED,
 		       bool *again,
 		       riscv_pcgp_relocs *pcgp_relocs,
-		       bool undefined_weak ATTRIBUTE_UNUSED)
+		       bool undefined_weak ATTRIBUTE_UNUSED,
+		       bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma foff = symval - (sec_addr (sec) + rel->r_offset);
@@ -4252,8 +4150,7 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
 
   /* Delete unnecessary JALR.  */
   *again = true;
-  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
-				   link_info, pcgp_relocs);
+  return riscv_relax_delete_bytes (rel->r_offset + len, 8 - len, rel + 1);
 }
 
 /* Traverse all output sections and return the max alignment.  */
@@ -4286,7 +4183,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
 		      bfd_vma reserve_size,
 		      bool *again,
 		      riscv_pcgp_relocs *pcgp_relocs,
-		      bool undefined_weak)
+		      bool undefined_weak,
+		      bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma gp = riscv_global_pointer_value (link_info);
@@ -4343,11 +4241,10 @@ _bfd_riscv_relax_lui (bfd *abfd,
 	  return true;
 
 	case R_RISCV_HI20:
-	  /* We can delete the unnecessary LUI and reloc.  */
+	  /* We can delete the unnecessary LUI and reuse the reloc.  */
 	  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
 	  *again = true;
-	  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4,
-					   link_info, pcgp_relocs);
+	  return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
 
 	default:
 	  abort ();
@@ -4379,8 +4276,7 @@ _bfd_riscv_relax_lui (bfd *abfd,
       rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
 
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2,
-				       link_info, pcgp_relocs);
+      return riscv_relax_delete_bytes (rel->r_offset + 2, 2, rel + 1);
     }
 
   return true;
@@ -4399,7 +4295,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
 			 bool *again,
 			 riscv_pcgp_relocs *pcgp_relocs,
-			 bool undefined_weak ATTRIBUTE_UNUSED)
+			 bool undefined_weak ATTRIBUTE_UNUSED,
+			 bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   /* See if this symbol is in range of tp.  */
   if (RISCV_CONST_HIGH_PART (tpoff (link_info, symval)) != 0)
@@ -4418,11 +4315,10 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 
     case R_RISCV_TPREL_HI20:
     case R_RISCV_TPREL_ADD:
-      /* We can delete the unnecessary instruction and reloc.  */
+      /* We can delete the unnecessary instruction and reuse the reloc.  */
       rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info,
-				       pcgp_relocs);
+      return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
 
     default:
       abort ();
@@ -4442,7 +4338,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			bfd_vma reserve_size ATTRIBUTE_UNUSED,
 			bool *again ATTRIBUTE_UNUSED,
 			riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
-			bool undefined_weak ATTRIBUTE_UNUSED)
+			bool undefined_weak ATTRIBUTE_UNUSED,
+			bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma alignment = 1, pos;
@@ -4496,10 +4393,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
   /* Mark the excess bytes for deletion.  */
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
-  rel->r_addend = rel->r_addend - nop_bytes;
-  rel->r_offset = rel->r_offset + nop_bytes;
-  return true;
+  return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
+				   rel->r_addend - nop_bytes, rel);
 }
 
 /* Relax PC-relative references to GP-relative references.  */
@@ -4515,7 +4410,8 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
 		     bfd_vma reserve_size,
 		     bool *again ATTRIBUTE_UNUSED,
 		     riscv_pcgp_relocs *pcgp_relocs,
-		     bool undefined_weak)
+		     bool undefined_weak,
+		     bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma gp = riscv_global_pointer_value (link_info);
@@ -4666,13 +4562,148 @@ _bfd_riscv_relax_delete (bfd *abfd,
 			 bfd_vma max_alignment ATTRIBUTE_UNUSED,
 			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
 			 bool *again ATTRIBUTE_UNUSED,
-			 riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
-			 bool undefined_weak ATTRIBUTE_UNUSED)
+			 riscv_pcgp_relocs *pcgp_relocs,
+			 bool undefined_weak ATTRIBUTE_UNUSED,
+			 bfd_vma *delete_total)
 {
-  if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend,
-				 link_info, NULL))
-    return false;
+  unsigned int i, symcount;
+  bfd_vma toaddr = sec->size;
+  struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (abfd);
+  Elf_Internal_Shdr *symtab_hdr = &elf_tdata (abfd)->symtab_hdr;
+  unsigned int sec_shndx = _bfd_elf_section_from_bfd_section (abfd, sec);
+  struct bfd_elf_section_data *data = elf_section_data (sec);
+  bfd_byte *contents = data->this_hdr.contents;
+
+  bfd_vma addr = rel->r_offset;
+  size_t count = rel->r_addend;
+  riscv_pcgp_relocs *p = pcgp_relocs;
+
+  /* Find the next DELETE reloc (if one exists).  */
+  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
+  Elf_Internal_Rela *next_delete = NULL;
+  /* Since we only replace existing relocs and don't add new relocs, the
+     relocs are in sequential order. We can skip the relocs prior to this one,
+     making this search linear time.  */
+  int start = rel - relocs;
+  for (unsigned int i = start; i < sec->reloc_count; i++)
+    {
+      next_delete = relocs + i;
+      if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
+	  && next_delete->r_offset > rel->r_offset)
+	break;
+      else
+	next_delete = NULL;
+    }
+
+  size_t bytes_to_move;
+  /* Make this a piecewise deletion.  */
+  if (next_delete == NULL)
+    bytes_to_move = toaddr - addr - count;
+  else
+    bytes_to_move = next_delete->r_offset - addr - count;
+
+  /* Actually delete the bytes.  */
+  sec->size -= count;
+  memmove (contents + addr, contents + addr + count + *delete_total, bytes_to_move);
+
+  *delete_total += count;
+
+  /* Delete the reloc.  */
   rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
+
+  /* Adjust the location of all of the relocs.  Note that we need not
+     adjust the addends, since all PC-relative references must be against
+     symbols, which we will adjust below.  */
+  for (i = 0; i < sec->reloc_count; i++)
+    if (data->relocs[i].r_offset > addr && data->relocs[i].r_offset < toaddr)
+      data->relocs[i].r_offset -= count;
+
+  /* Adjust the hi_sec_off, and the hi_addr of any entries in the pcgp relocs
+     table for which these values occur after the deleted bytes.  */
+  if (p)
+    riscv_update_pcgp_relocs (p, sec, addr, count);
+
+  /* Adjust the local symbols defined in this section.  */
+  for (i = 0; i < symtab_hdr->sh_info; i++)
+    {
+      Elf_Internal_Sym *sym = (Elf_Internal_Sym *) symtab_hdr->contents + i;
+      if (sym->st_shndx == sec_shndx)
+	{
+	  /* If the symbol is in the range of memory we just moved, we
+	     have to adjust its value.  */
+	  if (sym->st_value > addr && sym->st_value <= toaddr)
+	    sym->st_value -= count;
+
+	  /* If the symbol *spans* the bytes we just deleted (i.e. its
+	     *end* is in the moved bytes but its *start* isn't), then we
+	     must adjust its size.
+
+	     This test needs to use the original value of st_value, otherwise
+	     we might accidentally decrease size when deleting bytes right
+	     before the symbol.  But since deleted relocs can't span across
+	     symbols, we can't have both a st_value and a st_size decrease,
+	     so it is simpler to just use an else.  */
+	  else if (sym->st_value <= addr
+		   && sym->st_value + sym->st_size > addr
+		   && sym->st_value + sym->st_size <= toaddr)
+	    sym->st_size -= count;
+	}
+    }
+
+  /* Now adjust the global symbols defined in this section.  */
+  symcount = ((symtab_hdr->sh_size / sizeof (ElfNN_External_Sym))
+	      - symtab_hdr->sh_info);
+
+  for (i = 0; i < symcount; i++)
+    {
+      struct elf_link_hash_entry *sym_hash = sym_hashes[i];
+
+      /* The '--wrap SYMBOL' option is causing a pain when the object file,
+	 containing the definition of __wrap_SYMBOL, includes a direct
+	 call to SYMBOL as well. Since both __wrap_SYMBOL and SYMBOL reference
+	 the same symbol (which is __wrap_SYMBOL), but still exist as two
+	 different symbols in 'sym_hashes', we don't want to adjust
+	 the global symbol __wrap_SYMBOL twice.
+
+	 The same problem occurs with symbols that are versioned_hidden, as
+	 foo becomes an alias for foo@BAR, and hence they need the same
+	 treatment.  */
+      if (link_info->wrap_hash != NULL
+	  || sym_hash->versioned != unversioned)
+	{
+	  struct elf_link_hash_entry **cur_sym_hashes;
+
+	  /* Loop only over the symbols which have already been checked.  */
+	  for (cur_sym_hashes = sym_hashes; cur_sym_hashes < &sym_hashes[i];
+	       cur_sym_hashes++)
+	    {
+	      /* If the current symbol is identical to 'sym_hash', that means
+		 the symbol was already adjusted (or at least checked).  */
+	      if (*cur_sym_hashes == sym_hash)
+		break;
+	    }
+	  /* Don't adjust the symbol again.  */
+	  if (cur_sym_hashes < &sym_hashes[i])
+	    continue;
+	}
+
+      if ((sym_hash->root.type == bfd_link_hash_defined
+	   || sym_hash->root.type == bfd_link_hash_defweak)
+	  && sym_hash->root.u.def.section == sec)
+	{
+	  /* As above, adjust the value if needed.  */
+	  if (sym_hash->root.u.def.value > addr
+	      && sym_hash->root.u.def.value <= toaddr)
+	    sym_hash->root.u.def.value -= count;
+
+	  /* As above, adjust the size if needed.  */
+	  else if (sym_hash->root.u.def.value <= addr
+		   && sym_hash->root.u.def.value + sym_hash->size > addr
+		   && sym_hash->root.u.def.value + sym_hash->size <= toaddr)
+	    sym_hash->size -= count;
+	}
+    }
+
   return true;
 }
 
@@ -4706,6 +4737,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
   unsigned int i;
   bfd_vma max_alignment, reserve_size = 0;
   riscv_pcgp_relocs pcgp_relocs;
+  bfd_vma delete_bytes = 0;
 
   *again = false;
 
@@ -4941,7 +4973,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 
       if (!relax_func (abfd, sec, sym_sec, info, rel, symval,
 		       max_alignment, reserve_size, again,
-		       &pcgp_relocs, undefined_weak))
+		       &pcgp_relocs, undefined_weak, &delete_bytes))
 	goto fail;
     }
 
-- 
2.25.1

[PATCH 4/4] RISCV: Improve runtime of align directives

[Patrick O'Neill]

Align directives need an accurate count of the number of bytes to be
deleted. This can be computed using a running sum, giving us an O(n),
rather than O(n^2) runtime.

2022-04-11 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c (_bfd_riscv_relax_align): Rely on running
	  delete_bytes count when calculating alignment.
	* elfnn-riscv.c (_bfd_riscv_relax_section): Calculate running
	  deletion total during align pass.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This fixes the O(n^2) runtime introduced in patch 2/4
---
 bfd/elfnn-riscv.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 5ebf7fe578..e08d60edb0 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4339,24 +4339,15 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			bool *again ATTRIBUTE_UNUSED,
 			riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
 			bool undefined_weak ATTRIBUTE_UNUSED,
-			bfd_vma *delete_total ATTRIBUTE_UNUSED)
+			bfd_vma *delete_total)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma alignment = 1, pos;
   while (alignment <= rel->r_addend)
     alignment *= 2;
 
-  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
-  for (unsigned int i = 0; i < sec->reloc_count; i++)
-    {
-      Elf_Internal_Rela *reloc = relocs + i;
-      /* Ignore annotations after this alignment directive.  */
-      if (reloc == rel)
-	break;
-      /* Account for to-be-deleted bytes  */
-      else if (ELFNN_R_TYPE (reloc->r_info) == R_RISCV_DELETE)
-	symval -= reloc->r_addend;
-    }
+  /* Account for to-be-deleted bytes.  */
+  symval -= *delete_total;
 
   symval -= rel->r_addend;
   bfd_vma aligned_addr = ((symval - 1) & ~(alignment - 1)) + alignment;
@@ -4392,6 +4383,9 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   if (nop_bytes % 4 != 0)
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
+  /* Account for the soon-to-be marked bytes.  */
+  *delete_total += rel->r_addend - nop_bytes;
+
   /* Mark the excess bytes for deletion.  */
   return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
 				   rel->r_addend - nop_bytes, rel);
@@ -4816,8 +4810,18 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (info->relax_pass == 1 && type == R_RISCV_ALIGN)
-	relax_func = _bfd_riscv_relax_align;
+      else if (info->relax_pass == 1)
+        {
+	  if (type == R_RISCV_ALIGN)
+	    relax_func = _bfd_riscv_relax_align;
+	  else if (type == R_RISCV_DELETE)
+	    {
+	      delete_bytes += rel->r_addend;
+	      continue;
+	    }
+	  else
+	    continue;
+	}
       else if (info->relax_pass == 2 && type == R_RISCV_DELETE)
 	relax_func = _bfd_riscv_relax_delete;
       else
-- 
2.25.1

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

[Kito Cheng]

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

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
>

Re: [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
>>

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

[Alan Modra]

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.

-- 
Alan Modra
Australia Development Lab, IBM

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

[Palmer Dabbelt]

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.

Re: [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.

[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

[PATCH v2 1/5] RISCV: Add linker relaxation tests

[Patrick O'Neill]

Add basic tests for the behavior of relaxing function calls.
This covers behavior like relaxing a call, not relaxing a call, and
relaxing a call that is enabled by relaxing another call.

2022-04-29 Patrick O'Neill <patrick@rivosinc.com>

	* ld-riscv-elf.exp: Add testcases.
	* relax-call-1.d: Add new testcase.
	* relax-call-1.s: Likewise.
	* relax-call-2.d: Likewise.
	* relax-call-2.s: Likewise.
	* relax-call-3.d: Likewise.
	* relax-call-3.s: Likewise.
	* relax-call-4.d: Likewise.
	* relax-call-4.s: Likewise.
	* relax-call-5.d: Likewise.
	* relax-call-5.s: Likewise.
	* relax-call-6.d: Likewise.
	* relax-call-6.s: Likewise.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
 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 ++++++++++
 13 files changed, 193 insertions(+)
 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

diff --git a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
index 272424b33e3..60f7cc5f208 100644
--- a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
+++ b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
@@ -119,6 +119,12 @@ proc run_relax_twice_test {} {
 }
 
 if [istarget "riscv*-*-*"] {
+    run_dump_test "relax-call-1"
+    run_dump_test "relax-call-2"
+    run_dump_test "relax-call-3"
+    run_dump_test "relax-call-4"
+    run_dump_test "relax-call-5"
+    run_dump_test "relax-call-6"
     run_dump_test "align-small-region"
     run_dump_test "call-relax"
     run_dump_test "pcgp-relax-01"
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.d b/ld/testsuite/ld-riscv-elf/relax-call-1.d
new file mode 100644
index 00000000000..3e7bfb500c9
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.d
@@ -0,0 +1,17 @@
+#source: relax-call-1.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.s b/ld/testsuite/ld-riscv-elf/relax-call-1.s
new file mode 100644
index 00000000000..7b81e28f99f
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.s
@@ -0,0 +1,7 @@
+	.text
+foo:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.d b/ld/testsuite/ld-riscv-elf/relax-call-2.d
new file mode 100644
index 00000000000..7481bea8c1e
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.d
@@ -0,0 +1,21 @@
+#source: relax-call-2.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.s b/ld/testsuite/ld-riscv-elf/relax-call-2.s
new file mode 100644
index 00000000000..7f5844a6789
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.s
@@ -0,0 +1,10 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.d b/ld/testsuite/ld-riscv-elf/relax-call-3.d
new file mode 100644
index 00000000000..5c49222e056
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.d
@@ -0,0 +1,25 @@
+#source: relax-call-3.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.*<baz>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*jal.* <baz>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.s b/ld/testsuite/ld-riscv-elf/relax-call-3.s
new file mode 100644
index 00000000000..66e7c02ca19
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.s
@@ -0,0 +1,13 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+baz:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	call	baz
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.d b/ld/testsuite/ld-riscv-elf/relax-call-4.d
new file mode 100644
index 00000000000..09e939ca9b4
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.d
@@ -0,0 +1,19 @@
+#source: relax-call-4.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.s b/ld/testsuite/ld-riscv-elf/relax-call-4.s
new file mode 100644
index 00000000000..44eed0bc128
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.s
@@ -0,0 +1,8 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048570
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.d b/ld/testsuite/ld-riscv-elf/relax-call-5.d
new file mode 100644
index 00000000000..d9f44e5f8a2
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.d
@@ -0,0 +1,23 @@
+#source: relax-call-5.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.s b/ld/testsuite/ld-riscv-elf/relax-call-5.s
new file mode 100644
index 00000000000..5605fb14e78
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048566
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.d b/ld/testsuite/ld-riscv-elf/relax-call-6.d
new file mode 100644
index 00000000000..c385ccb5511
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.d
@@ -0,0 +1,22 @@
+#source: relax-call-6.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <bar>
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.s b/ld/testsuite/ld-riscv-elf/relax-call-6.s
new file mode 100644
index 00000000000..6df73e108f4
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048560
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	bar
+	call	foo
+	jr	ra
-- 
2.25.1

[PATCH v2 2/5] RISCV: Arrange DELETE pass after .align pass

[Patrick O'Neill]

By moving the deletion pass after the align pass, the linker can touch
each byte once via piecewise deletion. Otherwise, it may need to move
the same bytes twice.

2022-04-29 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c (_bfd_riscv_relax_align): Count to-be-deleted
	  bytes so the alignments are still accurate.
	* elfnn-riscv.c (_bfd_riscv_relax_section): Move DELETE pass
	  after ALIGN pass.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This gives us an O(n^2) runtime when the align pass counts the number of 
deleted bytes preceding it, but this will be fixed in Patch 4/5.
---
 bfd/elfnn-riscv.c | 45 +++++++++++++++++++++++++++++----------------
 1 file changed, 29 insertions(+), 16 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 8f9f0d8a86a..17f9607744f 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4435,7 +4435,7 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 static bool
 _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			asection *sym_sec,
-			struct bfd_link_info *link_info,
+			struct bfd_link_info *link_info ATTRIBUTE_UNUSED,
 			Elf_Internal_Rela *rel,
 			bfd_vma symval,
 			bfd_vma max_alignment ATTRIBUTE_UNUSED,
@@ -4449,6 +4449,18 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   while (alignment <= rel->r_addend)
     alignment *= 2;
 
+  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
+  for (unsigned int i = 0; i < sec->reloc_count; i++)
+    {
+      Elf_Internal_Rela *reloc = relocs + i;
+      /* Ignore annotations after this alignment directive.  */
+      if (reloc == rel)
+	break;
+      /* Account for to-be-deleted bytes  */
+      else if (ELFNN_R_TYPE (reloc->r_info) == R_RISCV_DELETE)
+	symval -= reloc->r_addend;
+    }
+
   symval -= rel->r_addend;
   bfd_vma aligned_addr = ((symval - 1) & ~(alignment - 1)) + alignment;
   bfd_vma nop_bytes = aligned_addr - symval;
@@ -4468,12 +4480,12 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
       return false;
     }
 
-  /* Delete the reloc.  */
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
-
-  /* If the number of NOPs is already correct, there's nothing to do.  */
+  /* If the number of NOPs is already correct, delete the reloc.  */
   if (nop_bytes == rel->r_addend)
-    return true;
+    {
+      rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
+      return true;
+    }
 
   /* Write as many RISC-V NOPs as we need.  */
   for (pos = 0; pos < (nop_bytes & -4); pos += 4)
@@ -4483,10 +4495,11 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   if (nop_bytes % 4 != 0)
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
-  /* Delete the excess bytes.  */
-  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + nop_bytes,
-				   rel->r_addend - nop_bytes, link_info,
-				   NULL);
+  /* Mark the excess bytes for deletion.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+  rel->r_addend = rel->r_addend - nop_bytes;
+  rel->r_offset = rel->r_offset + nop_bytes;
+  return true;
 }
 
 /* Relax PC-relative references to GP-relative references.  */
@@ -4677,8 +4690,8 @@ bfd_elfNN_riscv_set_data_segment_info (struct bfd_link_info *info,
 /* Relax a section.
 
    Pass 0: Shortens code sequences for LUI/CALL/TPREL/PCREL relocs.
-   Pass 1: Deletes the bytes that PCREL relaxation in pass 0 made obsolete.
-   Pass 2: Which cannot be disabled, handles code alignment directives.  */
+   Pass 1: Which cannot be disabled, handles code alignment directives.
+   Pass 2: Handle DELETE directives.  */
 
 static bool
 _bfd_riscv_relax_section (bfd *abfd, asection *sec,
@@ -4697,7 +4710,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
   *again = false;
 
   if (bfd_link_relocatable (info)
-      || sec->sec_flg0
+      || (sec->sec_flg0 && info->relax_pass == 0)
       || (sec->flags & SEC_RELOC) == 0
       || sec->reloc_count == 0
       || (info->disable_target_specific_optimizations
@@ -4771,10 +4784,10 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (info->relax_pass == 1 && type == R_RISCV_DELETE)
-	relax_func = _bfd_riscv_relax_delete;
-      else if (info->relax_pass == 2 && type == R_RISCV_ALIGN)
+      else if (info->relax_pass == 1 && type == R_RISCV_ALIGN)
 	relax_func = _bfd_riscv_relax_align;
+      else if (info->relax_pass == 2 && type == R_RISCV_DELETE)
+	relax_func = _bfd_riscv_relax_delete;
       else
 	continue;
 
-- 
2.25.1

[PATCH v2 3/5] RISCV: Implement piecewise deletion

[Patrick O'Neill]

Rather than deleting bytes immediately, we can first mark the bytes for
deletion. Then, using piecewise deletion, we reduce the runtime from
O(n^2) to O(n).

By moving the logic from the riscv_relax_delete_bytes function into the
RISCV_DELETE reloc handler, we can delete the bytes in a piecewise
manner.

2022-04-29 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c: Move deletion logic into DELETE reloc handler
	  and replace with DELETE reloc creation logic.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This change overwrites the R_RISCV_RELAX with a R_RISCV_DELETE reloc
when a relaxation wants to delete bytes. If it was going to delete a
reloc, we use that reloc rather than deleting it.
---
v2 Changelog:
- Arrange functions as to reduce the diff of each patch and make
  reviewing more manageable
---
 bfd/elfnn-riscv.c | 144 ++++++++++++++++++++++++++++------------------
 1 file changed, 88 insertions(+), 56 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 17f9607744f..10e76e8628d 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4054,15 +4054,28 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
     }
 }
 
-/* Delete some bytes from a section while relaxing.  */
+typedef bool (*relax_func_t) (bfd *, asection *, asection *,
+			      struct bfd_link_info *,
+			      Elf_Internal_Rela *,
+			      bfd_vma, bfd_vma, bfd_vma, bool *,
+			      riscv_pcgp_relocs *,
+			      bool undefined_weak, bfd_vma *);
+
+/* Delete the bytes for R_RISCV_DELETE.  */
 
 static bool
-riscv_relax_delete_bytes (bfd *abfd,
-			  asection *sec,
-			  bfd_vma addr,
-			  size_t count,
-			  struct bfd_link_info *link_info,
-			  riscv_pcgp_relocs *p)
+_bfd_riscv_relax_delete (bfd *abfd,
+			 asection *sec,
+			 asection *sym_sec ATTRIBUTE_UNUSED,
+			 struct bfd_link_info *link_info,
+			 Elf_Internal_Rela *rel,
+			 bfd_vma symval ATTRIBUTE_UNUSED,
+			 bfd_vma max_alignment ATTRIBUTE_UNUSED,
+			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
+			 bool *again ATTRIBUTE_UNUSED,
+			 riscv_pcgp_relocs *pcgp_relocs,
+			 bool undefined_weak ATTRIBUTE_UNUSED,
+			 bfd_vma *delete_total)
 {
   unsigned int i, symcount;
   bfd_vma toaddr = sec->size;
@@ -4072,9 +4085,42 @@ riscv_relax_delete_bytes (bfd *abfd,
   struct bfd_elf_section_data *data = elf_section_data (sec);
   bfd_byte *contents = data->this_hdr.contents;
 
+  bfd_vma addr = rel->r_offset;
+  size_t count = rel->r_addend;
+  riscv_pcgp_relocs *p = pcgp_relocs;
+
+  /* Find the next DELETE reloc (if one exists).  */
+  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
+  Elf_Internal_Rela *next_delete = NULL;
+  /* Since we only replace existing relocs and don't add new relocs, the
+     relocs are in sequential order. We can skip the relocs prior to this one,
+     making this search linear time.  */
+  int start = rel - relocs;
+  for (unsigned int i = start; i < sec->reloc_count; i++)
+    {
+      next_delete = relocs + i;
+      if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
+	  && next_delete->r_offset > rel->r_offset)
+	break;
+      else
+	next_delete = NULL;
+    }
+
+  size_t bytes_to_move;
+  /* Make this a piecewise deletion.  */
+  if (next_delete == NULL)
+    bytes_to_move = toaddr - addr - count;
+  else
+    bytes_to_move = next_delete->r_offset - addr - count;
+
   /* Actually delete the bytes.  */
   sec->size -= count;
-  memmove (contents + addr, contents + addr + count, toaddr - addr - count);
+  memmove (contents + addr, contents + addr + count + *delete_total, bytes_to_move);
+
+  *delete_total += count;
+
+  /* Delete the reloc.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
 
   /* Adjust the location of all of the relocs.  Note that we need not
      adjust the addends, since all PC-relative references must be against
@@ -4172,12 +4218,20 @@ riscv_relax_delete_bytes (bfd *abfd,
   return true;
 }
 
-typedef bool (*relax_func_t) (bfd *, asection *, asection *,
-			      struct bfd_link_info *,
-			      Elf_Internal_Rela *,
-			      bfd_vma, bfd_vma, bfd_vma, bool *,
-			      riscv_pcgp_relocs *,
-			      bool undefined_weak);
+/* Delete some bytes from a section while relaxing.  */
+
+static bool
+riscv_relax_delete_bytes (bfd_vma addr,
+			  size_t count,
+			  Elf_Internal_Rela *rel)
+{
+  /* Mark bytes for deletion.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+  rel->r_offset = addr;
+  rel->r_addend = count;
+
+  return true;
+}
 
 /* Relax AUIPC + JALR into JAL.  */
 
@@ -4190,7 +4244,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
 		       bfd_vma reserve_size ATTRIBUTE_UNUSED,
 		       bool *again,
 		       riscv_pcgp_relocs *pcgp_relocs,
-		       bool undefined_weak ATTRIBUTE_UNUSED)
+		       bool undefined_weak ATTRIBUTE_UNUSED,
+		       bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma foff = symval - (sec_addr (sec) + rel->r_offset);
@@ -4252,8 +4307,7 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
 
   /* Delete unnecessary JALR.  */
   *again = true;
-  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
-				   link_info, pcgp_relocs);
+  return riscv_relax_delete_bytes (rel->r_offset + len, 8 - len, rel + 1);
 }
 
 /* Traverse all output sections and return the max alignment.  */
@@ -4286,7 +4340,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
 		      bfd_vma reserve_size,
 		      bool *again,
 		      riscv_pcgp_relocs *pcgp_relocs,
-		      bool undefined_weak)
+		      bool undefined_weak,
+		      bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma gp = riscv_global_pointer_value (link_info);
@@ -4343,11 +4398,10 @@ _bfd_riscv_relax_lui (bfd *abfd,
 	  return true;
 
 	case R_RISCV_HI20:
-	  /* We can delete the unnecessary LUI and reloc.  */
+	  /* We can delete the unnecessary LUI and reuse the reloc.  */
 	  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
 	  *again = true;
-	  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4,
-					   link_info, pcgp_relocs);
+	  return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
 
 	default:
 	  abort ();
@@ -4379,8 +4433,7 @@ _bfd_riscv_relax_lui (bfd *abfd,
       rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
 
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2,
-				       link_info, pcgp_relocs);
+      return riscv_relax_delete_bytes (rel->r_offset + 2, 2, rel + 1);
     }
 
   return true;
@@ -4399,7 +4452,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
 			 bool *again,
 			 riscv_pcgp_relocs *pcgp_relocs,
-			 bool undefined_weak ATTRIBUTE_UNUSED)
+			 bool undefined_weak ATTRIBUTE_UNUSED,
+			 bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   /* See if this symbol is in range of tp.  */
   if (RISCV_CONST_HIGH_PART (tpoff (link_info, symval)) != 0)
@@ -4418,11 +4472,10 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 
     case R_RISCV_TPREL_HI20:
     case R_RISCV_TPREL_ADD:
-      /* We can delete the unnecessary instruction and reloc.  */
+      /* We can delete the unnecessary instruction and reuse the reloc.  */
       rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info,
-				       pcgp_relocs);
+      return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
 
     default:
       abort ();
@@ -4442,7 +4495,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			bfd_vma reserve_size ATTRIBUTE_UNUSED,
 			bool *again ATTRIBUTE_UNUSED,
 			riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
-			bool undefined_weak ATTRIBUTE_UNUSED)
+			bool undefined_weak ATTRIBUTE_UNUSED,
+			bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma alignment = 1, pos;
@@ -4496,10 +4550,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
   /* Mark the excess bytes for deletion.  */
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
-  rel->r_addend = rel->r_addend - nop_bytes;
-  rel->r_offset = rel->r_offset + nop_bytes;
-  return true;
+  return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
+				   rel->r_addend - nop_bytes, rel);
 }
 
 /* Relax PC-relative references to GP-relative references.  */
@@ -4515,7 +4567,8 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
 		     bfd_vma reserve_size,
 		     bool *again ATTRIBUTE_UNUSED,
 		     riscv_pcgp_relocs *pcgp_relocs,
-		     bool undefined_weak)
+		     bool undefined_weak,
+		     bfd_vma *delete_total ATTRIBUTE_UNUSED)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma gp = riscv_global_pointer_value (link_info);
@@ -4654,28 +4707,6 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
   return true;
 }
 
-/* Delete the bytes for R_RISCV_DELETE.  */
-
-static bool
-_bfd_riscv_relax_delete (bfd *abfd,
-			 asection *sec,
-			 asection *sym_sec ATTRIBUTE_UNUSED,
-			 struct bfd_link_info *link_info,
-			 Elf_Internal_Rela *rel,
-			 bfd_vma symval ATTRIBUTE_UNUSED,
-			 bfd_vma max_alignment ATTRIBUTE_UNUSED,
-			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
-			 bool *again ATTRIBUTE_UNUSED,
-			 riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
-			 bool undefined_weak ATTRIBUTE_UNUSED)
-{
-  if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend,
-				 link_info, NULL))
-    return false;
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
-  return true;
-}
-
 /* Called by after_allocation to set the information of data segment
    before relaxing.  */
 
@@ -4706,6 +4737,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
   unsigned int i;
   bfd_vma max_alignment, reserve_size = 0;
   riscv_pcgp_relocs pcgp_relocs;
+  bfd_vma delete_bytes = 0;
 
   *again = false;
 
@@ -4941,7 +4973,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 
       if (!relax_func (abfd, sec, sym_sec, info, rel, symval,
 		       max_alignment, reserve_size, again,
-		       &pcgp_relocs, undefined_weak))
+		       &pcgp_relocs, undefined_weak, &delete_bytes))
 	goto fail;
     }
 
-- 
2.25.1

[PATCH v2 4/5] RISCV: Improve runtime of align directives

[Patrick O'Neill]

Align directives need an accurate count of the number of bytes to be
deleted. This can be computed using a running sum, giving us an O(n),
rather than O(n^2) runtime.

2022-04-29 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c (_bfd_riscv_relax_align): Rely on running
	  delete_bytes count when calculating alignment.
	* elfnn-riscv.c (_bfd_riscv_relax_section): Calculate running
	  deletion total during align pass.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
 bfd/elfnn-riscv.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 10e76e8628d..0e94021d39c 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4496,24 +4496,15 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 			bool *again ATTRIBUTE_UNUSED,
 			riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
 			bool undefined_weak ATTRIBUTE_UNUSED,
-			bfd_vma *delete_total ATTRIBUTE_UNUSED)
+			bfd_vma *delete_total)
 {
   bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
   bfd_vma alignment = 1, pos;
   while (alignment <= rel->r_addend)
     alignment *= 2;
 
-  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
-  for (unsigned int i = 0; i < sec->reloc_count; i++)
-    {
-      Elf_Internal_Rela *reloc = relocs + i;
-      /* Ignore annotations after this alignment directive.  */
-      if (reloc == rel)
-	break;
-      /* Account for to-be-deleted bytes  */
-      else if (ELFNN_R_TYPE (reloc->r_info) == R_RISCV_DELETE)
-	symval -= reloc->r_addend;
-    }
+  /* Account for to-be-deleted bytes.  */
+  symval -= *delete_total;
 
   symval -= rel->r_addend;
   bfd_vma aligned_addr = ((symval - 1) & ~(alignment - 1)) + alignment;
@@ -4549,6 +4540,9 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   if (nop_bytes % 4 != 0)
     bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
 
+  /* Account for the soon-to-be marked bytes.  */
+  *delete_total += rel->r_addend - nop_bytes;
+
   /* Mark the excess bytes for deletion.  */
   return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
 				   rel->r_addend - nop_bytes, rel);
@@ -4816,8 +4810,18 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (info->relax_pass == 1 && type == R_RISCV_ALIGN)
-	relax_func = _bfd_riscv_relax_align;
+      else if (info->relax_pass == 1)
+        {
+	  if (type == R_RISCV_ALIGN)
+	    relax_func = _bfd_riscv_relax_align;
+	  else if (type == R_RISCV_DELETE)
+	    {
+	      delete_bytes += rel->r_addend;
+	      continue;
+	    }
+	  else
+	    continue;
+	}
       else if (info->relax_pass == 2 && type == R_RISCV_DELETE)
 	relax_func = _bfd_riscv_relax_delete;
       else
-- 
2.25.1

[PATCH v2 5/5] RISCV: Add --defer-deletion flag

[Patrick O'Neill]

Previously the linker failed to relax only the backwards case (where a
relaxation enables another relaxation that has already been checked).
With patches 1-4, the behavior has been changed to fail in both the
forward and backwards case. It's possible that this will lead to worse
performance, so the --no-defer-deletion flag allows you to use the
non-linear immediate deletion method.
By default, the linear deletion method is enabled as this is expected to
be more performant.

2022-04-29 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c: Add if statements and expand function calls to
	  enable immediately deleting bytes.
	* bfdlink.h: Add delete_immediately flag.
	* ld/ld.texi: Document the new --defer-deletion flag.
	* ld/ldlex.h: Add DEFER_DELETION and NO_DEFER_DELETION options.
	* ld/lexsup.c: Parse --defer-deletion and --no-defer-deletion
	  flags.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
I think that there may be a better way to phrase the --defer-deletion
flag. I'm also unsure if this is the correct way of expressing
a target-specific linker flag.
---
v2 Changelog:
- This is a new patch.
---
 bfd/elfnn-riscv.c | 61 ++++++++++++++++++++++++++++++++++-------------
 include/bfdlink.h |  4 ++++
 ld/ld.texi        | 10 ++++++++
 ld/ldlex.h        |  2 ++
 ld/lexsup.c       | 10 ++++++++
 5 files changed, 70 insertions(+), 17 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 0e94021d39c..4f57e9bef03 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4092,18 +4092,27 @@ _bfd_riscv_relax_delete (bfd *abfd,
   /* Find the next DELETE reloc (if one exists).  */
   Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
   Elf_Internal_Rela *next_delete = NULL;
-  /* Since we only replace existing relocs and don't add new relocs, the
-     relocs are in sequential order. We can skip the relocs prior to this one,
-     making this search linear time.  */
-  int start = rel - relocs;
-  for (unsigned int i = start; i < sec->reloc_count; i++)
+  if (link_info->immediate_deletion && link_info->relax_pass == 0)
     {
-      next_delete = relocs + i;
-      if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
-	  && next_delete->r_offset > rel->r_offset)
-	break;
-      else
-	next_delete = NULL;
+      /* When performing non-linear time deletions, disable piecewise
+	 deletion.  */
+      *delete_total = 0;
+    }
+  else
+    {
+      /* Since we only replace existing relocs and don't add new relocs, the
+	 relocs are in sequential order. We can skip the relocs prior to this one,
+	 making this search linear time.  */
+      int start = rel - relocs;
+      for (unsigned int i = start; i < sec->reloc_count; i++)
+	{
+	  next_delete = relocs + i;
+	  if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
+	      && next_delete->r_offset > rel->r_offset)
+	    break;
+	  else
+	    next_delete = NULL;
+	}
     }
 
   size_t bytes_to_move;
@@ -4221,7 +4230,11 @@ _bfd_riscv_relax_delete (bfd *abfd,
 /* Delete some bytes from a section while relaxing.  */
 
 static bool
-riscv_relax_delete_bytes (bfd_vma addr,
+riscv_relax_delete_bytes (bfd *abfd,
+			  asection *sec,
+			  struct bfd_link_info *link_info,
+			  riscv_pcgp_relocs *pcgp_relocs,
+			  bfd_vma addr,
 			  size_t count,
 			  Elf_Internal_Rela *rel)
 {
@@ -4230,6 +4243,15 @@ riscv_relax_delete_bytes (bfd_vma addr,
   rel->r_offset = addr;
   rel->r_addend = count;
 
+  if (link_info != NULL && link_info->immediate_deletion
+      && link_info->relax_pass == 0)
+    {
+      /* Delete the bytes immediately (non-linear time).  */
+      bfd_vma count = 0;
+      _bfd_riscv_relax_delete (abfd, sec, NULL, link_info, rel, NULL, NULL, NULL,
+			       NULL, pcgp_relocs, NULL, &count);
+    }
+
   return true;
 }
 
@@ -4307,7 +4329,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
 
   /* Delete unnecessary JALR.  */
   *again = true;
-  return riscv_relax_delete_bytes (rel->r_offset + len, 8 - len, rel + 1);
+  return riscv_relax_delete_bytes (abfd, sec, link_info, pcgp_relocs,
+				   rel->r_offset + len, 8 - len, rel + 1);
 }
 
 /* Traverse all output sections and return the max alignment.  */
@@ -4401,7 +4424,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
 	  /* We can delete the unnecessary LUI and reuse the reloc.  */
 	  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
 	  *again = true;
-	  return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
+	  return riscv_relax_delete_bytes (abfd, sec, link_info, pcgp_relocs,
+					   rel->r_offset, 4, rel);
 
 	default:
 	  abort ();
@@ -4433,7 +4457,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
       rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
 
       *again = true;
-      return riscv_relax_delete_bytes (rel->r_offset + 2, 2, rel + 1);
+      return riscv_relax_delete_bytes (abfd, sec, link_info, pcgp_relocs,
+				       rel->r_offset + 2, 2, rel + 1);
     }
 
   return true;
@@ -4475,7 +4500,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
       /* We can delete the unnecessary instruction and reuse the reloc.  */
       rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
       *again = true;
-      return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
+      return riscv_relax_delete_bytes (abfd, sec, link_info, pcgp_relocs,
+				       rel->r_offset, 4, rel);
 
     default:
       abort ();
@@ -4544,7 +4570,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
   *delete_total += rel->r_addend - nop_bytes;
 
   /* Mark the excess bytes for deletion.  */
-  return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
+  return riscv_relax_delete_bytes (NULL, NULL, NULL, NULL,
+				   rel->r_offset + nop_bytes,
 				   rel->r_addend - nop_bytes, rel);
 }
 
diff --git a/include/bfdlink.h b/include/bfdlink.h
index 69fc9d33ff4..f81a00c9f94 100644
--- a/include/bfdlink.h
+++ b/include/bfdlink.h
@@ -568,6 +568,10 @@ struct bfd_link_info
        args_type structure in ldmain.c:main.  */
   signed int disable_target_specific_optimizations;
 
+  /* Enable or disable deferred deletion of linker relaxations.
+     This option is enabled my default.  */
+  unsigned int immediate_deletion: 1;
+
   /* Function callbacks.  */
   const struct bfd_link_callbacks *callbacks;
 
diff --git a/ld/ld.texi b/ld/ld.texi
index fc75e9b3625..393ce28e5e3 100644
--- a/ld/ld.texi
+++ b/ld/ld.texi
@@ -2186,6 +2186,16 @@ This option is ignored for Linux compatibility.
 @item -Qy
 This option is ignored for SVR4 compatibility.
 
+@cindex defer relaxation deletion
+@kindex --defer-relaxation-deletions
+@kindex --no-defer-relaxation-deletions
+@item --defer-relaxation-deletions
+@itemx --no-defer-relaxation-deletions
+Enable (or don't enable) linear time linker relaxations by deferring byte
+deletion. This assumes the pathologial case is rare. If the pathological case
+is common, disabling linear linking will improve performance.
+Default to linear time linker relaxation.
+
 @kindex --relax
 @cindex synthesizing linker
 @cindex relaxing addressing modes
diff --git a/ld/ldlex.h b/ld/ldlex.h
index bc58fea73cc..dc2375da096 100644
--- a/ld/ldlex.h
+++ b/ld/ldlex.h
@@ -54,6 +54,8 @@ enum option_values
   OPTION_OFORMAT,
   OPTION_RELAX,
   OPTION_NO_RELAX,
+  OPTION_DEFER_DELETION,
+  OPTION_NO_DEFER_DELETION,
   OPTION_NO_SYMBOLIC,
   OPTION_RETAIN_SYMBOLS_FILE,
   OPTION_RPATH,
diff --git a/ld/lexsup.c b/ld/lexsup.c
index 5acc47ed5a0..5067cad5d09 100644
--- a/ld/lexsup.c
+++ b/ld/lexsup.c
@@ -442,6 +442,10 @@ static const struct ld_option ld_options[] =
     '\0', NULL, N_("Reduce code size by using target specific optimizations"), TWO_DASHES },
   { {"no-relax", no_argument, NULL, OPTION_NO_RELAX},
     '\0', NULL, N_("Do not use relaxation techniques to reduce code size"), TWO_DASHES },
+  { {"defer-deletion", no_argument, NULL, OPTION_DEFER_DELETION},
+    '\0', NULL, N_("Defer deletions caused by linker relaxation"), TWO_DASHES },
+  { {"no-defer-deletion", no_argument, NULL, OPTION_NO_DEFER_DELETION},
+    '\0', NULL, N_("Do not defer deletions caused by linker relaxation"), TWO_DASHES },
   { {"retain-symbols-file", required_argument, NULL,
      OPTION_RETAIN_SYMBOLS_FILE},
     '\0', N_("FILE"), N_("Keep only symbols listed in FILE"), TWO_DASHES },
@@ -915,6 +919,12 @@ parse_args (unsigned argc, char **argv)
 	case OPTION_NON_CONTIGUOUS_REGIONS_WARNINGS:
 	  link_info.non_contiguous_regions_warnings = true;
 	  break;
+	case OPTION_DEFER_DELETION:
+	  link_info.immediate_deletion = false;
+	  break;
+	case OPTION_NO_DEFER_DELETION:
+	  link_info.immediate_deletion = true;
+	  break;
 	case 'e':
 	  lang_add_entry (optarg, true);
 	  break;
-- 
2.25.1

Re: [PATCH v2 3/5] RISCV: Implement piecewise deletion

[Nelson Chu]

Hi Patrick,

Thanks for giving us this great idea.  I would suggest that we don't
consider the alignment issues for now, and focus on how to reduce the
time of the normal relaxations, which includes lui, auipc, call and
tls le relaxations.  The current relax behavior are listed as follows,

Pass 1: For lui, call and tls le relaxations, delete the redundant
bytes immediately;  For auipc, we build the table (pcgp_relocs) to
chain the %pcrel_lo insn to the corresponding %pcrel_hi insn, and then
actually delete the bytes until next relax pass.

Pass 2: Delete the bytes for each R_RISCV_DELETE  which are marked for
auipc relaxations.

Pass 3: Handle alignment, delete the bytes immediately for each R_RISCV_ALIGN.

So the current relax order should be,
Pass 1 -> Pass 1 -> ... -> Pass 1 -> Pass 2 -> Pass 3.  Since we
delete the bytes for lui/call/tls_le relaxations immediately, the Pass
1 will be done multiple times until there are no any bytes deleted.
There is a problem here - the auipc will not be deleted until Pass 2,
so we will need to update the pcgp_relocs table every time.  You can
see the PR28410 for details,
https://sourceware.org/bugzilla/show_bug.cgi?id=28410.

According to your patches, the relax order will be updated to,
Pass 1 (Do not delete the bytes immediately) -> Pass 2 (Handle
alignment) -> Pass 3 (Piecewise delete bytes for
lui/auipc/call/tls_le/alignment)

I would suggest we continue to put the alignment relaxations at the
last relax pass, that would reduce a lot of problems, including losing
too many relax opportunities in pass 1.  Therefore, the order will be,

Pass 1 (Do not delete the bytes immediately) -> Pass 2 (Piecewise
delete bytes for lui/auipc/call/tls_le) -> Pass 3 (Handle alignment)

However, the order doesn't help to increase the chance to relax more,
since we actually delete the bytes in Pass 2, so we won't be doing the
Pass 1 as much as we could, we just do it once.  However, if we want
to delete the bytes in the separate relax pass, then we probably need
the "restart_relax" again, to do the "Pass 1 -> Pass 2" many times.
Please see the following deprecated patch,
https://sourceware.org/pipermail/binutils-cvs/2021-March/056052.html.

Or we probably have another solution without adding the restart_relax
flag.  If my understanding is correct (please feel free to tell me if
I'm wrong), we always delete the bytes and adjust the tables (reloc,
local and global symbol tables) only for "one input section", and
won't cross sections.  That means, we could create another table to
record the deleted bytes rather than marking them as R_RISCV_DELETE,
and then actually delete them at the end of the
_bfd_riscv_relax_section, for each input section.  So that the order
will be,

Pass 1 (record the deleted bytes for lui/auipc/call/tls_le, and then
actually piecewise delete them at the end of _bfd_riscv_relax_section)
-> Pass 1 -> ... -> Pass 1 -> Pass 2 (Handle alignment).

As for the improvement of alignment, we could discuss it in the later
patches.  I would like to accept the piecewise deletion for the
lui/auipc/call/tls_le relaxations first, so let us start by making
some progress here.

BTW, we don't need to update the pcgp_relocs tables in the
_bfd_riscv_relax_delete anymore, since we don't delete bytes
immediately for each relax pattern.

Thanks
Nelson

On Mon, May 2, 2022 at 9:54 PM Patrick O'Neill <patrick@rivosinc.com> wrote:
>
> Rather than deleting bytes immediately, we can first mark the bytes for
> deletion. Then, using piecewise deletion, we reduce the runtime from
> O(n^2) to O(n).
>
> By moving the logic from the riscv_relax_delete_bytes function into the
> RISCV_DELETE reloc handler, we can delete the bytes in a piecewise
> manner.
>
> 2022-04-29 Patrick O'Neill <patrick@rivosinc.com>
>
>         * elfnn-riscv.c: Move deletion logic into DELETE reloc handler
>           and replace with DELETE reloc creation logic.
>
> Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
> ---
> This change overwrites the R_RISCV_RELAX with a R_RISCV_DELETE reloc
> when a relaxation wants to delete bytes. If it was going to delete a
> reloc, we use that reloc rather than deleting it.
> ---
> v2 Changelog:
> - Arrange functions as to reduce the diff of each patch and make
>   reviewing more manageable
> ---
>  bfd/elfnn-riscv.c | 144 ++++++++++++++++++++++++++++------------------
>  1 file changed, 88 insertions(+), 56 deletions(-)
>
> diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
> index 17f9607744f..10e76e8628d 100644
> --- a/bfd/elfnn-riscv.c
> +++ b/bfd/elfnn-riscv.c
> @@ -4054,15 +4054,28 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
>      }
>  }
>
> -/* Delete some bytes from a section while relaxing.  */
> +typedef bool (*relax_func_t) (bfd *, asection *, asection *,
> +                             struct bfd_link_info *,
> +                             Elf_Internal_Rela *,
> +                             bfd_vma, bfd_vma, bfd_vma, bool *,
> +                             riscv_pcgp_relocs *,
> +                             bool undefined_weak, bfd_vma *);
> +
> +/* Delete the bytes for R_RISCV_DELETE.  */
>
>  static bool
> -riscv_relax_delete_bytes (bfd *abfd,
> -                         asection *sec,
> -                         bfd_vma addr,
> -                         size_t count,
> -                         struct bfd_link_info *link_info,
> -                         riscv_pcgp_relocs *p)
> +_bfd_riscv_relax_delete (bfd *abfd,
> +                        asection *sec,
> +                        asection *sym_sec ATTRIBUTE_UNUSED,
> +                        struct bfd_link_info *link_info,
> +                        Elf_Internal_Rela *rel,
> +                        bfd_vma symval ATTRIBUTE_UNUSED,
> +                        bfd_vma max_alignment ATTRIBUTE_UNUSED,
> +                        bfd_vma reserve_size ATTRIBUTE_UNUSED,
> +                        bool *again ATTRIBUTE_UNUSED,
> +                        riscv_pcgp_relocs *pcgp_relocs,
> +                        bool undefined_weak ATTRIBUTE_UNUSED,
> +                        bfd_vma *delete_total)
>  {
>    unsigned int i, symcount;
>    bfd_vma toaddr = sec->size;
> @@ -4072,9 +4085,42 @@ riscv_relax_delete_bytes (bfd *abfd,
>    struct bfd_elf_section_data *data = elf_section_data (sec);
>    bfd_byte *contents = data->this_hdr.contents;
>
> +  bfd_vma addr = rel->r_offset;
> +  size_t count = rel->r_addend;
> +  riscv_pcgp_relocs *p = pcgp_relocs;
> +
> +  /* Find the next DELETE reloc (if one exists).  */
> +  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
> +  Elf_Internal_Rela *next_delete = NULL;
> +  /* Since we only replace existing relocs and don't add new relocs, the
> +     relocs are in sequential order. We can skip the relocs prior to this one,
> +     making this search linear time.  */
> +  int start = rel - relocs;
> +  for (unsigned int i = start; i < sec->reloc_count; i++)
> +    {
> +      next_delete = relocs + i;
> +      if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
> +         && next_delete->r_offset > rel->r_offset)
> +       break;
> +      else
> +       next_delete = NULL;
> +    }
> +
> +  size_t bytes_to_move;
> +  /* Make this a piecewise deletion.  */
> +  if (next_delete == NULL)
> +    bytes_to_move = toaddr - addr - count;
> +  else
> +    bytes_to_move = next_delete->r_offset - addr - count;
> +
>    /* Actually delete the bytes.  */
>    sec->size -= count;
> -  memmove (contents + addr, contents + addr + count, toaddr - addr - count);
> +  memmove (contents + addr, contents + addr + count + *delete_total, bytes_to_move);
> +
> +  *delete_total += count;
> +
> +  /* Delete the reloc.  */
> +  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>
>    /* Adjust the location of all of the relocs.  Note that we need not
>       adjust the addends, since all PC-relative references must be against
> @@ -4172,12 +4218,20 @@ riscv_relax_delete_bytes (bfd *abfd,
>    return true;
>  }
>
> -typedef bool (*relax_func_t) (bfd *, asection *, asection *,
> -                             struct bfd_link_info *,
> -                             Elf_Internal_Rela *,
> -                             bfd_vma, bfd_vma, bfd_vma, bool *,
> -                             riscv_pcgp_relocs *,
> -                             bool undefined_weak);
> +/* Delete some bytes from a section while relaxing.  */
> +
> +static bool
> +riscv_relax_delete_bytes (bfd_vma addr,
> +                         size_t count,
> +                         Elf_Internal_Rela *rel)
> +{
> +  /* Mark bytes for deletion.  */
> +  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
> +  rel->r_offset = addr;
> +  rel->r_addend = count;
> +
> +  return true;
> +}
>
>  /* Relax AUIPC + JALR into JAL.  */
>
> @@ -4190,7 +4244,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
>                        bfd_vma reserve_size ATTRIBUTE_UNUSED,
>                        bool *again,
>                        riscv_pcgp_relocs *pcgp_relocs,
> -                      bool undefined_weak ATTRIBUTE_UNUSED)
> +                      bool undefined_weak ATTRIBUTE_UNUSED,
> +                      bfd_vma *delete_total ATTRIBUTE_UNUSED)
>  {
>    bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>    bfd_vma foff = symval - (sec_addr (sec) + rel->r_offset);
> @@ -4252,8 +4307,7 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
>
>    /* Delete unnecessary JALR.  */
>    *again = true;
> -  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
> -                                  link_info, pcgp_relocs);
> +  return riscv_relax_delete_bytes (rel->r_offset + len, 8 - len, rel + 1);
>  }
>
>  /* Traverse all output sections and return the max alignment.  */
> @@ -4286,7 +4340,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
>                       bfd_vma reserve_size,
>                       bool *again,
>                       riscv_pcgp_relocs *pcgp_relocs,
> -                     bool undefined_weak)
> +                     bool undefined_weak,
> +                     bfd_vma *delete_total ATTRIBUTE_UNUSED)
>  {
>    bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>    bfd_vma gp = riscv_global_pointer_value (link_info);
> @@ -4343,11 +4398,10 @@ _bfd_riscv_relax_lui (bfd *abfd,
>           return true;
>
>         case R_RISCV_HI20:
> -         /* We can delete the unnecessary LUI and reloc.  */
> +         /* We can delete the unnecessary LUI and reuse the reloc.  */
>           rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>           *again = true;
> -         return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4,
> -                                          link_info, pcgp_relocs);
> +         return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
>
>         default:
>           abort ();
> @@ -4379,8 +4433,7 @@ _bfd_riscv_relax_lui (bfd *abfd,
>        rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
>
>        *again = true;
> -      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2,
> -                                      link_info, pcgp_relocs);
> +      return riscv_relax_delete_bytes (rel->r_offset + 2, 2, rel + 1);
>      }
>
>    return true;
> @@ -4399,7 +4452,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
>                          bfd_vma reserve_size ATTRIBUTE_UNUSED,
>                          bool *again,
>                          riscv_pcgp_relocs *pcgp_relocs,
> -                        bool undefined_weak ATTRIBUTE_UNUSED)
> +                        bool undefined_weak ATTRIBUTE_UNUSED,
> +                        bfd_vma *delete_total ATTRIBUTE_UNUSED)
>  {
>    /* See if this symbol is in range of tp.  */
>    if (RISCV_CONST_HIGH_PART (tpoff (link_info, symval)) != 0)
> @@ -4418,11 +4472,10 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
>
>      case R_RISCV_TPREL_HI20:
>      case R_RISCV_TPREL_ADD:
> -      /* We can delete the unnecessary instruction and reloc.  */
> +      /* We can delete the unnecessary instruction and reuse the reloc.  */
>        rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>        *again = true;
> -      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info,
> -                                      pcgp_relocs);
> +      return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
>
>      default:
>        abort ();
> @@ -4442,7 +4495,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
>                         bfd_vma reserve_size ATTRIBUTE_UNUSED,
>                         bool *again ATTRIBUTE_UNUSED,
>                         riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
> -                       bool undefined_weak ATTRIBUTE_UNUSED)
> +                       bool undefined_weak ATTRIBUTE_UNUSED,
> +                       bfd_vma *delete_total ATTRIBUTE_UNUSED)
>  {
>    bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>    bfd_vma alignment = 1, pos;
> @@ -4496,10 +4550,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
>      bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
>
>    /* Mark the excess bytes for deletion.  */
> -  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
> -  rel->r_addend = rel->r_addend - nop_bytes;
> -  rel->r_offset = rel->r_offset + nop_bytes;
> -  return true;
> +  return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
> +                                  rel->r_addend - nop_bytes, rel);
>  }
>
>  /* Relax PC-relative references to GP-relative references.  */
> @@ -4515,7 +4567,8 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
>                      bfd_vma reserve_size,
>                      bool *again ATTRIBUTE_UNUSED,
>                      riscv_pcgp_relocs *pcgp_relocs,
> -                    bool undefined_weak)
> +                    bool undefined_weak,
> +                    bfd_vma *delete_total ATTRIBUTE_UNUSED)
>  {
>    bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>    bfd_vma gp = riscv_global_pointer_value (link_info);
> @@ -4654,28 +4707,6 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
>    return true;
>  }
>
> -/* Delete the bytes for R_RISCV_DELETE.  */
> -
> -static bool
> -_bfd_riscv_relax_delete (bfd *abfd,
> -                        asection *sec,
> -                        asection *sym_sec ATTRIBUTE_UNUSED,
> -                        struct bfd_link_info *link_info,
> -                        Elf_Internal_Rela *rel,
> -                        bfd_vma symval ATTRIBUTE_UNUSED,
> -                        bfd_vma max_alignment ATTRIBUTE_UNUSED,
> -                        bfd_vma reserve_size ATTRIBUTE_UNUSED,
> -                        bool *again ATTRIBUTE_UNUSED,
> -                        riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
> -                        bool undefined_weak ATTRIBUTE_UNUSED)
> -{
> -  if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend,
> -                                link_info, NULL))
> -    return false;
> -  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
> -  return true;
> -}
> -
>  /* Called by after_allocation to set the information of data segment
>     before relaxing.  */
>
> @@ -4706,6 +4737,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
>    unsigned int i;
>    bfd_vma max_alignment, reserve_size = 0;
>    riscv_pcgp_relocs pcgp_relocs;
> +  bfd_vma delete_bytes = 0;
>
>    *again = false;
>
> @@ -4941,7 +4973,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
>
>        if (!relax_func (abfd, sec, sym_sec, info, rel, symval,
>                        max_alignment, reserve_size, again,
> -                      &pcgp_relocs, undefined_weak))
> +                      &pcgp_relocs, undefined_weak, &delete_bytes))
>         goto fail;
>      }
>
> --
> 2.25.1
>

Re: [PATCH v2 3/5] RISCV: Implement piecewise deletion

[Patrick O'Neill]

On 5/20/22 03:48, Nelson Chu wrote:

> Hi Patrick,
>
> Thanks for giving us this great idea.  I would suggest that we don't
> consider the alignment issues for now, and focus on how to reduce the
> time of the normal relaxations, which includes lui, auipc, call and
> tls le relaxations.  The current relax behavior are listed as follows,
>
> Pass 1: For lui, call and tls le relaxations, delete the redundant
> bytes immediately;  For auipc, we build the table (pcgp_relocs) to
> chain the %pcrel_lo insn to the corresponding %pcrel_hi insn, and then
> actually delete the bytes until next relax pass.
>
> Pass 2: Delete the bytes for each R_RISCV_DELETE  which are marked for
> auipc relaxations.
>
> Pass 3: Handle alignment, delete the bytes immediately for each R_RISCV_ALIGN.
>
> So the current relax order should be,
> Pass 1 -> Pass 1 -> ... -> Pass 1 -> Pass 2 -> Pass 3.  Since we
> delete the bytes for lui/call/tls_le relaxations immediately, the Pass
> 1 will be done multiple times until there are no any bytes deleted.
> There is a problem here - the auipc will not be deleted until Pass 2,
> so we will need to update the pcgp_relocs table every time.  You can
> see the PR28410 for details,
> https://sourceware.org/bugzilla/show_bug.cgi?id=28410.
>
> According to your patches, the relax order will be updated to,
> Pass 1 (Do not delete the bytes immediately) -> Pass 2 (Handle
> alignment) -> Pass 3 (Piecewise delete bytes for
> lui/auipc/call/tls_le/alignment)
>
> I would suggest we continue to put the alignment relaxations at the
> last relax pass, that would reduce a lot of problems, including losing
> too many relax opportunities in pass 1.  Therefore, the order will be,
>
> Pass 1 (Do not delete the bytes immediately) -> Pass 2 (Piecewise
> delete bytes for lui/auipc/call/tls_le) -> Pass 3 (Handle alignment)

Hi Nelson,

Thanks for reviewing the patch! I had misunderstood the flow of the
passes. I had assumed that the flow was:

Pass 1 (again=true) -> Pass 2 (skipped when again is true) -> Pass 3
-> Pass 1 (again=false) -> Pass 2 (performed) -> Pass 3

Basically trying the whole sequence until again=false.

When I put a print statement to display the pass that is being performed
I get this output (isolating print statements from a single section id):

(relax-call-2.s from Patch 1/5)
Pass 0
Pass 0
Pass 1
Pass 2
Pass 0
Pass 1
Pass 2

The second pass through was what had tripped me up. Thanks for the
clarification.

> However, the order doesn't help to increase the chance to relax more,
> since we actually delete the bytes in Pass 2, so we won't be doing the
> Pass 1 as much as we could, we just do it once.  However, if we want
> to delete the bytes in the separate relax pass, then we probably need
> the "restart_relax" again, to do the "Pass 1 -> Pass 2" many times.
> Please see the following deprecated patch,
> https://sourceware.org/pipermail/binutils-cvs/2021-March/056052.html.
>
> Or we probably have another solution without adding the restart_relax
> flag.  If my understanding is correct (please feel free to tell me if
> I'm wrong), we always delete the bytes and adjust the tables (reloc,
> local and global symbol tables) only for "one input section", and
> won't cross sections.  That means, we could create another table to
> record the deleted bytes rather than marking them as R_RISCV_DELETE,
> and then actually delete them at the end of the
> _bfd_riscv_relax_section, for each input section.  So that the order
> will be,
>
> Pass 1 (record the deleted bytes for lui/auipc/call/tls_le, and then
> actually piecewise delete them at the end of _bfd_riscv_relax_section)
> -> Pass 1 -> ... -> Pass 1 -> Pass 2 (Handle alignment).

I agree that that would be better. I'll try implementing this - it
has the added benefit of being reusable for the alignment directives
in future patches. It's fundamentally the same issue - deleting bytes
piecewise per pass rather than immediately.

> As for the improvement of alignment, we could discuss it in the later
> patches.  I would like to accept the piecewise deletion for the
> lui/auipc/call/tls_le relaxations first, so let us start by making
> some progress here.

Sounds good.

> BTW, we don't need to update the pcgp_relocs tables in the
> _bfd_riscv_relax_delete anymore, since we don't delete bytes
> immediately for each relax pattern.

Thanks, I'll remove that for v3.

Thank you again for looking at this, linkers are complicated and I'm
still learning ;)

Thanks,
Patrick

>
> Thanks
> Nelson
>
> On Mon, May 2, 2022 at 9:54 PM Patrick O'Neill<patrick@rivosinc.com>  wrote:
>> Rather than deleting bytes immediately, we can first mark the bytes for
>> deletion. Then, using piecewise deletion, we reduce the runtime from
>> O(n^2) to O(n).
>>
>> By moving the logic from the riscv_relax_delete_bytes function into the
>> RISCV_DELETE reloc handler, we can delete the bytes in a piecewise
>> manner.
>>
>> 2022-04-29 Patrick O'Neill<patrick@rivosinc.com>
>>
>>          * elfnn-riscv.c: Move deletion logic into DELETE reloc handler
>>            and replace with DELETE reloc creation logic.
>>
>> Signed-off-by: Patrick O'Neill<patrick@rivosinc.com>
>> ---
>> This change overwrites the R_RISCV_RELAX with a R_RISCV_DELETE reloc
>> when a relaxation wants to delete bytes. If it was going to delete a
>> reloc, we use that reloc rather than deleting it.
>> ---
>> v2 Changelog:
>> - Arrange functions as to reduce the diff of each patch and make
>>    reviewing more manageable
>> ---
>>   bfd/elfnn-riscv.c | 144 ++++++++++++++++++++++++++++------------------
>>   1 file changed, 88 insertions(+), 56 deletions(-)
>>
>> diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
>> index 17f9607744f..10e76e8628d 100644
>> --- a/bfd/elfnn-riscv.c
>> +++ b/bfd/elfnn-riscv.c
>> @@ -4054,15 +4054,28 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
>>       }
>>   }
>>
>> -/* Delete some bytes from a section while relaxing.  */
>> +typedef bool (*relax_func_t) (bfd *, asection *, asection *,
>> +                             struct bfd_link_info *,
>> +                             Elf_Internal_Rela *,
>> +                             bfd_vma, bfd_vma, bfd_vma, bool *,
>> +                             riscv_pcgp_relocs *,
>> +                             bool undefined_weak, bfd_vma *);
>> +
>> +/* Delete the bytes for R_RISCV_DELETE.  */
>>
>>   static bool
>> -riscv_relax_delete_bytes (bfd *abfd,
>> -                         asection *sec,
>> -                         bfd_vma addr,
>> -                         size_t count,
>> -                         struct bfd_link_info *link_info,
>> -                         riscv_pcgp_relocs *p)
>> +_bfd_riscv_relax_delete (bfd *abfd,
>> +                        asection *sec,
>> +                        asection *sym_sec ATTRIBUTE_UNUSED,
>> +                        struct bfd_link_info *link_info,
>> +                        Elf_Internal_Rela *rel,
>> +                        bfd_vma symval ATTRIBUTE_UNUSED,
>> +                        bfd_vma max_alignment ATTRIBUTE_UNUSED,
>> +                        bfd_vma reserve_size ATTRIBUTE_UNUSED,
>> +                        bool *again ATTRIBUTE_UNUSED,
>> +                        riscv_pcgp_relocs *pcgp_relocs,
>> +                        bool undefined_weak ATTRIBUTE_UNUSED,
>> +                        bfd_vma *delete_total)
>>   {
>>     unsigned int i, symcount;
>>     bfd_vma toaddr = sec->size;
>> @@ -4072,9 +4085,42 @@ riscv_relax_delete_bytes (bfd *abfd,
>>     struct bfd_elf_section_data *data = elf_section_data (sec);
>>     bfd_byte *contents = data->this_hdr.contents;
>>
>> +  bfd_vma addr = rel->r_offset;
>> +  size_t count = rel->r_addend;
>> +  riscv_pcgp_relocs *p = pcgp_relocs;
>> +
>> +  /* Find the next DELETE reloc (if one exists).  */
>> +  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
>> +  Elf_Internal_Rela *next_delete = NULL;
>> +  /* Since we only replace existing relocs and don't add new relocs, the
>> +     relocs are in sequential order. We can skip the relocs prior to this one,
>> +     making this search linear time.  */
>> +  int start = rel - relocs;
>> +  for (unsigned int i = start; i < sec->reloc_count; i++)
>> +    {
>> +      next_delete = relocs + i;
>> +      if (ELFNN_R_TYPE (next_delete->r_info) == R_RISCV_DELETE
>> +         && next_delete->r_offset > rel->r_offset)
>> +       break;
>> +      else
>> +       next_delete = NULL;
>> +    }
>> +
>> +  size_t bytes_to_move;
>> +  /* Make this a piecewise deletion.  */
>> +  if (next_delete == NULL)
>> +    bytes_to_move = toaddr - addr - count;
>> +  else
>> +    bytes_to_move = next_delete->r_offset - addr - count;
>> +
>>     /* Actually delete the bytes.  */
>>     sec->size -= count;
>> -  memmove (contents + addr, contents + addr + count, toaddr - addr - count);
>> +  memmove (contents + addr, contents + addr + count + *delete_total, bytes_to_move);
>> +
>> +  *delete_total += count;
>> +
>> +  /* Delete the reloc.  */
>> +  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>>
>>     /* Adjust the location of all of the relocs.  Note that we need not
>>        adjust the addends, since all PC-relative references must be against
>> @@ -4172,12 +4218,20 @@ riscv_relax_delete_bytes (bfd *abfd,
>>     return true;
>>   }
>>
>> -typedef bool (*relax_func_t) (bfd *, asection *, asection *,
>> -                             struct bfd_link_info *,
>> -                             Elf_Internal_Rela *,
>> -                             bfd_vma, bfd_vma, bfd_vma, bool *,
>> -                             riscv_pcgp_relocs *,
>> -                             bool undefined_weak);
>> +/* Delete some bytes from a section while relaxing.  */
>> +
>> +static bool
>> +riscv_relax_delete_bytes (bfd_vma addr,
>> +                         size_t count,
>> +                         Elf_Internal_Rela *rel)
>> +{
>> +  /* Mark bytes for deletion.  */
>> +  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
>> +  rel->r_offset = addr;
>> +  rel->r_addend = count;
>> +
>> +  return true;
>> +}
>>
>>   /* Relax AUIPC + JALR into JAL.  */
>>
>> @@ -4190,7 +4244,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
>>                         bfd_vma reserve_size ATTRIBUTE_UNUSED,
>>                         bool *again,
>>                         riscv_pcgp_relocs *pcgp_relocs,
>> -                      bool undefined_weak ATTRIBUTE_UNUSED)
>> +                      bool undefined_weak ATTRIBUTE_UNUSED,
>> +                      bfd_vma *delete_total ATTRIBUTE_UNUSED)
>>   {
>>     bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>>     bfd_vma foff = symval - (sec_addr (sec) + rel->r_offset);
>> @@ -4252,8 +4307,7 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
>>
>>     /* Delete unnecessary JALR.  */
>>     *again = true;
>> -  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
>> -                                  link_info, pcgp_relocs);
>> +  return riscv_relax_delete_bytes (rel->r_offset + len, 8 - len, rel + 1);
>>   }
>>
>>   /* Traverse all output sections and return the max alignment.  */
>> @@ -4286,7 +4340,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
>>                        bfd_vma reserve_size,
>>                        bool *again,
>>                        riscv_pcgp_relocs *pcgp_relocs,
>> -                     bool undefined_weak)
>> +                     bool undefined_weak,
>> +                     bfd_vma *delete_total ATTRIBUTE_UNUSED)
>>   {
>>     bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>>     bfd_vma gp = riscv_global_pointer_value (link_info);
>> @@ -4343,11 +4398,10 @@ _bfd_riscv_relax_lui (bfd *abfd,
>>            return true;
>>
>>          case R_RISCV_HI20:
>> -         /* We can delete the unnecessary LUI and reloc.  */
>> +         /* We can delete the unnecessary LUI and reuse the reloc.  */
>>            rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>>            *again = true;
>> -         return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4,
>> -                                          link_info, pcgp_relocs);
>> +         return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
>>
>>          default:
>>            abort ();
>> @@ -4379,8 +4433,7 @@ _bfd_riscv_relax_lui (bfd *abfd,
>>         rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
>>
>>         *again = true;
>> -      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2,
>> -                                      link_info, pcgp_relocs);
>> +      return riscv_relax_delete_bytes (rel->r_offset + 2, 2, rel + 1);
>>       }
>>
>>     return true;
>> @@ -4399,7 +4452,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
>>                           bfd_vma reserve_size ATTRIBUTE_UNUSED,
>>                           bool *again,
>>                           riscv_pcgp_relocs *pcgp_relocs,
>> -                        bool undefined_weak ATTRIBUTE_UNUSED)
>> +                        bool undefined_weak ATTRIBUTE_UNUSED,
>> +                        bfd_vma *delete_total ATTRIBUTE_UNUSED)
>>   {
>>     /* See if this symbol is in range of tp.  */
>>     if (RISCV_CONST_HIGH_PART (tpoff (link_info, symval)) != 0)
>> @@ -4418,11 +4472,10 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
>>
>>       case R_RISCV_TPREL_HI20:
>>       case R_RISCV_TPREL_ADD:
>> -      /* We can delete the unnecessary instruction and reloc.  */
>> +      /* We can delete the unnecessary instruction and reuse the reloc.  */
>>         rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>>         *again = true;
>> -      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info,
>> -                                      pcgp_relocs);
>> +      return riscv_relax_delete_bytes (rel->r_offset, 4, rel);
>>
>>       default:
>>         abort ();
>> @@ -4442,7 +4495,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
>>                          bfd_vma reserve_size ATTRIBUTE_UNUSED,
>>                          bool *again ATTRIBUTE_UNUSED,
>>                          riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
>> -                       bool undefined_weak ATTRIBUTE_UNUSED)
>> +                       bool undefined_weak ATTRIBUTE_UNUSED,
>> +                       bfd_vma *delete_total ATTRIBUTE_UNUSED)
>>   {
>>     bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>>     bfd_vma alignment = 1, pos;
>> @@ -4496,10 +4550,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
>>       bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos);
>>
>>     /* Mark the excess bytes for deletion.  */
>> -  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
>> -  rel->r_addend = rel->r_addend - nop_bytes;
>> -  rel->r_offset = rel->r_offset + nop_bytes;
>> -  return true;
>> +  return riscv_relax_delete_bytes (rel->r_offset + nop_bytes,
>> +                                  rel->r_addend - nop_bytes, rel);
>>   }
>>
>>   /* Relax PC-relative references to GP-relative references.  */
>> @@ -4515,7 +4567,8 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
>>                       bfd_vma reserve_size,
>>                       bool *again ATTRIBUTE_UNUSED,
>>                       riscv_pcgp_relocs *pcgp_relocs,
>> -                    bool undefined_weak)
>> +                    bool undefined_weak,
>> +                    bfd_vma *delete_total ATTRIBUTE_UNUSED)
>>   {
>>     bfd_byte *contents = elf_section_data (sec)->this_hdr.contents;
>>     bfd_vma gp = riscv_global_pointer_value (link_info);
>> @@ -4654,28 +4707,6 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
>>     return true;
>>   }
>>
>> -/* Delete the bytes for R_RISCV_DELETE.  */
>> -
>> -static bool
>> -_bfd_riscv_relax_delete (bfd *abfd,
>> -                        asection *sec,
>> -                        asection *sym_sec ATTRIBUTE_UNUSED,
>> -                        struct bfd_link_info *link_info,
>> -                        Elf_Internal_Rela *rel,
>> -                        bfd_vma symval ATTRIBUTE_UNUSED,
>> -                        bfd_vma max_alignment ATTRIBUTE_UNUSED,
>> -                        bfd_vma reserve_size ATTRIBUTE_UNUSED,
>> -                        bool *again ATTRIBUTE_UNUSED,
>> -                        riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
>> -                        bool undefined_weak ATTRIBUTE_UNUSED)
>> -{
>> -  if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend,
>> -                                link_info, NULL))
>> -    return false;
>> -  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
>> -  return true;
>> -}
>> -
>>   /* Called by after_allocation to set the information of data segment
>>      before relaxing.  */
>>
>> @@ -4706,6 +4737,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
>>     unsigned int i;
>>     bfd_vma max_alignment, reserve_size = 0;
>>     riscv_pcgp_relocs pcgp_relocs;
>> +  bfd_vma delete_bytes = 0;
>>
>>     *again = false;
>>
>> @@ -4941,7 +4973,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
>>
>>         if (!relax_func (abfd, sec, sym_sec, info, rel, symval,
>>                         max_alignment, reserve_size, again,
>> -                      &pcgp_relocs, undefined_weak))
>> +                      &pcgp_relocs, undefined_weak, &delete_bytes))
>>          goto fail;
>>       }
>>
>> --
>> 2.25.1
>>

[PATCH v3 0/3] 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 (3):
  RISCV: Add linker relaxation tests
  RISCV: Implement piecewise deletion
  RISCV: Add --defer-deletion flag

 bfd/elfnn-riscv.c                          | 193 ++++++++++++++++-----
 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, 366 insertions(+), 46 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

[PATCH v3 1/3] RISCV: Add linker relaxation tests

[Patrick O'Neill]

Add basic tests for the behavior of relaxing function calls.
This covers behavior like relaxing a call, not relaxing a call, and
relaxing a call that is enabled by relaxing another call.

2022-05-27 Patrick O'Neill <patrick@rivosinc.com>

	* ld-riscv-elf.exp: Add testcases.
	* relax-call-1.d: Add new testcase.
	* relax-call-1.s: Likewise.
	* relax-call-2.d: Likewise.
	* relax-call-2.s: Likewise.
	* relax-call-3.d: Likewise.
	* relax-call-3.s: Likewise.
	* relax-call-4.d: Likewise.
	* relax-call-4.s: Likewise.
	* relax-call-5.d: Likewise.
	* relax-call-5.s: Likewise.
	* relax-call-6.d: Likewise.
	* relax-call-6.s: Likewise.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
 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 ++++++++++
 13 files changed, 193 insertions(+)
 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

diff --git a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
index 272424b33e3..60f7cc5f208 100644
--- a/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
+++ b/ld/testsuite/ld-riscv-elf/ld-riscv-elf.exp
@@ -119,6 +119,12 @@ proc run_relax_twice_test {} {
 }
 
 if [istarget "riscv*-*-*"] {
+    run_dump_test "relax-call-1"
+    run_dump_test "relax-call-2"
+    run_dump_test "relax-call-3"
+    run_dump_test "relax-call-4"
+    run_dump_test "relax-call-5"
+    run_dump_test "relax-call-6"
     run_dump_test "align-small-region"
     run_dump_test "call-relax"
     run_dump_test "pcgp-relax-01"
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.d b/ld/testsuite/ld-riscv-elf/relax-call-1.d
new file mode 100644
index 00000000000..3e7bfb500c9
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.d
@@ -0,0 +1,17 @@
+#source: relax-call-1.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-1.s b/ld/testsuite/ld-riscv-elf/relax-call-1.s
new file mode 100644
index 00000000000..7b81e28f99f
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-1.s
@@ -0,0 +1,7 @@
+	.text
+foo:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.d b/ld/testsuite/ld-riscv-elf/relax-call-2.d
new file mode 100644
index 00000000000..7481bea8c1e
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.d
@@ -0,0 +1,21 @@
+#source: relax-call-2.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-2.s b/ld/testsuite/ld-riscv-elf/relax-call-2.s
new file mode 100644
index 00000000000..7f5844a6789
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-2.s
@@ -0,0 +1,10 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.d b/ld/testsuite/ld-riscv-elf/relax-call-3.d
new file mode 100644
index 00000000000..5c49222e056
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.d
@@ -0,0 +1,25 @@
+#source: relax-call-3.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+
+.*<bar>:
+.*ret
+
+.*<baz>:
+.*ret
+
+.* <_start>:
+.*jal.* <foo>
+.*jal.* <bar>
+.*jal.* <baz>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-3.s b/ld/testsuite/ld-riscv-elf/relax-call-3.s
new file mode 100644
index 00000000000..66e7c02ca19
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-3.s
@@ -0,0 +1,13 @@
+	.text
+foo:
+	jr	ra
+bar:
+	jr	ra
+baz:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	call	baz
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.d b/ld/testsuite/ld-riscv-elf/relax-call-4.d
new file mode 100644
index 00000000000..09e939ca9b4
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.d
@@ -0,0 +1,19 @@
+#source: relax-call-4.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-4.s b/ld/testsuite/ld-riscv-elf/relax-call-4.s
new file mode 100644
index 00000000000..44eed0bc128
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-4.s
@@ -0,0 +1,8 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048570
+	.globl	_start
+_start:
+	call	foo
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.d b/ld/testsuite/ld-riscv-elf/relax-call-5.d
new file mode 100644
index 00000000000..d9f44e5f8a2
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.d
@@ -0,0 +1,23 @@
+#source: relax-call-5.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*auipc.*
+.*jalr.* <foo>
+.*jal.* <bar>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-5.s b/ld/testsuite/ld-riscv-elf/relax-call-5.s
new file mode 100644
index 00000000000..5605fb14e78
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-5.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048566
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	foo
+	call	bar
+	jr	ra
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.d b/ld/testsuite/ld-riscv-elf/relax-call-6.d
new file mode 100644
index 00000000000..c385ccb5511
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.d
@@ -0,0 +1,22 @@
+#source: relax-call-6.s
+#ld: --relax
+#objdump: -d
+
+
+.*:     file format .*
+
+
+Disassembly of section \.text:
+
+.*<foo>:
+.*ret
+.*\.\.\.
+
+.*<bar>:
+.*ret
+
+.* <_start>:
+.*jal.* <bar>
+.*jal.* <foo>
+.*ret
+#pass
\ No newline at end of file
diff --git a/ld/testsuite/ld-riscv-elf/relax-call-6.s b/ld/testsuite/ld-riscv-elf/relax-call-6.s
new file mode 100644
index 00000000000..6df73e108f4
--- /dev/null
+++ b/ld/testsuite/ld-riscv-elf/relax-call-6.s
@@ -0,0 +1,11 @@
+	.text
+foo:
+	jr	ra
+	.zero 1048560
+bar:
+	jr	ra
+	.globl	_start
+_start:
+	call	bar
+	call	foo
+	jr	ra
-- 
2.25.1

[PATCH v3 2/3] RISCV: Implement piecewise deletion

[Patrick O'Neill]

Rather than deleting bytes immediately, we can first mark the bytes for
deletion. Then, using piecewise deletion, we reduce the runtime from
O(n^2) to O(n).

2022-05-27 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c: Add piecewise deletion option (Disabled for
	  .align directives).

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
This change overwrites the R_RISCV_RELAX with a R_RISCV_DELETE reloc
when a relaxation wants to delete bytes. If it was going to delete a
reloc, we use that reloc rather than deleting it.
---
v2 Changelog:
- Arrange functions as to reduce the diff of each patch and make
  reviewing more manageable
v3 Changelog:
- Remove alignment-directive related code and condense into 2 passes
---
 bfd/elfnn-riscv.c | 189 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 143 insertions(+), 46 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 8f9f0d8a86a..4b6ea179442 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4054,15 +4054,17 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
     }
 }
 
-/* Delete some bytes from a section while relaxing.  */
+/* Delete the bytes for R_RISCV_DELETE.  */
 
 static bool
-riscv_relax_delete_bytes (bfd *abfd,
-			  asection *sec,
-			  bfd_vma addr,
-			  size_t count,
-			  struct bfd_link_info *link_info,
-			  riscv_pcgp_relocs *p)
+riscv_relax_delete (bfd *abfd,
+		    asection *sec,
+		    struct bfd_link_info *link_info,
+		    riscv_pcgp_relocs *p,
+		    Elf_Internal_Rela *rel,
+		    bfd_vma *delete_total,
+		    Elf_Internal_Rela **next_delete,
+		    bool piecewise)
 {
   unsigned int i, symcount;
   bfd_vma toaddr = sec->size;
@@ -4072,9 +4074,49 @@ riscv_relax_delete_bytes (bfd *abfd,
   struct bfd_elf_section_data *data = elf_section_data (sec);
   bfd_byte *contents = data->this_hdr.contents;
 
+  bfd_vma addr = rel->r_offset;
+  size_t count = rel->r_addend;
+
+  /* Find the next DELETE reloc (if one exists).  */
+  Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs;
+  *next_delete = NULL;
+  if (piecewise)
+    {
+       /* Since we only replace existing relocs and don't add new relocs, the
+	  relocs are in sequential order. We can skip the relocs prior to this one,
+	  making this search linear time.  */
+	int start = rel - relocs;
+	for (i = start; i < sec->reloc_count; i++)
+	{
+	  *next_delete = relocs + i;
+	  if (ELFNN_R_TYPE ((*next_delete)->r_info) == R_RISCV_DELETE
+	      && (*next_delete)->r_offset > rel->r_offset)
+	    break;
+	  else
+	    *next_delete = NULL;
+	}
+    }
+  else
+    {
+      /* When performing immediate deletions, disable the running total.  */
+      *delete_total = 0;
+    }
+
+  size_t bytes_to_move;
+  /* Make this a piecewise deletion.  */
+  if (*next_delete == NULL)
+    bytes_to_move = toaddr - addr - count;
+  else
+    bytes_to_move = (*next_delete)->r_offset - addr - count;
+
   /* Actually delete the bytes.  */
   sec->size -= count;
-  memmove (contents + addr, contents + addr + count, toaddr - addr - count);
+  memmove (contents + addr, contents + addr + count + *delete_total, bytes_to_move);
+
+  *delete_total += count;
+
+  /* Delete the reloc.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
 
   /* Adjust the location of all of the relocs.  Note that we need not
      adjust the addends, since all PC-relative references must be against
@@ -4085,7 +4127,7 @@ riscv_relax_delete_bytes (bfd *abfd,
 
   /* Adjust the hi_sec_off, and the hi_addr of any entries in the pcgp relocs
      table for which these values occur after the deleted bytes.  */
-  if (p)
+  if (!piecewise && p)
     riscv_update_pcgp_relocs (p, sec, addr, count);
 
   /* Adjust the local symbols defined in this section.  */
@@ -4172,6 +4214,35 @@ riscv_relax_delete_bytes (bfd *abfd,
   return true;
 }
 
+/* Delete some bytes from a section while relaxing.  */
+
+static bool
+riscv_relax_delete_bytes (bfd *abfd,
+			  asection *sec,
+			  bfd_vma addr,
+			  size_t count,
+			  Elf_Internal_Rela *rel,
+			  struct bfd_link_info *link_info,
+			  riscv_pcgp_relocs *p,
+			  bool piecewise)
+{
+  /* Mark bytes for deletion.  */
+  rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+  rel->r_offset = addr;
+  rel->r_addend = count;
+
+  /* Delete immediately.  */
+  if (!piecewise)
+    {
+      bfd_vma delete_total = 0;
+      Elf_Internal_Rela *next_delete = NULL;
+      riscv_relax_delete(abfd, sec, link_info, p, rel,
+			 &delete_total, &next_delete, false);
+    }
+
+  return true;
+}
+
 typedef bool (*relax_func_t) (bfd *, asection *, asection *,
 			      struct bfd_link_info *,
 			      Elf_Internal_Rela *,
@@ -4253,7 +4324,7 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
   /* Delete unnecessary JALR.  */
   *again = true;
   return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
-				   link_info, pcgp_relocs);
+				   rel + 1, link_info, pcgp_relocs, true);
 }
 
 /* Traverse all output sections and return the max alignment.  */
@@ -4343,11 +4414,10 @@ _bfd_riscv_relax_lui (bfd *abfd,
 	  return true;
 
 	case R_RISCV_HI20:
-	  /* We can delete the unnecessary LUI and reloc.  */
-	  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
+	  /* We can delete the unnecessary LUI and reuse the reloc.  */
 	  *again = true;
-	  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4,
-					   link_info, pcgp_relocs);
+	  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, rel,
+					   link_info, pcgp_relocs, true);
 
 	default:
 	  abort ();
@@ -4379,8 +4449,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
       rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI);
 
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2,
-				       link_info, pcgp_relocs);
+      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2, rel + 1,
+				       link_info, pcgp_relocs, true);
     }
 
   return true;
@@ -4418,11 +4488,11 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
 
     case R_RISCV_TPREL_HI20:
     case R_RISCV_TPREL_ADD:
-      /* We can delete the unnecessary instruction and reloc.  */
+      /* We can delete the unnecessary instruction and reuse the reloc.  */
       rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
       *again = true;
-      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info,
-				       pcgp_relocs);
+      return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, rel,
+				       link_info, pcgp_relocs, true);
 
     default:
       abort ();
@@ -4485,8 +4555,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 
   /* Delete the excess bytes.  */
   return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + nop_bytes,
-				   rel->r_addend - nop_bytes, link_info,
-				   NULL);
+				   rel->r_addend - nop_bytes, rel, link_info,
+				   NULL, false);
 }
 
 /* Relax PC-relative references to GP-relative references.  */
@@ -4641,28 +4711,6 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED,
   return true;
 }
 
-/* Delete the bytes for R_RISCV_DELETE.  */
-
-static bool
-_bfd_riscv_relax_delete (bfd *abfd,
-			 asection *sec,
-			 asection *sym_sec ATTRIBUTE_UNUSED,
-			 struct bfd_link_info *link_info,
-			 Elf_Internal_Rela *rel,
-			 bfd_vma symval ATTRIBUTE_UNUSED,
-			 bfd_vma max_alignment ATTRIBUTE_UNUSED,
-			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
-			 bool *again ATTRIBUTE_UNUSED,
-			 riscv_pcgp_relocs *pcgp_relocs ATTRIBUTE_UNUSED,
-			 bool undefined_weak ATTRIBUTE_UNUSED)
-{
-  if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend,
-				 link_info, NULL))
-    return false;
-  rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
-  return true;
-}
-
 /* Called by after_allocation to set the information of data segment
    before relaxing.  */
 
@@ -4771,9 +4819,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (info->relax_pass == 1 && type == R_RISCV_DELETE)
-	relax_func = _bfd_riscv_relax_delete;
-      else if (info->relax_pass == 2 && type == R_RISCV_ALIGN)
+      else if (info->relax_pass == 1 && type == R_RISCV_ALIGN)
 	relax_func = _bfd_riscv_relax_align;
       else
 	continue;
@@ -4932,6 +4978,57 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	goto fail;
     }
 
+  bfd_vma delete_total = 0;
+
+  /* Resolve DELETE relocs.  */
+  if (info->relax_pass == 0)
+    {
+      for (i = 0; i < sec->reloc_count; i++)
+	{
+	  Elf_Internal_Rela *rel = relocs + i;
+	  int type = ELFNN_R_TYPE (rel->r_info);
+
+	  if (type != R_RISCV_DELETE)
+	    continue;
+
+	  /* Get the value of the symbol referred to by the reloc.  */
+	  if (!(ELFNN_R_SYM (rel->r_info) < symtab_hdr->sh_info))
+	    {
+	      unsigned long indx;
+	      struct elf_link_hash_entry *h;
+
+	      indx = ELFNN_R_SYM (rel->r_info) - symtab_hdr->sh_info;
+	      h = elf_sym_hashes (abfd)[indx];
+
+	      while (h->root.type == bfd_link_hash_indirect
+		     || h->root.type == bfd_link_hash_warning)
+		h = (struct elf_link_hash_entry *) h->root.u.i.link;
+
+	      /* Disable the relaxation for ifunc.  */
+	      if (h != NULL && h->type == STT_GNU_IFUNC)
+		continue;
+
+	      if (!((h->root.type == bfd_link_hash_defined
+		     || h->root.type == bfd_link_hash_defweak)
+		    && h->root.u.def.section != NULL
+		    && h->root.u.def.section->output_section != NULL))
+		continue;
+	    }
+
+	  Elf_Internal_Rela *next_delete = NULL;
+
+	  if (!riscv_relax_delete (abfd, sec, info, &pcgp_relocs, rel,
+				   &delete_total, &next_delete, true))
+	    goto fail;
+
+	  /* Skip ahead to the next delete reloc.  */
+	  if (next_delete != NULL)
+	    i = next_delete - relocs - 1;
+	  else
+	    i = sec->reloc_count;
+	}
+    }
+
   ret = true;
 
  fail:
-- 
2.25.1

[PATCH v3 3/3] RISCV: Add --defer-deletion flag

[Patrick O'Neill]

Previously the linker failed to relax only the backwards case (where a
relaxation enables another relaxation that has already been checked).
With patches 1-4, the behavior has been changed to fail in both the
forward and backwards case. It's possible that this will lead to worse
performance, so the --no-defer-deletion flag allows you to use the
non-linear immediate deletion method.
By default, the linear deletion method is enabled as this is expected to
be more performant.

2022-05-27 Patrick O'Neill <patrick@rivosinc.com>

	* elfnn-riscv.c: Pass flag to deletion function to immediately
	  delete bytes (or not).
	* bfdlink.h: Add delete_immediately flag.
	* ld/ld.texi: Document the new --defer-deletion flag.
	* ld/ldlex.h: Add DEFER_DELETION and NO_DEFER_DELETION options.
	* ld/lexsup.c: Parse --defer-deletion and --no-defer-deletion
	  flags.

Signed-off-by: Patrick O'Neill <patrick@rivosinc.com>
---
I think that there may be a better way to phrase the --defer-deletion
flag. I'm also unsure if this is the correct way of expressing
a target-specific linker flag.
---
v2 Changelog:
- This is a new patch.
---
v3 Changelog:
- Rebase with changes to elfnn-riscv.c from patch 2/3.
---
 bfd/elfnn-riscv.c | 12 ++++++++----
 include/bfdlink.h |  4 ++++
 ld/ld.texi        | 10 ++++++++++
 ld/ldlex.h        |  2 ++
 ld/lexsup.c       | 10 ++++++++++
 5 files changed, 34 insertions(+), 4 deletions(-)

diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 4b6ea179442..0a750773d47 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4324,7 +4324,8 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec,
   /* Delete unnecessary JALR.  */
   *again = true;
   return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len,
-				   rel + 1, link_info, pcgp_relocs, true);
+				   rel + 1, link_info, pcgp_relocs,
+				   !link_info->immediate_deletion);
 }
 
 /* Traverse all output sections and return the max alignment.  */
@@ -4417,7 +4418,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
 	  /* We can delete the unnecessary LUI and reuse the reloc.  */
 	  *again = true;
 	  return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, rel,
-					   link_info, pcgp_relocs, true);
+					   link_info, pcgp_relocs,
+					   !link_info->immediate_deletion);
 
 	default:
 	  abort ();
@@ -4450,7 +4452,8 @@ _bfd_riscv_relax_lui (bfd *abfd,
 
       *again = true;
       return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2, rel + 1,
-				       link_info, pcgp_relocs, true);
+				       link_info, pcgp_relocs,
+				       !link_info->immediate_deletion);
     }
 
   return true;
@@ -4492,7 +4495,8 @@ _bfd_riscv_relax_tls_le (bfd *abfd,
       rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE);
       *again = true;
       return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, rel,
-				       link_info, pcgp_relocs, true);
+				       link_info, pcgp_relocs,
+				       !link_info->immediate_deletion);
 
     default:
       abort ();
diff --git a/include/bfdlink.h b/include/bfdlink.h
index 09a3ec01685..f6c87fbe911 100644
--- a/include/bfdlink.h
+++ b/include/bfdlink.h
@@ -587,6 +587,10 @@ struct bfd_link_info
        args_type structure in ldmain.c:main.  */
   signed int disable_target_specific_optimizations;
 
+  /* Enable or disable deferred deletion of linker relaxations.
+     This option is enabled my default.  */
+  unsigned int immediate_deletion: 1;
+
   /* Function callbacks.  */
   const struct bfd_link_callbacks *callbacks;
 
diff --git a/ld/ld.texi b/ld/ld.texi
index eabbec8faa9..c536eed4162 100644
--- a/ld/ld.texi
+++ b/ld/ld.texi
@@ -2186,6 +2186,16 @@ This option is ignored for Linux compatibility.
 @item -Qy
 This option is ignored for SVR4 compatibility.
 
+@cindex defer relaxation deletion
+@kindex --defer-relaxation-deletions
+@kindex --no-defer-relaxation-deletions
+@item --defer-relaxation-deletions
+@itemx --no-defer-relaxation-deletions
+Enable (or don't enable) linear time linker relaxations by deferring byte
+deletion. This assumes the pathologial case is rare. If the pathological case
+is common, disabling linear linking will improve performance.
+Default to linear time linker relaxation.
+
 @kindex --relax
 @cindex synthesizing linker
 @cindex relaxing addressing modes
diff --git a/ld/ldlex.h b/ld/ldlex.h
index 57ade1f754b..ce9f5d5aafe 100644
--- a/ld/ldlex.h
+++ b/ld/ldlex.h
@@ -54,6 +54,8 @@ enum option_values
   OPTION_OFORMAT,
   OPTION_RELAX,
   OPTION_NO_RELAX,
+  OPTION_DEFER_DELETION,
+  OPTION_NO_DEFER_DELETION,
   OPTION_NO_SYMBOLIC,
   OPTION_RETAIN_SYMBOLS_FILE,
   OPTION_RPATH,
diff --git a/ld/lexsup.c b/ld/lexsup.c
index 9225f71b3ce..1a0d9a31fef 100644
--- a/ld/lexsup.c
+++ b/ld/lexsup.c
@@ -442,6 +442,10 @@ static const struct ld_option ld_options[] =
     '\0', NULL, N_("Reduce code size by using target specific optimizations"), TWO_DASHES },
   { {"no-relax", no_argument, NULL, OPTION_NO_RELAX},
     '\0', NULL, N_("Do not use relaxation techniques to reduce code size"), TWO_DASHES },
+  { {"defer-deletion", no_argument, NULL, OPTION_DEFER_DELETION},
+    '\0', NULL, N_("Defer deletions caused by linker relaxation"), TWO_DASHES },
+  { {"no-defer-deletion", no_argument, NULL, OPTION_NO_DEFER_DELETION},
+    '\0', NULL, N_("Do not defer deletions caused by linker relaxation"), TWO_DASHES },
   { {"retain-symbols-file", required_argument, NULL,
      OPTION_RETAIN_SYMBOLS_FILE},
     '\0', N_("FILE"), N_("Keep only symbols listed in FILE"), TWO_DASHES },
@@ -935,6 +939,12 @@ parse_args (unsigned argc, char **argv)
 	case OPTION_NO_WARN_RWX_SEGMENTS:
 	  link_info.no_warn_rwx_segments = 1;
 	  break;
+	case OPTION_DEFER_DELETION:
+	  link_info.immediate_deletion = false;
+	  break;
+	case OPTION_NO_DEFER_DELETION:
+	  link_info.immediate_deletion = true;
+	  break;
 	case 'e':
 	  lang_add_entry (optarg, true);
 	  break;
-- 
2.25.1