[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