From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com [IPv6:2607:f8b0:4864:20::536]) by sourceware.org (Postfix) with ESMTPS id 3B36F3858418 for ; Tue, 12 Apr 2022 16:26:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3B36F3858418 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-pg1-x536.google.com with SMTP id r66so17722441pgr.3 for ; Tue, 12 Apr 2022 09:26: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=yPpb3ZPosR5QHkJZd9yh8Hd/mHsr1p/H8KFtOeQftXU=; b=K0YNPG9VtdyazaPptBh/G88P+Em0lBy5M408ZEhR1Xvz3fyZ72IhS7ZObztukKQ5t1 TZ9VuAujoxSOrgQ5sJcw9qnzGOyOCUSnjscYbZ4gC9El5tO0nfIpygPE82fFsVLjpmdf K5+3B0TunAWRtQ7yjzmdxkBVDkfxjFSSkcBdtQ79bz+jaDFurM8PKIVxjc/X+wZ5l7S/ X4Td34dGR5suNZaB1F+6WQzpN/I1hyjuo92W9kfc6wgsQTaloVy2Bo5aVhNkf5xG9pyn 9eMchfZaYk/UzprJhuwgK4kmFl5ina/5HVzQzKSl/GnO59Ji0LcwYyaO3wFGyptd/+gb czvw== 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=yPpb3ZPosR5QHkJZd9yh8Hd/mHsr1p/H8KFtOeQftXU=; b=KqHHuIG+PGl3CHTDwgkvSjsNwRuh24kCsRPHoLfsjEAXpLYGBPBk3n9ilmgAjqUPMs r3zxuKQXxtMELNKfYhCGh94RyxdL+tNIkZO7RTXZjJg3Ozx0i4ESne5+u+GUlrX9mPZ1 xn94HMwqbkJshUcu0NNcGyJVfYIdk5sDPjma702zu7XUVaNhRxBeFjNkVv0QgF6kzMoZ H46CGLQJoZvRjXOyKuTGTvEgGhn3YCUcon7KOXC/1W1txa4FCfHa7o45AeQeeV3BIuGj HuSA40qDRWsIVBKcnB1PFIKCkJ7lyz6pidJ7vYKx6TI+K4/10Nhw+O8ntJCNnsId1EiR J2ig== X-Gm-Message-State: AOAM532dwScNc/QszrwJuwEpR80AktTCU/Mro74DA5V4jPmFcfWy5gTD dXUGs+PpaiApnP6S3vqDotWbXSK39dZv7b7A X-Google-Smtp-Source: ABdhPJzpy00fZanVNdIsaZrX74zKn0FWqSck2FHfH4kwH4uwtm0gopazSKiPRiTcBk5h8oO25d2DWQ== X-Received: by 2002:a63:2f01:0:b0:39d:6503:af60 with SMTP id v1-20020a632f01000000b0039d6503af60mr8275277pgv.444.1649780798631; Tue, 12 Apr 2022 09:26:38 -0700 (PDT) Received: from patrick-ThinkPad-X1-Carbon-Gen-8.hq.rivosinc.com ([12.3.194.138]) by smtp.gmail.com with ESMTPSA id x5-20020aa79a45000000b00505c1ab148esm8385246pfj.131.2022.04.12.09.26.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Apr 2022 09:26:38 -0700 (PDT) From: Patrick O'Neill To: binutils@sourceware.org Cc: gnu-toolchain@rivosinc.com, palmer@dabbelt.com, andrew@sifive.com, Patrick O'Neill Subject: [PATCH 3/4] RISCV: Implement piecewise deletion Date: Tue, 12 Apr 2022 09:26:00 -0700 Message-Id: <20220412162601.146507-4-patrick@rivosinc.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220412162601.146507-1-patrick@rivosinc.com> References: <20220412162601.146507-1-patrick@rivosinc.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.2 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: Tue, 12 Apr 2022 16:26: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-11 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. --- bfd/elfnn-riscv.c | 302 +++++++++++++++++++++++++--------------------- 1 file changed, 167 insertions(+), 135 deletions(-) diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c index 17f9607744..5ebf7fe578 100644 --- a/bfd/elfnn-riscv.c +++ b/bfd/elfnn-riscv.c @@ -4057,117 +4057,14 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec, /* Delete some bytes from a section while relaxing. */ static bool -riscv_relax_delete_bytes (bfd *abfd, - asection *sec, - bfd_vma addr, +riscv_relax_delete_bytes (bfd_vma addr, size_t count, - struct bfd_link_info *link_info, - riscv_pcgp_relocs *p) + Elf_Internal_Rela *rel) { - unsigned int i, symcount; - bfd_vma toaddr = sec->size; - struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (abfd); - Elf_Internal_Shdr *symtab_hdr = &elf_tdata (abfd)->symtab_hdr; - unsigned int sec_shndx = _bfd_elf_section_from_bfd_section (abfd, sec); - struct bfd_elf_section_data *data = elf_section_data (sec); - bfd_byte *contents = data->this_hdr.contents; - - /* Actually delete the bytes. */ - sec->size -= count; - memmove (contents + addr, contents + addr + count, toaddr - addr - count); - - /* Adjust the location of all of the relocs. Note that we need not - adjust the addends, since all PC-relative references must be against - symbols, which we will adjust below. */ - for (i = 0; i < sec->reloc_count; i++) - if (data->relocs[i].r_offset > addr && data->relocs[i].r_offset < toaddr) - data->relocs[i].r_offset -= count; - - /* 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) - riscv_update_pcgp_relocs (p, sec, addr, count); - - /* Adjust the local symbols defined in this section. */ - for (i = 0; i < symtab_hdr->sh_info; i++) - { - Elf_Internal_Sym *sym = (Elf_Internal_Sym *) symtab_hdr->contents + i; - if (sym->st_shndx == sec_shndx) - { - /* If the symbol is in the range of memory we just moved, we - have to adjust its value. */ - if (sym->st_value > addr && sym->st_value <= toaddr) - sym->st_value -= count; - - /* If the symbol *spans* the bytes we just deleted (i.e. its - *end* is in the moved bytes but its *start* isn't), then we - must adjust its size. - - This test needs to use the original value of st_value, otherwise - we might accidentally decrease size when deleting bytes right - before the symbol. But since deleted relocs can't span across - symbols, we can't have both a st_value and a st_size decrease, - so it is simpler to just use an else. */ - else if (sym->st_value <= addr - && sym->st_value + sym->st_size > addr - && sym->st_value + sym->st_size <= toaddr) - sym->st_size -= count; - } - } - - /* Now adjust the global symbols defined in this section. */ - symcount = ((symtab_hdr->sh_size / sizeof (ElfNN_External_Sym)) - - symtab_hdr->sh_info); - - for (i = 0; i < symcount; i++) - { - struct elf_link_hash_entry *sym_hash = sym_hashes[i]; - - /* The '--wrap SYMBOL' option is causing a pain when the object file, - containing the definition of __wrap_SYMBOL, includes a direct - call to SYMBOL as well. Since both __wrap_SYMBOL and SYMBOL reference - the same symbol (which is __wrap_SYMBOL), but still exist as two - different symbols in 'sym_hashes', we don't want to adjust - the global symbol __wrap_SYMBOL twice. - - The same problem occurs with symbols that are versioned_hidden, as - foo becomes an alias for foo@BAR, and hence they need the same - treatment. */ - if (link_info->wrap_hash != NULL - || sym_hash->versioned != unversioned) - { - struct elf_link_hash_entry **cur_sym_hashes; - - /* Loop only over the symbols which have already been checked. */ - for (cur_sym_hashes = sym_hashes; cur_sym_hashes < &sym_hashes[i]; - cur_sym_hashes++) - { - /* If the current symbol is identical to 'sym_hash', that means - the symbol was already adjusted (or at least checked). */ - if (*cur_sym_hashes == sym_hash) - break; - } - /* Don't adjust the symbol again. */ - if (cur_sym_hashes < &sym_hashes[i]) - continue; - } - - if ((sym_hash->root.type == bfd_link_hash_defined - || sym_hash->root.type == bfd_link_hash_defweak) - && sym_hash->root.u.def.section == sec) - { - /* As above, adjust the value if needed. */ - if (sym_hash->root.u.def.value > addr - && sym_hash->root.u.def.value <= toaddr) - sym_hash->root.u.def.value -= count; - - /* As above, adjust the size if needed. */ - else if (sym_hash->root.u.def.value <= addr - && sym_hash->root.u.def.value + sym_hash->size > addr - && sym_hash->root.u.def.value + sym_hash->size <= toaddr) - sym_hash->size -= count; - } - } + /* Mark bytes for deletion. */ + rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE); + rel->r_offset = addr; + rel->r_addend = count; return true; } @@ -4177,7 +4074,7 @@ typedef bool (*relax_func_t) (bfd *, asection *, asection *, Elf_Internal_Rela *, bfd_vma, bfd_vma, bfd_vma, bool *, riscv_pcgp_relocs *, - bool undefined_weak); + bool undefined_weak, bfd_vma *); /* Relax AUIPC + JALR into JAL. */ @@ -4190,7 +4087,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 +4150,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 +4183,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 +4241,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 +4276,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 +4295,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 +4315,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 +4338,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 +4393,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 +4410,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); @@ -4666,13 +4562,148 @@ _bfd_riscv_relax_delete (bfd *abfd, 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) + riscv_pcgp_relocs *pcgp_relocs, + bool undefined_weak ATTRIBUTE_UNUSED, + bfd_vma *delete_total) { - if (!riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend, - link_info, NULL)) - return false; + unsigned int i, symcount; + bfd_vma toaddr = sec->size; + struct elf_link_hash_entry **sym_hashes = elf_sym_hashes (abfd); + Elf_Internal_Shdr *symtab_hdr = &elf_tdata (abfd)->symtab_hdr; + unsigned int sec_shndx = _bfd_elf_section_from_bfd_section (abfd, sec); + 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 + *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 + symbols, which we will adjust below. */ + for (i = 0; i < sec->reloc_count; i++) + if (data->relocs[i].r_offset > addr && data->relocs[i].r_offset < toaddr) + data->relocs[i].r_offset -= count; + + /* 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) + riscv_update_pcgp_relocs (p, sec, addr, count); + + /* Adjust the local symbols defined in this section. */ + for (i = 0; i < symtab_hdr->sh_info; i++) + { + Elf_Internal_Sym *sym = (Elf_Internal_Sym *) symtab_hdr->contents + i; + if (sym->st_shndx == sec_shndx) + { + /* If the symbol is in the range of memory we just moved, we + have to adjust its value. */ + if (sym->st_value > addr && sym->st_value <= toaddr) + sym->st_value -= count; + + /* If the symbol *spans* the bytes we just deleted (i.e. its + *end* is in the moved bytes but its *start* isn't), then we + must adjust its size. + + This test needs to use the original value of st_value, otherwise + we might accidentally decrease size when deleting bytes right + before the symbol. But since deleted relocs can't span across + symbols, we can't have both a st_value and a st_size decrease, + so it is simpler to just use an else. */ + else if (sym->st_value <= addr + && sym->st_value + sym->st_size > addr + && sym->st_value + sym->st_size <= toaddr) + sym->st_size -= count; + } + } + + /* Now adjust the global symbols defined in this section. */ + symcount = ((symtab_hdr->sh_size / sizeof (ElfNN_External_Sym)) + - symtab_hdr->sh_info); + + for (i = 0; i < symcount; i++) + { + struct elf_link_hash_entry *sym_hash = sym_hashes[i]; + + /* The '--wrap SYMBOL' option is causing a pain when the object file, + containing the definition of __wrap_SYMBOL, includes a direct + call to SYMBOL as well. Since both __wrap_SYMBOL and SYMBOL reference + the same symbol (which is __wrap_SYMBOL), but still exist as two + different symbols in 'sym_hashes', we don't want to adjust + the global symbol __wrap_SYMBOL twice. + + The same problem occurs with symbols that are versioned_hidden, as + foo becomes an alias for foo@BAR, and hence they need the same + treatment. */ + if (link_info->wrap_hash != NULL + || sym_hash->versioned != unversioned) + { + struct elf_link_hash_entry **cur_sym_hashes; + + /* Loop only over the symbols which have already been checked. */ + for (cur_sym_hashes = sym_hashes; cur_sym_hashes < &sym_hashes[i]; + cur_sym_hashes++) + { + /* If the current symbol is identical to 'sym_hash', that means + the symbol was already adjusted (or at least checked). */ + if (*cur_sym_hashes == sym_hash) + break; + } + /* Don't adjust the symbol again. */ + if (cur_sym_hashes < &sym_hashes[i]) + continue; + } + + if ((sym_hash->root.type == bfd_link_hash_defined + || sym_hash->root.type == bfd_link_hash_defweak) + && sym_hash->root.u.def.section == sec) + { + /* As above, adjust the value if needed. */ + if (sym_hash->root.u.def.value > addr + && sym_hash->root.u.def.value <= toaddr) + sym_hash->root.u.def.value -= count; + + /* As above, adjust the size if needed. */ + else if (sym_hash->root.u.def.value <= addr + && sym_hash->root.u.def.value + sym_hash->size > addr + && sym_hash->root.u.def.value + sym_hash->size <= toaddr) + sym_hash->size -= count; + } + } + return true; } @@ -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