RISC-V sign extension query

RISC-V sign extension query

[Vineet Gupta]

Hi Jeff, Andrew

I've been looking into redundant sign extension and while there are 
things to be improved in REE, there's something I wanted to confirm 
before heading off into the weeds.

Consider the test below:

int foo(int unused, int n, unsigned y, unsigned delta){
   int s = 0;
   unsigned int x = 0;    // if int, sext elided
   for (;x<n;x +=delta)
     s += x+y;
   return s;
}

-O2 -march=rv64gc_zba_zbb_zbs

foo2:
     sext.w    a6,a1            # 1
     beq    a1,zero,.L4
     li    a5,0
     li    a0,0
.L3:
     addw    a4,a2,a5
     addw    a5,a3,a5
     addw    a0,a4,a0
     bltu    a5,a6,.L3
     ret
.L4:
     li    a0,0
     ret

I believe the SEXT.W is not semantically needed as a1 is supposed to be 
sign extended already at call site as per psABI [1]. I quote

     "When passed in registers or on the stack, integer scalars narrower 
than XLEN bits are widened according to the sign of their type up to 32 
bits, then sign-extended to XLEN bits"

However currently RISC-V backend thinks otherwise: changing @x to int, 
causes the the sign extend to go away. I think both the cases should 
behave the same (and not generate SEXT.w) given the ABI clause above. 
Note that this manifests in initial RTL expand itself 
generating/or-not-generating the sign_extend so if it is unnecessary we 
can avoid late fixups in REE.

So the questions is for you to confirm if my conclusions above are correct.

For the cases which do require sign extends, but not being eliminated 
due to "missing definition(s)" I'm working on adapting Ajit's REE ABI 
interfaces work [2] to work for RISC-V as well.

Thx,
-Vineet

[1] 
https://github.com/riscv-non-isa/riscv-elf-psabi-doc/blob/master/riscv-cc.adoc
[2] https://gcc.gnu.org/pipermail/gcc-patches/2023-September/630713.html

Re: RISC-V sign extension query

[Andrew Waterman]

Vineet,

Your understanding of the ABI is correct; both int and unsigned int
arguments must already be sign-extended.  The sext.w is semantically
unnecessary; the bltu could correctly reference a1 instead of a6.

Good luck eliminating it!

Andrew


On Mon, Sep 18, 2023 at 12:45 PM Vineet Gupta <vineetg@rivosinc.com> wrote:
>
> Hi Jeff, Andrew
>
> I've been looking into redundant sign extension and while there are
> things to be improved in REE, there's something I wanted to confirm
> before heading off into the weeds.
>
> Consider the test below:
>
> int foo(int unused, int n, unsigned y, unsigned delta){
>    int s = 0;
>    unsigned int x = 0;    // if int, sext elided
>    for (;x<n;x +=delta)
>      s += x+y;
>    return s;
> }
>
> -O2 -march=rv64gc_zba_zbb_zbs
>
> foo2:
>      sext.w    a6,a1            # 1
>      beq    a1,zero,.L4
>      li    a5,0
>      li    a0,0
> .L3:
>      addw    a4,a2,a5
>      addw    a5,a3,a5
>      addw    a0,a4,a0
>      bltu    a5,a6,.L3
>      ret
> .L4:
>      li    a0,0
>      ret
>
> I believe the SEXT.W is not semantically needed as a1 is supposed to be
> sign extended already at call site as per psABI [1]. I quote
>
>      "When passed in registers or on the stack, integer scalars narrower
> than XLEN bits are widened according to the sign of their type up to 32
> bits, then sign-extended to XLEN bits"
>
> However currently RISC-V backend thinks otherwise: changing @x to int,
> causes the the sign extend to go away. I think both the cases should
> behave the same (and not generate SEXT.w) given the ABI clause above.
> Note that this manifests in initial RTL expand itself
> generating/or-not-generating the sign_extend so if it is unnecessary we
> can avoid late fixups in REE.
>
> So the questions is for you to confirm if my conclusions above are correct.
>
> For the cases which do require sign extends, but not being eliminated
> due to "missing definition(s)" I'm working on adapting Ajit's REE ABI
> interfaces work [2] to work for RISC-V as well.
>
> Thx,
> -Vineet
>
> [1]
> https://github.com/riscv-non-isa/riscv-elf-psabi-doc/blob/master/riscv-cc.adoc
> [2] https://gcc.gnu.org/pipermail/gcc-patches/2023-September/630713.html

