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

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>

>
>
> 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 :)
>
In general, I would never assume someone sat down and thought *really hard*
about the design of an API in a piece of software to get it right for all
time. It happens, but it's actually pretty rare.  One of the most limited
resources most software teams have is time, and they use often use that
time to get done what they need, and design APIs based on current and
easily predictable future needs.

The same thing is true about LLVM's APIs.  You shouldn't assume we sat
down, thought really hard about AA by meditating upon a mountain, and then
designed this API.  Instead, some thought was put into it, based on current
and easily predicted needs, and then people moved on.

I can't say this was the wrong choice, either, given how long it has been
since someone has even come along considering implementing context
sensitive or flow-sensitive AA (and having talked to tons of people over
the years, this is *not* a chicken and egg problem. Literally nobody has
had a *strong* desire). It wouldn't make much sense to try to design an API
without any implementations that want to use those API's.

As that changes, i expect the AA API will be redesigned and reworked to
accomodate the needs of those things.

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

----- Original Message -----
> From: "Jia Chen via llvm-dev" <llvm-dev at lists.llvm.org>
> To: "Chris Lattner" <clattner at apple.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Monday, March 28, 2016 10:10:12 AM
> Subject: Re: [llvm-dev] Existing studies on the benefits of pointer
> analysis
> 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.
Can you elaborate on what you mean by flow sensitive? We have a mod/ref query
interface that can return answers specific to a particular instruction/call
pair. The code above could easily live in a single basic block, and if we had
function attribute deduction on the 'argmemonly' attribute, we could
probably do this now.

-Hal 
> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160328/18081d12/attachment.html>

On 03/28/2016 10:50 AM, Hal Finkel wrote:
>
>     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()
>
>
> Can you elaborate on what you mean by flow sensitive? We have a 
> mod/ref query interface that can return answers specific to a 
> particular instruction/call pair. The code above could easily live in 
> a single basic block, and if we had function attribute deduction on 
> the 'argmemonly' attribute, we could probably do this now.
>
>  -Hal
What I meant is that the CSE needs to be aware of the execution order, 
i.e. the call to V1.pop_back() should not be in the middle of the two 
V1.size() for zero to be 0. If there exists more complicated control 
flows, CSE needs to be able to make the same kind of argument across 
basic blocks.

I didn't follow LLVM development very closely to be familiar with how 
LLVM handles CSE. If what I said above is exactly how it works today, 
then yes we could probably do this now.

But still, there is no APIs that answers "are p and q aliases before 
this instruction x?". The same can be done for mod-ref today (if I 
remembered correctly this isn't even the case before the AAResult class 
came into existence), but not for aliases.

-- 
Best Regards,

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

> On Mar 28, 2016, at 8:26 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> 
>> 
> 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 :)
>  
> In general, I would never assume someone sat down and thought *really hard*
about the design of an API in a piece of software to get it right for all time.
It happens, but it's actually pretty rare.  One of the most limited
resources most software teams have is time, and they use often use that time to
get done what they need, and design APIs based on current and easily predictable
future needs.
> 
> The same thing is true about LLVM's APIs.  You shouldn't assume we
sat down, thought really hard about AA by meditating upon a mountain, and then
designed this API.  Instead, some thought was put into it, based on current and
easily predicted needs, and then people moved on.
> 
> I can't say this was the wrong choice, either, given how long it has
been since someone has even come along considering implementing context
sensitive or flow-sensitive AA (and having talked to tons of people over the
years, this is *not* a chicken and egg problem. Literally nobody has had a
*strong* desire). It wouldn't make much sense to try to design an API
without any implementations that want to use those API's.
> 
> As that changes, i expect the AA API will be redesigned and reworked to
accomodate the needs of those things.
FWIW, DS-AA is context sensitive in this way, and LLVM definitely does take
advantage of it.  Even circa 2005. This is the whole point of chapter 4 of
http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160329/681843df/attachment.html>