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:

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

Finkel, Hal J. via llvm-dev

2019-Jun-03 21:01 UTC

head link

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

On 6/3/19 1:45 PM, Eli Friedman via llvm-dev wrote:

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.


+1

The flaw here seems to be in the way that DA is using AA.
DependenceAnalysis's underlyingObjectsAlias is doing this:

  // Check the original locations (minus size) for noalias, which can happen for
  // tbaa, incompatible underlying object locations, etc.
  MemoryLocation LocAS(LocA.Ptr, LocationSize::unknown(), LocA.AATags);
  MemoryLocation LocBS(LocB.Ptr, LocationSize::unknown(), LocB.AATags);
  if (AA->alias(LocAS, LocBS) == NoAlias)
    return NoAlias;

  // Check the underlying objects are the same
  const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);
  const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);

  // If the underlying objects are the same, they must alias
  if (AObj == BObj)
    return MustAlias;

  // We may have hit the recursion limit for underlying objects, or have
  // underlying objects where we don't know they will alias.
  if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
    return MayAlias;

  // Otherwise we know the objects are different and both identified objects so
  // must not alias.
  return NoAlias;


and I recall suggesting this use of AA to pick up the metadata-based AA results.
We shouldn't need both the AA check here and the underlying-object check
also, as the AA check includes an underlying-object check (and not much else,
aside from checks on metadata, when both sizes are unknown). However, as this
example shows, the fact that the two SSA values in question refer to different,
identified underlying objects, doesn't prevent them from having a
cross-iteration dependence as the identify of those underlying objects can
change across different iterations (and, thus, the underlying object of one
variable in one iteration might be the underlying object used by another
variable in another iteration).

I'm open to suggestions on how to best resolve this situation. I'm
leaning toward suggesting that we have a metadata-only AA query, and use that
here, instead of calling something that will invoke BasicAA's logic. My
metadata-only AA query, I specifically mean a fundamental dependency-analysis
query, likely implemented by the AA subsystem for code-reuse reasons, which
answers the question: is there some reason to believe that any instances of
these two values never take the same value along any dynamic path through the
CFG (or something similar).


Thanks again,

Hal




For information across loop iterations, the appropriate analysis is probably
LoopAccessAnalysis.

-Eli



-----Original Message-----
From: llvm-dev <llvm-dev-bounces at
lists.llvm.org><mailto: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><mailto:felipe.de.azevedo.piovezan at intel.com>
Cc: llvm-dev at lists.llvm.org<mailto: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<mailto:jdoerfert at anl.gov>


________________________________________
From: De Azevedo Piovezan, Felipe <felipe.de.azevedo.piovezan at
intel.com><mailto:felipe.de.azevedo.piovezan at intel.com>
Sent: Monday, June 3, 2019 11:00
To: Doerfert, Johannes
Cc: llvm-dev at lists.llvm.org<mailto: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><mailto:felipe.de.azevedo.piovezan at intel.com>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>; Finkel,
Hal J. <hfinkel at anl.gov><mailto: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><mailto:felipe.de.azevedo.piovezan at intel.com>
Cc: llvm-dev at lists.llvm.org<mailto: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<mailto: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<mailto:jdoerfert at anl.gov>



--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov<mailto:jdoerfert at anl.gov>
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190603/330ad437/attachment.html>

David Green via llvm-dev

2019-Jun-05 17:02 UTC

head link

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

Oh. So it wasn't just the memory location size that was incorrect on those
aliasing checks.

I took a look at the tests and it appears that the alias call also catches some
cases of restrict/noalias attributes, along with the tbaa info. My first idea of
constructing an alias call with no Ptr's but valid tbaa info won't catch
that at least.

I will create a bug report and try and see if I can come up with anything more
sensible.

Dave





From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Finkel,
Hal J. via llvm-dev <llvm-dev at lists.llvm.org>
Sent: 03 June 2019 22:01
To: Eli Friedman; Doerfert, Johannes; De Azevedo Piovezan, Felipe; llvm-dev
Subject: Re: [llvm-dev] Question about a AA result and its use in Dependence
Analysis
 




On 6/3/19 1:45 PM, Eli Friedman via llvm-dev wrote:

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.




+1

The flaw here seems to be in the way that DA is using AA.
DependenceAnalysis's underlyingObjectsAlias is doing this:

  // Check the original locations (minus size) for noalias, which can happen for
  // tbaa, incompatible underlying object locations, etc.
  MemoryLocation LocAS(LocA.Ptr, LocationSize::unknown(), LocA.AATags);
  MemoryLocation LocBS(LocB.Ptr, LocationSize::unknown(), LocB.AATags);
  if (AA->alias(LocAS, LocBS) == NoAlias)
    return NoAlias;

  // Check the underlying objects are the same
  const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);
  const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);

  // If the underlying objects are the same, they must alias
  if (AObj == BObj)
    return MustAlias;

  // We may have hit the recursion limit for underlying objects, or have
  // underlying objects where we don't know they will alias.
  if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
    return MayAlias;

  // Otherwise we know the objects are different and both identified objects so
  // must not alias.
  return NoAlias;




and I recall suggesting this use of AA to pick up the metadata-based AA results.
We shouldn't need both the AA check here and the underlying-object check
also, as the AA check includes an underlying-object check (and not much else,
aside from checks on metadata, when both sizes are unknown). However, as this
example shows, the fact that the two SSA values in question refer to different,
identified underlying objects, doesn't prevent them from having a
cross-iteration dependence as the identify of those underlying objects can
change across different iterations (and, thus, the underlying object of one
variable in one iteration might be the underlying object used by another
variable in another iteration).

I'm open to suggestions on how to best resolve this situation. I'm
leaning toward suggesting that we have a metadata-only AA query, and use that
here, instead of calling something that will invoke BasicAA's logic. My
metadata-only AA query, I specifically mean a fundamental dependency-analysis
query, likely implemented by the AA subsystem for code-reuse reasons, which
answers the question: is there some reason to believe that any instances of
these two values never take the same value along any dynamic path through the
CFG (or something similar).





Thanks again,

Hal




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

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

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