sparse-llvm issue with handling of phisrc instruction

sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi

I am trying to see if sparse-llvm can handle unsimplified IR output
from linearizer. I think there is a problem in how it handles phisrc.
Example:

static int testfunc(int i) {
return i-6;
}

Linearied IR:
testfunc:
.L0:
        <entry-point>
        store.32    %arg1 -> 0[i]
        load.32     %r1 <- 0[i]
        sub.32      %r2 <- %r1, $6
        phisrc.32   %phi1(return) <- %r2
        br          .L1

.L1:
        phi.32      %r3 <- %phi1(return)
        ret.32      %r2


But the LLVM IR is missing a store instruction corresponding to the
phisrc instruction:

define internal i32 @testfunc(i32 %ARG1) {
L0:
  %i_0000029F015CAA78 = alloca i32
  %0 = alloca i32
  %1 = ptrtoint i32* %i_0000029F015CAA78 to i64
  %2 = add i64 %1, 0
  %3 = inttoptr i64 %2 to i32*
  store i32 %ARG1, i32* %3
  %4 = ptrtoint i32* %i_0000029F015CAA78 to i64
  %5 = add i64 %4, 0
  %6 = inttoptr i64 %5 to i32*
  %load_target = load i32, i32* %6
  %R2 = sub i32 %load_target, 6
  br label %L1

L1:                                               ; preds = %L0
  %7 = load i32, i32* %0
  ret i32 %R2
}

Basically we need a store from %i_0000029F015CAA78 to %0 output for
the phisrc instruction above.

I see that it emits stores for phi_users when it encounters a phisrc
but the phi_users list appears to be empty here. Is that expected? If
so, then how to fix this issue i.e. add the missing store?

Thanks and Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 5:46 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi
>
> I am trying to see if sparse-llvm can handle unsimplified IR output
> from linearizer. I think there is a problem in how it handles phisrc.

Does your non-simplified sparse IR contain the liveness information?
I think those are needed for the handling of OP_PHI & OP_PHISOURCE
in sparse-llvm.

Luc

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 17:38, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Mar 22, 2017 at 5:46 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> I am trying to see if sparse-llvm can handle unsimplified IR output
>> from linearizer. I think there is a problem in how it handles phisrc.
>
> Does your non-simplified sparse IR contain the liveness information?
> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
> in sparse-llvm.
>

Probably not - I commented out everything in linearize_fn() from
simplify_symbol_usage() and downwards. Please tell me if this is
incorrect.

Thanks and Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 7:05 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Luc,
>
> On 22 March 2017 at 17:38, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Wed, Mar 22, 2017 at 5:46 PM, Dibyendu Majumdar
>> <mobile@majumdar.org.uk> wrote:
>>> I am trying to see if sparse-llvm can handle unsimplified IR output
>>> from linearizer. I think there is a problem in how it handles phisrc.
>>
>> Does your non-simplified sparse IR contain the liveness information?
>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
>> in sparse-llvm.
>>
>
> Probably not - I commented out everything in linearize_fn() from
> simplify_symbol_usage() and downwards. Please tell me if this is
> incorrect.

As far as I understand, sparse-llvm needs track_pseudo_liveness().

-- Luc

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 18:15, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>>>> I am trying to see if sparse-llvm can handle unsimplified IR output
>>>> from linearizer. I think there is a problem in how it handles phisrc.
>>>
>>> Does your non-simplified sparse IR contain the liveness information?
>>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
>>> in sparse-llvm.
>>>
>>
>> Probably not - I commented out everything in linearize_fn() from
>> simplify_symbol_usage() and downwards. Please tell me if this is
>> incorrect.
>
> As far as I understand, sparse-llvm needs track_pseudo_liveness().
>

Tried that - it made no difference.

Regards

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 18:17, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>>>>> I am trying to see if sparse-llvm can handle unsimplified IR output
>>>>> from linearizer. I think there is a problem in how it handles phisrc.
>>>>
>>>> Does your non-simplified sparse IR contain the liveness information?
>>>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
>>>> in sparse-llvm.
>>>>
>>>
>>> Probably not - I commented out everything in linearize_fn() from
>>> simplify_symbol_usage() and downwards. Please tell me if this is
>>> incorrect.
>>
>> As far as I understand, sparse-llvm needs track_pseudo_liveness().
>>
>
> Tried that - it made no difference.
>

If there is a single phisrc and phi instruction then is phisrc meant
to have the phi in its user list?

I am trying out a different way of handling phisrc - I will let you
know if it works.

Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 06:55:37PM +0000, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 22 March 2017 at 18:17, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> >>>>> I am trying to see if sparse-llvm can handle unsimplified IR output
> >>>>> from linearizer. I think there is a problem in how it handles phisrc.
> >>>>
> >>>> Does your non-simplified sparse IR contain the liveness information?
> >>>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
> >>>> in sparse-llvm.
> >>>>
> >>>
> >>> Probably not - I commented out everything in linearize_fn() from
> >>> simplify_symbol_usage() and downwards. Please tell me if this is
> >>> incorrect.
> >>
> >> As far as I understand, sparse-llvm needs track_pseudo_liveness().
> >>
> >
> > Tried that - it made no difference.
> >
> 
> If there is a single phisrc and phi instruction then is phisrc meant
> to have the phi in its user list?

