From: Patrick O'Neill <patrick@rivosinc.com>
To: binutils@sourceware.org
Cc: gnu-toolchain@rivosinc.com, palmer@dabbelt.com,
andrew@sifive.com, Patrick O'Neill <patrick@rivosinc.com>
Subject: [PATCH 4/4] RISCV: Improve runtime of align directives
Date: Tue, 12 Apr 2022 09:26:01 -0700 [thread overview]
Message-ID: <20220412162601.146507-5-patrick@rivosinc.com> (raw)
In-Reply-To: <20220412162601.146507-1-patrick@rivosinc.com>
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
next prev parent reply other threads:[~2022-04-12 16:26 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-04-12 16:25 [PATCH 0/4] RISCV: Improve linker time complexity Patrick O'Neill
2022-04-12 16:25 ` [PATCH 1/4] RISCV: Add linker relaxation tests Patrick O'Neill
2022-04-12 16:25 ` [PATCH 2/4] RISCV: Arrange DELETE pass after .align pass Patrick O'Neill
2022-04-12 16:26 ` [PATCH 3/4] RISCV: Implement piecewise deletion Patrick O'Neill
2022-04-12 16:26 ` Patrick O'Neill [this message]
2022-04-13 0:58 ` [PATCH 0/4] RISCV: Improve linker time complexity Kito Cheng
2022-04-13 2:23 ` Palmer Dabbelt
2022-04-13 5:12 ` Alan Modra
2022-04-13 18:11 ` Palmer Dabbelt
2022-04-25 17:26 ` Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 0/5] " Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 1/5] RISCV: Add linker relaxation tests Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 2/5] RISCV: Arrange DELETE pass after .align pass Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 3/5] RISCV: Implement piecewise deletion Patrick O'Neill
2022-05-20 10:48 ` Nelson Chu
2022-05-20 17:36 ` Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 4/5] RISCV: Improve runtime of align directives Patrick O'Neill
2022-05-02 13:50 ` [PATCH v2 5/5] RISCV: Add --defer-deletion flag Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 0/3] RISCV: Improve linker time complexity Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 1/3] RISCV: Add linker relaxation tests Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 2/3] RISCV: Implement piecewise deletion Patrick O'Neill
2022-05-27 21:20 ` [PATCH v3 3/3] RISCV: Add --defer-deletion flag Patrick O'Neill
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220412162601.146507-5-patrick@rivosinc.com \
--to=patrick@rivosinc.com \
--cc=andrew@sifive.com \
--cc=binutils@sourceware.org \
--cc=gnu-toolchain@rivosinc.com \
--cc=palmer@dabbelt.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).