Summarizing graphs by regular expressions

ABSTRACT

This paper shows how to rapidly determine the path relationships between k different elements of a graph (of the type primarily resulting from programs) in time proportional to k log k. Given the path relations between elements u,v, and w, it is easy to answer questions like "is there a path from u to w?" and "is there a path from u to w which does not go through v?" (The elements can be either nodes or edges.)This algorithm can be used in a wide variety of contexts. For example, in order to prove that whenever control reaches a point p, the last assignment of a value to a variable, v, has always been of the form v := c, where c is a certain constant, it is only necessary to know the path relations between the point p and all assignments to that variable.Ordinarily one is interested in the possible points, where a variable was assigned its current value (definition points), and at the points at which that value is used. Previously, all flow analysis algorithms would compute the definition points of all variables at all nodes in the graph, despite the fact that any given node may use only one of those variables.This algorithm may also be a generally useful graph algorithm. It can compute transitive closure more rapidly than the standard algorithm using the current best matrix multiplication algorithm on the kinds of graphs resulting from programs. The algorithm proceeds by preprocessing the graph, creating tables that can be used later to rapidly determine flow relationships between any sections of the program. In addition, small changes to the graph need only result in small changes to the tables. The algorithm is therefore suitable for incremental analysis.

REFERENCES

• 1: Lawrence T. Kou, On Live-Dead Analysis for Global Data Flow Problems, Journal of the ACM (JACM), v.24 n.3, p.473-483, July 1977 [doi>10.1145/322017.322027]
• 2: 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]
• 3: Mark N. Wegman, General and efficient methods for global code improvement, 1981
• 4: Harel, Dov, 'A linear time algorithm for the lowest common ancestors problem' 21st Annual Symposium on Foundations of Computer Science, Syracuse N.Y., Oct. 1980 pp. 308-319
• 5: Barry K. Rosen, Linear cost is sometimes quadratic, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.117-124, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567545]
• 6: Allen, F. E. et. al. 'The Experimental Compiling System' IBM Journal of Research and Development, vol 24, no 6, Nov. 1980 pp. 695-715.
• 7: 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]
• 8: 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]
• 9: Cocke, J., private communication to a number of people, 1961-62(?).
• 10: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 11: Ferrante, J. personal communication.
• 12: Coppersmith, D. and Winograd, S., On the Asymptotic Complexity of Matrix Multiplication, to appear SIAM Journal on Computing, Aug 82 (also FOCS 1981.
• 13: Aho Hopcroft and Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1975.
• 14: 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]