Yes but again this may depends on the simplification for
its correctness.

Also, for phi-nodes liveness is a bit different, unintuitive at first,
the PSEUDO_PHI play no role in liveness. So, in IR code like:
   .L0
	phisrc	%phi1 <- ...
	...

   .L1
	phi	%r2 <- %phi1, %phi2

the "liveness between .L0 & .L1" is not made via %phi1 but with the
"real" pseudo: %r2 (.L0 defines %r2, .L1 needs %r2).
 
-- Luc

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 20:42, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Mar 22, 2017 at 06:55:37PM +0000, Dibyendu Majumdar wrote:
>> If there is a single phisrc and phi instruction then is phisrc meant
>> to have the phi in its user list?
>
> Yes but again this may depends on the simplification for
> its correctness.
>
> Also, for phi-nodes liveness is a bit different, unintuitive at first,
> the PSEUDO_PHI play no role in liveness. So, in IR code like:
>    .L0
>         phisrc  %phi1 <- ...
>         ...
>
>    .L1
>         phi     %r2 <- %phi1, %phi2
>
> the "liveness between .L0 & .L1" is not made via %phi1 but with the
> "real" pseudo: %r2 (.L0 defines %r2, .L1 needs %r2).
>

Luckily (or by design) the track_pseudo_death() is called right at the
end after all the modifications are done. So I think it will always be
correct as long as this is called.

Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 9:48 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Luckily (or by design) the track_pseudo_death() is called right at the
> end after all the modifications are done. So I think it will always be
> correct as long as this is called.

It's very much by design, almost by necessity.

-- Luc

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 06:17:50PM +0000, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> On 22 March 2017 at 18:15, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >>>> I am trying to see if sparse-llvm can handle unsimplified IR output
> >>>> from linearizer. I think there is a problem in how it handles phisrc.
> >>>
> >>> Does your non-simplified sparse IR contain the liveness information?
> >>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
> >>> in sparse-llvm.
> >>>
> >>
> >> Probably not - I commented out everything in linearize_fn() from
> >> simplify_symbol_usage() and downwards. Please tell me if this is
> >> incorrect.
> >
> > As far as I understand, sparse-llvm needs track_pseudo_liveness().
> >
> 
> Tried that - it made no difference.

I'm not sure liveness info has much sense without simplification,
at least part of it.

-- Luc

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 19:29, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> >>>> I am trying to see if sparse-llvm can handle unsimplified IR output
>> >>>> from linearizer. I think there is a problem in how it handles phisrc.
>> >>>
>> >>> Does your non-simplified sparse IR contain the liveness information?
>> >>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
>> >>> in sparse-llvm.
>> >>>
>> >>
>> >> Probably not - I commented out everything in linearize_fn() from
>> >> simplify_symbol_usage() and downwards. Please tell me if this is
>> >> incorrect.
>> >
>> > As far as I understand, sparse-llvm needs track_pseudo_liveness().
>> >
>>
>> Tried that - it made no difference.
>
> I'm not sure liveness info has much sense without simplification,
> at least part of it.
>

You were right - I needed to retain following line:

track_pseudo_death(C, ep);

I mistakenly thought (going by name) that I had to call:

track_pseudo_liveness(C, ep);

Anyway it appears that this now populates the phi_users list so that
the code works correctly.

Thanks for your help.

Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Dibyendu Majumdar]

Hi Luc,

On 22 March 2017 at 19:46, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
>
> You were right - I needed to retain following line:
>
> track_pseudo_death(C, ep);
>
> Anyway it appears that this now populates the phi_users list so that
> the code works correctly.
>

Of course now I can see the following in sparse-llvm:

/* need ->phi_users */
dbg_dead = 1;

Regards
Dibyendu

Re: sparse-llvm issue with handling of phisrc instruction

[Luc Van Oostenryck]

On Wed, Mar 22, 2017 at 8:46 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Luc,
>
> On 22 March 2017 at 19:29, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>> >>>> I am trying to see if sparse-llvm can handle unsimplified IR output
>>> >>>> from linearizer. I think there is a problem in how it handles phisrc.
>>> >>>
>>> >>> Does your non-simplified sparse IR contain the liveness information?
>>> >>> I think those are needed for the handling of OP_PHI & OP_PHISOURCE
>>> >>> in sparse-llvm.
>>> >>>
>>> >>
>>> >> Probably not - I commented out everything in linearize_fn() from
>>> >> simplify_symbol_usage() and downwards. Please tell me if this is
>>> >> incorrect.
>>> >
>>> > As far as I understand, sparse-llvm needs track_pseudo_liveness().
>>> >
>>>
>>> Tried that - it made no difference.
>>
>> I'm not sure liveness info has much sense without simplification,
>> at least part of it.
>>
>
> You were right - I needed to retain following line:
>
> track_pseudo_death(C, ep);
>
> I mistakenly thought (going by name) that I had to call:
>
> track_pseudo_liveness(C, ep);

It's what I thought too :)

> Anyway it appears that this now populates the phi_users list so that
> the code works correctly.
>
> Thanks for your help.

Great.
You're welcome.