Re: RISC-V sign extension query

[Vineet Gupta]

On 9/18/23 13:10, Andrew Waterman wrote:
> Vineet,
>
> Your understanding of the ABI is correct; both int and unsigned int
> arguments must already be sign-extended.  The sext.w is semantically
> unnecessary; the bltu could correctly reference a1 instead of a6.
>
> Good luck eliminating it!

Thanks for the quick response and confirmation !

-Vineet

Re: RISC-V sign extension query

[Jeff Law]

On 9/18/23 13:45, Vineet Gupta wrote:
> Hi Jeff, Andrew
> 
> I've been looking into redundant sign extension and while there are 
> things to be improved in REE, there's something I wanted to confirm 
> before heading off into the weeds.
> 
> Consider the test below:
> 
> int foo(int unused, int n, unsigned y, unsigned delta){
>    int s = 0;
>    unsigned int x = 0;    // if int, sext elided
>    for (;x<n;x +=delta)
>      s += x+y;
>    return s;
> }
> 
> -O2 -march=rv64gc_zba_zbb_zbs
> 
> foo2:
>      sext.w    a6,a1            # 1
>      beq    a1,zero,.L4
>      li    a5,0
>      li    a0,0
> .L3:
>      addw    a4,a2,a5
>      addw    a5,a3,a5
>      addw    a0,a4,a0
>      bltu    a5,a6,.L3
>      ret
> .L4:
>      li    a0,0
>      ret
> 
> I believe the SEXT.W is not semantically needed as a1 is supposed to be 
> sign extended already at call site as per psABI [1]. I quote
> 
>      "When passed in registers or on the stack, integer scalars narrower 
> than XLEN bits are widened according to the sign of their type up to 32 
> bits, then sign-extended to XLEN bits"
That's my understanding.  We can (and should) assume that a sub-word 
argument has been properly sign extended to XLEN.

> 
> However currently RISC-V backend thinks otherwise: changing @x to int, 
> causes the the sign extend to go away. I think both the cases should 
> behave the same (and not generate SEXT.w) given the ABI clause above. 
> Note that this manifests in initial RTL expand itself 
> generating/or-not-generating the sign_extend so if it is unnecessary we 
> can avoid late fixups in REE.
So for parameters I think there are knobs that we can set in the target 
files to indicate they're extended/promoted.  TARGET_PROMOTE_PROTOTYPES 
would be a good search term I think.  I don't think it's a heavily used 
feature, so we may need to beat on it a little to get it to do what we want.



Jeff

Re: RISC-V sign extension query

[Jeff Law]

On 9/18/23 13:45, Vineet Gupta wrote:

> 
> For the cases which do require sign extends, but not being eliminated 
> due to "missing definition(s)" I'm working on adapting Ajit's REE ABI 
> interfaces work [2] to work for RISC-V as well.
I wonder if we could walk the DECL_ARGUMENTS for current_function_decl 
and create sign extensions for integer arguments smaller than XLEN at 
the start of the function.  Record them in a list.

Then we just let the rest of REE do its thing.  When REE is done we go 
back and delete those sign extensions we created.

Assuming that works, then we just need to conditionalize the code on ABI 
properties.



Jeff

PR 111/466 (was Re: RISC-V sign extension query)

[Vineet Gupta]

On 9/18/23 19:41, Jeff Law wrote:
> On 9/18/23 13:45, Vineet Gupta wrote:
>>
>> For the cases which do require sign extends, but not being eliminated 
>> due to "missing definition(s)" I'm working on adapting Ajit's REE ABI 
>> interfaces work [2] to work for RISC-V as well.
> I wonder if we could walk the DECL_ARGUMENTS for current_function_decl 
> and create sign extensions for integer arguments smaller than XLEN at 
> the start of the function.  Record them in a list.
>
> Then we just let the rest of REE do its thing.  When REE is done we go 
> back and delete those sign extensions we created.

