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. G. Agrawal. Interprocedural partial redundancy elimination with application to distributed memory compilation. IEEE Transactions on Parallel and Distributed Systems, 9(7):609--625, 1998.
2. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers -- Principles, Techniques, and Tools. Addison-Wesley, 1986.
3. F. E. Allen and J. Cocke. A program data flow analysis procedure. Communications of ACM, 19(3):137--147, 1977.
4. R. Bodik and R. Gupta. Partial dead code elimination using slicing transformations. In Proceedings of ACM SIGPLAN '97 Conference on Programming Language Design and Implementation, pages 159--170, 1997. Also Published as SIGPLAN Notices, 32(5).
5. R. Bodik, R. Gupta, and M. L. Soffa. Complete removal of redundant computations. In Proceedings of ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 1--14, 1998. Also Published as SIGPLAN Notices, 33(5).
6. P. Briggs and K. D. Kooper. Effective partial redundancy elimination. In Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 159--170, 1994. Also Published as SIGPLAN Notices, 29(6).
7. F. C. Chow. A portable machine-independent global optimizer --- Design and measurements. PhD thesis, Computer Systems Laboratory, Stanford University, 1983.
8. F. C. Chow. Minimizing register usage penalty at procedure calls. In Proceedings of SIGPLAN '88 Symposium on Compiler Construction, pages 85--94, 1988. Also Published as SIGPLAN Notices, 23(7).
9. F. C. Chow, S. Chan, R. Kennedy, S. M. Liu, R. Lo, and P. Tu. A new algorithm for partial redundancy elimination based on SSA form. In Proceesings of ACM SIGPLAN '97 Conference on Programming Language Design and Implementation, pages 273--286, 1997. Also Published as SIGPLAN Notices, 32(5).
10. P. Cousot. Semantic foundations of program analysis, 1981. In {46}.
11. P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th Annual ACM Symposium on Principles of Programming Languages, pages 238--252, 1977.
12. P. Cousot and R. Cousot. Systematic design of program analysis frameworks. In Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages, pages 269--282, 1979.
13. D. M. Dhamdhere. A fast algorithm for code movement optimization. ACM SIGPLAN Notices, 23(10):172--180, 1988.
14. D. M. Dhamdhere. Register assignment using code placement techniques. Computer Languages, 13(2):75--93, 1988.
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 adaptation of the global optimization algorithm by Morel & Renvoise. ACM Transactions on Programming Languages and Systems, 13(2):291--294, 1991.
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. D. M. Dhamdhere and Uday P. Khedker. Complexity of bidirectional data flow analysis. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, pages 397--408, 1993.
19. D. M. Dhamdhere and Harish Patil. An elimination algorithm for bidirectional data flow analysis using edge placement technique. ACM Transactions on Programming Languages and Systems, 15(2): 312--336, 1993.
20. D. M. Dhamdhere, B. K. Rosen, and F. K. Zadeck. How to analyze large programs efficiently and informatively. In Proceedings of ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 212--223, 1992. Also Published as SIGPLAN Notices, 27(7).
21. V. Dhaneshwar and D. M. Dhamdhere. Strength reduction of large expressions. Journal of Programming Languages, 3:95--120, 1995.
22. K. Drechsler and M. P. Stadel. A solution to a problem with Morel and Renvoise's "Global optimizations by suppression of partial redundancies". ACM Transactions on Programming Languages and Systems, 10(4):635--640, 1988.
23. K. Drechsler and M. P. Stadel. A variation of Knoop, Ruthing, and Steffen's lazy code motion. ACM SIGPLAN Notices, 28(5):29--38, 1993.
24. S. Graham and M. Wegman. A fast and usually linear algorithm for global data flow analysis. Journal of ACM, 23(1): 172--202, 1976.
25. M. Gupta, E. Schonberg, and H. Srinivasan. A unified framework for optimizing communication in data-parallel programs. IEEE Transactions on Parallel and Distributed Systems, 7(7):689--704, 1996.
26. Max Hailperin. Cost-optimal code motion. ACM Transactions on Programming Languages and Systems, 20(6): 1297--1322, 1998.
27. R. Hanxleden and K. Kennedy. GIVE-N-TAKE --- A balanced code placement framework. In Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 107--120, 1994. Also Published as SIGPLAN Notices, 29(6).
28. M. S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland Inc., 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 and D. M. Dhamdhere. A generalized theory of bit vector data flow analysis. ACM Transactions on Programming Languages and Systems, 16(5): 1472--1511, 1994.
34. G. Kildall. A unified approach to global program optimization. In Proceedings of the 1st Annual ACM Symposium on Principles of Programming Languages, pages 194--206, 1973.
35. J. Knoop, O. Ruthing, and B. Steffen. Lazy code motion. In Proceedings of ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 224--234, 1992. Also Published as SIGPLAN Notices, 27(7).
36. J. Knoop, O. Ruthing, and B. Steffen. Lazy strength reduction. Journal of Programming Languages, 1(1):71--91, 1993.
37. J. Knoop, O. Ruthing, and B. Steffen. Optimal code motion. ACM Transactions on Programming Languages and Systems, 16(4): 1117--1155, 1994.
38. J. Knoop, O. Ruthing, and B. Steffen. Partial dead code elimination. In Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 147--158, 1994. Also Published as SIGPLAN Notices, 29(6).
39. J. Knoop, O. Ruthing, and B. Steffen. The power of assignment motion. In Proceedings of ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 233--245, 1995. Also Published as SIGPLAN Notices, 30(6).
40. P. Kolte and M. Wolfe. Elimination of redundant array subscript checks. In Proceedings of ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 270--278, 1995. Also Published as SIGPLAN Notices, 30(6).
41. R. Lo, F. C. Chow, R. Kennedy, S. M. Liu, and P. Tu. Register promotion by sparse partial redundancy elimination of loads and stores. In Proceesings of ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 26--37, 1997. Also Published as SIGPLAN Notices, 33(5).
42. T. J. Marlowe and B. G. Ryder. Properties of data flow frameworks. Acta Informatica, 28:121--163, 1990.
43. S. P. Masticola, T. J. Marlowe, and B. G. Ryder. Lattice frameworks for multi-source and bidirectional data flow problems. ACM Transactions on Programming Languages and Systems, 17(5):777--803, 1995.
44. E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of ACM, 22(2):96--103, 1979.
45. S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishing Co., 1997.
46. S. S. Muchnick and N. D. Jones. Program Flow Analysis: Theory and Applications. Prentice-Hall Inc., 1981.
47. V. K. Paleri, Y. N. Srikant, and P. Shankar. A simple algorithm for partial redundancy elimination. ACM SIGPLAN Notices, 33(12):35--43, 1998.
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. Wegmen, and F. K. Zadeck. Global value numbers and redundant computations. In Proceedings of the 15th Annual ACM Symposium on Principles of Programming Languages, pages 12--27, 1988.
50. B. G. Ryder and M. C. Paull. Elimination algorithms for data flow analysis. ACM Computing Surveys, 18:277--316, 1986.
51. David A. Schmidt. Data flow analysis is model checking of abstract interpretation. In Proceedings of the 25th Annual ACM Symposium on Principles of Programming Languages, pages 38--48, 1998.
52. V. C. Shreedhar, G. R. Gao, and Y-F Lee. A new framework for exhaustive and incremental data flow analysis using D-J graphs. In Proceedings of ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 278--290, 1996. Also Published as S1GPLAN Notices, 31(6).
53. L. T. Simpson. Value-Driven Redundancy Elimination. PhD thesis, Department of Computer Science, Rice University, Houston, 1996.
54. A. Sorkin. Some comments on a solution to a problem with Morel and Renvoise's "Global optimizations by suppression of partial redundancies". ACM Transactions on Programming Languages and Systems, 11(4):666--668, 1989.
55. Ashok Sreeniwas. Program Transformations and Representations. PhD thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1998.
56. R. E. Tarjan. Fast algorithms for solving path problems. Journal of ACM, 28(3):594--614, 1981.