HELP: MIPS PC Relative Addressing

HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

Hi all,

I'm trying to implement PC Relative addressing for toolchain (GCC, LLVM).

MIPS Release6 had introduced pcrel instructions (e.g. auipc) that made
PC relative addressing for local data possible. It can help us reduce GOT
overhead and implement position independent kernel easier.

Just as RISC-V, MIPS R6 can load address by a pair of %pcrel_hi and 
%pcrel_lo
modifier. However, the usage is slightly different.

For RISC-V, %pcrel_lo shall point to the label of corresponding 
%pcrel_hi, like

.LA0:
     auipc    a0, %pcrel_hi(sym)
     addi      a0, a0, %pcrel_lo(.LA0)

However, for MIPS %pcrel_lo simply calculate LO16 of the symbol to current
PC, thus PC relative addressing will look like:

.LA0:
     auipc  a0, %pcrel_hi(sym)
.LA1:
     addi    a0, %pcrel_lo(sym + (.LA1 - .LA0))

I found it's very difficult for GCC to generate this kind of pcrel_lo 
expression,
RTX label_ref can't be lower into such LOW_SUM expression.

Could you please give me some hints about how to implement it?

If it looks infeasible for GCC side, another option would be adding 
RISC-V style
%pcrel_{hi,lo} modifier at assembler side. We can add another pair of 
modifier
like %pcrel_paired_{hi,lo} to implement the behavior. Would it be a good 
idea?

Thanks.

-Jiaxun

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Wed, 24 Feb 2021, Jiaxun Yang wrote:

> For RISC-V, %pcrel_lo shall point to the label of corresponding %pcrel_hi,
> like
> 
> .LA0:
>     auipc    a0, %pcrel_hi(sym)
>     addi      a0, a0, %pcrel_lo(.LA0)

 I commented on it once, in the course of the FDPIC design project, and I 
find it broken by design.  Sadly it has made it into the RISC-V psABI and 
it is hard to revert at this time, too many places have started relying on 
it.

> However, for MIPS %pcrel_lo simply calculate LO16 of the symbol to current
> PC, thus PC relative addressing will look like:
> 
> .LA0:
>     auipc  a0, %pcrel_hi(sym)
> .LA1:
>     addi    a0, %pcrel_lo(sym + (.LA1 - .LA0))
> 
> I found it's very difficult for GCC to generate this kind of pcrel_lo
> expression,
> RTX label_ref can't be lower into such LOW_SUM expression.

 You may want to use composed relocations to refer to .LA1 (R_MIPS_32) and 
.LA0 (R_MIPS_SUB).  There may or may not be linker updates needed; unlike 
the RISC-V one the MIPS BFD backend already supports composed relocations 
with the usual ELF gABI semantics.  It would be good to switch to RELA at 
this point universally too; none of new stuff will work with old linkers 
anyway.

 HTH,

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Wed, 24 Feb 2021, Jim Wilson wrote:

> >  I commented on it once, in the course of the FDPIC design project, and I
> > find it broken by design.  Sadly it has made it into the RISC-V psABI and
> > it is hard to revert at this time, too many places have started relying on
> > it.
> >
> 
> It was already a production ABI before you asked for the change.  And
> changing a production ABI is extremely difficult.  You were not the first
> to complain about this, and you probably won't be the last.

 Thanks for chiming in.

 I accepted it as a fact of life, but we don't have to follow the mistake 
with the MIPS psABI.  If you ever decide to have a RISC-V NewABI just as 
MIPS did at one point, then you can reevaluate the choices made.  At least 
there are no REL relocations there with RISC-V, it was a gross mistake to 
have them with MIPS o32.  I think we can try switching away from them with 
R6, or at least evaluate what would be required to do so.

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

