Demand-driven points-to analysis for Java Export

@inproceedings{citeulike:693603, abstract = {We present a points-to analysis technique suitable for environments with small time and memory budgets, such as just-in-time (JIT) compilers and interactive development environments (IDEs). Our technique is demand-driven, performing only the work necessary to answer each query (a request for a variable's points-to information) issued by a client. In cases where even the demand-driven approach exceeds the time budget for a query, we employ early termination, i.e., stopping the analysis prematurely and returning an over-approximated result to the client. Our technique improves on previous demand-driven points-to analysis algorithms [17, 33] by achieving much higher precision under small time budgets and early termination.We formulate Andersen's analysis [5] for Java as a CFL-reachability problem [33]. This formulation shows that Andersen's analysis for Java is a balanced-parentheses problem, an insight that enables our new techniques. We exploit the balanced parentheses structure to approximate Andersen's analysis by regularizing the CFL-reachability problem, yielding an asymptotically cheaper algorithm. We also show how to regain most of the precision lost in the regular approximation as needed through refinement. Our evaluation shows that our regularization and refinement approach achieves nearly the precision of field-sensitive Andersen's analysis in time budgets as small as 2ms per query. Our technique can yield speedups of up to 16x over computing an exhaustive Andersen's analysis for some clients, with little to no precision loss.}, address = {New York, NY, USA}, author = {Sridharan, Manu and Gopan, Denis and Shan, Lexin and Bod\&\#237;k, Rastislav}, booktitle = {OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications}, citeulike-article-id = {693603}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1094817}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1094811.1094817}, doi = {10.1145/1094811.1094817}, issn = {0362-1340}, keywords = {analysis, cfl, nasko, points-to, reachability, static}, month = {October}, number = {10}, pages = {59--76}, posted-at = {2009-01-02 19:22:13}, priority = {2}, publisher = {ACM Press}, title = {Demand-driven points-to analysis for Java}, url = {http://dx.doi.org/10.1145/1094811.1094817}, volume = {40}, year = {2005} }

TY - CONF ID - citeulike:693603 L3 - citeulike-article-id:693603 N2 - We present a points-to analysis technique suitable for environments with small time and memory budgets, such as just-in-time (JIT) compilers and interactive development environments (IDEs). Our technique is demand-driven, performing only the work necessary to answer each query (a request for a variable's points-to information) issued by a client. In cases where even the demand-driven approach exceeds the time budget for a query, we employ early termination, i.e., stopping the analysis prematurely and returning an over-approximated result to the client. Our technique improves on previous demand-driven points-to analysis algorithms [17, 33] by achieving much higher precision under small time budgets and early termination.We formulate Andersen's analysis [5] for Java as a CFL-reachability problem [33]. This formulation shows that Andersen's analysis for Java is a balanced-parentheses problem, an insight that enables our new techniques. We exploit the balanced parentheses structure to approximate Andersen's analysis by regularizing the CFL-reachability problem, yielding an asymptotically cheaper algorithm. We also show how to regain most of the precision lost in the regular approximation as needed through refinement. Our evaluation shows that our regularization and refinement approach achieves nearly the precision of field-sensitive Andersen's analysis in time budgets as small as 2ms per query. Our technique can yield speedups of up to 16x over computing an exhaustive Andersen's analysis for some clients, with little to no precision loss. IS - 10 SN - 0362-1340 AD - New York, NY, USA EP - 76 TI - Demand-driven points-to analysis for Java PB - ACM Press VL - 40 T2 - OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications SP - 59 KW - analysis KW - cfl KW - nasko KW - points-to KW - reachability KW - static AU - Sridharan, Manu AU - Gopan, Denis AU - Shan, Lexin AU - Bod&\#237;k, Rastislav PY - 2005/10// UR - http://dx.doi.org/10.1145/1094811.1094817 ER -