Umm, not sure I follow: the need for creating more sign extends.

At least for test in PR/111466 one's already present, at the entry for 
REE. And given these are hard regs, Ajit's code is able to identify them 
as functions args or return etc.

> Assuming that works, then we just need to conditionalize the code on 
> ABI properties.

Right, in the production version it could be a new target hook. For 
power it would be true for ZERO_EXTEND, for RISC-V true for sign_Extend etc.
As of now ive hacked Ajit's patch to check for both of them. It seems to 
be doing something.

However in my current approach I'm trying to not have to do this in ree 
at all if we can remove these at expand time.
RISC-V doesn't have TARGET_PROMOTE_PROTOTYPES, but per documentation it 
is needed for types smaller than int. This case already has int.
I'm trying to wrap my head around PROMOTE_MODE and 
TARGET_PROMOTE_FUNCTION_MODE.

Thx,
-Vineet

Re: RISC-V sign extension query

[Vineet Gupta]

On 9/18/23 19:41, Jeff Law wrote:
> On 9/18/23 13:45, Vineet Gupta wrote:
>
>>
>> For the cases which do require sign extends, but not being eliminated 
>> due to "missing definition(s)" I'm working on adapting Ajit's REE ABI 
>> interfaces work [2] to work for RISC-V as well.
> I wonder if we could walk the DECL_ARGUMENTS for current_function_decl 
> and create sign extensions for integer arguments smaller than XLEN at 
> the start of the function.  Record them in a list.
>
> Then we just let the rest of REE do its thing.  When REE is done we go 
> back and delete those sign extensions we created.

Forgot to add that even if we were to do this (and the test is doing 
this already), REE would fail anyways. It does DF use/def traversal - 
starting with use in an extension insn and finding the defs. If the def 
was implicit - as in a function arg, it bails out. This is essentially 
what Ajit is trying to fix by identifying the def as a potential 
function arg and not bailing.

Thx,
-Vineet

Re: RISC-V sign extension query

[Jeff Law]

On 9/18/23 21:37, Vineet Gupta wrote:
> On 9/18/23 19:41, Jeff Law wrote:
>> On 9/18/23 13:45, Vineet Gupta wrote:
>>
>>>
>>> For the cases which do require sign extends, but not being eliminated 
>>> due to "missing definition(s)" I'm working on adapting Ajit's REE ABI 
>>> interfaces work [2] to work for RISC-V as well.
>> I wonder if we could walk the DECL_ARGUMENTS for current_function_decl 
>> and create sign extensions for integer arguments smaller than XLEN at 
>> the start of the function.  Record them in a list.
>>
>> Then we just let the rest of REE do its thing.  When REE is done we go 
>> back and delete those sign extensions we created.
> 
> Forgot to add that even if we were to do this (and the test is doing 
> this already), REE would fail anyways. It does DF use/def traversal - 
> starting with use in an extension insn and finding the defs. If the def 
> was implicit - as in a function arg, it bails out. This is essentially 
> what Ajit is trying to fix by identifying the def as a potential 
> function arg and not bailing.
> 
Right.  What I'm suggesting is to create an explicit extension in the IL 
at the very beginning of REE for the appropriate arguments.  Put the 
extension in the entry block.

That would make extensions that were previously in the RTL redundant 
allowing REE to remove them.

Then we also remove the explicitly added extensions.

Think of the extensions we're adding as expressing the the extension 
that the caller would have done and would expose the redundant 
extensions in the callee.  We put them in the IL merely to make the 
existing REE algorithm happy.  Once they've served their purpose in 
exposing redundant extensions we remove the ones we added.

If you're familiar with DSE there's a lot of similarities with how we 
discover dead stores into the stack.  We pretend there's a store to each 
local frame slot in the epilogue, that in turn exposes stores into the 
local frame that would never be read because we're exiting the function.

Jeff

Re: RISC-V sign extension query

[Vineet Gupta]

Hi Jeff,

