From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x32c.google.com (mail-ot1-x32c.google.com [IPv6:2607:f8b0:4864:20::32c]) by sourceware.org (Postfix) with ESMTPS id 9BE853851150 for ; Wed, 26 Oct 2022 02:06:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9BE853851150 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-ot1-x32c.google.com with SMTP id r13-20020a056830418d00b0065601df69c0so9064053otu.7 for ; Tue, 25 Oct 2022 19:06:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rivosinc-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=mpLtpbgKkVVir3anf4tL/Yf3OjWzCuuCArS67tF7890=; b=LDu0en4a4E3kJtr8ycNrX9/oZU5Hy63sUls1VZKWaZ/rex+Rxk4/jygjoOqotFk/C2 D+CJ9y9oM47Qij0TuXmSanaHefD7BG+X5mm2AdJmISX8iJEVHIiYuzJHNfKZK2M0lrB8 /iFvU8lRw87fuXroJdAYG773da01EY/Wky4Be7NCFYbtyELgPUcgHAR7X6HD7M0xsVBp 0iUe06+xvVFVESZQGusnXmp1NNAbiIfdNXpNGn/HwRAPsQBVLwhbjr4faoqxxfk55Xwg GOREl6LVGZsEANhTatsB7jLtVbMbN1kGbVNaOdHkabzsiovlPhvgHcz5s8qjFJY8xZvd HxuA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mpLtpbgKkVVir3anf4tL/Yf3OjWzCuuCArS67tF7890=; b=aYGSQ4TJgvi6GAKBRPuFYdlW1uMKJnegHZNwLvszh3gDyXCqAptBUN1TnV8y0kgs49 Gp56ZI4BQJt3dP2g9UVsiOPAP0G+fYWFc79WnqNkMF0bspy5py5EZ4+Qik1aJbbxKvSU irSRWKYANHNPhcwbzCIPcsQJ32d9pjkaDfMRLmNvsdQznQd51h641raqWuptBNWzUTBx 9iksfR8yQvESp6VNq6KdikmjQ3PRjG+gEyVS8aWEX0wJF/wkHmO7Cl2LG6ThtTM/lq7a hHPkZl2Zq2iPOF2jQYct49s15jsET2VmvnTclj7sRoicQ/IzrF/uT6l7mj+xZmTosY1L HUhw== X-Gm-Message-State: ACrzQf1FcQSB7VJfpI2GusfYqDvS+GZGei7r2KEu4J6S+u/c9TepQn8k GMdKa3zgll8IkyYYbeo4uGw1qlfdza6BP+gnBB/vYw== X-Google-Smtp-Source: AMsMyM71QAZyHgtuSojW2xsJbC4mvHjy+WoeQY37A2w6e5/DplMZYM4IeYagzIsO6ZrsnYOHG5uJPoDVR92CgTAPdpE= X-Received: by 2002:a05:6830:603:b0:661:b07c:bf24 with SMTP id w3-20020a056830060300b00661b07cbf24mr20827575oti.208.1666750002977; Tue, 25 Oct 2022 19:06:42 -0700 (PDT) MIME-Version: 1.0 References: <20221025013347.68282-1-nelson@rivosinc.com> <84a75951-f5a7-fc53-a11a-9a1b964200b7@arm.com> In-Reply-To: <84a75951-f5a7-fc53-a11a-9a1b964200b7@arm.com> From: Nelson Chu Date: Wed, 26 Oct 2022 10:06:32 +0800 Message-ID: Subject: Re: [committed 1/2] RISC-V: Improve link time complexity. To: Luis Machado Cc: binutils@sourceware.org, "Patrick O'Neill" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-9.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,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 List-Id: Hi Luis, Although I cannot reproduce the case from my side, does the following fix work for you? diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c index cf852636c9c..73e422dd57a 100644 --- a/bfd/elfnn-riscv.c +++ b/bfd/elfnn-riscv.c @@ -4253,7 +4253,8 @@ riscv_relax_resolve_delete_relocs (bfd *abfd, rel->r_info =3D ELFNN_R_INFO (0, R_RISCV_NONE); /* Skip ahead to the next delete reloc. */ - i =3D rel_next !=3D NULL ? rel_next - relocs - 1 : sec->reloc_count; + i =3D rel_next !=3D NULL ? (unsigned int) (rel_next - relocs - 1) + : sec->reloc_count; } return true; Thanks Nelson On Tue, Oct 25, 2022 at 6:11 PM Luis Machado wrote: > > Hi Nelson, > > On 10/25/22 02:33, Nelson Chu wrote: > > From: Patrick O'Neill > > > > The riscv port does deletion and symbol table update for each relocatio= n > > while relaxing, so we are moving section bytes and scanning symbol tabl= e once > > for each relocation. Compared to microblaze port, they record the rela= xation > > changes into a table, then do the deletion and symbol table update once= per > > section, rather than per relocation. Therefore, they should have bette= r link > > time complexity than us. > > > > To improve the link time complexity, this patch try to make the deletio= n in > > linear time. Compared to record the relaxation changes into a table, w= e > > 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 com= plexity > > 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 s= ymbol > > 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 f= unctions. > > (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 r= eusing > > 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_de= lete_relocs > > to delete bytes for DELETE relocations from a section. > > --- > > bfd/elfnn-riscv.c | 180 +++++++++++++++++++++++++++++++++------------= - > > 1 file changed, 131 insertions(+), 49 deletions(-) > > > > This seems to cause build failures due to a couple warnings (Werror). I c= an reproduce it on > armhf Ubuntu 22.04, with the following configure line: > > configure --enable-targets=3Dall --enable-64-bit-bfd > > The following warnings show up: > > elfnn-riscv.c: In function =E2=80=98riscv_relax_resolve_delete_relocs=E2= =80=99: > elfnn-riscv.c:4256:30: error: operand of =E2=80=98?:=E2=80=99 changes sig= nedness from =E2=80=98int=E2=80=99 to =E2=80=98unsigned int=E2=80=99 due to= unsignedness of other operand [-Werror=3Dsign-compare] > > elfnn-riscv.c: In function =E2=80=98riscv_relax_resolve_delete_relocs=E2= =80=99: > elfnn-riscv.c:4256:30: error: operand of =E2=80=98?:=E2=80=99 changes sig= nedness from =E2=80=98int=E2=80=99 to =E2=80=98unsigned int=E2=80=99 due to= unsignedness of other operand [-Werror=3Dsign-compare]