THE COMBINING DAG - A TECHNIQUE FOR PARALLEL DATA-FLOW ANALYSIS

As the number of available multiprocessors increases, so does the impo rtance of providing software support for these systems, including para llel compilers. Data flow analysis, an important component of software tools, may be computed many times during the compilation of a program , especially when compiling for a multiprocessor. Although converting a sequential data flow algorithm to a parallel algorithm can present s ome opportunities for computing data flow in parallel, more parallelis m can be exposed by the development of new parallel data flow algorith ms. In this paper, we present a technique that computes rapid data flo w problems in parallel and thus is applicable for commonly used classi cal data flow problems, including reaching definitions, reachable uses , available expressions, and very busy expressions. Unlike previous te chniques, our technique exploits the inherent parallelism in the data flow computation that occurs across independent paths, within linear p aths, and in paths through loops of a control flow graph. The techniqu e first changes cyclic structures in a control flow graph to acyclic s tructures and then builds a combining directed acyclic graph (DAG) tha t represents the paths through the control flow graph needed to comput e data flow. Data flow is then computed using two passes over the DAG by computing the data flow for the nodes on each level of the DAG in p arallel. We also present experimental results comparing the performanc e of our algorithm with a sequential algorithm and a parallelized sequ ential algorithm.