E-path_PRE: partial redundancy elimination made easy

ABSTRACT

Partial redundancy elimination (PRE) subsumes the classical optimizations of loop invariant movement and common subexpression elimination. The original formulation of PRE involved complex bi-directional data flows and had two major deficiencies---missed optimization opportunities and redundant code movement. To eliminate redundant code movement, most current PRE approaches use a hoisting-followed-by-sinking approach. Unfortunately, this approach has a high conceptual complexity and requires complicated correctness proofs.We show that optimization by partial redundancy elimination is simpler than it has been made out to be. Its essence is the concept of eliminatability of an expression. We show that E-path_PRE, a formulation of PRE based on the concept of eliminatability paths (E-paths), is easy to understand and simple to prove correct. It uses only well-known data flow concepts of available expressions and anticipatable (i.e. very-busy) expressions to directly identify code insertion points which avoid redundant code movement. These features reduce the conceptual complexity of PRE considerably. Interestingly, performance studies show that E-path_PRE is also less expensive to perform than the closest equivalent approach to PRE. This is a sheer bonus.

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: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.1-14, June 17-19, 1998, Montreal, Quebec, Canada
• 3: Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.273-286, June 16-18, 1997, Las Vegas, Nevada, United States
• 4: D. M. Dhamdhere, A fast algorithm for code movement optimisation, ACM SIGPLAN Notices, v.23 n.10, p.172-180, Oct. 1988 [doi>10.1145/51607.51621]
• 5: D. M. Dhamdhere, Register assignment using code placement techniques, Computer Languages, v.13 n.2, p.75-93, July 1988 [doi>10.1016/0096-0551(88)90011-2]
• 6: D. M. Dhamdhere. A new algorithm for composite hoisting and strength reduction optimisation. International Journal of Computer Mathematics, 27:1-14, 1989.
• 7: D. M. Dhamdhere, A usually linear algorithm for register assignment using edge placement of load and store instructions, Computer Languages, v.15 n.2, p.83-94, 1990 [doi>10.1016/0096-0551(90)90012-E]
• 8: 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]
• 9: D. M. Dhamdhere and J. R. Isaac. A composite algorithm for strength reduction and code movement. International Journal of Computers and Information Sciences, pages 243-273, 1980.
• 10: Dhananjay M. Dhamdhere , Uday P. Khedker, Complexity of bi-directional data flow analysis, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158696]
• 11: D. M. Dhamdhere , Harish Patil, An elimination algorithm for bidirectional data flow problems using edge placement, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.312-336, April 1993 [doi>10.1145/169701.169684]
• 12: Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.212-223, June 15-19, 1992, San Francisco, California, United States
• 13: V. M. Dhaneshwar and D. M. Dhamdhere. Strength reduction of large expressions. Journal of Programming Languages, 3:95-120, 1995.
• 14: 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]
• 15: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• 16: S. M. Joshi and D. M. Dhamdhere. A composite hoisting-strength reduction transformation for global program optimisation, Parts I and II. International Journal of Computer Mathematics, 11(1 & 2):21-24 & 111-126, 1982.
• 17: K. Kennedy. Safety of code movement. International Journal of Computer Mathematics, 3:112-130, 1972.
• 18: Robert Kennedy , Fred C. Chow , Peter Dahl , Shin-Ming Liu , Raymond Lo , Mark Streich, Strength Reduction via SSAPRE, Proceedings of the 7th International Conference on Compiler Construction, p.144-158, March 28-April 04, 1998
• 19: Uday P. Khedker , Dhananjay M. Dhamdhere, A generalized theory of bit vector data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1472-1511, Sept. 1994 [doi>10.1145/186025.186043]
• 20: Uday P. Khedker , Dhananjay M. Dhamdhere, Bidirectional data flow analysis: myths and reality, ACM SIGPLAN Notices, v.34 n.6, June 1999 [doi>10.1145/606666.606676]
• 21: 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
• 22: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 23: Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.233-245, June 18-21, 1995, La Jolla, California, United States
• 24: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.26-37, June 17-19, 1998, Montreal, Quebec, Canada
• 25: 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]
• 26: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 27: Vineeth Kumar Paleri , Y. N. Srikant , Priti Shankar, A simple algorithm for partial redundancy elimination, ACM SIGPLAN Notices, v.33 n.12, p.35-43, Dec. 1998 [doi>10.1145/307824.307851]
• 28: 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]
• 29: Oliver Rüthing, Bidirectional Data Flow Analysis in Code Motion: Myth and Reality, Proceedings of the 5th International Symposium on Static Analysis, p.1-16, September 14-16, 1998
• 30: Oliver Rüthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325715]
• 31: Bernhard Steffen, Property-Oriented Expansion, Proceedings of the Third International Symposium on Static Analysis, p.22-41, September 24-26, 1996
• 32: Michael Wolfe, Partial redundancy elimination is not bidirectional, ACM SIGPLAN Notices, v.34 n.6, June 1999 [doi>10.1145/606666.606675]

INDEX TERMS

Keywords:
code optimization, data flow analysis, eliminatability of expressions, partial redundancy elimination, redundant code movement