thr3ads.net - llvm dev - [llvm-dev] Question about a AA result and its use in Dependence Analysis [Jun 2019]

If this information is useful, please help other people find it:
Share via:

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

head link

[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

head link

[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

Seemingly Similar Threads

Search for more possibly parallel threads

llvm dev - Jun 2019 - Question about a AA result and its use in Dependence Analysis

[llvm-dev] Question about a AA result and its use in Dependence Analysis

[llvm-dev] Question about a AA result and its use in Dependence Analysis

[llvm-dev] Question about a AA result and its use in Dependence Analysis

Seemingly Similar Threads