Lattice frameworks for multisource and bidirectional data flow problems

ABSTRACT

Multisource data flow problems involve information which may enter nodes independently through different classes of edges. In some cases, dissimilar meet operations appear to be used for different types of nodes. These problems include bidirectional and flow-sensitive problems as well as many static analyses of concurrent programs with synchronization. K-tuple frameworks, a type of standard data flow framework, provide a natural encoding for multisource problems using a single meet operator. Previously, the solution of these problems has been described as the fixed point of a set of data flow equations. Using our k-tuple representation, we can access the general results of standard data flow frameworks concerning convergence time and solution precision for these problems. We demonstrate this for the bidirectional component of partial redundancy suppression and two problems on the program summary graph. An interesting subclass of k-tuple frameworks, the join-of-meets frameworks, is useful for reachability problems, especially those stemming from analyses of explicitly parallel programs. We give results on function space properties for join-of-meets frameworks that indicate precise solutions for most of them will be difficult to obtain.

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: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 4: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• 5: 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
• 6: DIJKSTRA, E. W. 1968. Co-operating sequential processes. In Programming Languages; NATO Advanced Study {nstitute~ F. Genuys, Ed., Academic Press, London, 43-112.
• 7: Evelyn Duesterwald , Mary Lou Soffa, Concurrency analysis in the presence of procedures using a data-flow framework, Proceedings of the symposium on Testing, analysis, and verification, p.36-48, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120811]
• 8: 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]
• 9: Dirk Grunwald , Harini Srinivasan, Data flow equations for explicitly parallel programs, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.159-168, May 19-22, 1993, San Diego, California, United States
• 10: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 11: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 12: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 13: Douglas Long , Lori A. Clarke, Data flow analysis of concurrent systems that use the rendezvous model of synchronization, Proceedings of the symposium on Testing, analysis, and verification, p.21-35, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120810]
• 14: 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]
• 15: Stephen P. Masticola, Static detection of deadlocks in polynomial time, Rutgers University, New Brunswick, NJ, 1993
• 16: Stephen P. Masticola , Barbara G. Ryder, A model of Ada programs for static deadlock detection in polynomial times, ACM SIGPLAN Notices, v.26 n.12, p.97-107, Dec. 1991
• 17: Stephen P. Masticola , Barbara G. Ryder, Non-concurrency analysis, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.129-138, May 19-22, 1993, San Diego, California, United States
• 18: 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]
• 19: 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]
• 20: SLOMAN, B. AND LAKE, T. 1993. Scalar renaming, rescoping and optimising liveness analysis in the presence of pointer induced aliasing and side-effecting expressions. In Proceedings of the 4th International Workshop on Compilers for Parallel Computers, H. J. Sips, Ed., Technical University of Delft, Faculty of Applied Physics, Advanced School for Computing and Imaging.
• 21: 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]
• 22: Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
• 23: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, 1984
• 24: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages

Keywords:
data flow analysis, lattice frameworks