[llvm-dev] Existing studies on the benefits of pointer analysis

[Philip Reames via llvm-dev]

On 03/21/2016 06:53 PM, Daniel Berlin wrote:
>
>
> On Mon, Mar 21, 2016 at 6:28 PM, Philip Reames via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>
>
>     On 03/21/2016 08:56 AM, Jia Chen via llvm-dev wrote:
>>
>>
>>     I did some preliminary experiments with licm on c programs over
>>     the last weekend. I chose licm because intuitively that's the
>>     optimization that could have the biggest performance impact. The
>>     result suggested that tbaa, cfl-aa, scev-aa and globals-aa yields
>>     very little additional benefits over basic-aa. Again, both the
>>     methodology and benchmark selection are very immature and the
>>     results need to be double-checked, but my hope is that by looking
>>     at how aa algorithms and their clients interact I may be able to
>>     get some hints on what kind of aa a compiler really wants.
>     Just to chime in here, your results match my experience and
>     expectations with LICM as well.  Between basic-aa, and TBAA
>     (specifically LLVM's implementation thereof), I haven't seen a lot
>     of cases where an imprecision in the alias analysis prevents hoisting.
>
>
> Yeah, at best, for LICM, it's just going to tell you the best place to 
> insert runtime checks.  LICM has a specific goal, and it's usually not 
> AA that prevents proving something loop invariant.  Most loads/stores 
> are also either trivially loop invariant, or impossible to prove loop 
> invariant.
Side note: The key limiting factor for load hoisting is most often being 
able to prove dereferenceability.  I only mention that because the OP 
had asked for where other optimizer changes might help.
>
>
>     *However*, if you're interested in LICM specifically, I have
>     *definitely* seen cases where the precision of AliasSetTracker
>     (our grouping of AA results to prevent O(n^2) queries) prevents
>     hoisting in spurious cases. AST could use some serious attention,
>     both from an engineering standpoint and from (possibly) a
>     theoretically one.
>
>
>
> You already know my view on this one: It's going to be remarkably hard 
> to make AST work the way folks want it and have it be incremental and 
> completely agnostic of anything but the AA API.
>
> It's just really hard if not provably impossible to do this 
> incrementally and avoid duplicate work, and get precise results and ...
>
>
> On the other hand, it's pretty easy if you basically say "i provide 
> list of all pointers and statements i care about, you make me some 
> sets", and you let it figure out the answers upfront.
Er, this is actually fairly close to what the code does.  It just does 
it in a really oddly structured manner.  But yes, I agree, this code 
could be radically improved.
>
> (it's also not clear to me why AST is the right abstraction for LICM 
> to work on top of, but that's neither here nor there :P)
Out of curiosity, what would you suggest instead?

For context, I have a patch in my tree which falls back to O(n^2) 
queries for small loops.  We found this to be rather important for the 
optimization of IR derived from our Java frontend.

Philip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160322/ca6f170e/attachment.html>