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

>  You can solve andersens and steengaards and everything else using 
> standard dataflow solvers, and that's an implementation strategy, but 
> it will be really slow.
>
> Part of the tradeoff is how fast something runs, and approaches that 
> are orders of magnitude faster often change the calculus of what 
> people do. For example, before hardekopf's work, andersens was 
> considered too slow to be practical in a real compiler.
>
> Now, GCC does it by default.
>
> So i would call that approach a superior approach :)
>
> So saying that CFL-AA offers nothing superior in terms of approach, 
> IMHO, misunderstands the nature of the problem. If your goal is to get 
> precision at all costs, then yes, it's not superior.  If your goal is 
> to get something into a production compiler, that is understandable, 
> maintainable, can turn on and off field and context sensitivity 
> easily, etc, then it may be a superior approach.
>
>
Apparently "superior approach" is a misnomer on my side. My apologies.
What I should have said is "an approach with superior precision". Both
cfl and Ben Hardekopf's work you mentioned (which improves analysis 
performance by using SSA transformation as a pre-pass to eliminate 
easy-to-analyze pointers) can be viewed as optimizations on standard 
dataflow solver, but at the end of the day they do nothing more than 
that. From a client's perspective, they are no different from standard 
solvers except they are faster.

I do acknowledge that cfl may work better in practice (although I held 
different opinions about understandability and maintainability). It's 
just that I tend to make judgment of pointer analysis based on the need 
of a client. Again, I meant no offense and I apologize for my 
inappropriate choice of words.

-- 
Best Regards,

--
Jia Chen

On Mon, Mar 21, 2016 at 12:26 PM, Jia Chen <jchen at cs.utexas.edu> wrote:
>
>  You can solve andersens and steengaards and everything else using
>> standard dataflow solvers, and that's an implementation strategy,
but it
>> will be really slow.
>>
>> Part of the tradeoff is how fast something runs, and approaches that
are
>> orders of magnitude faster often change the calculus of what people do.
For
>> example, before hardekopf's work, andersens was considered too slow
to be
>> practical in a real compiler.
>>
>> Now, GCC does it by default.
>>
>> So i would call that approach a superior approach :)
>>
>> So saying that CFL-AA offers nothing superior in terms of approach,
IMHO,
>> misunderstands the nature of the problem. If your goal is to get
precision
>> at all costs, then yes, it's not superior.  If your goal is to get
>> something into a production compiler, that is understandable,
maintainable,
>> can turn on and off field and context sensitivity easily, etc, then it
may
>> be a superior approach.
>>
>>
>> Apparently "superior approach" is a misnomer on my side. My
apologies.

No worries at all!

> What I should have said is "an approach with superior precision".
Both cfl
> and Ben Hardekopf's work you mentioned (which improves analysis
performance
> by using SSA transformation as a pre-pass to eliminate easy-to-analyze
> pointers)
can be viewed as optimizations on standard dataflow solver,


Well, not quite. Just to be pedantic:
It does hash value numbering and CSE and some other things on the
constraint graph.

CFL is not a dataflow solver at all. It's a graph reachability solver.
Ben's work is a constraint solver.
It does not know or care about CFG's, basic blocks, etc.
Dataflow solvers are like Ryder and Landi's approach



> but at the end of the day they do nothing more than that.
>From a client's perspective, they are no different from standard solvers
> except they are faster.
>
Yes.

>
> I do acknowledge that cfl may work better in practice (although I held
> different opinions about understandability and maintainability).

Sure. Having implemented tons and tons and tons of these algorithms and
things, i'd argue that constraint solving tends to be easier to understand
once you get it, but has limitations that are harder to overcome than in
CFL land.

> It's just that I tend to make judgment of pointer analysis based on the
> need of a client.

Thinking about individual clients, while useful, is not always the right
end game.

It pretty much  does not matter if i improve GVN if now it just catches
cases some other cheap pass does anyway.
Maybe it does in some ways, but it's often not going to let you remove that
other pass, or the expense of improving it is not worth the cost.

So providing context-sensitive AA to a pass so it can do an amazing job
will buy you pretty much nothing if the other passes can do the same job
with less info.


> Again, I meant no offense and I apologize for my inappropriate choice of
> words.
>
>
It was neither offensive nor inappropriate :)

>
> --
> Best Regards,
>
> --
> Jia Chen
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/e4e470ab/attachment.html>