在 2021/2/25 上午5:40, Jim Wilson 写道:
> On Wed, Feb 24, 2021 at 6:18 AM Jiaxun Yang <jiaxun.yang@flygoat.com 
> <mailto:jiaxun.yang@flygoat.com>> wrote:
>
>     I found it's very difficult for GCC to generate this kind of pcrel_lo
>     expression,
>     RTX label_ref can't be lower into such LOW_SUM expression.
>
>
> Yes, it is difficult.  You need to generate a label, and put the label 
> number in an unspec in the auipc pattern, and then create a label_ref 
> to put in the addi.  The fact that we have an unspec and a label_ref 
> means a number of optimizations get disabled, like basic block 
> duplication and loop unrolling, because they can't make a copy of an 
> instruction that uses a label as data, as they have no way to know how 
> to duplicate the label itself.  Or at least RISC-V needs to create one 
> label.  You probably need to create two labels.
>
> There is a far easier way to do this, which is to just emit an 
> assembler macro, and let the assembler generate the labels and 
> relocs.  This is what the RISC-V GCC port does by default.  This 
> prevents some optimizations like scheduling the two instructions, but 
> enables some other optimizations like loop unrolling.  So it is a 
> tossup.  Sometimes we get better code with the assembler macro, and 
> sometimes we get better code by emitting the auipc and addi separately.

Thanks all,

I'll take this approach first, add "lla, dlla" pseudo-instructions to 
assembler and seeking optimization
in future.

Btw I found we don't have any document for MIPS pseudo-instructions. 
RISC-V put them in ISA manual
but it is not the case for MIPS. Is it possible to have one in binutils?

>
> The RISC-V gcc port can emit the auipc/addi with 
> -mexplicit-relocs -mcode-model=medany, but this is known to sometimes 
> fail.  The problem is that if you have an 8-byte variable with 8-byte 
> alignment, and try to load it with 2 4-byte loads, gcc knows that 
> offset+4 must be safe from overflow because the data is 8-byte 
> aligned.  However, when you use a pc-relative offset that is data 
> address-code address, the offset is only as aligned as the code is. 
> RISC-V has 2-byte instruction alignment with the C extension.  So if 
> you have offset+4 and offset is only 2-byte aligned, it is possible 
> that offset+4 may overflow the add immediate field.  The same thing 
> can happen with 16-byte data that is 16-byte aligned, accessed with 
> two 8-byte loads.  There is no easy software solution.  We just emit a 
> linker error in that case as we can't do anything else.  I think this 
> would work better if auipc cleared some low bits of the result, in 
> which case the pc-relative offset would have enough alignment to 
> prevent overflow when adding small offsets, but it is far too late to 
> change how the RISC-V auipc works.

Got your point, thanks for the remainder!

>
>     If it looks infeasible for GCC side, another option would be adding
>     RISC-V style
>     %pcrel_{hi,lo} modifier at assembler side. We can add another pair of
>     modifier
>     like %pcrel_paired_{hi,lo} to implement the behavior. Would it be
>     a good
>     idea?
>
>
> I wouldn't recommend following the RISC-V approach for the relocation.

Thanks.

- Jiaxun
>
> Jim

Re: HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

在 2021/2/25 上午1:30, Maciej W. Rozycki 写道:
> On Wed, 24 Feb 2021, Jiaxun Yang wrote:
>
>> For RISC-V, %pcrel_lo shall point to the label of corresponding %pcrel_hi,
>> like
>>
>> .LA0:
>>      auipc    a0, %pcrel_hi(sym)
>>      addi      a0, a0, %pcrel_lo(.LA0)
>   I commented on it once, in the course of the FDPIC design project, and I
> find it broken by design.  Sadly it has made it into the RISC-V psABI and
> it is hard to revert at this time, too many places have started relying on
> it.
>
>> However, for MIPS %pcrel_lo simply calculate LO16 of the symbol to current
>> PC, thus PC relative addressing will look like:
>>
>> .LA0:
>>      auipc  a0, %pcrel_hi(sym)
>> .LA1:
>>      addi    a0, %pcrel_lo(sym + (.LA1 - .LA0))
>>
>> I found it's very difficult for GCC to generate this kind of pcrel_lo
>> expression,
>> RTX label_ref can't be lower into such LOW_SUM expression.
>   You may want to use composed relocations to refer to .LA1 (R_MIPS_32) and
> .LA0 (R_MIPS_SUB).  There may or may not be linker updates needed; unlike
> the RISC-V one the MIPS BFD backend already supports composed relocations
> with the usual ELF gABI semantics.  It would be good to switch to RELA at
> this point universally too; none of new stuff will work with old linkers
> anyway.

