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

[De Azevedo Piovezan, Felipe via llvm-dev]

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