llvm dev - Nov 2015 - [lld] R_MIPS_HI16 / R_MIPS_LO16 calculation

On Sat, Nov 21, 2015 at 10:08 AM, Rui Ueyama <ruiu at google.com>
wrote:
> On Fri, Nov 20, 2015 at 11:02 PM, Simon Atanasyan <simon at
atanasyan.com>
> wrote:
>>
>> On Sat, Nov 21, 2015 at 9:28 AM, Rui Ueyama <ruiu at google.com>
wrote:
>> > On Fri, Nov 20, 2015 at 10:13 PM, Simon Atanasyan <simon at
atanasyan.com>
>> > wrote:
>> >>
>> >> In case of MIPS O32 ABI we have to find a matching R_MIPS_LO16
>> >> relocation to calculate R_MIPS_HI16 one because R_MIPS_HI16
uses
>> >> combined addend (AHI << 16) + (short)ALO where AHI is
original
>> >> R_MIPS_HI16 addend and ALO is addend of the matching
R_MIPS_LO16
>> >> relocation [1]. There are two methods to do matching and
R_MIPS_HI16
>> >> calculation.
>> >>
>> >> Method A:
>> >> 1. Postpone R_MIPS_HI16 relocation calculation and record its
>> >> arguments.
>> >> 2. When R_MIPS_LO16 is found, iterate over recorded
R_MIPS_HI16
>> >> relocations, calculate combined addend and apply relocations.
>> >> 3. At the end check orphaned (without R_MIPS_LO16 pair)
R_MIPS_HI16
>> >> relocations, show warnings and apply them with zero addend.
>> >>
>> >> Method B:
>> >> 1. Each time we have found R_MIPS_HI16 relocation, iterate
remaining
>> >> relocations list to find matching R_MIPS_LO16.
>> >> 2. Calculate combined adddend and apply relocation or show
warning if
>> >> the R_MIPS_LO16 is not found.
>> >>
>> >> Method A requires some sort of container to keep postponed
HI16
>> >> relocations. If we add the container to the `MipsTargetInfo`
class we
>> >> will be able to hide all this unusual scheme inside MIPS
specific code
>> >> and will not need to perform LO16 lookups. But the
`MipsTargetInfo`
>> >> becomes stateful.
>> >>
>> >> Method B keeps the `MipsTargetInfo` stateless but requires
forward
>> >> LO16 lookup for each HI16 relocation and requires to provide
an
>> >> interface for such lookup to the `MipsTargetInfo`.
>> >>
>> >> Sure we can implement each of these methods somewhere in the
>> >> `InputSectionBase` class under `if (MIPS)` statements.
>> >>
>> >> Any opinions about the best method / approach?
>> >
>> >
>> > If I understand that spec correctly, an R_MIPS_HI16 should
immediately
>> > be
>> > followed by an R_MIPS_LO16. Can't you use that property? It
doesn't seem
>> > to
>> > me that you really have to search and pair up HI16 and LO16
relocations.
>>
>> It is a question what the ABI authors did mean by the "R_MIPS_HI16
>> must have an associated R_MIPS_LO16 entry immediately following
it"
>> phrase. In fact you can get from a compiler this code:
>>
>> lui    $t0,%hi(sym1+4)      # R_MIPS_HI16
>> lui    $t0,%hi(sym1+8)      # R_MIPS_HI16
>> lui    $t0,%hi(sym1+12)     # R_MIPS_HI16
>> addi   $t0,$t0,%lo(sym1+16) # R_MIPS_LO16
>
>
> The first two relocations don't conform to the standard because there
are no
> corresponding LO16 relocations, no?
>
>> and even such code:
>>
>> lui    $t0,%hi(sym1)     # R_MIPS_HI16 on sym1
>> lui    $t0,%hi(sym2)     # R_MIPS_HI16 on sym2
>> addi   $t0,$t0,%lo(sym1) # R_MIPS_LO16 on sym1
>> addi   $t0,$t0,%lo(sym2) # R_MIPS_LO16 on sym2
>
>
> Hmm, isn't this a violation of the ABI? My interpretation of
"[e]ach
> relocation type of R_MIPS_HI16 must have an associated R_MIPS_LO16 entry
> immediately following it in the list of relocations" is not ambiguous
to
> allow them. Is there any chance to fix the compiler? (I guess there
isn't,
> though.)
Strictly speaking yes, it is a violation. But it is not a bug of the
single compiler. You can find such code everywhere from various
versions of libc compiled by different versions of gcc and to the code
produced by Clang.

Moreover, I scan through the libc code and found some places where
R_MIPS_HI16 / R_MIPS_LO16 pairs are interleaved with other types of
relocations.

-- 
Simon Atanasyan

I'm not sure if I understand the semantics of HI16 and LO16 relocations. If
my understanding is correct, a pair of HI16 and LO16 represents an addend
AHL. AHL is computed by (AHI<<16) | (ALO&0xFFFF). Can't we apply
HI16 and
LO16 relocations separately and produce the same relocation result? Do we
have to pair them up before applying relocations?

