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

[Patrick O'Neill <patrick@rivosinc.com>]

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