The revival transformation

ABSTRACT

The notion that a definition of a variable is dead is used by optimizing compilers to delete code whose execution is useless. We extend the notion of deadness to that of partial deadness, and define a transformation, the revival transformation, which eliminates useless executions of a (partially dead) definition by tightening its execution conditions without changing the set of uses which it reaches or the conditions under which it reaches each of them.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alien, F. E. and Cocke, J. A catalogue of optimizing techniques. Design and Optimization of Compilers, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., (1971) 1-30.
• 3: Ferrante, J., Ottenstein, K. J., and Warren, J. D. The program dependence graph and its use in optimization. Technical Report CS-TR 86- 8, Computer Science Department, Michigan Technological University- Houghton, M.I., (1986).
• 4: Jeanne Ferrante , Mary Mace, On linearizing parallel code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.179-190, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318636]
• 5: J. Ferrante , M. Mace , B. Simons, Generating sequential code from parallel code, Proceedings of the 2nd international conference on Supercomputing, p.582-592, June 1988, St. Malo, France [doi>10.1145/55364.55421]
• 6: B. Simons , D. Alpern , J. Ferrante, A foundation for sequentializing parallel code, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.350-359, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97702]
• 7: Ball, T., and Horwitz S. Constructing control flow from control dependence. Technical Report TR1091, Computer Sciences Department, University of Wisconsin- Madison, W.I., (1992).
• 8: Morel, E., and Renvoise, C. A global algorithm for the elimination of partial redundancies. 2nd Int. Syrup. on Programming, Paris, (1976) 147-159.
• 9: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 10: Karl-Heinz Drechsler , Manfred P. Stadel, A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.635-640, Oct. 1988 [doi>10.1145/48022.214509]
• 11: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 12: Arthur Sorkin, Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.666-668, Oct. 1989 [doi>10.1145/69558.214513]
• 13: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• 14: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Theory