Bidirectional data flow analysis: myths and reality

ABSTRACT

Research in bidirectional data flow analysis seems to have come to a halt due to an impression that the case for bidirectional data flow analysis has been considerably weakened by a plethora of investigations based on decomposability of known bidirectional placement algorithms into a sequence of purely unidirectional components. This paper shows that the approach of decomposability is not general enough in that it derives its power from the simplifying graph transformation of edge-splitting and the favourable nature of flows in partial redundancy elimination (PRE). This follows from the fact that in the absence of edge-splitting, PRE cannot be performed using a sequence of cascaded unidirectional flows. Further, edge-splitting inherently converts data flows involved in PRE into unidirectional flows. In our opinion, this obviates the need of an alternative formulation. We also show that edge-splitting cannot convert data flows involved in "truly" bidirectional data flow problems into unidirectional flows. Thus not every bidirectional data flow problem can be converted into unidirectional flows. Besides, we argue that the premise that bidirectional analysis is more complex than unidirectional analysis, is invalid. We also mention some issues in bidirectional data flow analysis which need to be investigated.

REFERENCES

• 1: Gagan Agrawal, Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.609-625, July 1998 [doi>10.1109/71.707537]
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 4: Rastislav Bodík , Rajiv Gupta, Partial dead code elimination using slicing transformations, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.159-170, June 16-18, 1997, Las Vegas, Nevada, United States
• 5: 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
• 6: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
• 7: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 8: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 9: 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
• 10: P. Cousot. Semantic foundations of program analysis, 1981. In {46}.
• 11: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 12: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 13: 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]
• 14: 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]
• 15: D. M. Dhamdhere. A new algorithm for composite hoisting and strength reduction optimization. International Journal of Computer Mathematics, 27(1): 1--14, 1989.
• 16: 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]
• 17: D. M. Dhamdhere and J. R. Isaac. A composite algorithm for strength reduction and code movement optimization. International Journal of Computers and Information Sciences, 9(3):243--273, 1980.
• 18: 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]
• 19: 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]
• 20: 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
• 21: V. Dhaneshwar and D. M. Dhamdhere. Strength reduction of large expressions. Journal of Programming Languages, 3:95--120, 1995.
• 22: 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]
• 23: 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]
• 24: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 25: Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Framework for Optimizing Communication in Data-Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.7, p.689-704, July 1996 [doi>10.1109/71.508249]
• 26: Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998 [doi>10.1145/295656.295664]
• 27: Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.107-120, June 20-24, 1994, Orlando, Florida, United States
• 28: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 29: S. M. Joshi and D. M. Dhamdhere. A composite algorithm for strength reduction and code movement: Part I. International Journal of Computer Mathematics, 11(1):21--44, 1982.
• 30: S. M. Joshi and D. M. Dhamdhere. A composite algorithm for strength reduction and code movement: Part II. International Journal of Computer Mathematics, 11(2): 111--126, 1982.
• 31: J. B. Kam and J. D. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7(3):305--318, 1977.
• 32: Uday P. Khedker. A Generalized Theory of Bit Vector Data Flow Analysis. PhD thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1997.
• 33: 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]
• 34: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 35: 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
• 36: J. Knoop, O. Ruthing, and B. Steffen. Lazy strength reduction. Journal of Programming Languages, 1(1):71--91, 1993.
• 37: 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]
• 38: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• 39: 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
• 40: Priyadarshan Kolte , Michael Wolfe, Elimination of redundant array subscript range checks, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.270-278, June 18-21, 1995, La Jolla, California, United States
• 41: 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
• 42: T. J. Marlowe , B. G. Ryder, Properties of data flow frameworks: a unified model, Acta Informatica, v.28 n.2, p.121-163, Dec. 1990 [doi>10.1007/BF01237234]
• 43: Stephen P. Masticola , Thomas J. Marlowe , Barbara G. Ryder, Lattice frameworks for multisource and bidirectional data flow problems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.5, p.777-803, Sept. 1995 [doi>10.1145/213978.213989]
• 44: 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]
• 45: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 46: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 47: 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]
• 48: B. K. Rosen. Monoids for rapid data flow analysis. SIAM Journal of Computing, 9(1): 159--196, 1980.
• 49: 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]
• 50: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 51: David A. Schmidt, Data flow analysis is model checking of abstract interpretations, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.38-48, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268950]
• 52: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for exhaustive and incremental data flow analysis using DJ graphs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.278-290, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 53: Loren Taylor Simpson , Keith D. Cooper, Value-driven redundancy elimination, 1996
• 54: 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]
• 55: Ashok Sreeniwas. Program Transformations and Representations. PhD thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1998.
• 56: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]