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

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190531/abb502c6/attachment.html>

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
-------------- 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/05640db0/attachment.sig>

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