Manuel Fähndrich
Jakob Rehof
Abstract
This paper shows that a type graph (obtained via polymorphic type inference) harbors explicit directional flow paths between functions. These flow paths arise from the instantiations of polymorphic types and correspond to call-return sequences in first-order programs. We show that flow information can be computed efficiently while considering only paths with well matched call-return sequences, even in the higher-order case. Furthermore, we present a practical algorithm for inferring type instantiation graphs and provide empirical evidence to the scalability of the presented techniques by applying them in the context of points-to analysis for C programs.
- ASU88 A.V. Aho, R. Sethi, and J. D. Ullman. Compilers Principles, Techniques, and Tools. Addison Wesley, 1988. Google Scholar
Digital Library
- CGS+99 Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. Escape analysis for java. In OOPSLA'99 {OOP99}, pages 1-19. Google ScholarDigital Library
- CRL99 Ramkrishna Chatterjee, Barbara G. Ryder, and William A. Landi. Relevant context inference. In Conference Record of the 26th Annual A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages, January 1999. Google ScholarDigital Library
- DM82 L. Damas and R. Milner. Principle type-schemes for functional programs. In Conference Record of the 9th Annual ACM Symposium on Principles of Programming Languages, pages 207-212, January 1982. Google ScholarDigital Library
- FFA00 Jeffrey S. Foster, Manuel Fahndrich, and Alexander Aiken. Polymorphic versus monomorphic points-to analysis. In Proceedings of the 7th International Static Analysis Symposium, Lecture Notes in Computer Science. Springer Verlag, June 2000. Google ScholarDigital Library
- FRD00 Manuel Fahndrich, Jakob Rehof, and Manuvir Das. From polymorphic subtyping to CFL reachability: Context-sensitive flow analysis using instantiation constraints. Technical Report MSR- TR-99-84, Microsoft Research, March 2000.Google Scholar
- Hen93 Fritz Henglein. Type inference with polymorphic recursion. ACM Transactions on Programming Languages and Systems, 15(2):253-289, 1993. Google ScholarDigital Library
- HM97 Nevin Heintze and David McAllester. Lineartime subtransitive control flow analysis. In Proceedings of the 1997 A CM SIGPLAN Conference on Programming Language Design and Implementation, number 32:6 in SIGPLAN notices, pages 261-272, June 1997. Google ScholarDigital Library
- JW95 Suresh Jagannathan and Andrew Wright. Effective flow analysis for avoiding run-time checks. In Proceedings of the 2nd International Static Analysis Symposium, volume 983 of Lecture Notes in Computer Science, pages 207-224. Springer Verlag, September 1995. Google ScholarDigital Library
- KTU93 A.J. Kfoury, J. Tiuryn, and P. Urzyczyn. The undecidability of the semi-unification problem. Information and Computation, 102(1):83-101, January 1993. Google ScholarDigital Library
- KTU94 A.J. Kfoury, J. Tiuryn, and P. Urzyczyn. An analysis of ML typability. Journal of the A CM, 41(2):368-398, March 1994. Google ScholarDigital Library
- LH99 Donglin Liang and Mary Jean Harrold. Efficient points-to analysis for whole-program analysis. In Proceedings of the 7th European Software Engineering Conference and the 7th A CM SIGSOFT Symposium on the Foundations of Software Engineering, September 1999. Google ScholarDigital Library
- Mil78 R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, 1978.Google ScholarCross Ref
- MR97 David Melski and Thomas Reps. Interconvertibility of set constraints and context-free language reachability. In Proceedings of the A CM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM-97), volume 32, 12 of ACM SIGPLAN Notices, pages 74-89. ACM Press, June 1997. Google ScholarDigital Library
- Myc84 A. Mycroft. Polymorphic type schemes and recursive definitions. In Proceedings of the 6th International Symposium on Programming, pages 217-228, 1984. Google ScholarDigital Library
- NN97 Flemming Nielson and Hanne Riis Nielson. Infinitary control flow analysis: a collecting semantics for closure analysis. In Conference Record of the 24th Annual A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages, pages 332-345. ACM Press, January 1997. Google ScholarDigital Library
- OJ97 Robert O'Callahan and Daniel Jackson. Lackwit: A program understanding tool based on type inference. In International Conference on Software Engineering, May 1997. Google ScholarDigital Library
- OOP99 Proceedings of 14th Annual Conference on Object-Oriented Programming, Systems, Languages, and Applications, volume 34, 10 of A CM SIGPLAN Notices. ACM Press, November 1999.Google Scholar
- RHS95 Thomas Reps, Susan Horwitz, and Mooly Sagiv. Precise interprocedural datafiow analysis via graph reachability. In Conference record of POPL '95, 22nd A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages: papers presented at the Symposium: San Francisco, California, January 22-25, 1995, pages 49-61, 1995. Google ScholarDigital Library
- Ste96 Bjarne Steensgaard. Points-to analysis in almost linear time. In Conference Record of the 23rd Annual A CM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32- 41, January 1996. Google ScholarDigital Library
- WL95 Robert P. Wilson and Monica S. Lain. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the 1995 A CM SIGPLAN Conference on Programming Language Design and Implementation, number 30:6 in SIGPLAN notices, June 1995. Google ScholarDigital Library
- WR99 John Whaley and Martin Rinard. Compositional pointer and escape analysis for java programs. In OOPSLA'99 {OOP99}, pages 187-206. Google ScholarDigital Library
Index Terms
- Scalable context-sensitive flow analysis using instantiation constraints
Recommendations
Scalable context-sensitive flow analysis using instantiation constraints
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationThis paper shows that a type graph (obtained via polymorphic type inference) harbors explicit directional flow paths between functions. These flow paths arise from the instantiations of polymorphic types and correspond to call-return sequences in first-...
Precise and scalable context-sensitive pointer analysis via value flow graph
ISMM '13: Proceedings of the 2013 international symposium on memory managementIn this paper, we propose a novel method for context-sensitive pointer analysis using the value flow graph (VFG) formulation. We achieve context-sensitivity by simultaneously applying function cloning and computing context-free language reachability (...
Precise and scalable context-sensitive pointer analysis via value flow graph
ISMM '13: Proceedings of the 2013 international symposium on memory managementIn this paper, we propose a novel method for context-sensitive pointer analysis using the value flow graph (VFG) formulation. We achieve context-sensitivity by simultaneously applying function cloning and computing context-free language reachability (...
Comments