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
Doerfert, Johannes via llvm-dev
2019-Jun-03 16:04 UTC
[llvm-dev] Question about a AA result and its use in Dependence Analysis
Thanks for investigating this further.
In BasicAAResult::aliasSelect the "same" logic is used:
// If the values are Selects with the same condition, we can do a more
precise
// check: just check for aliases between the values on corresponding arms.
That is what happens for PHI nodes as well. So, if either is broken both are.
Now it remains to definitively decide if this is broken (which I still think).
---------------------------------------
Johannes Doerfert
Researcher
Argonne National Laboratory
Lemont, IL 60439, USA
jdoerfert at anl.gov
________________________________________
From: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at
intel.com>
Sent: Monday, June 3, 2019 11:00
To: Doerfert, Johannes
Cc: llvm-dev at lists.llvm.org; Finkel, Hal J.
Subject: RE: [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
Eli Friedman via llvm-dev
2019-Jun-03 18:45 UTC
[llvm-dev] Question about a AA result and its use in Dependence Analysis
Alias analysis is figuring out the relationship between two pointer expressions, at some location in the program. At a given point in the program, do two expressions always refer to the same location? At a given point in the program, do two expressions never refer to the same location? AliasAnalysis::alias() doesn't explicitly take a "point" in the program because we don't implement any alias analysis that cares about the precise point in the program; the answer applies to any point in the program dominated by the definitions of both values. This produces useful results because LLVM uses SSA form. Working from that definition, it's easy to see that the logic used in aliasSelect is valid, and that aliasPHI is returning the correct result for the given example. Maybe it's worth calling this out in the alias analysis documentation. For information across loop iterations, the appropriate analysis is probably LoopAccessAnalysis. -Eli> -----Original Message----- > From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Doerfert, > Johannes via llvm-dev > Sent: Monday, June 3, 2019 9:04 AM > To: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at intel.com> > Cc: llvm-dev at lists.llvm.org > Subject: [EXT] Re: [llvm-dev] Question about a AA result and its use in > Dependence Analysis > > Thanks for investigating this further. > > In BasicAAResult::aliasSelect the "same" logic is used: > > // If the values are Selects with the same condition, we can do a more precise > // check: just check for aliases between the values on corresponding arms. > > That is what happens for PHI nodes as well. So, if either is broken both are. > Now it remains to definitively decide if this is broken (which I still think). > > > --------------------------------------- > Johannes Doerfert > Researcher > > Argonne National Laboratory > Lemont, IL 60439, USA > > jdoerfert at anl.gov > > > ________________________________________ > From: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at intel.com> > Sent: Monday, June 3, 2019 11:00 > To: Doerfert, Johannes > Cc: llvm-dev at lists.llvm.org; Finkel, Hal J. > Subject: RE: [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 > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev