Abstract
In this paper, we show how previous work on escape analysis can be adapted and extended to yield a static analysis that is efficient yet effective for reducing the number of interference dependence edges considered while slicing concurrent Java programs. The key idea is to statically detect situations where run-time heap objects are reachable from a single thread and use it to prune spurious interference dependence edges. We also show how this analysis can be extended to reduce the number of ready dependence edges – dependences that capture indefinite delay due to Java synchronization constructs.
The analysis we describe has been implemented in the Bandera [9] slicer which is being applied to reduce the size of software models for model-checking. Using this implementation, we give experimental results that demonstrate the effectiveness of our approach. We believe leveraging escape information in the manner we describe is a crucial element in scaling slicing techniques to larger concurrent object-oriented programs.
This work was supported in part by the U.S. Army Research Office (DAAD190110564), by DARPA/IXO’s PCES program (AFRL Contract F33615-00-C-3044), and by Rockwell-Collins and by Intel Corporation (Grant 11462).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aldrich, J., Chambers, C., Sirer, E.G., Eggers, S.J.: Static analyses for eliminating unnecessary synchronization from java programs. In: Cortesi, A., Filé, G. (eds.) SAS 1999. LNCS, vol. 1694, pp. 19–38. Springer, Heidelberg (1999)
Blanchet, B.: Escape analysis for object-oriented languages: application to Java. ACM SIGPLAN Notices 34(10), 20–34 (1999)
Bogda, J., Hölzle, U.: Removing unnecessary synchronization in Java. ACM SIGPLAN Notices 34(10), 35–46 (1999)
Boyapati, C., Rinard, M.: A parameterized type system for race-free Java programs. In: Proceedings of 16th Annual Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2001), Tampa Bay, FL, USA (October 2001)
Chen, Z., Baowen, X.: Slicing concurrent java programs. SIGPLAN Notices 36(4), 41–47 (2001)
Choi, J.D., Gupta, M., Serrano, M.J., Sreedhar, V.C., Midkiff, S.P.: Escape analysis for object oriented languages. application to Java. In: Proceedings of Conference on Object-Oriented Systems, Languages and Applications (OOPSLA 1999), Denver, CO, USA, October 1999. ACM SIGPLAN Notices, vol. 34(10), pp. 1–19. ACM, New York (1999)
Choi, J.D., Lee, K., Loginov, A., O’Callahan, R., Sarkar, V., Sridharan, M.: Efficient and precise datarace detection for multithreaded object-oriented programs. In: Proceedings of ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI 2002) (June 2002)
Choi, J.D., Loginov, A., Sarkar, V.: Static datarace analysis for multithreaded object-oriented programs. Technical report, IBM Research Division, Thomas J. Watson Research Centre (2001)
Corbett, J.C., Dwyer, M.B., Hatcliff, J., Laubach, S., Păsăreanu, C.S., Robby, Zheng, H.: Bandera: Extracting finite-state models from Java source code. In: Proceedings of the 22nd International Conference on Software Engineering (ICSE 2000), June 2000, pp. 439–448 (2000)
Flanagan, C., Freund, S.N.: Type-based race detection for Java. ACM SIGPLAN Notices 35(5), 219–232 (2000)
Flanagan, C., Freund, S.N.: Detecting race conditions in large programs. In: Proceedings ACM SIGPLAN/SIGFSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE 2001 (2001)
Gosling, J., Joy, B., Steele, G.: The Java Language Specification, 2nd edn. Addison Wesley, Reading (2000)
Hatcliff, J., Corbett, J.C., Dwyer, M.B., Sokolowski, S., Zheng, H.: A formal study of slicing for multi-threaded programs with jvm concurrency primitives. In: Cortesi, A., Filé, G. (eds.) SAS 1999. LNCS, vol. 1694, p. 1. Springer, Heidelberg (1999)
Horwitz, S., Pfeiffer, P., Reps, T.W.: Dependence analysis for pointer variables. In: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation (PLDI 1989), pp. 28–40. ACM, New York (1989)
Horwitz, S., Reps, T., Binkley, D.: Interprocedural slicing using dependence graphs. In: Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation (PLDI 1988), vol. 23, pp. 35–46 (1988)
Indus, a toolkit to customize and adapt java programs. This software is, available at http://indus.projects.cis.ksu.edu
Java grande forum benchmark suite - thread version 1.0. This software is, Java Grande Benchmarking Project at Edinburgh Parallel Computing Centre, available at http://www.epcc.ed.ac.uk/computing/research_activities/java_grande/
Krinke, J.: Static slicing of threaded programs. In: Proceedings ACM SIGPLAN/ SIGFSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE 1998), Montreal, Canada, June 1998. ACM SIGPLAN Notices, vol. 33(7), pp. 35–42 (1998)
Krinke, J.: Context-sensitive slicing of concurrent programs. In: Proceedings of ESEC/SIGSOFT FSE 2003 (2003)
Larsen, L., Harrold, M.J.: Slicing object-oriented software. In: Proceedings of International Conference on Software Engineering (ICSE 1996), pp. 495–505 (1996)
Liang, D., Harrold, M.J.: Slicing objects using system dependence graphs. In: Proceedings of International Conference on Software Maintenance (ICSM 1998), pp. 358–367 (1998)
Livadas, P., Rosenstein, A.: Slicing in the presence of pointer variables (1994)
Müller-Olm, M., Seidl, H.: On optimal slicing of parallel programs. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC 2001), Hersonissos, Greece, pp. 647–656. ACM Press, New York (2001)
Nanda, M.G., Ramesh, S.: Slicing concurrent programs. In: Proceedings of International Symposium on Software Testing and Analysis (ISSTA 2000), pp. 180–190 (2000)
Naumovich, G., Avrunin, G., Clarke, L.: An efficient algorithm for computing MHP information for concurrent java programs. Technical Report UM-CS-1998- 044, University of Massachusetts, Amherst (October 1998)
Ramalingam, G.: Context-sensitive synchronization-sensitive analysis is undecidable. ACM Transactions on Programming Languages and Systems (TOPLAS) 22(2), 416–430 (2000)
Ranganath, V.P.: Object-flow analysis for optimizing finite-state models of java software. Master’s thesis, Kansas State University (2002)
Ruf, E.: Effective synchronization removal for java. In: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI 2000), June 2000, pp. 203–213 (2000)
Aho, V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley International, Reading (1986)
Vallée-Rai, R.: Soot: A Java Bytecode Optimization Framework. Master’s thesis, School of Computer Science, McGill University, Montreal, Canada (October 2000)
Weiser, M.: Program slicing. IEEE Transactions on Software Engineering 10(4), 352–357 (1984)
Zhao, J.: Slicing concurrent Java programs. In: Proceedings of the 7th IEEE International Workshop on Program Comprehension (IWPC 1999), May 1999, pp. 126–133 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ranganath, V.P., Hatcliff, J. (2004). Pruning Interference and Ready Dependence for Slicing Concurrent Java Programs. In: Duesterwald, E. (eds) Compiler Construction. CC 2004. Lecture Notes in Computer Science, vol 2985. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24723-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-24723-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21297-3
Online ISBN: 978-3-540-24723-4
eBook Packages: Springer Book Archive