Complexity of bi-directional data flow analysis

ABSTRACT

The concept of an information flow path arising from the generalized theory of data flow analysis [21] is used to analyze the complexity of data flow analysis. The width (w) of a program flow graph with respect to a class of data flow problems is introduced as a measure of the complexity of round-robin iterative analysis. This provides the first known complexity result for round robin iterative analysis of bidirectional data flows commonly used in algorithms based on the suppression of partial redundancies [6, 7, 8, 9, 17, 18, 25]. We also show that width provides a better bound on the complexity of unidirectional data flows than the classical notion of depth. The paper presents ways to reduce the width, and thereby the complexity of flow analysis, for several interesting problems. Complexity analysis using the notion of width is also shown to motivate efficient solution methods for various bidirectional problems, viz. The alternating iterations method, and an interval analysis based elimination method for the partial redundancy elimination problems. The paper also presents a condition for the decomposability of a bidirectional problem into a sequence of unidirectional problems.

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: 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]
• 3: S. Biswas, G. P. Bhattacharjee, and P. Dhar. A comparison of some algorithms for live variable analysis. International Journal of Computer Mathematics, 8:121-134, 1980.
• 4: 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
• 5: D. M. Dhamdhere. An elimination algorithm for bi-directional data flow analysis. Technical report CSE-TR-88-31, Department of Computer Science and Engineering, The University of Connecticut, Storrs, 1988.
• 6: 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]
• 7: 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]
• 8: D. M. Dhamdhere. A new algorithm for composite hoisting and strength reduction optimization. International Journal of Computer Mathematics, 27(i):I-14, 1989.
• 9: 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]
• 10: 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]
• 11: 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
• 12: Vikram Dhaneshwar. M. Tech. dissertation (stage 1). Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1992.
• 13: Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
• 14: 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]
• 15: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 16: M. S. Hecht and J. D. Ullman. A simple algorithm for global data flow analysis problems. SIAM Journal oS Compu~in~t, 4(4):519-532, 1977.
• 17: S. M. Joshi and D. M. Dhamdhere. A composite algorithm for strength reduction and code movemerit : part I. International Journal of Computer Mathematics, 11(1):21-44, 1982.
• 18: 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.
• 19: J. B. Kam and J. D. Ullman. Monotone data flow analyaie frameworks. Ac~a Informa$ica, 7(3):305- 318, 1977.
• 20: Uday P. Khedker and D. M. Dhamdhere. Elimination algorithms for bi-directional data flow problems. Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1992. (In preparation).
• 21: Uday P. Khedker and D. M. Dhamdhere. A generalized theory of data flow analysis. Technical report TR-070-92, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, 1992.
• 22: 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]
• 23: 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
• 24: 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]
• 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: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages, Verification