ABSTRACT
Dynamic languages such as Python allow programs to be written more easily using high-level constructs such as comprehensions for queries and using generic code. Efficient execution of programs then requires powerful optimizations - incrementalization of expensive queries and specialization of generic code. Effective incrementalization and specialization of dynamic languages require precise and scalable alias analysis.
This paper describes the development and experimental evaluation of a may-alias analysis for a full dynamic object-oriented language, for program optimization by incrementalization and specialization. The analysis is flow-sensitive; we show that this is necessary for effective optimization of dynamic languages. It uses precise type analysis and a powerful form of context sensitivity, called trace sensitivity, to further improve analysis precision. It uses a compressed representation to significantly reduce the memory used by flow-sensitive analyses.We evaluate the effectiveness of this analysis and 17 variants of it for incrementalization and specialization of Python programs, and we evaluate the precision, memory usage, and running time of these analyses on programs of diverse sizes. The results show that our analysis has acceptable precision and efficiency and represents the best trade-off between them compared to the variants.
- }}L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994.Google Scholar
- }}C. Anderson, P. Giannini, and S. Drossopoulou. Towards type inference for JavaScript. In Proc. of the 19th European Conf. on Object-Oriented Programming, pages 428--452, 2005. Google ScholarDigital Library
- }}D. F. Bacon and P. F. Sweeney. Fast static analysis of C++ virtual function calls. In Proc. of the 1996 ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages, and Applications, pages 324--341, 1996. Google ScholarDigital Library
- }}D. Balzarotti, M. Cova, V. Felmetsger, N. Jovanovic, E. Kirda, C. Kruegel, and G. Vigna. Saner: composing static and dynamic analysis to validate sanitization in web applications. In Proc. of the 2008 IEEE Symp. on Security and Privacy, pages 387--401, 2008. Google ScholarDigital Library
- }}M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proc. of the 24th Annual ACM SIGPLAN Conf. on Object Oriented Programming, Systems, Languages, and Applications, pages 243--262, 2009. Google ScholarDigital Library
- }}B. Cannon. Localized Type Inference of Atomic Types in Python. PhD thesis, California Polytechnic State University, 2005.Google Scholar
- }}J.D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Proc. of the 20th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pages 232--245, 1993. Google ScholarDigital Library
- }}A. Diwan, K.S. McKinley, and J.E.B. Moss. Type-based alias analysis. In Proc. of the 1998 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 106--117, 1998. Google ScholarDigital Library
- }}M. Emami, R. Ghiya, and L.J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proc. of the 1994 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 242--256, 1994. Google ScholarDigital Library
- }}M. Fahndrich, J. Rehof, and M. Das. Scalable context-sensitive flow analysis using instantiation constraints. In Proc. of the 2000 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 253--263, 2000. Google ScholarDigital Library
- }}J.S. Foster, M. Fahndrich, and A. Aiken. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proc. of the 7th Intl. Symp. on Static Analysis, pages 175--198, 2000. Google ScholarDigital Library
- }}M. Furr, J. D. An, J. S. Foster, and M. W. Hicks. Static type inference for Ruby. In Proc. of the 2009 ACM Symp. on Applied Computing, pages 1859--1866, 2009. Google ScholarDigital Library
- }}M. Gorbovitski, K.T. Tekle, T. Rothamel, S.D. Stoller, and Y.A. Liu. Analysis and transformations for efficient query-based debugging. In Proc. of the 8th IEEE Intl. Working Conf. on Source Code Analysis and Manipulation, pages 174--183, 2008.Google ScholarCross Ref
- }}D. Goyal. Transformational derivation of an improved alias analysis algorithm. Higher-Order and Symbolic Computation, 18 (1--2): 15--49, 2005. Google ScholarDigital Library
- }}A. Guha, S. Krishnamurthi, and T. Jim. Using static analysis for Ajax intrusion detection. In Proc. of the 18th Intl. Conf. on World Wide Web, pages 561--570, 2009. Google ScholarDigital Library
- }}S. Z. Guyer and C Lin. Error checking with client-driven pointer analysis. Science of Computer Programming, 58 (1-2): 83--114, 2005. Google ScholarDigital Library
- }}B. Hardekopf and C. Lin. Semi-sparse flow-sensitive pointer analysis. In Proc. of the 36th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pages 226--238, 2009. Google ScholarDigital Library
- }}R. Hasti and S. Horwitz. Using static single assignment form to improve flow-insensitive pointer analysis. In Proc. of the ACM SIGPLAN 1998 Conf. on Programming Language Design and Implementation, page 105, 1998. Google ScholarDigital Library
- }}M. Hind. Pointer analysis: haven't we solved this problem yet? In Proc. of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 54--61, 2001. Google ScholarDigital Library
- }}M. Hind and A. Pioli. Evaluating the effectiveness of pointer alias analyses. Science of Computer Programming, 39 (1): 31--55, 2001. Google ScholarDigital Library
- }}D. Jang and K.M. Choe. Points-to analysis for JavaScript. In Proceedings of the 2009 ACM Symp. on Applied Computing, pages 1930--1937, 2009. Google ScholarDigital Library
- }}N. Jovanovic, C. Kruegel, and E. Kirda. Precise alias analysis for static detection of web application vulnerabilities. In Proc. of the 2006 ACM SIGPLAN Workshop on Programming Languages and Analysis for Security, pages 27--36, 2006. Google ScholarDigital Library
- }}M.S. Lam, J. Whaley, V.B. Livshits, M.C. Martin, D. Avots, M. Carbin, and C. Unkel. Context-sensitive program analysis as database queries. In Proc. of the 24th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 1--12, 2005. Google ScholarDigital Library
- }}C. Lattner, A. Lenharth, and V. Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In Proc. of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 278--289, 2007. Google ScholarDigital Library
- }}O. Lhoták and L. Hendren. Context-sensitive points-to analysis: is it worth it? In Proc. of the 15th Intl. Conf. on Compiler Construction, pages 47--64, 2006. Google ScholarDigital Library
- }}O. Lhoták and L.J. Hendren. Scaling Java points-to analysis using spark. In Proc. of 12th Intl. Conf. on Compiler Construction, pages 153--169, 2003. Google ScholarDigital Library
- }}Y.A. Liu, S.D. Stoller, M. Gorbovitski, T. Rothamel, and Y.E. Liu. Incrementalization across object abstraction. In Proc. of the 20th Annual ACM SIGPLAN Conf. on Object Oriented Programming, Systems, Languages, and Applications, pages 473--486, 2005. Google ScholarDigital Library
- }}Y.A. Liu, M. Gorbovitski, and S.D. Stoller. A language and framework for invariant-driven transformations. In Proc. of the 8th Intl. Conf. on Generative Programming and Component Engineering, pages 55--64, 2009. Google ScholarDigital Library
- }}A. Milanova, A. Rountev, and B.G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. on Software Engineering and Methodology, 14 (1): 1--41, 2005. Google ScholarDigital Library
- }}M. Mock, D.C. Atkinson, C. Chambers, and S.J. Eggers. Improving program slicing with dynamic points-to data. ACM SIGSOFT Software Engineering Notes, 27 (6): 71--80, 2002. Google ScholarDigital Library
- }}G. Ramalingam. The undecidability of aliasing. ACM Trans. on Programming Languages and Systems, 16 (5): 1467--1471, 1994. Google ScholarDigital Library
- }}A. Rigo. Representation-based just-in-time specialization and the Psyco prototype for Python. In Proc. of the 2004 ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation, pages 15--26, 2004. Google ScholarDigital Library
- }}E. Ruf. Context-insensitive alias analysis reconsidered. In Proc. of the 1995 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 13--22, 1995. Google ScholarDigital Library
- }}M. Salib. Faster than C: Static type inference with Starkiller. In Proc. of PyCon 04, pages 2--26, 2004.Google Scholar
- }}O. Shivers. Control-flow analysis in Scheme. In Proc. of the SIGPLAN 1988 Conf. on Programming Language Design and Implementation, pages 164--174, 1988. Google ScholarDigital Library
- }}V.C. Sreedhar, M. Burke, and J.D. Choi. A framework for interprocedural optimization in the presence of dynamic class loading. In Proc. of the 2000 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 196--207, 2000. Google ScholarDigital Library
- }}M. Sridharan and R. Bodik. Refinement-based context-sensitive points-to analysis for Java. In Proc. of the 2006 ACM SIGPLAN Conf. on Programming Language Design and Implementation, pages 387--400, 2006. Google ScholarDigital Library
- }}B. Steensgaard. Points-to analysis in almost linear time. In Proc. of the 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pages 32--41, 1996. Google ScholarDigital Library
- }}J. Vitek, R. N. Horspool, and J. S. Uhl. Compile-time analysis of object-oriented programs. In Proc. of the 4th Intl. Conf. on Compiler Construction, pages 236--250, 1992. Google ScholarDigital Library
Index Terms
Alias analysis for optimization of dynamic languages
Recommendations
Demand-driven alias analysis for C
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThis paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. ...
Precise flow-insensitive may-alias analysis is NP-hard
Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...
Alias analysis for optimization of dynamic languages
DLS '10Dynamic languages such as Python allow programs to be written more easily using high-level constructs such as comprehensions for queries and using generic code. Efficient execution of programs then requires powerful optimizations - incrementalization of ...
Comments