On Sat, Nov 21, 2015 at 7:34 AM, Simon Atanasyan <simon at atanasyan.com>
wrote:
> On Sat, Nov 21, 2015 at 10:08 AM, Rui Ueyama <ruiu at google.com>
wrote:
> > On Fri, Nov 20, 2015 at 11:02 PM, Simon Atanasyan <simon at
atanasyan.com>
> > wrote:
> >>
> >> On Sat, Nov 21, 2015 at 9:28 AM, Rui Ueyama <ruiu at
google.com> wrote:
> >> > On Fri, Nov 20, 2015 at 10:13 PM, Simon Atanasyan <
> simon at atanasyan.com>
> >> > wrote:
> >> >>
> >> >> In case of MIPS O32 ABI we have to find a matching
R_MIPS_LO16
> >> >> relocation to calculate R_MIPS_HI16 one because
R_MIPS_HI16 uses
> >> >> combined addend (AHI << 16) + (short)ALO where AHI
is original
> >> >> R_MIPS_HI16 addend and ALO is addend of the matching
R_MIPS_LO16
> >> >> relocation [1]. There are two methods to do matching and
R_MIPS_HI16
> >> >> calculation.
> >> >>
> >> >> Method A:
> >> >> 1. Postpone R_MIPS_HI16 relocation calculation and record
its
> >> >> arguments.
> >> >> 2. When R_MIPS_LO16 is found, iterate over recorded
R_MIPS_HI16
> >> >> relocations, calculate combined addend and apply
relocations.
> >> >> 3. At the end check orphaned (without R_MIPS_LO16 pair)
R_MIPS_HI16
> >> >> relocations, show warnings and apply them with zero
addend.
> >> >>
> >> >> Method B:
> >> >> 1. Each time we have found R_MIPS_HI16 relocation,
iterate remaining
> >> >> relocations list to find matching R_MIPS_LO16.
> >> >> 2. Calculate combined adddend and apply relocation or
show warning if
> >> >> the R_MIPS_LO16 is not found.
> >> >>
> >> >> Method A requires some sort of container to keep
postponed HI16
> >> >> relocations. If we add the container to the
`MipsTargetInfo` class we
> >> >> will be able to hide all this unusual scheme inside MIPS
specific
> code
> >> >> and will not need to perform LO16 lookups. But the
`MipsTargetInfo`
> >> >> becomes stateful.
> >> >>
> >> >> Method B keeps the `MipsTargetInfo` stateless but
requires forward
> >> >> LO16 lookup for each HI16 relocation and requires to
provide an
> >> >> interface for such lookup to the `MipsTargetInfo`.
> >> >>
> >> >> Sure we can implement each of these methods somewhere in
the
> >> >> `InputSectionBase` class under `if (MIPS)` statements.
> >> >>
> >> >> Any opinions about the best method / approach?
> >> >
> >> >
> >> > If I understand that spec correctly, an R_MIPS_HI16 should
immediately
> >> > be
> >> > followed by an R_MIPS_LO16. Can't you use that property?
It doesn't
> seem
> >> > to
> >> > me that you really have to search and pair up HI16 and LO16
> relocations.
> >>
> >> It is a question what the ABI authors did mean by the
"R_MIPS_HI16
> >> must have an associated R_MIPS_LO16 entry immediately following
it"
> >> phrase. In fact you can get from a compiler this code:
> >>
> >> lui    $t0,%hi(sym1+4)      # R_MIPS_HI16
> >> lui    $t0,%hi(sym1+8)      # R_MIPS_HI16
> >> lui    $t0,%hi(sym1+12)     # R_MIPS_HI16
> >> addi   $t0,$t0,%lo(sym1+16) # R_MIPS_LO16
> >
> >
> > The first two relocations don't conform to the standard because
there
> are no
> > corresponding LO16 relocations, no?
> >
> >> and even such code:
> >>
> >> lui    $t0,%hi(sym1)     # R_MIPS_HI16 on sym1
> >> lui    $t0,%hi(sym2)     # R_MIPS_HI16 on sym2
> >> addi   $t0,$t0,%lo(sym1) # R_MIPS_LO16 on sym1
> >> addi   $t0,$t0,%lo(sym2) # R_MIPS_LO16 on sym2
> >
> >
> > Hmm, isn't this a violation of the ABI? My interpretation of
"[e]ach
> > relocation type of R_MIPS_HI16 must have an associated R_MIPS_LO16
entry
> > immediately following it in the list of relocations" is not
ambiguous to
> > allow them. Is there any chance to fix the compiler? (I guess there
> isn't,
> > though.)
>
> Strictly speaking yes, it is a violation. But it is not a bug of the
> single compiler. You can find such code everywhere from various
> versions of libc compiled by different versions of gcc and to the code
> produced by Clang.
>
> Moreover, I scan through the libc code and found some places where
> R_MIPS_HI16 / R_MIPS_LO16 pairs are interleaved with other types of
> relocations.
>
> --
> Simon Atanasyan
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151121/5fadbef4/attachment.html>

On Sun, Nov 22, 2015 at 1:28 AM, Rui Ueyama <ruiu at google.com>
wrote:
> I'm not sure if I understand the semantics of HI16 and LO16
relocations. If
> my understanding is correct, a pair of HI16 and LO16 represents an addend
> AHL. AHL is computed by (AHI<<16) | (ALO&0xFFFF). Can't we
apply HI16 and
> LO16 relocations separately and produce the same relocation result? Do we
> have to pair them up before applying relocations?
The correct formula for the combined addend is (AHI << 16) +
(short)ALO. So the combined addend depends on both AHI and ALO
addends, therefore ALO affects result of R_MIPS_HI16 relocation.

Current version of bfd GNU linker looks up R_MIPS_LO16 relocation each
time it needs to calculate R_MIPS_HI16 relocation. It uses
`mips_elf_add_lo16_rel_addend` function for that
(https://goo.gl/P7nb76).

-- 
Simon Atanasyan