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

Daniel Berlin via llvm-dev llvm-dev at lists.llvm.org
Mon Mar 21 13:36:29 PDT 2016


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>


More information about the llvm-dev mailing list