Data flow analysis of distributed communicating processes

Data flow analysis is a technique essential to the compile-time optimization of computer programs, wherein facts relevant to program optimizations are discovered by the global propagation of facts obvious locally. This paper extends several known techniques for data flow analysis of sequential programs to the static analysis of distributed communicating processes. In particular, we present iterative algorithms for detecting unreachable program statements, and for determining the values of program expressions. The latter information can be used to place bounds on the size of variables and messages. Our main innovation is the event spanning graph, which serves as a heuristic for ordering the nodes through which data flow information is propagated. We consider both static communication, where all channel arguments are constants, and the more difficult dynamic communication, where channel arguments may be variables and channels may be passed as messages. © 1990 Plenum Publishing Corporation.

Duke Scholars

Author John H. Reif Computer Science