On 9/19/23 07:59, Jeff Law wrote:
>
>
> On 9/18/23 21:37, Vineet Gupta wrote:
>> On 9/18/23 19:41, Jeff Law wrote:
>>> On 9/18/23 13:45, Vineet Gupta wrote:
>>>
>>>>
>>>> For the cases which do require sign extends, but not being 
>>>> eliminated due to "missing definition(s)" I'm working on adapting 
>>>> Ajit's REE ABI interfaces work [2] to work for RISC-V as well.
>>> I wonder if we could walk the DECL_ARGUMENTS for 
>>> current_function_decl and create sign extensions for integer 
>>> arguments smaller than XLEN at the start of the function. Record 
>>> them in a list.
>>>
>>> Then we just let the rest of REE do its thing.  When REE is done we 
>>> go back and delete those sign extensions we created.
>>
>> [..]
>>
> Right.  What I'm suggesting is to create an explicit extension in the 
> IL at the very beginning of REE for the appropriate arguments.  Put 
> the extension in the entry block.
>
> That would make extensions that were previously in the RTL redundant 
> allowing REE to remove them.
>
> Then we also remove the explicitly added extensions.
>
> Think of the extensions we're adding as expressing the the extension 
> that the caller would have done and would expose the redundant 
> extensions in the callee.  We put them in the IL merely to make the 
> existing REE algorithm happy.  Once they've served their purpose in 
> exposing redundant extensions we remove the ones we added.
>
> If you're familiar with DSE there's a lot of similarities with how we 
> discover dead stores into the stack.  We pretend there's a store to 
> each local frame slot in the epilogue, that in turn exposes stores 
> into the local frame that would never be read because we're exiting 
> the function.

We touched upon this in our airport "rendezvous". I'm curious if you 
have the wip bits lying around - (a) to get a feel for how this could be 
done and (b) to see why REE and/or similar construct in CSE don't work 
as expected.

Thx,
-Vineet

Re: RISC-V sign extension query

[Jeff Law]

On 9/27/23 00:29, Vineet Gupta wrote:
> Hi Jeff,

> 
> We touched upon this in our airport "rendezvous". I'm curious if you 
> have the wip bits lying around - (a) to get a feel for how this could be 
> done and (b) to see why REE and/or similar construct in CSE don't work 
> as expected.
Not in any usable form.  Just several variants that didn't work ;-)

They don't work with REE because I'd forgotten a key point.  REE doesn't 
look for lexical redundancies like you'd see with CSE/PRE.  ie, given a 
pair of identical sign extensions in the IL, REE doesn't eliminate one.

Instead REE is focused on cases where we can transform an existing 
operation such as a load into an extending load to eliminate a 
subsequent extension.

This leads to a couple thoughts.

First, we ought to be able to use the same concept, but instead of 
putting something like this into the IL to express the extension done by 
the caller

(set (reg:DI a0) (sign_extend:DI (reg:SI a0)))

Instead we probably want to insert this as a dummy into the IL

(set (reg:SI a0) (mem:SI (sp))

If this is followed by a sign extension, then it'll get turned into

(set (reg:DI a0) (sign_extend:DI (mem:SI (sp)))

And the subsequent extension will get removed.  And since we've tracked 
the dummy, we can just eliminate the dummy as well.  I'm a bit worried 
about how this plays with the copy_needed bits in REE.

This should at least tell us how often there's an extension of an 
incoming argument that can be trivially eliminated.  I'm not sure it's 
the best place to eliminate the extensions though.  Leading to....



We should make sure that CSE/PRE are properly identifying and 
eliminating lexical redundancies.   I wouldn't be surprised if the class 
of problems we're chasing are better detected and optimized by CSE/PRE 
since those can work on an extended block or global basis respectively.

For CSE/PRE we'd want to insert something like

(set (reg:DI a0) (sign_extend:DI (reg:SI a0)))

Into the IL which should make any expressions like

(sign_extend:DI (reg:SI a0))

fully redundant in the IL, thus allowing CSE/PRE to eliminate them.

I've got a few things backed up from before the Cauldron, but expect to 
be able to poke at this some this week.

jeff