[PATCH v2 3/5] RISCV: Implement piecewise deletion
Patrick O'Neill
patrick@rivosinc.com
Mon May 2 13:50:46 GMT 2022
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-29 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.
---
v2 Changelog:
- Arrange functions as to reduce the diff of each patch and make
reviewing more manageable
---
bfd/elfnn-riscv.c | 144 ++++++++++++++++++++++++++++------------------
1 file changed, 88 insertions(+), 56 deletions(-)
diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index 17f9607744f..10e76e8628d 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -4054,15 +4054,28 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec,
}
}
-/* Delete some bytes from a section while relaxing. */
+typedef bool (*relax_func_t) (bfd *, asection *, asection *,
+ struct bfd_link_info *,
+ Elf_Internal_Rela *,
+ bfd_vma, bfd_vma, bfd_vma, bool *,
+ riscv_pcgp_relocs *,
+ bool undefined_weak, bfd_vma *);
+
+/* 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)
+_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,
+ bool undefined_weak ATTRIBUTE_UNUSED,
+ bfd_vma *delete_total)
{
unsigned int i, symcount;
bfd_vma toaddr = sec->size;
@@ -4072,9 +4085,42 @@ 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;
+ 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, 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
@@ -4172,12 +4218,20 @@ riscv_relax_delete_bytes (bfd *abfd,
return true;
}
-typedef bool (*relax_func_t) (bfd *, asection *, asection *,
- struct bfd_link_info *,
- Elf_Internal_Rela *,
- bfd_vma, bfd_vma, bfd_vma, bool *,
- riscv_pcgp_relocs *,
- bool undefined_weak);
+/* Delete some bytes from a section while relaxing. */
+
+static bool
+riscv_relax_delete_bytes (bfd_vma addr,
+ size_t count,
+ Elf_Internal_Rela *rel)
+{
+ /* Mark bytes for deletion. */
+ rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE);
+ rel->r_offset = addr;
+ rel->r_addend = count;
+
+ return true;
+}
/* Relax AUIPC + JALR into JAL. */
@@ -4190,7 +4244,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 +4307,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 +4340,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 +4398,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 +4433,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 +4452,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 +4472,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 +4495,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 +4550,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 +4567,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);
@@ -4654,28 +4707,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. */
@@ -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
More information about the Binutils
mailing list