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

[Luis Machado <luis.machado@arm.com>]

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]