Hello fellow LLVM developers,
I was wondering about the semantic of aliasing.
Here are some examples where I am not sure if the two stores aliases:
Example 1:
for (int i = 2; i < n; ++i) {
store A[i];
store A[i-2];
}
Example 2:
for (int i = 2; i < n; ++i)
store A[i];
for (int i = 2; i < n; ++i)
store A[i-2];
In the example 1, they do not alias in a single iteration, but they do
alias at some point if n > 4.
That is, there is an execution path from one instance of the store to an
instance of the other store such that they access the same memory cell.
In example 2 it is easier to see the difference.
I am somewhat in the fog here.
Best regard.
--
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170309/cea1d6a4/attachment.html>
On 03/09/2017 01:39 PM, Alexandre Isoard via llvm-dev wrote:> Hello fellow LLVM developers, > > I was wondering about the semantic of aliasing. > Here are some examples where I am not sure if the two stores aliases: > > Example 1: > > for (int i = 2; i < n; ++i) { > store A[i]; > store A[i-2]; > } > > Example 2: > > for (int i = 2; i < n; ++i) > store A[i]; > for (int i = 2; i < n; ++i) > store A[i-2]; > > In the example 1, they do not alias in a single iteration, but they do > alias at some point if n > 4.If you ask LLVM's AA whether 'store A[i]' and 'store A[i-2]' alias, it should say NoAlias. When two memory accesses have addresses that depend on common SSA values (the PHI node %i in this case), then it is interpreted as having the same value in both instructions. In example 2, you should get a MayAlias result, the PHI in both loops will be distinct SSA values (even though you've given them the same name in your example), and we can't prove that the memory accessed by the first store is disjoint from the memory accessed by the second. In any case, please don't confuse our AA for a loop dependence analysis. Are you looking for a loop dependence analysis? -Hal> That is, there is an execution path from one instance of the store to > an instance of the other store such that they access the same memory cell. > > In example 2 it is easier to see the difference. > > I am somewhat in the fog here. > > Best regard. > > -- > *Alexandre Isoard* > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://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/20170309/ecdf8f6a/attachment.html>
On Thu, Mar 9, 2017 at 8:03 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > On 03/09/2017 01:39 PM, Alexandre Isoard via llvm-dev wrote: > > Hello fellow LLVM developers, > > I was wondering about the semantic of aliasing. > Here are some examples where I am not sure if the two stores aliases: > > Example 1: > > for (int i = 2; i < n; ++i) { > store A[i]; > store A[i-2]; > } > > Example 2: > > for (int i = 2; i < n; ++i) > store A[i]; > for (int i = 2; i < n; ++i) > store A[i-2]; > > In the example 1, they do not alias in a single iteration, but they do > alias at some point if n > 4. > > > If you ask LLVM's AA whether 'store A[i]' and 'store A[i-2]' alias, it > should say NoAlias. When two memory accesses have addresses that depend on > common SSA values (the PHI node %i in this case), then it is interpreted as > having the same value in both instructions. > > In example 2, you should get a MayAlias result, the PHI in both loops will > be distinct SSA values (even though you've given them the same name in your > example), and we can't prove that the memory accessed by the first store is > disjoint from the memory accessed by the second. > > In any case, please don't confuse our AA for a loop dependence analysis. > Are you looking for a loop dependence analysis? >That is most certainly what I am looking for. I was wrongly assuming that AliasAnalysis would be a cheap over-approximation, I was wrong. Thanks.> -Hal > > That is, there is an execution path from one instance of the store to an > instance of the other store such that they access the same memory cell. > > In example 2 it is easier to see the difference. > > I am somewhat in the fog here. > > Best regard. > > -- > *Alexandre Isoard* > > > _______________________________________________ > LLVM Developers mailing listllvm-dev at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National Laboratory > >-- *Alexandre Isoard* -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170309/fe62faf1/attachment.html>