From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x836.google.com (mail-qt1-x836.google.com [IPv6:2607:f8b0:4864:20::836]) by sourceware.org (Postfix) with ESMTPS id BD0423857805 for ; Mon, 2 May 2022 13:51:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BD0423857805 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivosinc.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rivosinc.com Received: by mail-qt1-x836.google.com with SMTP id o18so11094999qtk.7 for ; Mon, 02 May 2022 06:51:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rivosinc-com.20210112.gappssmtp.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=9amUub0tVpfE1upi/MwaF0sDlZhlaU9cllalGccenX4=; b=zixl34GMgJo5m+6TqGO9P3o4hc2rcWYPw4CZRYrgf9sKOmwB6rK4WVTgJ9vYPzMq+g LaZ4KD33iadNnCCVp9BQrzYhazDp1GvfJ0uzY6emlChZi7p3LS5GAtYK1Oist7awPI8a SmyzOPUlHSNm7g6OhXfajEXuetsIFbbWcp1wpc/GgU3Yv/+zaN+iIlU4Qpfhi1jrXYW4 nEszHw5t0eXPI3k/GDW8OIDA1P3yJJQPGykLnyzMiue95noSC91HCiRTcdGhQMGWUzIE l8Mvf/X3z5gosDHRqNahZmb93woJDIJn5qa1J4dzfuya4Uclsk4oTWeoEOXP8HIcTR5j 01gA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=9amUub0tVpfE1upi/MwaF0sDlZhlaU9cllalGccenX4=; b=yVQIFqBPwv42KEaXBHqA5PNv2KamEwO2DxOGBdTRNb+uc+6gZlPAiSGUXKOO7TWErc pRjpMFco+m3RswFjVpxxmc8Ofwav1HGc8J/qt2gHw9E1LzldFlr0Fl7pZEf+wZmnmndA iiGGfz4ojTrn2c8upcs11e0epI5ilNyW4XKxKjBiiflhsfHOQGx47KIwV41eHD0cjVQq KaSo3WJKeEPwhYK3abFmhHMPKwHCddRMOrnQNYHrGlOwDnSbbF3DcbVvw0OIS66RVtoq 6O25/o6zl5BxDPj28t+FsMOT7O0BfxdrImZfIu61II4gap4ECDK9EkvAD2WkG2gJKnXf 2IYA== X-Gm-Message-State: AOAM533pmTfrEllorvdSFkx7rUsmWIMLNs71CGiZoh8kx4W8DiemS/Gj djec/IrqkJabTVoeEnLcb+DFN/QXSF/vEQ== X-Google-Smtp-Source: ABdhPJw9gaeGHbuaPAiryRU9ACQkkJpXp2WytthBX5PpvG+0AOz3v4S7v743aZM0hK6Rg3e1RrEUjg== X-Received: by 2002:ac8:5a10:0:b0:2f3:90c5:5f0c with SMTP id n16-20020ac85a10000000b002f390c55f0cmr10582630qta.121.1651499499695; Mon, 02 May 2022 06:51:39 -0700 (PDT) Received: from localhost.localdomain ([38.101.220.237]) by smtp.gmail.com with ESMTPSA id v19-20020ac873d3000000b002f39b99f69asm4232132qtp.52.2022.05.02.06.51.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 May 2022 06:51:38 -0700 (PDT) From: Patrick O'Neill To: binutils@sourceware.org Cc: kito.cheng@gmail.com, palmer@dabbelt.com, gnu-toolchain@rivosinc.com, Patrick O'Neill Subject: [PATCH v2 3/5] RISCV: Implement piecewise deletion Date: Mon, 2 May 2022 06:50:46 -0700 Message-Id: <20220502135048.1392596-4-patrick@rivosinc.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220502135048.1392596-1-patrick@rivosinc.com> References: <20220412162601.146507-1-patrick@rivosinc.com> <20220502135048.1392596-1-patrick@rivosinc.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 02 May 2022 13:51:43 -0000 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 * elfnn-riscv.c: Move deletion logic into DELETE reloc handler and replace with DELETE reloc creation logic. Signed-off-by: Patrick O'Neill --- 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