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

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

Hi,

On 10/26/22 03:06, Nelson Chu wrote:
> 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;

That fixes it for me.

Thanks,
Luis

> 
> 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]