Interprocedural slicing of multithreaded programs with applications to Java

ABSTRACT

Slicing is a well-known program reduction technique where for a given program P and a variable of interest v at some statement P in the program, a program slice contains those set of statements belonging to P that affect v. This article presents two algorithms for interprocedural slicing of concurrent programs--a context-insensitive algorithm and a context-sensitive algorithm. The context-insensitive algorithm is efficient and correct (it includes every statement that may affect the slicing criterion) but is imprecise since it may include certain extra statements that are unnecessary. Precise slicing has been shown to be undecidable for concurrent programs. However, the context-sensitive algorithm computes correct and reasonably precise slices, but has a worst-case exponential-time complexity. Our context-sensitive algorithm computes a closure of dependencies while ensuring that statements sliced in each thread belong to a realizable path in that thread.A realizable path in a thread with procedure calls is one that reflects the fact that when a procedure finishes, execution returns to the site of the most recently executed call in that thread. One of the novelties of this article is a practical solution to determine whether a given set of statements in a thread may belong to a realizable path. This solution is precise even in the presence of recursion and long call chains in the flow graph.The slicing algorithms are applicable to concurrent programs with shared memory, interleaving semantics, explicit wait/notify synchronization and monitors. We first give a solution for a simple model of concurrency and later show how to extend the solution to the Java concurrency model. We have implemented the algorithms for Java bytecode and give experimental results.

REFERENCES

• 1: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Jon Beck , David Eichmann, Program and interface slicing for reverse engineering, Proceedings of the 15th international conference on Software Engineering, p.509-518, May 17-21, 1993, Baltimore, Maryland, United States
• 4: Binkley, D. and Gallagher, K. 1996. Program slicing. Advances in Computers 43.
• 5: David Binkley , Susan Horwitz , Thomas Reps, Program integration for languages with procedure calls, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.1, p.3-35, Jan. 1995 [doi>10.1145/201055.201056]
• 6: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 7: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 8: Zhenqiang Chen , Baowen Xu, Slicing concurrent java programs, ACM SIGPLAN Notices, v.36 n.4, p.41-47, April 1, 2001 [doi>10.1145/375431.375420]
• 9: Jingde Cheng, Slicing Concurrent Programs - A Graph-Theoretical Approach, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.223-240, May 03-05, 1993
• 10: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Dijkstra, E. W. 1968. Programming Languages. Academic Press, London, England.
• 13: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912 ]
• 14: Mark Harman , David Binkley , Sebastian Danicic, Amorphous program slicing, Journal of Systems and Software, v.68 n.1, p.45-64, 15 October 2003 [doi>10.1016/S0164-1212(02)00135-8]
• 15: Harman, M. and Danicic, S. 1995. Using program slicing to simplify testing. Softw. Test. Verifi. Reliab., 143--162.
• 16: Mary Jean Harrold , Gregg Rothermel , Saurabh Sinha, Computation of interprocedural control dependence, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.11-20, March 02-04, 1998, Clearwater Beach, Florida, United States
• 17: John Hatcliff , James C. Corbett , Matthew B. Dwyer , Stefan Sokolowski , Hongjun Zheng, A Formal Study of Slicing for Multi-threaded Programs with JVM Concurrency Primitives, Proceedings of the 6th International Symposium on Static Analysis, p.1-18, September 22-24, 1999
• 18: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 19: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 20: JavaGrand. Benchmark suite---thread version 1.0. URL http://www.epcc.ed.ac.uk/computing/research_activities/java_grande/.
• 21: Richard Johnson , Keshav Pingali, Dependence-based program analysis, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.78-89, June 21-25, 1993, Albuquerque, New Mexico, United States
• 22: Jens Krinke, Static slicing of threaded programs, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.35-42, June 16-16, 1998, Montreal, Quebec, Canada
• 23: Jens Krinke, Context-sensitive slicing of concurrent programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 24: Arvind Krishnamurthy , Katherine Yelick, Optimizing parallel programs with explicit synchronization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.196-204, June 18-21, 1995, La Jolla, California, United States
• 25: Markus Müller-Olm , Helmut Seidl, On optimal slicing of parallel programs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.647-656, July 2001, Hersonissos, Greece [doi>10.1145/380752.380864]
• 26: Millet, L. and Teitelbaum, T. 1998. Slicing Promela and its application to model checking, simulation, and protocol understanding. In Proceedings of the 4th Workshop on Automata Theoretic Verification with the SPIN Model Checker.
• 27: Lynette I. Millett , Tim Teitelbaum, Channel Dependence Analysis for Slicing Promela, Proceedings of the International Symposium on Software Engineering for Parallel and Distributed Systems, p.52, May 17-18, 1999
• 28: Nanda, M. G. 2001. Slicing concurrent Java programs: Issues and solutions. Ph.D. thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay. http://www.cse.iitb.ernet.in/~ramesh/gow-thesis.ps.gz; Examiners: Dr. Frank Tip, IBM T. J. Watson Research Center and Prof. R. Mall, Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur.
• 29: Mangala Gowri Nanda, An application of compiler technology to the year 2000 problem, Software—Practice & Experience, v.29 n.4, p.359-377, April 10, 1999 [doi>10.1002/(SICI)1097-024X(19990410)29:4<359::AID-SPE232>3.0.CO;2-H ]
• 30: Mangala Gowri Nanda , S. Ramesh, Slicing concurrent programs, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.180-190, August 21-24, 2000, Portland, Oregon, United States
• 31: Mangala Gowri Nanda , S. Ramesh, Pointer analysis of multithreaded Java programs, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952741]
• 32: Diego Novillo , Ronald C. Unrau , Jonathan Schaeffer, Concurrent SSA Form in the Presence of Mutual Exclusion, Proceedings of the 1998 International Conference on Parallel Processing, p.356, August 10-14, 1998
• 33: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 34: G. Ramalingam, Context-sensitive synchronization-sensitive analysis is undecidable, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.416-430, March 2000 [doi>10.1145/349214.349241]
• 35: Ranganath, V. P. and Hatcliff, J. 2004. Pruning interference and ready dependence for slicing concurrent java. In Proceedings of the 13th International Conference on Compiler Construction (CC).
• 36: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 37: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 38: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 39: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 40: V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
• 41: Sharir, M. and Pnueli, A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, NJ, 189--233.
• 42: Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow, Proceedings of the 21st international conference on Software engineering, p.432-441, May 16-22, 1999, Los Angeles, California, United States
• 43: Tip, F. 1995. A survey of program slicing techniques. J. Prog. Lang. 3, 121--181.
• 44: G. A. Venkatesh, The semantic approach to program slicing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.107-119, June 24-28, 1991, Toronto, Ontario, Canada
• 45: Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Eng. 10, 352--357.
• 46: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 47: Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.3, p.310-354, July 1992 [doi>10.1145/131736.131756]
• 48: Jianjun Zhao, Slicing Concurrent Java Programs, Proceedings of the 7th International Workshop on Program Comprehension, p.126, May 05-07, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

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

General Terms:
Algorithms, Design

Keywords:
Multithreading, context-sensitivity, data dependence, interference dependence, program slicing, strongly connected regions