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

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