De Azevedo Piovezan, Felipe via llvm-dev
2019-Jun-01 01:22 UTC
[llvm-dev] Question about a AA result and its use in Dependence Analysis
Hi Johannes,
I followed your advice and got the same result: NoAlias and No dependence. Would
you say AA is faulty for saying NoAlias or DA is faulty for saying no
dependence? Or both?
(revised example below)
Thanks!
define float @f() {
entry:
%g = alloca float, align 4
%h = alloca float, align 4
br label %for.body
for.cond.cleanup: ; preds = %for.body
ret float undef
for.body: ; preds = %for.body, %entry
%p = phi float* [ %g, %entry ], [ %q, %for.body ]
%q = phi float* [ %h, %entry ], [ %p, %for.body ]
%0 = load float, float* %p, align 4
store float undef, float* %q, align 4
%branch_cond = fcmp ugt float %0, 0.0
br i1 %branch_cond, label %for.cond.cleanup, label %for.body
}
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x83e1fe0, 1] must alias, Ref Pointers: (float* %p,
LocationSize::precise(4))
AliasSet[0x83e3390, 1] must alias, Mod Pointers: (float* %q,
LocationSize::precise(4))
da analyze -
%0 = load float, float* %p, align 4
store float undef, float* %q, align 4
none!
-----Original Message-----
From: Doerfert, Johannes [mailto:jdoerfert at anl.gov]
Sent: Friday, May 31, 2019 9:07 PM
To: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at intel.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Question about a AA result and its use in Dependence
Analysis
Can you try it without the undef branch condition. If you get still the same
result I'd argue its a bug. In the program as it is, I'd say it is not
because the back edge is never taken.
On 05/31, De Azevedo Piovezan, Felipe via llvm-dev
wrote:> Hello llvm-dev,
>
> I would appreciate your feedback on the following problem. We're trying
to determine whether this is a bug in LLVM or not.
>
> In the IR snippet below, we have two pointers (p and q) which initially
point to two completely non-overlapping locations. Then, on every iteration of a
loop, we swap the pointers and load from the first, followed by a store to the
second.
>
> 1) AA says the two pointers are NoAlias, even though they do point to the
same location if we consider them in distinct loop iterations. Is this right?
> 2) Dependence Analysis says there is no dependence between the load and the
store. Is this right?
>
> define float @f() {
> entry:
> %g = alloca float, align 4
> %h = alloca float, align 4
> br label %for.body
>
> for.cond.cleanup:
> ret float undef
>
> for.body:
> %p = phi float* [ %g, %entry ], [ %q, %for.body ]
> %q = phi float* [ %h, %entry ], [ %p, %for.body ]
> %0 = load float, float* %p, align 4
> store float undef, float* %q, align 4
> br i1 undef, label %for.cond.cleanup, label %for.body }
>
> AliasSet[0x872d800, 1] must alias, Ref Pointers: (float* %p,
LocationSize::precise(4))
> AliasSet[0x872d8b0, 1] must alias, Mod Pointers: (float* %q,
LocationSize::precise(4))
>
> da analyze -
> %0 = load float, float* %p, align 4 ; I added these two debug
statements, DA doesn't print the values it is looking at...
> store float undef, float* %q, align 4 none!
>
> --
> Felipe
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
Johannes Doerfert
Researcher
Argonne National Laboratory
Lemont, IL 60439, USA
jdoerfert at anl.gov
Doerfert, Johannes via llvm-dev
2019-Jun-01 18:28 UTC
[llvm-dev] Question about a AA result and its use in Dependence Analysis
Hi Felipe, (+ Hal) I think the reasoning in `BasicAAResult::aliasPHI(...)` is flawed but I want someone else to take a look as well. As far as I can tell, the reasoning there is as follows: - Two phi nodes in the same block do not alias by default. - They do alias if the pair of inputs from the same predecessor alias. - If all inputs are pair-wise alias free, they do not alias. Now in the case below, %g and %h do clearly not alias, which is what the query for %entry will determine. Since %p and %q are initially assumed to be not aliasing, the query for the incoming values from %for.body will return NoAlias. Cheers, Johannes On 06/01, De Azevedo Piovezan, Felipe wrote:> Hi Johannes, > > I followed your advice and got the same result: NoAlias and No dependence. Would you say AA is faulty for saying NoAlias or DA is faulty for saying no dependence? Or both? > (revised example below) > > Thanks! > > define float @f() { > entry: > %g = alloca float, align 4 > %h = alloca float, align 4 > br label %for.body > > for.cond.cleanup: ; preds = %for.body > ret float undef > > for.body: ; preds = %for.body, %entry > %p = phi float* [ %g, %entry ], [ %q, %for.body ] > %q = phi float* [ %h, %entry ], [ %p, %for.body ] > %0 = load float, float* %p, align 4 > store float undef, float* %q, align 4 > %branch_cond = fcmp ugt float %0, 0.0 > br i1 %branch_cond, label %for.cond.cleanup, label %for.body > } > > Alias Set Tracker: 2 alias sets for 2 pointer values. > AliasSet[0x83e1fe0, 1] must alias, Ref Pointers: (float* %p, LocationSize::precise(4)) > AliasSet[0x83e3390, 1] must alias, Mod Pointers: (float* %q, LocationSize::precise(4)) > > da analyze - > %0 = load float, float* %p, align 4 > store float undef, float* %q, align 4 > none! > > -----Original Message----- > From: Doerfert, Johannes [mailto:jdoerfert at anl.gov] > Sent: Friday, May 31, 2019 9:07 PM > To: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at intel.com> > Cc: llvm-dev at lists.llvm.org > Subject: Re: [llvm-dev] Question about a AA result and its use in Dependence Analysis > > Can you try it without the undef branch condition. If you get still the same result I'd argue its a bug. In the program as it is, I'd say it is not because the back edge is never taken. > > On 05/31, De Azevedo Piovezan, Felipe via llvm-dev wrote: > > Hello llvm-dev, > > > > I would appreciate your feedback on the following problem. We're trying to determine whether this is a bug in LLVM or not. > > > > In the IR snippet below, we have two pointers (p and q) which initially point to two completely non-overlapping locations. Then, on every iteration of a loop, we swap the pointers and load from the first, followed by a store to the second. > > > > 1) AA says the two pointers are NoAlias, even though they do point to the same location if we consider them in distinct loop iterations. Is this right? > > 2) Dependence Analysis says there is no dependence between the load and the store. Is this right? > > > > define float @f() { > > entry: > > %g = alloca float, align 4 > > %h = alloca float, align 4 > > br label %for.body > > > > for.cond.cleanup: > > ret float undef > > > > for.body: > > %p = phi float* [ %g, %entry ], [ %q, %for.body ] > > %q = phi float* [ %h, %entry ], [ %p, %for.body ] > > %0 = load float, float* %p, align 4 > > store float undef, float* %q, align 4 > > br i1 undef, label %for.cond.cleanup, label %for.body } > > > > AliasSet[0x872d800, 1] must alias, Ref Pointers: (float* %p, LocationSize::precise(4)) > > AliasSet[0x872d8b0, 1] must alias, Mod Pointers: (float* %q, LocationSize::precise(4)) > > > > da analyze - > > %0 = load float, float* %p, align 4 ; I added these two debug statements, DA doesn't print the values it is looking at... > > store float undef, float* %q, align 4 none! > > > > -- > > Felipe > > > > > _______________________________________________ > > LLVM Developers mailing list > > llvm-dev at lists.llvm.org > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- > > Johannes Doerfert > Researcher > > Argonne National Laboratory > Lemont, IL 60439, USA > > jdoerfert at anl.gov-- Johannes Doerfert Researcher Argonne National Laboratory Lemont, IL 60439, USA jdoerfert at anl.gov -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 228 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190601/53d9be01/attachment.sig>
De Azevedo Piovezan, Felipe via llvm-dev
2019-Jun-03 16:00 UTC
[llvm-dev] Question about a AA result and its use in Dependence Analysis
It seems the same bug is there if we do pointer swapping with selects. Do you
agree? (see example below)
define void @f() {
entry:
%a1 = alloca float, align 4
%a2 = alloca float, align 4
br label %loop
end:
ret void
loop:
%phi = phi i32 [ 0, %entry ], [ 1, %loop ]
%select_cond = icmp eq i32 %phi, 0
%ptr1 = select i1 %select_cond, float* %a1, float* %a2
%ptr2 = select i1 %select_cond, float* %a2, float* %a1
store float 0.000000e+00, float* %ptr1, align 4
store float 1.000000e+00, float* %ptr2, align 4
br i1 %select_cond, label %end, label %loop
}
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x55bd786b8300, 1] must alias, Mod Pointers: (float* %ptr1,
LocationSize::precise(4))
AliasSet[0x55bd786b96b0, 1] must alias, Mod Pointers: (float* %ptr2,
LocationSize::precise(4))
-----Original Message-----
From: Doerfert, Johannes [mailto:jdoerfert at anl.gov]
Sent: Saturday, June 1, 2019 2:29 PM
To: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at intel.com>
Cc: llvm-dev at lists.llvm.org; Finkel, Hal J. <hfinkel at anl.gov>
Subject: Re: [llvm-dev] Question about a AA result and its use in Dependence
Analysis
Hi Felipe,
(+ Hal)
I think the reasoning in `BasicAAResult::aliasPHI(...)` is flawed but I want
someone else to take a look as well.
As far as I can tell, the reasoning there is as follows:
- Two phi nodes in the same block do not alias by default.
- They do alias if the pair of inputs from the same predecessor alias.
- If all inputs are pair-wise alias free, they do not alias.
Now in the case below, %g and %h do clearly not alias, which is what the query
for %entry will determine. Since %p and %q are initially assumed to be not
aliasing, the query for the incoming values from %for.body will return NoAlias.
Cheers,
Johannes
On 06/01, De Azevedo Piovezan, Felipe wrote:> Hi Johannes,
>
> I followed your advice and got the same result: NoAlias and No dependence.
Would you say AA is faulty for saying NoAlias or DA is faulty for saying no
dependence? Or both?
> (revised example below)
>
> Thanks!
>
> define float @f() {
> entry:
> %g = alloca float, align 4
> %h = alloca float, align 4
> br label %for.body
>
> for.cond.cleanup: ; preds = %for.body
> ret float undef
>
> for.body: ; preds = %for.body,
%entry
> %p = phi float* [ %g, %entry ], [ %q, %for.body ]
> %q = phi float* [ %h, %entry ], [ %p, %for.body ]
> %0 = load float, float* %p, align 4
> store float undef, float* %q, align 4
> %branch_cond = fcmp ugt float %0, 0.0
> br i1 %branch_cond, label %for.cond.cleanup, label %for.body }
>
> Alias Set Tracker: 2 alias sets for 2 pointer values.
> AliasSet[0x83e1fe0, 1] must alias, Ref Pointers: (float* %p,
LocationSize::precise(4))
> AliasSet[0x83e3390, 1] must alias, Mod Pointers: (float* %q,
LocationSize::precise(4))
>
> da analyze -
> %0 = load float, float* %p, align 4
> store float undef, float* %q, align 4 none!
>
> -----Original Message-----
> From: Doerfert, Johannes [mailto:jdoerfert at anl.gov]
> Sent: Friday, May 31, 2019 9:07 PM
> To: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at
intel.com>
> Cc: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Question about a AA result and its use in
> Dependence Analysis
>
> Can you try it without the undef branch condition. If you get still the
same result I'd argue its a bug. In the program as it is, I'd say it is
not because the back edge is never taken.
>
> On 05/31, De Azevedo Piovezan, Felipe via llvm-dev wrote:
> > Hello llvm-dev,
> >
> > I would appreciate your feedback on the following problem. We're
trying to determine whether this is a bug in LLVM or not.
> >
> > In the IR snippet below, we have two pointers (p and q) which
initially point to two completely non-overlapping locations. Then, on every
iteration of a loop, we swap the pointers and load from the first, followed by a
store to the second.
> >
> > 1) AA says the two pointers are NoAlias, even though they do point to
the same location if we consider them in distinct loop iterations. Is this
right?
> > 2) Dependence Analysis says there is no dependence between the load
and the store. Is this right?
> >
> > define float @f() {
> > entry:
> > %g = alloca float, align 4
> > %h = alloca float, align 4
> > br label %for.body
> >
> > for.cond.cleanup:
> > ret float undef
> >
> > for.body:
> > %p = phi float* [ %g, %entry ], [ %q, %for.body ]
> > %q = phi float* [ %h, %entry ], [ %p, %for.body ]
> > %0 = load float, float* %p, align 4
> > store float undef, float* %q, align 4
> > br i1 undef, label %for.cond.cleanup, label %for.body }
> >
> > AliasSet[0x872d800, 1] must alias, Ref Pointers: (float* %p,
LocationSize::precise(4))
> > AliasSet[0x872d8b0, 1] must alias, Mod Pointers: (float* %q,
LocationSize::precise(4))
> >
> > da analyze -
> > %0 = load float, float* %p, align 4 ; I added these two debug
statements, DA doesn't print the values it is looking at...
> > store float undef, float* %q, align 4 none!
> >
> > --
> > Felipe
> >
>
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> --
>
> Johannes Doerfert
> Researcher
>
> Argonne National Laboratory
> Lemont, IL 60439, USA
>
> jdoerfert at anl.gov
--
Johannes Doerfert
Researcher
Argonne National Laboratory
Lemont, IL 60439, USA
jdoerfert at anl.gov