Thanks for your hint;-)

I'm unsure about how should we express composed relocations in assembly :-/

MIPS N32/N64 ABI is already using RELA, do you mean switch to RELA for o32
as well?

Thanks.

- Jiaxun

>
>   HTH,
>
>    Maciej

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Thu, 25 Feb 2021, Jiaxun Yang wrote:

> > There is a far easier way to do this, which is to just emit an assembler
> > macro, and let the assembler generate the labels and relocs.  This is what
> > the RISC-V GCC port does by default.  This prevents some optimizations like
> > scheduling the two instructions, but enables some other optimizations like
> > loop unrolling.  So it is a tossup.  Sometimes we get better code with the
> > assembler macro, and sometimes we get better code by emitting the auipc and
> > addi separately.
> 
> Thanks all,
> 
> I'll take this approach first, add "lla, dlla" pseudo-instructions to
> assembler and seeking optimization
> in future.

 The DLA and LA macros are supposed to do that already, no need to invent 
new names.

 They may not have been implemented for R6, but I'm not sure.  There was 
some resistance against macros at one point as the new generation came to 
work on the MIPS assembler and consequently inconsistencies resulted in 
the language that may not have been removed to date.

 In any case you need to use `-mno-explicit-relocs' with GCC then so as 
not to break the compiler's semantics or assumptions.

> Btw I found we don't have any document for MIPS pseudo-instructions. RISC-V
> put them in ISA manual
> but it is not the case for MIPS. Is it possible to have one in binutils?

 There are MIPS assembly language books available; I'm fairly sure Dominic 
Sweetman's "See MIPS Run" has a chapter (I don't have the book at hand).  
I don't think GNU binutils documentation is supposed to describe the 
assembly dialects supported, except maybe for GNU extensions (pseudo-ops).

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

On Thu, Feb 25, 2021, at 10:57 AM, Maciej W. Rozycki wrote:
> On Thu, 25 Feb 2021, Jiaxun Yang wrote:
> 
> > > There is a far easier way to do this, which is to just emit an assembler
> > > macro, and let the assembler generate the labels and relocs.  This is what
> > > the RISC-V GCC port does by default.  This prevents some optimizations like
> > > scheduling the two instructions, but enables some other optimizations like
> > > loop unrolling.  So it is a tossup.  Sometimes we get better code with the
> > > assembler macro, and sometimes we get better code by emitting the auipc and
> > > addi separately.
> > 
> > Thanks all,
> > 
> > I'll take this approach first, add "lla, dlla" pseudo-instructions to
> > assembler and seeking optimization
> > in future.
> 
>  The DLA and LA macros are supposed to do that already, no need to invent 
> new names.

Hmm, how could we tell if the symbol is local?
Global symbols still needs to be load from GOT.
I saw RISC-V dealt that by “lla” pesudo-op which indicate the symbol is local.

> 
>  They may not have been implemented for R6, but I'm not sure.  There was 
> some resistance against macros at one point as the new generation came to 
> work on the MIPS assembler and consequently inconsistencies resulted in 
> the language that may not have b"en removed to date.
> 
>  In any case you need to use `-mno-explicit-relocs' with GCC then so as 
> not to break the compiler's semantics or assumptions.
> 
> > Btw I found we don't have any document for MIPS pseudo-instructions. RISC-V
> > put them in ISA manual
> > but it is not the case for MIPS. Is it possible to have one in binutils?
> 
>  There are MIPS assembly language books available; I'm fairly sure Dominic 
> Sweetman's "See MIPS Run" has a chapter (I don't have the book at hand).  
> I don't think GNU binutils documentation is supposed to describe the 
> assembly dialects supported, except maybe for GNU extensions (pseudo-ops).

