<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 6/3/19 1:45 PM, Eli Friedman via llvm-dev wrote:<br>
</div>
<blockquote type="cite" cite="mid:d8702af4ff454a379bffddd91a679114@NALASEXR01B.na.qualcomm.com">
<pre class="moz-quote-pre" wrap="">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.</pre>
</blockquote>
<p><br>
</p>
<p>+1</p>
<p>The flaw here seems to be in the way that DA is using AA. DependenceAnalysis's underlyingObjectsAlias is doing this:</p>
<p></p>
<blockquote type="cite"><font size="-2"> // Check the original locations (minus size) for noalias, which can happen for<br>
// tbaa, incompatible underlying object locations, etc.<br>
MemoryLocation LocAS(LocA.Ptr, LocationSize::unknown(), LocA.AATags);<br>
MemoryLocation LocBS(LocB.Ptr, LocationSize::unknown(), LocB.AATags);<br>
if (AA->alias(LocAS, LocBS) == NoAlias)<br>
return NoAlias;<br>
<br>
// Check the underlying objects are the same<br>
const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);<br>
const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);<br>
<br>
// If the underlying objects are the same, they must alias<br>
if (AObj == BObj)<br>
return MustAlias;<br>
<br>
// We may have hit the recursion limit for underlying objects, or have<br>
// underlying objects where we don't know they will alias.<br>
if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))<br>
return MayAlias;<br>
<br>
// Otherwise we know the objects are different and both identified objects so<br>
// must not alias.<br>
return NoAlias;</font><br>
</blockquote>
<br>
<p></p>
<p>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).</p>
<p>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).<br>
</p>
<p><br>
</p>
<p>Thanks again,</p>
<p>Hal</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:d8702af4ff454a379bffddd91a679114@NALASEXR01B.na.qualcomm.com">
<pre class="moz-quote-pre" wrap="">
For information across loop iterations, the appropriate analysis is probably LoopAccessAnalysis.
-Eli
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">-----Original Message-----
From: llvm-dev <a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev-bounces@lists.llvm.org"><llvm-dev-bounces@lists.llvm.org></a> On Behalf Of Doerfert,
Johannes via llvm-dev
Sent: Monday, June 3, 2019 9:04 AM
To: De Azevedo Piovezan, Felipe <a class="moz-txt-link-rfc2396E" href="mailto:felipe.de.azevedo.piovezan@intel.com"><felipe.de.azevedo.piovezan@intel.com></a>
Cc: <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
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
<a class="moz-txt-link-abbreviated" href="mailto:jdoerfert@anl.gov">jdoerfert@anl.gov</a>
________________________________________
From: De Azevedo Piovezan, Felipe <a class="moz-txt-link-rfc2396E" href="mailto:felipe.de.azevedo.piovezan@intel.com"><felipe.de.azevedo.piovezan@intel.com></a>
Sent: Monday, June 3, 2019 11:00
To: Doerfert, Johannes
Cc: <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>; 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 [<a class="moz-txt-link-freetext" href="mailto:jdoerfert@anl.gov">mailto:jdoerfert@anl.gov</a>]
Sent: Saturday, June 1, 2019 2:29 PM
To: De Azevedo Piovezan, Felipe <a class="moz-txt-link-rfc2396E" href="mailto:felipe.de.azevedo.piovezan@intel.com"><felipe.de.azevedo.piovezan@intel.com></a>
Cc: <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>; Finkel, Hal J. <a class="moz-txt-link-rfc2396E" href="mailto:hfinkel@anl.gov"><hfinkel@anl.gov></a>
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:
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">Hi Johannes,
I followed your advice and got the same result: NoAlias and No dependence.
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">Would you say AA is faulty for saying NoAlias or DA is faulty for saying no
dependence? Or both?
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">(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,
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">LocationSize::precise(4))
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap=""> AliasSet[0x83e3390, 1] must alias, Mod Pointers: (float* %q,
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">LocationSize::precise(4))
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
da analyze -
%0 = load float, float* %p, align 4
store float undef, float* %q, align 4 none!
-----Original Message-----
From: Doerfert, Johannes [<a class="moz-txt-link-freetext" href="mailto:jdoerfert@anl.gov">mailto:jdoerfert@anl.gov</a>]
Sent: Friday, May 31, 2019 9:07 PM
To: De Azevedo Piovezan, Felipe <a class="moz-txt-link-rfc2396E" href="mailto:felipe.de.azevedo.piovezan@intel.com"><felipe.de.azevedo.piovezan@intel.com></a>
Cc: <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
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
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">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.
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
On 05/31, De Azevedo Piovezan, Felipe via llvm-dev wrote:
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">Hello llvm-dev,
I would appreciate your feedback on the following problem. We're trying to
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">determine whether this is a bug in LLVM or not.
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
In the IR snippet below, we have two pointers (p and q) which initially point
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">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.
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
1) AA says the two pointers are NoAlias, even though they do point to the
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">same location if we consider them in distinct loop iterations. Is this right?
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">2) Dependence Analysis says there is no dependence between the load and
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">the store. Is this right?
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
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,
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">LocationSize::precise(4))
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">AliasSet[0x872d8b0, 1] must alias, Mod Pointers: (float* %q,
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">LocationSize::precise(4))
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">
da analyze -
%0 = load float, float* %p, align 4 ; I added these two debug statements,
</pre>
</blockquote>
</blockquote>
<pre class="moz-quote-pre" wrap="">DA doesn't print the values it is looking at...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap=""> store float undef, float* %q, align 4 none!
--
Felipe
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">
--
Johannes Doerfert
Researcher
Argonne National Laboratory
Lemont, IL 60439, USA
<a class="moz-txt-link-abbreviated" href="mailto:jdoerfert@anl.gov">jdoerfert@anl.gov</a>
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">
--
Johannes Doerfert
Researcher
Argonne National Laboratory
Lemont, IL 60439, USA
<a class="moz-txt-link-abbreviated" href="mailto:jdoerfert@anl.gov">jdoerfert@anl.gov</a>
_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>