Efficient and precise modeling of exceptions for the analysis of Java programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient and precise modeling of exceptions for the analysis of Java programs

Full text

Pdf (1.16 MB)

Source

Workshop on Program Analysis for Software Tools and Engineering archive
Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering table of contents

Toulouse, France

Pages: 21 - 31

Year of Publication: 1999

ISBN:1-58113-137-2

Also published in ...

Authors

Jong-Deok Choi	IBM Research, Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
David Grove	IBM Research, Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
Michael Hind	IBM Research, Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
Vivek Sarkar	IBM Research, Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 49, Citation Count: 40

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/316158.316171 What is a DOI?

ABSTRACT

The Factored Control Flow Graph, FCFG, is a novel representation of a program's intraprocedural control flow, which is designed to efficiently support the analysis of programs written in languages, such as Java, that have frequently occurring operations whose execution may result in exceptional control flow. The FCFG is more compact than traditional CFG representations for exceptional control flow, yet there is no loss of precision in using the FCFG. In this paper, we introduce the FCFG representation and outline how standard forward and backward data flow analysis algorithms can be adapted to work on this representation. We also present empirical measurements of FCFG sizes for a large number of methods obtained from a variety of Java programs, and compare these sizes with those of a traditional CFG representation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
	2	Bowen Alpern, Anthony Cocchi, Derek Lieber, Mark Mergen, and Vivek Sarkar. Jalapeiio - a compiler-supported Java virtual machine for servers. In ACM SIGPLAN Workshop on Compiler Support for System Software, pages 36-46, May 1999. INRIA Technical Report #0228.
	3	Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
	4	D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, ACM SIGPLAN Notices, v.23 n.7, p.47-56, July 1988
	5	Craig Chambers. The Cecil language: Specification and rationale. Technical Report UW-CSE-93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993. Revised, March 1997.
	6	Ramkrishna Chatterjee , Barbara G. Ryder , William Landi, Complexity of Concrete Type-Inference in the Presence of Exceptions, Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.57-74, March 28-April 04, 1998
	7	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	8	Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
	9	J. A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 7(C-30):478-490, July 1981.
	10	Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David Tarditi. Marmot: An optimizing compiler for Java. Technical Report MSR-TR-99-33, Microsoft Research, June 1999.
	11	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	12	Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994 [doi>10.1145/174662.174663]
	13	Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
	14	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
	15	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	16	Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
	17	Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	18	Martin P. Robillard , Gail C. Murphy, Analyzing exception flow in Java programs, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.322-337, September 06-10, 1999, Toulouse, France
	19	Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189-234. Prentice-Hall, 1981.
	20	S. Sinha , M. J. Harrold, Analysis of Programs with Exception-Handling Constructs, Proceedings of the International Conference on Software Maintenance, p.348, March 16-19, 1998

