skip to main content
10.1145/1869631.1869635acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
research-article

Alias analysis for optimization of dynamic languages

Authors Info & Claims
Published:18 October 2010Publication History

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.

References

  1. }}L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994.Google ScholarGoogle Scholar
  2. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  6. }}B. Cannon. Localized Type Inference of Atomic Types in Python. PhD thesis, California Polytechnic State University, 2005.Google ScholarGoogle Scholar
  7. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. }}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 ScholarGoogle ScholarCross RefCross Ref
  14. }}D. Goyal. Transformational derivation of an improved alias analysis algorithm. Higher-Order and Symbolic Computation, 18 (1--2): 15--49, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. }}S. Z. Guyer and C Lin. Error checking with client-driven pointer analysis. Science of Computer Programming, 58 (1-2): 83--114, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. }}M. Hind and A. Pioli. Evaluating the effectiveness of pointer alias analyses. Science of Computer Programming, 39 (1): 31--55, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  22. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  23. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  24. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  26. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  29. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  30. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  31. }}G. Ramalingam. The undecidability of aliasing. ACM Trans. on Programming Languages and Systems, 16 (5): 1467--1471, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  33. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  34. }}M. Salib. Faster than C: Static type inference with Starkiller. In Proc. of PyCon 04, pages 2--26, 2004.Google ScholarGoogle Scholar
  35. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  36. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  37. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  38. }}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 ScholarGoogle ScholarDigital LibraryDigital Library
  39. }}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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Alias analysis for optimization of dynamic languages

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      DLS '10: Proceedings of the 6th symposium on Dynamic languages
      October 2010
      120 pages
      ISBN:9781450304054
      DOI:10.1145/1869631
      • cover image ACM SIGPLAN Notices
        ACM SIGPLAN Notices  Volume 45, Issue 12
        DLS '10
        December 2010
        107 pages
        ISSN:0362-1340
        EISSN:1558-1160
        DOI:10.1145/1899661
        Issue’s Table of Contents

      Copyright © 2010 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 18 October 2010

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate32of77submissions,42%

      Upcoming Conference

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader