[PATCH 4/4] RISCV: Improve runtime of align directives
Patrick O'Neill
patrick@rivosinc.com
Tue Apr 12 16:26:01 GMT 2022
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
More information about the Binutils
mailing list