Re: [committed 1/2] RISC-V: Improve link time complexity.

[Nelson Chu <nelson@rivosinc.com>]

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 = 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;
+      i = rel_next != 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 <luis.machado@arm.com> wrote:
>
> Hi Nelson,
>
> On 10/25/22 02:33, Nelson Chu wrote:
> > From: Patrick O'Neill <patrick@rivosinc.com>
> >
> > 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(-)
> >
>
> This seems to cause build failures due to a couple warnings (Werror). I can reproduce it on
> armhf Ubuntu 22.04, with the following configure line:
>
> configure --enable-targets=all --enable-64-bit-bfd
>
> The following warnings show up:
>
> elfnn-riscv.c: In function ‘riscv_relax_resolve_delete_relocs’:
> elfnn-riscv.c:4256:30: error: operand of ‘?:’ changes signedness from ‘int’ to ‘unsigned int’ due to unsignedness of other operand [-Werror=sign-compare]
>
> elfnn-riscv.c: In function ‘riscv_relax_resolve_delete_relocs’:
> elfnn-riscv.c:4256:30: error: operand of ‘?:’ changes signedness from ‘int’ to ‘unsigned int’ due to unsignedness of other operand [-Werror=sign-compare]