From patchwork Tue Oct 25 01:33:46 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nelson Chu X-Patchwork-Id: 10456 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp745437wru; Mon, 24 Oct 2022 18:34:47 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7jvn34NvUKj+CYu6e33lUI571UFZGXeYlpu0/barqya7Al9th6uxs4cpIV2orCpVSBUNPQ X-Received: by 2002:a17:906:36d1:b0:76c:a723:9445 with SMTP id b17-20020a17090636d100b0076ca7239445mr28847445ejc.548.1666661687835; Mon, 24 Oct 2022 18:34:47 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1666661687; cv=none; d=google.com; s=arc-20160816; b=SAfany+rlQARi/NycBiSnqkIXHFzDbPF+5YAN3V4qBUrj5S9ywFuTD30mkmmfjkcmj XzPDRbxi4BTm/of4VIcfF0Mm87eWqK7OG8fR4HlU/3zFd+sHmdB9CK27v5sxudhuCx/h 5lhgkgk7QBTuT0zqk9vZgAvSbVi9GcNfTVYK7vG5gfXTwLtLJ/H/B0pQOCSYOSl7T0E1 0Ecg+XaITeYPXwAUW+iQzrGY6esyf8ok2HbU0Pyyo8jNA1I/utg/KwOZasOCPxWE8gXm sktpNPYKrFblqlGb2dcYamEhXf6xotRBfniHjwymx85Rvko5GImXeNMo+0Mqk19d+xzq qpGA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:to:from:dmarc-filter :delivered-to; bh=kGPdbtjpS3Uzwo7ZiIXlfbAeY76YClkJY+34dO20Tag=; b=ZafoQZ298IPkrAyPvMu+l0ge1SZY+p9ZeYqRHk3y5dAxDGfcKkGe+daiOYBBgFwdHr 3Uh8IAY7wP9FBKKePVb7nM9uwYhbSJ9+dElZYZ+B7GVmDZivcbFU2gDftyEYK48zSBOG P4jZPpgdY9TmmvqK/nWA628p19T1nW28sfSGdlvo5cb2ipZP3iMys8GRS3tePbN/ef+Q 4YGukIS/FZT/XyQqyz3gV4mB2NuCVlhkZWWLCQ3agDDgR8d9obY4jSZMnnyiivOvqyR1 eNDVslCJgCcHgYRfGzvwYpLN9ZcWSym9NEvXOQ4Q5hMpwiv0BJBL5XXnEKuYR6W35eRu K9Lw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org" Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id bh4-20020a170906a0c400b007806964b2fcsi1141935ejb.447.2022.10.24.18.34.47 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 24 Oct 2022 18:34:47 -0700 (PDT) Received-SPF: pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org" Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CB68D3858291 for ; Tue, 25 Oct 2022 01:34:42 +0000 (GMT) X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from NelsondeMBP.localdomain (114-25-108-97.dynamic-ip.hinet.net [114.25.108.97]) by sourceware.org (Postfix) with ESMTP id 8048A3858C83 for ; Tue, 25 Oct 2022 01:33:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8048A3858C83 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivosinc.com Authentication-Results: sourceware.org; spf=none smtp.mailfrom=NelsondeMBP.localdomain Received: by NelsondeMBP.localdomain (Postfix, from userid 501) id 48B4D341D81; Tue, 25 Oct 2022 09:33:48 +0800 (CST) From: Nelson Chu To: binutils@sourceware.org Subject: [committed 1/2] RISC-V: Improve link time complexity. Date: Tue, 25 Oct 2022 09:33:46 +0800 Message-Id: <20221025013347.68282-1-nelson@rivosinc.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) MIME-Version: 1.0 X-Spam-Status: No, score=-5.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, KHOP_HELO_FCRDNS, NO_DNS_FOR_FROM, PDS_RDNS_DYNAMIC_FP, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_PBL, RDNS_DYNAMIC, SPF_HELO_NONE, SPF_NONE, TXREP 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: , Cc: Patrick O'Neill Errors-To: binutils-bounces+ouuuleilei=gmail.com@sourceware.org Sender: "Binutils" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1747621446408851053?= X-GMAIL-MSGID: =?utf-8?q?1747621446408851053?= From: Patrick O'Neill The riscv port does deletion and symbol table update for each relocation while relaxing, so we are moving section bytes and scanning symbol table once for each relocation. Compared to microblaze port, they record the relaxation changes into a table, then do the deletion and symbol table update once per section, rather than per relocation. Therefore, they should have better link time complexity than us. To improve the link time complexity, this patch try to make the deletion in linear time. Compared to record the relaxation changes into a table, we replace the unused relocation with R_RISCV_DELETE for the deleted bytes, and then resolve them at the end of the section. Assuming the number of R_RISCV_DELETE is m, and the number of symbols is n, the total link complexity should be O(m) for moving section bytes, and O(m*n^2) for symbol table update. If we record the relaxation changes into the table, and then sort the symbol table by values, then probably can reduce the time complexity to O(m*n*log(n)) for updating symbol table, but it doesn't seem worth it for now. bfd/ * elfnn-riscv.c (_riscv_relax_delete_bytes): Renamed from riscv_relax_delete_bytes, updated to reduce the tiem complexity to O(m) for memmove. (typedef relax_delete_t): Function pointer declaration of delete functions. (riscv_relax_delete_bytes): Can choose to use _riscv_relax_delete_piecewise or _riscv_relax_delete_immediate for deletion. (_riscv_relax_delete_piecewise): Just mark the deleted bytes as R_RISCV_DELETE. (_riscv_relax_delete_immediate): Delete some bytes from a section while relaxing. (riscv_relax_resolve_delete_relocs): Delete the bytes for R_RISCV_DELETE relocations from a section, at the end of _bfd_riscv_relax_section. (_bfd_riscv_relax_call): Mark deleted bytes as R_RISCV_DELETE by reusing R_RISCV_RELAX. (_bfd_riscv_relax_lui): Likewise, but reuse R_RISCV_HI20 for lui, and reuse R_RISCV_RELAX for c.lui. (_bfd_riscv_relax_tls_le): Likewise, but resue R_RISCV_TPREL_HI20 and R_RISCV_TPREL_ADD. (_bfd_riscv_relax_pc): Likewise, but resue R_RISCV_PCREL_HI20 for auipc. (_bfd_riscv_relax_align): Updated, don't need to resue relocation since calling _riscv_relax_delete_immediate. (_bfd_riscv_relax_delete): Removed. (_bfd_riscv_relax_section): Set riscv_relax_delete_bytes for each relax_func, to delete bytes immediately or later. Call riscv_relax_resolve_delete_relocs to delete bytes for DELETE relocations from a section. --- bfd/elfnn-riscv.c | 180 +++++++++++++++++++++++++++++++++------------- 1 file changed, 131 insertions(+), 49 deletions(-) diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c index 3d2ddf4e651..e4064313724 100644 --- a/bfd/elfnn-riscv.c +++ b/bfd/elfnn-riscv.c @@ -4043,27 +4043,32 @@ riscv_update_pcgp_relocs (riscv_pcgp_relocs *p, asection *deleted_sec, } } -/* Delete some bytes from a section while relaxing. */ +/* Delete some bytes, adjust relcocations and symbol table from a section. */ 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_bytes (bfd *abfd, + asection *sec, + bfd_vma addr, + size_t count, + struct bfd_link_info *link_info, + riscv_pcgp_relocs *p, + bfd_vma delete_total, + bfd_vma toaddr) { 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; + size_t bytes_to_move = toaddr - 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); + + /* Still adjust relocations and symbols in non-linear times. */ + toaddr = sec->size + 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 @@ -4161,6 +4166,99 @@ riscv_relax_delete_bytes (bfd *abfd, return true; } +typedef bool (*relax_delete_t) (bfd *, asection *, + bfd_vma, size_t, + struct bfd_link_info *, + riscv_pcgp_relocs *, + Elf_Internal_Rela *); + +static relax_delete_t riscv_relax_delete_bytes; + +/* Do not delete some bytes from a section while relaxing. + Just mark the deleted bytes as R_RISCV_DELETE. */ + +static bool +_riscv_relax_delete_piecewise (bfd *abfd ATTRIBUTE_UNUSED, + asection *sec ATTRIBUTE_UNUSED, + bfd_vma addr, + size_t count, + struct bfd_link_info *link_info ATTRIBUTE_UNUSED, + riscv_pcgp_relocs *p ATTRIBUTE_UNUSED, + Elf_Internal_Rela *rel) +{ + if (rel == NULL) + return false; + rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE); + rel->r_offset = addr; + rel->r_addend = count; + return true; +} + +/* Delete some bytes from a section while relaxing. */ + +static bool +_riscv_relax_delete_immediate (bfd *abfd, + asection *sec, + bfd_vma addr, + size_t count, + struct bfd_link_info *link_info, + riscv_pcgp_relocs *p, + Elf_Internal_Rela *rel) +{ + if (rel != NULL) + rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE); + return _riscv_relax_delete_bytes (abfd, sec, addr, count, + link_info, p, 0, sec->size); +} + +/* Delete the bytes for R_RISCV_DELETE relocs. */ + +static bool +riscv_relax_resolve_delete_relocs (bfd *abfd, + asection *sec, + struct bfd_link_info *link_info, + Elf_Internal_Rela *relocs) +{ + bfd_vma delete_total = 0; + unsigned int i; + + for (i = 0; i < sec->reloc_count; i++) + { + Elf_Internal_Rela *rel = relocs + i; + if (ELFNN_R_TYPE (rel->r_info) != R_RISCV_DELETE) + continue; + + /* Find the next R_RISCV_DELETE reloc if possible. */ + Elf_Internal_Rela *rel_next = NULL; + unsigned int start = rel - relocs; + for (i = start; i < sec->reloc_count; i++) + { + /* 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. */ + rel_next = relocs + i; + if (ELFNN_R_TYPE ((rel_next)->r_info) == R_RISCV_DELETE + && (rel_next)->r_offset > rel->r_offset) + break; + else + rel_next = NULL; + } + + bfd_vma toaddr = rel_next == NULL ? sec->size : rel_next->r_offset; + if (!_riscv_relax_delete_bytes (abfd, sec, rel->r_offset, rel->r_addend, + link_info, NULL, delete_total, toaddr)) + return false; + + delete_total += rel->r_addend; + rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE); + + /* Skip ahead to the next delete reloc. */ + i = rel_next != NULL ? rel_next - relocs - 1 : sec->reloc_count; + } + + return true; +} + typedef bool (*relax_func_t) (bfd *, asection *, asection *, struct bfd_link_info *, Elf_Internal_Rela *, @@ -4239,10 +4337,10 @@ _bfd_riscv_relax_call (bfd *abfd, asection *sec, asection *sym_sec, /* Replace the AUIPC. */ riscv_put_insn (8 * len, auipc, contents + rel->r_offset); - /* Delete unnecessary JALR. */ + /* Delete unnecessary JALR and reuse the R_RISCV_RELAX reloc. */ *again = true; return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + len, 8 - len, - link_info, pcgp_relocs); + link_info, pcgp_relocs, rel + 1); } /* Traverse all output sections and return the max alignment. */ @@ -4332,11 +4430,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); + /* Delete unnecessary LUI and reuse the reloc. */ *again = true; return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, - link_info, pcgp_relocs); + link_info, pcgp_relocs, rel); default: abort (); @@ -4367,9 +4464,10 @@ _bfd_riscv_relax_lui (bfd *abfd, /* Replace the R_RISCV_HI20 reloc. */ rel->r_info = ELFNN_R_INFO (ELFNN_R_SYM (rel->r_info), R_RISCV_RVC_LUI); + /* Delete extra bytes and reuse the R_RISCV_RELAX reloc. */ *again = true; return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + 2, 2, - link_info, pcgp_relocs); + link_info, pcgp_relocs, rel + 1); } return true; @@ -4407,11 +4505,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. */ - rel->r_info = ELFNN_R_INFO (0, R_RISCV_NONE); + /* Delete unnecessary instruction and reuse the reloc. */ *again = true; return riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info, - pcgp_relocs); + pcgp_relocs, rel); default: abort (); @@ -4472,10 +4569,10 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec, if (nop_bytes % 4 != 0) bfd_putl16 (RVC_NOP, contents + rel->r_offset + pos); - /* Delete the excess bytes. */ + /* Delete excess bytes. */ return riscv_relax_delete_bytes (abfd, sec, rel->r_offset + nop_bytes, rel->r_addend - nop_bytes, link_info, - NULL); + NULL, NULL); } /* Relax PC-relative references to GP-relative references. */ @@ -4617,9 +4714,9 @@ _bfd_riscv_relax_pc (bfd *abfd ATTRIBUTE_UNUSED, ELFNN_R_SYM(rel->r_info), sym_sec, undefined_weak); - /* We can delete the unnecessary AUIPC and reloc. */ - rel->r_info = ELFNN_R_INFO (0, R_RISCV_DELETE); - rel->r_addend = 4; + /* Delete unnecessary AUIPC and reuse the reloc. */ + riscv_relax_delete_bytes (abfd, sec, rel->r_offset, 4, link_info, + pcgp_relocs, rel); return true; default: @@ -4630,28 +4727,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. */ @@ -4729,6 +4804,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec, bool undefined_weak = false; relax_func = NULL; + riscv_relax_delete_bytes = NULL; if (info->relax_pass == 0) { if (type == R_RISCV_CALL @@ -4750,6 +4826,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec, relax_func = _bfd_riscv_relax_pc; else continue; + riscv_relax_delete_bytes = _riscv_relax_delete_piecewise; /* Only relax this reloc if it is paired with R_RISCV_RELAX. */ if (i == sec->reloc_count - 1 @@ -4760,10 +4837,11 @@ _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) - relax_func = _bfd_riscv_relax_align; + else if (info->relax_pass == 1 && type == R_RISCV_ALIGN) + { + relax_func = _bfd_riscv_relax_align; + riscv_relax_delete_bytes = _riscv_relax_delete_immediate; + } else continue; @@ -4921,6 +4999,10 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec, goto fail; } + /* Resolve R_RISCV_DELETE relocations. */ + if (!riscv_relax_resolve_delete_relocs (abfd, sec, info, relocs)) + goto fail; + ret = true; fail: