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

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

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