Yeah I saw See MIPS Run, but it's not a mandatory specification.
Without a specification we may have different implementation across toolchains and trouble users.

Thanks.

- Jiaxun

> 
>   Maciej
>

-- 
- Jiaxun

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Thu, 25 Feb 2021, Jiaxun Yang wrote:

> > > I'll take this approach first, add "lla, dlla" pseudo-instructions to
> > > assembler and seeking optimization
> > > in future.
> > 
> >  The DLA and LA macros are supposed to do that already, no need to invent 
> > new names.
> 
> Hmm, how could we tell if the symbol is local?
> Global symbols still needs to be load from GOT.

 Just do what all the other MIPS/GAS macros do in this situation.  GAS 
knows whether a given symbol is local or external.

> I saw RISC-V dealt that by “lla” pesudo-op which indicate the symbol is local.

 But RISC-V is not MIPS.  Despite the similarities in the ISA its assembly 
language and psABI conventions are subtly different throughout.

> > > Btw I found we don't have any document for MIPS pseudo-instructions. RISC-V
> > > put them in ISA manual
> > > but it is not the case for MIPS. Is it possible to have one in binutils?
> > 
> >  There are MIPS assembly language books available; I'm fairly sure Dominic 
> > Sweetman's "See MIPS Run" has a chapter (I don't have the book at hand).  
> > I don't think GNU binutils documentation is supposed to describe the 
> > assembly dialects supported, except maybe for GNU extensions (pseudo-ops).
> 
> Yeah I saw See MIPS Run, but it's not a mandatory specification.
> Without a specification we may have different implementation across 
> toolchains and trouble users.

 I do not oppose a normative document, though there are ISAs for which 
several independently developed assembly dialects exist (e.g. x86).

 Traditionally GAS was meant as an assembler solely for GCC output, so it 
used to be adapted as a need arose.  Having a formal specification would 
hinder such quick adaptation.  I think we need to weigh pros and cons 
carefully.

 NB most macros date back to the IRIX if not MIPSCO compiler.  Semantics 
has been documented in books and is pretty straightforward to apply in a 
mechanical manner to new machine instructions that need macroisation.

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Thu, 25 Feb 2021, Jiaxun Yang wrote:

> >   You may want to use composed relocations to refer to .LA1 (R_MIPS_32) and
> > .LA0 (R_MIPS_SUB).  There may or may not be linker updates needed; unlike
> > the RISC-V one the MIPS BFD backend already supports composed relocations
> > with the usual ELF gABI semantics.  It would be good to switch to RELA at
> > this point universally too; none of new stuff will work with old linkers
> > anyway.
> 
> Thanks for your hint;-)
> 
> I'm unsure about how should we express composed relocations in assembly :-/

 Just like we already do; R_MIPS_SUB could be easily produced directly 
