J. Michael Ashley
Skip Abstract Section
Abstract
A flow analysis collects data-flow and control-flow information about programs. A compiler can use this information to enable optimizations. The analysis described in this article unifies and extends previous work on flow analysis for higher-order languages supporting assignment and control operators. The analysis is abstract interpretation based and is parameterized over two polyvariance operators and a projection operator. These operators are used to regulate the speed and accuracy of the analysis. An implementation of the analysis is incorporated into and used in a production Scheme compiler. The analysis can process any legal Scheme program without modification. Others have demonstrated that a 0CFA analysis can enables the optimizations, but a 0CFA analysis is O(n)3). An O(n) instantiation of our analysis successfully enables the optimization of closure representations and procedure calls. Experiments with the cheaper instantiation show that it is as effective as 0CFA for these optimizations.
- ASHLEY~ J. iV{. 1997. The effectiveness of flow analysis for inlining. In Proceedings of the 1997ACM SIGPLAN International Conference on Functional Programming. ACM, New York, 99-111. Google Scholar
Digital Library
- ASHLEY~ J. ~/{. AND CONSEL~ C. 1994. Fixpoint computation for polyvariant static analyses of higher-order applicative programs. ACM Trans. Program. Lang. Syst. 16, 5, 1431-1448. Google ScholarDigital Library
- ASHLEY~ J. iV{. AND DYBVIG~ R. K. 1994. An efficient implementation of multiple return values in Scheme. In Proceedings of the 1994 ACM Conference on LISP and Functional Programming. ACM, New York, 140-149. Google ScholarDigital Library
- ASHLEY~ J. iV{. AND DYBVIG~ R. K. 1998. A practical and flexible flow analysis for higher-order languages (extended version). Tech. Rep. DL-1998-02, Univ. of Kansas Design Laboratory, Lawrence, Kan. May.Google Scholar
- AYERS~ A. E. 1993. Abstract analysis and optimization of Scheme. Ph.D. thesis, MIT, Cambridge, Mass. Google ScholarDigital Library
- BONDORF, A. 1993. Similix Manual, System Version 5.0. DIKU, Univ. of Copenhagen, Denmark.Google Scholar
- BOSE, B. 1991. DDD--A transformation system for Digital Design Derivation. Tech. Rep. 331, Computer Science Dept., Indiana Univ., Bloomington, Ind. May.Google Scholar
- BOUCHER~ D. AND FEELEY~ M. 1996. Abstract compilation: A new implementation paradigm for static analysis. In Proceedings of the 1996 International Conference on Compiler Construction. ACM, New York. Google ScholarDigital Library
- BOURDONCLE~ F. 1992. Abstract interpretation by dynamic partitioning. J. Funct. Program. 2, 4 (Oct.), 407-436.Google Scholar
- BOURDONCLE~ F. 1993. Efficient chaotic iteration strategies with widening. In Proceedings of the International Conference on Formal Methods in Programming and their Applications. Lecture Notes in Computer Science, vol. 735. Springer-Verlag, Berlin, 128-141. Google ScholarDigital Library
- BURGER~ R. G. 1994. The Scheme machine. Tech. Rep. 413, Computer Science Dept., Indiana Univ., Bloomington, Ind. Aug.Google Scholar
- CONSEL~ C. 1993. Polyvariant binding-time analysis for higher-order, applicative languages. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM '93. ACM, New York, 66-77. Google ScholarDigital Library
- COUSOT~ P. AND COUSOT~ R. 1977. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the gth A CM Symposium on Principles of Programming Languages. ACM, New York, 238-252. Google ScholarDigital Library
- DYBVIG~ R. K. 1994. Chez Scheme System Manual, Rev. 2.4. Cadence Research Systems, Bloomington, Ind.Google Scholar
- DYBVIG~ R. K. AND HIEB~ R. 1990. A new approach to procedures with variable arity. Lisp Symbol. Comput. 3, 3 (Sept.}, 229-244. Google ScholarDigital Library
- FELLEISEN~ iV{. 1987. The calculi of lambda-v-cs-conversion: A syntactic theory of control and state in imperative higher-order programming languages. Ph.D. thesis, Indiana Univ., Bloomington, Ind. Google ScholarDigital Library
- FLANAGAN~ C. AND FELLEISEN~ iV{. 1995. Set-based analysis for full Scheme and its use in softtyping. Tech. Rep. 253, Computer Science Dept., Rice Univ., Houston, Tex. Oct.Google Scholar
- FLANAGAN, C., SABRY, A., DUBA, B. F., AND FELLEISEN, M. 1993. The essence of compiling with continuations. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. ACM, New York, 237-247. Google ScholarDigital Library
- GABRIEL, R. P. 1985. Performance and Evaluation of LISP Systems. MIT Press Series in Computer Systems. MIT Press, Cambridge, Mass. Google ScholarDigital Library
- HARRISON, W. L. 1989. The interprocedurM analysis and automatic parallelization of Scheme programs. Lisp Symbol. Comput. 2, 3/4, 179-396.Google Scholar
- HEINTZE, N. 1994. Set-based analysis of ML programs. In Proceedings of the 1994 ACM Conference on LISP and Functional Programming. ACM, New York, 306-317. Google ScholarDigital Library
- JAGANNATHAN, S. AND WEEKS, S. 1995. A unified treatment of flow analysis in higher-order languages. In Proceedings of the 22nd Annual A CM SIGPLAN//SIGA CT Symposium on Principles of Programming Languages. ACM, New York, 393-407. Google ScholarDigital Library
- JONES, N. D., GOMARD, C. I~., AND SESTOFT, P. 1993. Partial Evaluation and Automatic Program Generation. Prentice-HM1, Englewood Cliffs, New Jersey. Google ScholarDigital Library
- NIELSON, F. AND NIELSON, H. R. 1992. Two-Level Functional Languages. Cambridge Tracts in Theoretical Computer Science, vol. 34. Cambridge University Press, Cambridge, Mass. Google ScholarDigital Library
- PALSBERG, J. AND SCHWARTZBACH, M. I. 1995. Safety analysis versus type inference. Inf. Comput. 118, 1, 128-141. Google ScholarDigital Library
- SERRANO, M. AND FEELEY, M. 1996. Storage use analysis and its applications. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming. ACM, New York, 50-61. Google ScholarDigital Library
- SHAO, Z. AND APPEL, A. W. 1994. Space-efficient closure representations. In Proceedings of the 1994 ACM Conference on LISP and Functional Programming. ACM, New York, 130-161. Google ScholarDigital Library
- SHIVERS, O. 1988. Control flow analysis in Scheme. In Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation. ACM, New York, 164-174. Google ScholarDigital Library
- SHIVERS, O. 1991. Control-flow analysis of higher-order languages. Ph.D. thesis, Computer Science Dept., Carnegie Mellon Univ., Pittsburgh, Pa. Also available as Tech. Rep. CMU-CS-91-145. Google ScholarDigital Library
- STECKLER, P. A. AND WAND, M. 1997. Lightweight closure conversion. ACM Trans. Program. Lang. Syst. 19, 1, 48-86. Google ScholarDigital Library
- YI, K. AND HARRISON, W. L. 1993. Automatic generation and management of interprocedural program analyses. In Proceedings of the 20th Annual A CM SIGPLAN//SIGACT Symposium on Principles of Programming Languages. ACM, New York, 246-259. Google ScholarDigital Library
- YOUNG, J. H. 1987. The theory and practice: Semantic program analysis for higher-order functional programming languages. Ph.D. thesis, Computer Science Dept., Yale Univ., New Haven, Conn. Google ScholarDigital Library
Index Terms
- A practical and flexible flow analysis for higher-order languages
Recommendations
Introspective pushdown analysis of higher-order programs
ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programmingIn the static analysis of functional programs, pushdown flow analysis and abstract garbage collection skirt just inside the boundaries of soundness and decidability. Alone, each method reduces analysis times and boosts precision by orders of magnitude. ...
Hash-flow taint analysis of higher-order programs
PLAS '12: Proceedings of the 7th Workshop on Programming Languages and Analysis for SecurityAs web applications have grown in popularity, so have attacks on such applications. Cross-site scripting and injection attacks have become particularly problematic. Both vulnerabilities stem, at their core, from improper sanitization of user input.
We ...
Comments