A demand-driven adaptive type analysis

ABSTRACT

Compilers for dynamically and statically typed languages ensure safe execution by verifying that all operations are performed on appropriate values. An operation as simple as car in Scheme and hd in SML will include a run time check unless the compiler can prove that the argument is always a non-empty list using some type analysis. We present a demand-driven type analysis that can adapt the precision of the analysis to various parts of the program being compiled. This approach has the advantage that the analysis effort can be spent where it is justified by the possibility of removing a run time check, and where added precision is needed to accurately analyze complex parts of the program. Like the k-cfa our approach is based on abstract interpretation but it can analyze some important programs more accurately than the k-cfa for any value of k. We have built a prototype of our type analysis and tested it on various programs with higher order functions. It can remove all run time type checks in some nontrivial programs which use map and the Y combinator.

REFERENCES

• 1: Gagan Agrawal, Simultaneous Demand-Driven Data-Flow and Call Graph Analysis, Proceedings of the IEEE International Conference on Software Maintenance, p.453, August 30-September 03, 1999
• 2: J. Michael Ashley , R. Kent Dybvig, A practical and flexible flow analysis for higher-order languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.845-868, July 1998 [doi>10.1145/291891.291898]
• 3: D. Dubé. Demand-Driven Type Analysis for Dynamically-Typed Functional Languages. PhD thesis, Université de Montréal, 2002. Available at: http://www.iro.umontreal.ca/~dube.
• 4: D. Dubé and M. Feeley. Demand-driven type analysis: an introduction. In Proceedings of the Workshop on Scheme and Functional Programming 2001, pages 21--32, sep 2001.
• 5: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
• 6: Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.24-34, June 2001, Snowbird, Utah, United States
• 7: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 8: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 9: Olin Shivers, The semantics of Scheme control-flow analysis, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-198, June 17-19, 1991, New Haven, Connecticut, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages

Keywords:
demand-driven analysis, static analysis, type analysis