from the `-' operator.

 I note too that $pc is effectively used twice in the calculation, 
cancelling itself, so I think we can do better, though it seems to me the 
original semantics of %pcrel_hi/%pcrel_lo pseudo-ops wasn't thought well 
(I guess it was just blindly copied from %hi/%lo by adding PC-relative 
interpretation with no further thinking as to whether it is usable in 
reality).  It seems to me that we could overload the semantics of these 
pseudo-ops in a compatible manner though.

 Also are you concerned about linker relaxation you're possibly working on 
here?  I'm asking because a calculation like (.LA1 - .LA0) works out as an 
assembly constant normally, so it's not a concern really.  And as I recall 
existing MIPS linker relaxation does not rely on label symbols anyway (and 
is probably not defined for plain R6 anyway as I reckon there is nothing 
to relax at the link stage for that ISA).

 Where it might start to matter is the microMIPS ISA however; offhand I 
don't remember what exactly it looks like at R6 though.

> MIPS N32/N64 ABI is already using RELA, do you mean switch to RELA for o32
> as well?

 Yes, with "universally" I meant: "across all the ABIs".

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

在 2021/2/25 上午5:40, Jim Wilson 写道:
> On Wed, Feb 24, 2021 at 6:18 AM Jiaxun Yang <jiaxun.yang@flygoat.com 
> <mailto:jiaxun.yang@flygoat.com>> wrote:
> 
>     I found it's very difficult for GCC to generate this kind of pcrel_lo
>     expression,
>     RTX label_ref can't be lower into such LOW_SUM expression.
> 
> 
> Yes, it is difficult.  You need to generate a label, and put the label 
> number in an unspec in the auipc pattern, and then create a label_ref to 
> put in the addi.  The fact that we have an unspec and a label_ref means 
> a number of optimizations get disabled, like basic block duplication and 
> loop unrolling, because they can't make a copy of an instruction that 
> uses a label as data, as they have no way to know how to duplicate the 
> label itself.  Or at least RISC-V needs to create one label.  You 
> probably need to create two labels.
> 
> There is a far easier way to do this, which is to just emit an assembler 
> macro, and let the assembler generate the labels and relocs.  This is 
> what the RISC-V GCC port does by default.  This prevents some 
> optimizations like scheduling the two instructions, but enables some 
> other optimizations like loop unrolling.  So it is a tossup.  Sometimes 
> we get better code with the assembler macro, and sometimes we get better 
> code by emitting the auipc and addi separately.
> 
> The RISC-V gcc port can emit the auipc/addi with 
> -mexplicit-relocs -mcode-model=medany, but this is known to sometimes 
> fail.  The problem is that if you have an 8-byte variable with 8-byte 
> alignment, and try to load it with 2 4-byte loads, gcc knows that 
> offset+4 must be safe from overflow because the data is 8-byte aligned.  
> However, when you use a pc-relative offset that is data address-code 
> address, the offset is only as aligned as the code is.  RISC-V has 
> 2-byte instruction alignment with the C extension.  So if you have 
> offset+4 and offset is only 2-byte aligned, it is possible that offset+4 
> may overflow the add immediate field.  The same thing can happen with 
> 16-byte data that is 16-byte aligned, accessed with two 8-byte loads.  
> There is no easy software solution.  We just emit a linker error in that 
> case as we can't do anything else.  I think this would work better if 
> auipc cleared some low bits of the result, in which case the pc-relative 
> offset would have enough alignment to prevent overflow when adding small 
> offsets, but it is far too late to change how the RISC-V auipc works.
> 

Hi all,

After spending days poking with AUIPC, I suddenly found we indeed have 
ALUIPC
instruction in MIPS R6, which will clear low 16bit of AUIPC result.

So the whole thing now looks easier, we can have R_MIPS_PC_PAGE and 
R_MIPS_PC_OFST and avoid  all mess we met in RISC-V.

A pcrel loading could be as simple as:
aluipc     a0, %pcrel_page(sym)
addiu      a0, %pcrel_ofst(sym)

Thanks.

- Jiaxun

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Tue, 2 Mar 2021, Jiaxun Yang wrote:

> After spending days poking with AUIPC, I suddenly found we indeed have ALUIPC
> instruction in MIPS R6, which will clear low 16bit of AUIPC result.
> 
> So the whole thing now looks easier, we can have R_MIPS_PC_PAGE and
> R_MIPS_PC_OFST and avoid  all mess we met in RISC-V.
> 
> A pcrel loading could be as simple as:
> aluipc     a0, %pcrel_page(sym)
> addiu      a0, %pcrel_ofst(sym)

 Yes, it should work, but you'll have to 64KiB-align the module in the 
static link.

 You may not need a new relocation for the low part as it looks to me like 
the semantics of plain LO16 fits (though its REL handling peculiarities 
may indeed favour an entirely new "clean" relocation"), but it's a design 
detail and the general principle seems right to me.

 I'm not sure though why you try to avoid composed relocations given we've
had them for 20+ years now.  Relocations are just calculation operators 
for expressions evaluated at link time rather than assembly or high-level 
language compilation time.  And just like we don't invent single operators 
for complex combinations of `+', `&', `%', `<<', etc. and instead compose 
the exiting ones in expressions used in various programming languages to 
get the desired calculation, we don't need to do that for relocation and 
we can just have a collection of simple relocation operators to choose 
from and combine.

  Maciej

