On optimal slicing of parallel programs

ABSTRACT

Optimal program slicing determines for a statement S in a program &pgr; whether or not S affects a specified set of statements, given that all conditionals in &pgr; are interpreted as non-deterministic choices.Only recently, it has been shown that reachability of program points and hence also optimal slicing is undecidable for multi-threaded programs with (parameterless) procedures and synchronization [23]. Here, we sharpen this result by proving that slicing remains undecidable if synchronization is abandoned---although reachability becomes polynomial. Moreover, we show for multi-threaded programs without synchronization, that slicing stays PSPACE-hard when procedure calls are forbidden, and becomes NP-hard for loop-free programs. Since the latter two problems can be solved in PSPACE and NP, respectively, even in presence of synchronization, our new lower bounds are tight.Finally, we show that the above decidability and lower bound properties equally apply to other simple program analysis problems like copy constant propagation and true liveness of variables. This should be contrasted to the problems of strong copy constant propagation and (ordinary) liveness of variables for which polynomial algorithms have been designed [15, 14, 24].

REFERENCES

• 1: Krzysztof R. Apt , Ernst-Rüdiger Olderog, Verification of sequential and concurrent programs (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 2: Ahmed Bouajjani , Peter Habermehl, Constrained Properties, Semilinear Systems, and Petri Nets, Proceedings of the 7th International Conference on Concurrency Theory, p.481-497, August 26-29, 1996
• 3: 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
• 4: E. M. Clarke, M. Fujita, S. P. Rajan, T. Reps, S. Shankar, and T. Teitelbaum. Program slicing for VHDL. In Charme'99, Bad Herrenalb, Germany, September 1999.
• 5: Javier Esparza , Jens Knoop, An Automata-Theoretic Approach to Interprocedural Data-Flow Analysis, Proceedings of the Second International Conference on Foundations of Software Science and Computation Structure, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.14-30, March 22-28, 1999
• 6: Javier Esparza , Andreas Podelski, Efficient algorithms for pre* and post* on interprocedural parallel flow graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325697]
• 7: Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 8: Nissim Francez, Program Verification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 9: Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, Invariance of Approximate Semantics with Respect to Program Transformations, GI - 11. Jahrestagung in Verbindung mit Third Conference of the European Co-operation in Informatics (ECI), p.1-10, October 20-23, 1981
• 10: 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
• 11: 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]
• 12: S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural data ow analysis. Technical Report TR-1283, Computer Sciences Department, University of Wisconsin, Madison, WI, 1995.
• 13: M. Iwaihara, M. Nomura, S. Ichinose, and H. Yasuura. Program slicing on VHDL descriptions and its applications. In Proc. 3rd APCHDL'96, pp. 132-139, Bangalore, 1996.
• 14: Jens Knoop, Parallel Constant Propagation, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.445-455, September 01-04, 1998
• 15: Jens Knoop , Bernhard Steffen , Jürgen Vollmer, Parallelism for free: efficient and optimal bitvector analyses for parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.268-299, May 1996 [doi>10.1145/229542.229545]
• 16: D. Kozen. Lower bounds for natural proof systems. In IEEE FOCS'77, pp. 254-266, Long Beach, CA, 1977.
• 17: 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
• 18: L. I. Millett and T. Teitelbaum. Issues in slicing PROMELA and its applications to model checking, protocol understanding, and simulation. STTT, 2(4):343-349, 2000.
• 19: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 20: Markus Müller-Olm, The Complexity of Copy Constant Detection in Parallel Programs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.490-501, February 15-17, 2001
• 21: 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
• 22: S. Owicki and D. Gries. An axiomatic proof technique for parallel programs. Acta Informatica, 6:319-340, 1976.
• 23: 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]
• 24: Helmut Seidl , Bernhard Steffen, Constraint-Based Inter-Procedural Analysis of Parallel Programs, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.351-365, April 02, 2000
• 25: R. N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19:57-84, 1983.
• 26: F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121-189, 1995.
• 27: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352-357, 1984.
• 28: 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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Keywords:
complexity, interprocedural analysis, parallel programs, slicing, undecidability