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

[Jia Chen via llvm-dev]

On 03/22/2016 01:51 PM, Philip Reames wrote:
>
>
> On 03/21/2016 06:53 PM, Daniel Berlin wrote:
>>
>>
>>     *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.

Also out of curiosity, why LLVM choose to expose pointer analysis 
information as alias-query APIs rather than APIs that let the client 
query points-to sets? This question has bothered me ever since I started 
to look into LLVM's alias analysis framework.

It seems to me that alias queries may yield less precise results than 
points-to queries. To put it in another way, it is easy to convert 
points-to information to aliasing information (just check for emptiness 
of points-to set intersection), but the reverse is much harder and may 
not be possible sometimes. The alias set tracker also introduce an 
additional source of imprecision: if a may alias b and b may alias c, it 
is not necessary that a may alias c but the AST would merge them all 
into one set.

It also doesn't seem like alias information is cheaper to compute (e.g. 
andersen) and is cheaper to query (e.g. the O(n^2) query problem).

-- 
Best Regards,

--
Jia Chen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160322/9d629f0d/attachment.html>