CITED BY 40

	Kazuaki Ishizaki , Mikio Takeuchi , Kiyokuni Kawachiya , Toshio Suganuma , Osamu Gohda , Tatsushi Inagaki , Akira Koseki , Kazunori Ogata , Motohiro Kawahito , Toshiaki Yasue , Takeshi Ogasawara , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Effectiveness of cross-platform optimizations for a java just-in-time compiler, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Markus Mohnen, An open framework for data-flow analysis in Java: extended abstract, Proceedings of the inaugural conference on the Principles and Practice of programming, 2002 and Proceedings of the second workshop on Intermediate representation engineering for virtual machines, 2002, June 13-14, 2002, Dublin, Ireland
	Jongwook Woo , Jehak Woo , Isabelle Attali , Denis Caromel , Jean-Luc Gaudiot , Andrew L Wendelborn, Alias analysis for exceptions in Java, Australian Computer Science Communications, v.24 n.1, p.321-329, January-February 2002
	Igor Pechtchanski , Vivek Sarkar, Dynamic optimistic interprocedural analysis: a framework and an application, ACM SIGPLAN Notices, v.36 n.11, p.195-210, 11/01/2001
	Vivek Sarkar , Mauricio J. Serrano , Barbara B. Simons, Register-sensitive selection, duplication, and sequencing of instructions, Proceedings of the 15th international conference on Supercomputing, p.277-288, June 2001, Sorrento, Italy
	Martin P. Robillard , Gail C. Murphy, Analyzing exception flow in Java programs, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.322-337, Nov. 1999
	Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, ACM SIGPLAN Notices, v.34 n.10, p.1-19, Oct. 1999
	Gregor Snelting , Frank Tip, Understanding class hierarchies using concept analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.540-582, May 2000
	Jan-Willem Maessen , Vivek Sarkar , David Grove, Program analysis for safety guarantees in a Java virtual machine written in Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.62-65, June 2001, Snowbird, Utah, United States
	John Whaley, Joeq: a virtual machine and compiler infrastructure, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.58-66, June 12-12, 2003, San Diego, California
	Walter Binder, Portable, efficient, and accurate sampling profiling for java-based middleware, Proceedings of the 5th international workshop on Software engineering and middleware, September 05-06, 2005, Lisbon, Portugal
	Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, A study of exception handling and its dynamic optimization in Java, ACM SIGPLAN Notices, v.36 n.11, p.83-95, 11/01/2001
	Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, EDO: Exception-directed optimization in java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.70-105, January 2006
	Martin P. Robillard , Gail C. Murphy, Static analysis to support the evolution of exception structure in object-oriented systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.2, p.191-221, April 2003
	Chen Fu , Ana Milanova , Barbara Gershon Ryder , David G. Wonnacott, Robustness Testing of Java Server Applications, IEEE Transactions on Software Engineering, v.31 n.4, p.292-311, April 2005
	Martin P. Robillard , Gail C. Murphy, Concern graphs: finding and describing concerns using structural program dependencies, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida
	Jang-Wu Jo , Byeong-Mo Chang , Kwangkeun Yi , Kwang-Moo Choe, An uncaught exception analysis for Java, Journal of Systems and Software, v.72 n.1, p.59-69, June 2004
	Chen Fu , Barbara G. Ryder , Ana Milanova , David Wonnacott, Testing of java web services for robustness, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
	Matthew Arnold , Michael Hsiao , Ulrich Kremer , Barbara G. Ryder, Exploring the Interaction between Java's Implicitly Thrown Exceptions and Instruction Scheduling, International Journal of Parallel Programming, v.29 n.2, p.111-137, April 2001
	Jongwook Woo , Jean-Luc Gaudiot , Andrew L. Wendelborn, Alias analysis in Java with reference-set representation for high-performance computing, International Journal of Parallel Programming, v.32 n.1, p.39-76, February 2004
	T. Suganuma , T. Ogasawara , K. Kawachiya , M. Takeuchi , K. Ishizaki , A. Koseki , T. Inagaki , T. Yasue , M. Kawahito , T. Onodera , H. Komatsu , T. Nakatani, Evolution of a java just-in-time compiler for IA-32 platforms, IBM Journal of Research and Development, v.48 n.5/6, p.767-795, September/November 2004
	Marko van Dooren , Eric Steegmans, Combining the robustness of checked exceptions with the flexibility of unchecked exceptions using anchored exception declarations, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Saurabh Sinha , Mary Jean Harrold, Analysis and Testing of Programs with Exception Handling Constructs, IEEE Transactions on Software Engineering, v.26 n.9, p.849-871, September 2000
	Walter Binder, Portable and accurate sampling profiling for Java, Software—Practice & Experience, v.36 n.6, p.615-650, May 2006
	Raymond P.L. Buse , Westley R. Weimer, Automatic documentation inference for exceptions, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Walter Binder , Jarle Hulaas, Flexible and efficient measurement of dynamic bytecode metrics, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
	John Whaley, Joeq: a virtual machine and compiler infrastructure, Science of Computer Programming, v.57 n.3, p.339-356, September 2005
	Shujuan Jiang , Baowen Xu , Liang Shi, An approach to analyzing recursive programs with exception handling constructs, ACM SIGPLAN Notices, v.41 n.4, April 2006
	Martin Bravenboer , Yannis Smaragdakis, Exception analysis and points-to analysis: better together, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA
	Martin Hirzel , Daniel Von Dincklage , Amer Diwan , Michael Hind, Fast online pointer analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.11-es, April 2007
	Patricia M. Hill , Fausto Spoto, Deriving escape analysis by abstract interpretation, Higher-Order and Symbolic Computation, v.19 n.4, p.415-463, December 2006
	Yunhe Shi , Kevin Casey , M. Anton Ertl , David Gregg, Virtual machine showdown: Stack versus registers, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.4, p.1-36, January 2008
	Shujuan Jiang , Yuanpeng Jiang, An analysis approach for testing exception handling programs, ACM SIGPLAN Notices, v.42 n.4, p.3-8, April 2007
	Brian R. Murphy , Vijay Menon , Florian T. Schneider , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai, Fault-safe code motion for type-safe languages, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA
	Thomas Kotzmann , Christian Wimmer , Hanspeter Mössenböck , Thomas Rodriguez , Kenneth Russell , David Cox, Design of the Java HotSpot™ client compiler for Java 6, ACM Transactions on Architecture and Code Optimization (TACO), v.5 n.1, p.1-32, May 2008
	Pramod G. Joisha, A principled approach to nondeferred reference-counting garbage collection, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Westley Weimer , George C. Necula, Exceptional situations and program reliability, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.2, p.1-51, March 2008
	Walter Binder , Alex Villazón , Martin Schoeberl , Philippe Moret, Cache-aware cross-profiling for java processors, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA
	Cristina David , Cristian Gherghina , Wei-Ngan Chin, Translation and optimization for a core calculus with exceptions, Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, January 19-20, 2009, Savannah, GA, USA