Re: HELP: MIPS PC Relative Addressing

[Jiaxun Yang]

在 2021/3/2 下午11:30, Maciej W. Rozycki 写道:
> On Tue, 2 Mar 2021, Jiaxun Yang wrote:
> 
>> After spending days poking with AUIPC, I suddenly found we indeed have ALUIPC
>> instruction in MIPS R6, which will clear low 16bit of AUIPC result.
>>
>> So the whole thing now looks easier, we can have R_MIPS_PC_PAGE and
>> R_MIPS_PC_OFST and avoid  all mess we met in RISC-V.
>>
>> A pcrel loading could be as simple as:
>> aluipc     a0, %pcrel_page(sym)
>> addiu      a0, %pcrel_ofst(sym)
> 
>   Yes, it should work, but you'll have to 64KiB-align the module in the
> static link.
> 
>   You may not need a new relocation for the low part as it looks to me like
> the semantics of plain LO16 fits (though its REL handling peculiarities
> may indeed favour an entirely new "clean" relocation"), but it's a design
> detail and the general principle seems right to me.

Let me take a look ;-)

> 
>   I'm not sure though why you try to avoid composed relocations given we've
> had them for 20+ years now.  Relocations are just calculation operators
> for expressions evaluated at link time rather than assembly or high-level
> language compilation time.  And just like we don't invent single operators
> for complex combinations of `+', `&', `%', `<<', etc. and instead compose
> the exiting ones in expressions used in various programming languages to
> get the desired calculation, we don't need to do that for relocation and
> we can just have a collection of simple relocation operators to choose
> from and combine.

Well just because binutils code drives me crazy:-(
I tired very hard to understand those stuff but when I trying to modify them
I just got endless assert failure or other unreasonable errors :-/

Thanks.

- Jiaxun

> 
>    Maciej
> 

Re: HELP: MIPS PC Relative Addressing

[Maciej W. Rozycki]

On Thu, 4 Mar 2021, Jiaxun Yang wrote:

> >   I'm not sure though why you try to avoid composed relocations given we've
> > had them for 20+ years now.  Relocations are just calculation operators
> > for expressions evaluated at link time rather than assembly or high-level
> > language compilation time.  And just like we don't invent single operators
> > for complex combinations of `+', `&', `%', `<<', etc. and instead compose
> > the exiting ones in expressions used in various programming languages to
> > get the desired calculation, we don't need to do that for relocation and
> > we can just have a collection of simple relocation operators to choose
> > from and combine.
> 
> Well just because binutils code drives me crazy:-(
> I tired very hard to understand those stuff but when I trying to modify them
> I just got endless assert failure or other unreasonable errors :-/

 The code certainly has decades of baggage, it can be complicated and even 
hairy at places.  I guess nobody knows it all or understands all parts 
right away.  However you'll get better with getting around it as you work 
with it longer and get experience, you just need patience.  Nobody says 
learning tough stuff is easy.

 But difficulty with understanding one particular implementation mustn't
drive psABI design decisions!

  Maciej