llvm dev - Mar 2016 - Existing studies on the benefits of pointer analysis

On 03/25/2016 08:08 PM, Chris Lattner wrote:
> I’m still a big fan of context sensitive, flow insensitive, 
> unification based models.
Interestingly I find the unification approach quite unsatisfactory 
sometime. What happens there is pointers with the same "depth" are too
often clobbered together unless they are really unrelated to each other.
> Contrary to your claim, context sensitivity *is* useful for mod-ref 
> analysis, e.g. “can I hoist a load across this call”?  Context 
> sensitivity improves the precision of the mod/ref set of the call.
>
I'm not sure about that. How often does mod-ref information change 
across callsites? Isn't a good context-insensitive function summary good 
enough?

-Jia

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/2473e70e/attachment.html>

> On Mar 25, 2016, at 9:04 PM, Jia Chen <jchen at cs.utexas.edu> wrote:
> 
> On 03/25/2016 08:08 PM, Chris Lattner wrote:
>> I’m still a big fan of context sensitive, flow insensitive, unification
based models.
> 
> Interestingly I find the unification approach quite unsatisfactory
sometime. What happens there is pointers with the same "depth" are too
often clobbered together unless they are really unrelated to each other.
> 
>> Contrary to your claim, context sensitivity *is* useful for mod-ref
analysis, e.g. “can I hoist a load across this call”?  Context sensitivity
improves the precision of the mod/ref set of the call.
>> 
> I'm not sure about that. How often does mod-ref information change
across callsites? Isn't a good context-insensitive function summary good
enough?
It changes all the time.  Here’s a trivial example, assume no inlining and no AA
other than the one in question:

std::vector<int> V1 = { 1, 2, 3 };
std::vector<int> V2 = { 4, 5, 6 };

V1.pop_back();    // Mutates *this

auto length = V1.size();

V2.pop_back();    // Mutates *this

auto zero = length - V1.size()

In this case, the compiler should “obviously” be able to CSE length, allowing
further simplification to substitute zero with 0.

However, with a context sensitive AA, both &V1 and &V2 end up aliasing
the “this” pointer in std::vector::pop_back.  As such, without context
sensitivity, you would falsely assume that “V2.pop_back();” could modify “V1”. 
This is unfortunate, particularly for OO languages that frequently use static
dispatch (like C++, Swift, and others).


That said, I have no idea what you’re referring to by "context-insensitive
function summary”.  If you’re talking about something context sensitive, then
ya, it can handle this.  :-)

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160327/0b312a81/attachment.html>

On 03/28/2016 12:37 AM, Chris Lattner wrote:
> It changes all the time.  Here’s a trivial example, assume no inlining 
> and no AA other than the one in question:
>
>     std::vector<int> V1 = { 1, 2, 3 };
>     std::vector<int> V2 = { 4, 5, 6 };
>
>     V1.pop_back();    // Mutates *this
>
>     auto length = V1.size();
>
>     V2.pop_back();    // Mutates *this
>
>     auto zero = length - V1.size()
>
>
> In this case, the compiler should “obviously” be able to CSE length, 
> allowing further simplification to substitute zero with 0.
>
> However, with a context sensitive AA, both &V1 and &V2 end up
aliasing
> the “this” pointer in std::vector::pop_back.  As such, without context 
> sensitivity, you would falsely assume that “V2.pop_back();” could 
> modify “V1”.  This is unfortunate, particularly for OO languages that 
> frequently use static dispatch (like C++, Swift, and others).
>
>
> That said, I have no idea what you’re referring to by 
> "context-insensitive function summary”.  If you’re talking about 
> something context sensitive, then ya, it can handle this.  :-)
>
For the example to work here the CSE pass itself needs to be 
flow-sensitive and context-sensitive. I don't think that's how most 
optimizations in LLVM work. If it is, then I agree with all you said. 
But if it isn't, there's no point in bumping up the context sensitivity 
just for the pointer analysis.

As Daniel mentioned earlier in this thread, the analysis analysis 
framework in LLVM doesn't provide any APIs for flow-sensitive queries as 
well as context-sensitive queries. This design choice almost eliminate 
any possibilities for a flow-sensitive or context-sensitive pointer 
analysis to be useful. Strangely, the set of APIs does support 1-CFA 
context-sensitive mod-ref queries (so I guess one could somehow reap 
some context-sensitive benefits out of them after all). To me that 
design incoherence looks confusing, but I'm pretty sure you know much 
better than me why it should work that way :)


- Jia
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160328/a458f954/attachment-0001.html>