[LLVMdev] Contribute a new precise pointer analysis to LLVM

[Daniel Berlin]

I notice you guys formulate your CFL reachability problem as a
balanced parentheses problem.
What algorithm do you use to solve it?

Are you aware of recent work that comes up with linear time and n log
n time algorithms to solve this class of problems:
http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf

In particular, the time bound from the paper:

"However, if we need the precise pointer information for all
variables, CFL-based
pointer analysis is generally more expensive as it has O(L^3 N^3)
complexity [29], where L is the size of the grammar and N is the
size of the graph."

should now been reduced to  O(n + m log m) time, assuming you are
using a standard balanced parentheses formulation.




On Thu, Oct 17, 2013 at 9:51 PM, lian li <lianli at gmail.com> wrote:
> Hi Hal,
>
> Thanks for your interest.
>
> We tested with the following existing compiler optimizations in LLVM
> with SPECINT2006 benchmarks:
> -dse (dead store elimination),
> -gvn (global value numbering),
> -licm (loop invariant code motion),
> -bb-vectorize (basic block vectorization),
> -memcpyopt (memcpy optimization),
> -sink (code sinking),
> -loop-idom (recognize loop idioms),
> -argpromotion (argument promotion).
>
> As far as I know, this list includes all optmizations in LLVM that
> requires alias information. With our pointer analysis, for the three
> optimizations "-dse, -gvn, -licm", we have observed significant
> improvements in terms of the number of optimizations being conducted.
> Take licm as an example, with our analysis, the number of instructions
> being hoisted out of loops more than doubled for some benchmarks. We
> have not seen big changes in terms of runtime performance though.
>
> We measure compile time by first linking all modules of the same
> benchmark together, then running the analysis against the linked
> module. It finishes in less than 1 minute over applications such as
> httpd and sendmail, both with more than 100,000 LOC. For some
> benchmarks, it is time-consuming: the analysis time for GCC is close
> to 45 minutes.  But if you run the analysis over individual files (as
> in your normal compilation process), there is no observable overhead
> in terms of compile time.
>
> Regards,
> Lian
>
>
>
> On Fri, Oct 18, 2013 at 12:15 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>> Hi Lian,
>>
>> I am certainly interested in seeing this; do you have performance numbers (compile time)? Also, can you share more information about the promising optimization results you mentioned?
>>
>> Thanks,
>> Hal
>>
>> ----- Original Message -----
>>> Hi All,
>>>
>>> This is Lian Li  from Oracle Labs in Brisbane Australia.
>>>
>>> We have developed a precise and highly efficient pointer analysis
>>> framework on top of LLVM,  The approach is flow, context, and field
>>> sensitive, details are described in the two papers below:
>>>
>>> "Boosting the performance of flow-sensitive points-to analysis using
>>> value flow" (in ESEC-FSE 2011), and
>>> "Precise and scalable context-sensitive pointer analysis via value
>>> flow graph" (in ISMM 2013).
>>>
>>> The analysis was initially developed for the purpose of bug checking,
>>> and is now extended to support compiler optimizations. We have tested
>>> it with existing compiler optimizations in LLVM, and have seen
>>> promising results.
>>>
>>> We are now considering to make this analysis available to the LLVM
>>> community, and contribute resources for future maintenance needs,
>>> provided that there is enough interest. We think that a new precise
>>> pointer analysis in LLVM can enable more new optimization and
>>> analysis
>>> techniques to be developed in LLVM.
>>>
>>> Any people interested in seeing a new precise pointer analysis in
>>> LLVM?
>>>
>>> Regards,
>>> Lian Li
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>
>
>
> --
> // Copyright @ 2011 Authorized by ** LIAN LI **
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev