<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Oct 18, 2013 at 7:27 AM, lian li <span dir="ltr"><<a href="mailto:lianli@gmail.com" target="_blank">lianli@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Daniel,<br>
<br>
I want to clarify that our analysis is not based on CFL-reachability.<br>
We apply CFL-reachability to matching context information where the<br>
exist from a function to a call-site must match<br>
the entry from the corresponding call-site. </blockquote><div><br></div><div>Yes, sorry, I pulled the wrong quote, it was late.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
The problem is a simple<br>
balanced parentheses problem in CFL-reachability, and it can be<br>
computed<br>
efficiently.<br></blockquote><div><br></div><div>Yes, it can, however, it was not clear from the paper that you were :)</div><div>You cite a fairly old paper next to that that essentially gives a >O(1) query time bound for this, but your</div>
<div>problem exactly fits into the bidirectional graph problem, unless i'm missing something.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
The paper you mentioned is a very nice paper that proposed an<br>
efficient algorithm to solve Dyck-CFL-reachability problem in<br>
bidirectional graphs. </blockquote><div><br></div><div>Right, and your  matching call sites can be formulated as one.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
However, precise pointer analysis cannot be<br>
formulated as a Dyck-CFL-reachability problem.</blockquote><div><br></div><div>FWIW: This remains to be seen, and certainly also depends on your definitions of "precise".<br></div><div> I agree you cannot currently formulate precise andersen style field sensitive pointer analysis as this.</div>
<div>As for whether it is impossible to get within a very very small percentage, ...</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> The alias analysis<br>

presented in that paper is an over approximation. Hence the time bound<br>
from our paper still applies.<br>
<br>
Regards,<br>
Lian<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
<br>
<br>
<br>
On Fri, Oct 18, 2013 at 4:39 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
> I notice you guys formulate your CFL reachability problem as a<br>
> balanced parentheses problem.<br>
> What algorithm do you use to solve it?<br>
><br>
> Are you aware of recent work that comes up with linear time and n log<br>
> n time algorithms to solve this class of problems:<br>
> <a href="http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf" target="_blank">http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf</a><br>
><br>
> In particular, the time bound from the paper:<br>
><br>
> "However, if we need the precise pointer information for all<br>
> variables, CFL-based<br>
> pointer analysis is generally more expensive as it has O(L^3 N^3)<br>
> complexity [29], where L is the size of the grammar and N is the<br>
> size of the graph."<br>
><br>
> should now been reduced to  O(n + m log m) time, assuming you are<br>
> using a standard balanced parentheses formulation.<br>
><br>
><br>
><br>
><br>
> On Thu, Oct 17, 2013 at 9:51 PM, lian li <<a href="mailto:lianli@gmail.com">lianli@gmail.com</a>> wrote:<br>
>> Hi Hal,<br>
>><br>
>> Thanks for your interest.<br>
>><br>
>> We tested with the following existing compiler optimizations in LLVM<br>
>> with SPECINT2006 benchmarks:<br>
>> -dse (dead store elimination),<br>
>> -gvn (global value numbering),<br>
>> -licm (loop invariant code motion),<br>
>> -bb-vectorize (basic block vectorization),<br>
>> -memcpyopt (memcpy optimization),<br>
>> -sink (code sinking),<br>
>> -loop-idom (recognize loop idioms),<br>
>> -argpromotion (argument promotion).<br>
>><br>
>> As far as I know, this list includes all optmizations in LLVM that<br>
>> requires alias information. With our pointer analysis, for the three<br>
>> optimizations "-dse, -gvn, -licm", we have observed significant<br>
>> improvements in terms of the number of optimizations being conducted.<br>
>> Take licm as an example, with our analysis, the number of instructions<br>
>> being hoisted out of loops more than doubled for some benchmarks. We<br>
>> have not seen big changes in terms of runtime performance though.<br>
>><br>
>> We measure compile time by first linking all modules of the same<br>
>> benchmark together, then running the analysis against the linked<br>
>> module. It finishes in less than 1 minute over applications such as<br>
>> httpd and sendmail, both with more than 100,000 LOC. For some<br>
>> benchmarks, it is time-consuming: the analysis time for GCC is close<br>
>> to 45 minutes.  But if you run the analysis over individual files (as<br>
>> in your normal compilation process), there is no observable overhead<br>
>> in terms of compile time.<br>
>><br>
>> Regards,<br>
>> Lian<br>
>><br>
>><br>
>><br>
>> On Fri, Oct 18, 2013 at 12:15 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<br>
>>> Hi Lian,<br>
>>><br>
>>> 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?<br>
>>><br>
>>> Thanks,<br>
>>> Hal<br>
>>><br>
>>> ----- Original Message -----<br>
>>>> Hi All,<br>
>>>><br>
>>>> This is Lian Li  from Oracle Labs in Brisbane Australia.<br>
>>>><br>
>>>> We have developed a precise and highly efficient pointer analysis<br>
>>>> framework on top of LLVM,  The approach is flow, context, and field<br>
>>>> sensitive, details are described in the two papers below:<br>
>>>><br>
>>>> "Boosting the performance of flow-sensitive points-to analysis using<br>
>>>> value flow" (in ESEC-FSE 2011), and<br>
>>>> "Precise and scalable context-sensitive pointer analysis via value<br>
>>>> flow graph" (in ISMM 2013).<br>
>>>><br>
>>>> The analysis was initially developed for the purpose of bug checking,<br>
>>>> and is now extended to support compiler optimizations. We have tested<br>
>>>> it with existing compiler optimizations in LLVM, and have seen<br>
>>>> promising results.<br>
>>>><br>
>>>> We are now considering to make this analysis available to the LLVM<br>
>>>> community, and contribute resources for future maintenance needs,<br>
>>>> provided that there is enough interest. We think that a new precise<br>
>>>> pointer analysis in LLVM can enable more new optimization and<br>
>>>> analysis<br>
>>>> techniques to be developed in LLVM.<br>
>>>><br>
>>>> Any people interested in seeing a new precise pointer analysis in<br>
>>>> LLVM?<br>
>>>><br>
>>>> Regards,<br>
>>>> Lian Li<br>
>>>><br>
>>>><br>
>>>><br>
>>>><br>
>>>><br>
>>>><br>
>>>><br>
>>>> --<br>
>>>> _______________________________________________<br>
>>>> LLVM Developers mailing list<br>
>>>> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>>>> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
>>>><br>
>>><br>
>>> --<br>
>>> Hal Finkel<br>
>>> Assistant Computational Scientist<br>
>>> Leadership Computing Facility<br>
>>> Argonne National Laboratory<br>
>><br>
>><br>
>><br>
>> --<br>
>> // Copyright @ 2011 Authorized by ** LIAN LI **<br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
<br>
--<br>
// Copyright @ 2011 Authorized by ** LIAN LI **<br>
</div></div></blockquote></div><br></div></div>