llvm dev - Dec 2015 - Can someone give me some pointer on alias analysis ?

I'm trying to fix that bug: https://llvm.org/bugs/show_bug.cgi?id=20049

It turns out this is the kind of optimization that I really need, as when
it isn't done, all kind of other optimizations opportunities down the road
are not realized as they are not exposed.

I have no idea where to start digging for this. I assume there is some kind
of interaction between memory dependency and alias analysis that is overly
conservative. Can someone gives me some infos on how the 2 interact
together ? What is the code that is supposed to remove these kind of loads ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151226/7bde144d/attachment.html>

On 12/26/2015 02:17 AM, Amaury SECHET via llvm-dev
wrote:
> I'm trying to fix that bug: https://llvm.org/bugs/show_bug.cgi?id=20049
>
> It turns out this is the kind of optimization that I really need, as 
> when it isn't done, all kind of other optimizations opportunities down 
> the road are not realized as they are not exposed.
>
> I have no idea where to start digging for this. I assume there is some 
> kind of interaction between memory dependency and alias analysis that 
> is overly conservative. Can someone gives me some infos on how the 2 
> interact together ? What is the code that is supposed to remove these 
> kind of loads ?
First, it looks like you're using an older version of LLVM (the load 
syntax has changed).  That's definitely not recommended since it will 
greatly limit your choices when encountering an issue like this.

Second, the aliasing problem has to do with the effects of the 
"allocmemory" callsite on a memory location associated with an earlier
alloca.  There's nothing that prevents your allocmemory function from 
writing to global state.  You have to teach the alias analysis that an 
unescaped noalias pointer can't alias the global state allocmemory might 
access.  Slightly surprised we don't get this today, but oh well.  Take 
a look at the isNonEscapingLocalObject predicate in BasicAA.  Then look 
at "getModRefInfo(ImmutableCallSite CS, const MemoryLocation
&Loc)".
Double check to make sure this is the one that MDA actually calls.

Third, you might want to take a look the new 
inaccessiblememonlyattribute. Depending on how you're modelling your 
allocation, this might help resolve the aliasing problem in different 
way.  However, be aware that this is *very* new.  In particular, I 
triggered an optimizer bug by adding the new attribute to your 
particular example.  :(

Fourth, have you considered implementing a simple escape analysis pass?  
I notice that the store-load forwarding would just fall out once you 
removed the last allocation.  I believe the fixed point would then 
become a function which returns the constant answer and does nothing else.

Fifth, some pointers on debugging this yourself.  GVN (which is the one 
which does complicated *-load forwarding) calls MDA 
(MemoryDepedenceAnalysis).  Using the appropriate -debug-only options 
will likely get you to the right area.  You can also consider using the 
MemDepPrinter pass to bypass GVN.  I don't know of a way to issue raw AA 
queries for testing.  That would be useful, but I don't know that we 
have it.

Hope that helps.
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151226/9d51996f/attachment.html>

2015-12-26 18:32 GMT+01:00 Philip Reames <listmail at philipreames.com>:
> On 12/26/2015 02:17 AM, Amaury SECHET via llvm-dev wrote:
>
> I'm trying to fix that bug: https://llvm.org/bugs/show_bug.cgi?id=20049
>
> It turns out this is the kind of optimization that I really need, as when
> it isn't done, all kind of other optimizations opportunities down the
road
> are not realized as they are not exposed.
>
> I have no idea where to start digging for this. I assume there is some
> kind of interaction between memory dependency and alias analysis that is
> overly conservative. Can someone gives me some infos on how the 2 interact
> together ? What is the code that is supposed to remove these kind of loads
?
>
> First, it looks like you're using an older version of LLVM (the load
> syntax has changed).  That's definitely not recommended since it will
> greatly limit your choices when encountering an issue like this.
>
>
I just reused an old code sample. The problem still exists in recent
version of LLVM.

> Second, the aliasing problem has to do with the effects of the
> "allocmemory" callsite on a memory location associated with an
earlier
> alloca.  There's nothing that prevents your allocmemory function from
> writing to global state.  You have to teach the alias analysis that an
> unescaped noalias pointer can't alias the global state allocmemory
might
> access.  Slightly surprised we don't get this today, but oh well.  Take
a
> look at the isNonEscapingLocalObject predicate in BasicAA.  Then look at
> "getModRefInfo(ImmutableCallSite CS, const MemoryLocation
&Loc)".  Double
> check to make sure this is the one that MDA actually calls.
>
>
I don't think this is the problem. When there is only 2 calls to
allocmemory, loads are optimized away as expected. But it seems that the
analysis is confused with 3+ calls.

> Third, you might want to take a look the new inaccessiblememonly
> attribute. Depending on how you're modelling your allocation, this
might
> help resolve the aliasing problem in different way.  However, be aware that
> this is *very* new.  In particular, I triggered an optimizer bug by adding
> the new attribute to your particular example.  :(
>
> Fourth, have you considered implementing a simple escape analysis pass?  I
> notice that the store-load forwarding would just fall out once you removed
> the last allocation.  I believe the fixed point would then become a
> function which returns the constant answer and does nothing else.
>
>
Yes I did. More specifically, there is a pass that try to recognize memory
allocation like calls and optimize them, which right now have libc and some
overloads of operator new hardcoded in it but not much more. This could be
greatly improved IMO, to be language agnostic (and better support C++ in
the process), but really, I do think relying on this to get the load
eliminated, when noalias already provide this information to the optimizer,
is overkill.

> Fifth, some pointers on debugging this yourself.  GVN (which is the one
> which does complicated *-load forwarding) calls MDA
> (MemoryDepedenceAnalysis).  Using the appropriate -debug-only options will
> likely get you to the right area.  You can also consider using the
> MemDepPrinter pass to bypass GVN.  I don't know of a way to issue raw
AA
> queries for testing.  That would be useful, but I don't know that we
have
> it.
>
> Hope that helps.
>
>
Yes, thanks. I'll probably come back with more question once I've played
with these options a bit. Sorry for the late answer, I was mostly off the
grid the past 2 weeks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160104/91d3ad68/attachment.html>