From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1030.google.com (mail-pj1-x1030.google.com [IPv6:2607:f8b0:4864:20::1030]) by sourceware.org (Postfix) with ESMTPS id E997B383919B for ; Fri, 27 May 2022 21:20:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E997B383919B 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-pj1-x1030.google.com with SMTP id l20-20020a17090a409400b001dd2a9d555bso5416196pjg.0 for ; Fri, 27 May 2022 14:20:43 -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=jAVvGFVMtlVkJkAv5ErOFmgtThTcPT44Vyl/IdQrTdA=; b=fxWRlsxfhmPwy5Wi2kNOW+vznG22h4fDY8zP+DTCDDsMxFgMkKsa9uQ7QI5EGxeKbA DFRiQVenOyrx2Vv0UW5w63JhjWMKnA5IQgTNYlLZgBKn1kj2iXipe5G9Xt09uUECoOzG vH8XQhUe94UAroc1eRgWw/fnFxUlOAf+FXu74nKRxJKOeQxs99b3L/UnVuPnDN9nepld 6qXu9eZ/LFq9k6SUdcaEj9HH+nre/1X+sX/EROhHURsDcR/6fQCr1sMtmHrQcEikhd8u lppjMG/3V5nHx9klNKLLL7XOlvqtWUXB8ZKHdz6WtHcB9a+6xvN/kEOGbO4qg05j7YDt VqzA== 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=jAVvGFVMtlVkJkAv5ErOFmgtThTcPT44Vyl/IdQrTdA=; b=oroJGKTmLCUwOuO5RMStoBPQZ/13gz29oA1Ol35rJOVn7bWvnBO/O2gQHf3eK6aTgN oemvq48dQGTSGxZUdYy68O+T+Ktb267GIxWohYGj8pDpUH4nW1I3b6kSXLIGb1VgzK6p Dg/YHV2hPON3PYtVvltqr5ZHoJRpY2y+LUso33hgFhaL6ZVQiRHD2Wtiqs1n3TqJZV0z HOKcy//1m88mhsgGnA5yTKnYV2fQZyVweZ16Y2U0FHowXCzk3k3huNuuGmCyOwlTG2Bx jKKeLqGQjI0W3q+yZO9+fh5ms1HZmELDO0BjQ2hVEu4EeBAB4TyLr8dJhqTSZ1HjuucV Tt3Q== X-Gm-Message-State: AOAM532Epsek4Gra74DIsjUMWJzwaxAxZivX3b7uz63yMvZKWtdzfE3P gSpogrLaAd2+NrsYeq3EJq8l7CNVX7XCfg== X-Google-Smtp-Source: ABdhPJxlNf2x2R5T6QgCec+C1wL3P6cYSmG3M8BTXubD1c1TDxqW2r6jSZTrYRLlhWXX068puObNiw== X-Received: by 2002:a17:902:8342:b0:163:783a:3474 with SMTP id z2-20020a170902834200b00163783a3474mr10277260pln.8.1653686442503; Fri, 27 May 2022 14:20:42 -0700 (PDT) Received: from patrick-ThinkPad-X1-Carbon-Gen-8.hq.rivosinc.com ([12.3.194.138]) by smtp.gmail.com with ESMTPSA id o20-20020a63fb14000000b003ed6b3dc52esm3901320pgh.55.2022.05.27.14.20.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 May 2022 14:20:41 -0700 (PDT) From: Patrick O'Neill To: binutils@sourceware.org, nelson.chu@sifive.com Cc: gnu-toolchain@rivosinc.com, jim.wilson.gcc@gmail.com, palmer@rivosinc.com, andrew@sifive.com, kito.cheng@gmail.com, Patrick O'Neill Subject: [PATCH v3 2/3] RISCV: Implement piecewise deletion Date: Fri, 27 May 2022 14:20:04 -0700 Message-Id: <20220527212005.30709-3-patrick@rivosinc.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220527212005.30709-1-patrick@rivosinc.com> References: <20220502135048.1392596-1-patrick@rivosinc.com> <20220527212005.30709-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Fri, 27 May 2022 21:20:46 -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). 2022-05-27 Patrick O'Neill * elfnn-riscv.c: Add piecewise deletion option (Disabled for .align directives). 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 v3 Changelog: - Remove alignment-directive related code and condense into 2 passes --- bfd/elfnn-riscv.c | 189 +++++++++++++++++++++++++++++++++++----------- 1 file changed, 143 insertions(+), 46 deletions(-) diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c index 8f9f0d8a86a..4b6ea179442 100644 --- a/bfd/elfnn-riscv.c +++ b/bfd/elfnn-riscv.c @@ -4054,15 +4054,17 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec, } } -/* Delete some bytes from a section while relaxing. */ +/* 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) +riscv_relax_delete (bfd *abfd, + asection *sec, + struct bfd_link_info *link_info, + riscv_pcgp_relocs *p, + Elf_Internal_Rela *rel, + bfd_vma *delete_total, + Elf_Internal_Rela **next_delete, + bool piecewise) { unsigned int i, symcount; bfd_vma toaddr = sec->size; @@ -4072,9 +4074,49 @@ 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; + + /* Find the next DELETE reloc (if one exists). */ + Elf_Internal_Rela *relocs = elf_section_data (sec)->relocs; + *next_delete = NULL; + if (piecewise) + { + /* 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 (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; + } + } + else + { + /* When performing immediate deletions, disable the running total. */ + *delete_total = 0; + } + + 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 @@ -4085,7 +4127,7 @@ riscv_relax_delete_bytes (bfd *abfd, /* Adjust the hi_sec_off, and the hi_addr of any entries in the pcgp relocs table for which these values occur after the deleted bytes. */ - if (p) + if (!piecewise && p) riscv_update_pcgp_relocs (p, sec, addr, count); /* Adjust the local symbols defined in this section. */ @@ -4172,6 +4214,35 @@ riscv_relax_delete_bytes (bfd *abfd, return true; } +/* Delete some bytes from a section while relaxing. */ + +static bool +riscv_relax_delete_bytes (bfd *abfd, + asection *sec, + bfd_vma addr, + size_t count, + Elf_Internal_Rela *rel, + struct bfd_link_info *link_info, + riscv_pcgp_relocs *p, + bool piecewise) +{ + /* Mark bytes for deletion. */ + rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE); + rel->r_offset = addr; + rel->r_addend = count; + + /* Delete immediately. */ + if (!piecewise) + { + bfd_vma delete_total = 0; + Elf_Internal_Rela *next_delete = NULL; + riscv_relax_delete(abfd, sec, link_info, p, rel, + &delete_total, &next_delete, false); + } + + return true; +} + typedef bool (*relax_func_t) (bfd *, asection *, asection *, struct bfd_link_info *, Elf_Internal_Rela *, @@ -4253,7 +4324,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); + rel + 1, link_info, pcgp_relocs, true); } /* Traverse all output sections and return the max alignment. */ @@ -4343,11 +4414,10 @@ _bfd_riscv_relax_lui (bfd *abfd, return true; case R_RISCV_HI20: - /* We can delete the unnecessary LUI and reloc. */ - rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE); + /* We can delete the unnecessary LUI and reuse the reloc. */ *again = true; - return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, - link_info, pcgp_relocs); + return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, rel, + link_info, pcgp_relocs, true); default: abort (); @@ -4379,8 +4449,8 @@ _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 (abfd, sec, rel->r_offset + 2, 2, rel + 1, + link_info, pcgp_relocs, true); } return true; @@ -4418,11 +4488,11 @@ _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 (abfd, sec, rel->r_offset, 4, rel, + link_info, pcgp_relocs, true); default: abort (); @@ -4485,8 +4555,8 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec, /* Delete the excess bytes. */ return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + nop_bytes, - rel->r_addend - nop_bytes, link_info, - NULL); + rel->r_addend - nop_bytes, rel, link_info, + NULL, false); } /* Relax PC-relative references to GP-relative references. */ @@ -4641,28 +4711,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. */ @@ -4771,9 +4819,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec, /* Skip over the R_RISCV_RELAX. */ i++; } - else if (info->relax_pass == 1 && type == R_RISCV_DELETE) - relax_func = _bfd_riscv_relax_delete; - else if (info->relax_pass == 2 && type == R_RISCV_ALIGN) + else if (info->relax_pass == 1 && type == R_RISCV_ALIGN) relax_func = _bfd_riscv_relax_align; else continue; @@ -4932,6 +4978,57 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec, goto fail; } + bfd_vma delete_total = 0; + + /* Resolve DELETE relocs. */ + if (info->relax_pass == 0) + { + for (i = 0; i < sec->reloc_count; i++) + { + Elf_Internal_Rela *rel = relocs + i; + int type = ELFNN_R_TYPE (rel->r_info); + + if (type != R_RISCV_DELETE) + continue; + + /* Get the value of the symbol referred to by the reloc. */ + if (!(ELFNN_R_SYM (rel->r_info) < symtab_hdr->sh_info)) + { + unsigned long indx; + struct elf_link_hash_entry *h; + + indx = ELFNN_R_SYM (rel->r_info) - symtab_hdr->sh_info; + h = elf_sym_hashes (abfd)[indx]; + + while (h->root.type == bfd_link_hash_indirect + || h->root.type == bfd_link_hash_warning) + h = (struct elf_link_hash_entry *) h->root.u.i.link; + + /* Disable the relaxation for ifunc. */ + if (h != NULL && h->type == STT_GNU_IFUNC) + continue; + + if (!((h->root.type == bfd_link_hash_defined + || h->root.type == bfd_link_hash_defweak) + && h->root.u.def.section != NULL + && h->root.u.def.section->output_section != NULL)) + continue; + } + + Elf_Internal_Rela *next_delete = NULL; + + if (!riscv_relax_delete (abfd, sec, info, &pcgp_relocs, rel, + &delete_total, &next_delete, true)) + goto fail; + + /* Skip ahead to the next delete reloc. */ + if (next_delete != NULL) + i = next_delete - relocs - 1; + else + i = sec->reloc_count; + } + } + ret = true; fail: -- 2.25.1