A Comprehensive Approach to Parallel Data Flow Analysis

We present a comprehensive approach to performing data flow analysis in parallel. We identify three types of parallelism inherent in the data flow solution process: independent-problem parallelism, separate-unit parallelism and algorithmic parallelism; and describe a unified framework to exploit them. Our investigations of typical Fortran programs reveal an abundance of the last two types of parallelism. In particular, we illustrate the exploitation of algorithmic parallelism in the design of our parallel hybrid data flow analysis algorithms. We report on the empirical performance of the parallel hybrid algorithm for the Reaching Definitions problem and the structural characteristics of the program flow graphs that affect algorithm performance. Keywords. Data flow analysis, parallel algorithms, parallel data flow analysis. 1 Introduction 1.1 Motivation Data flow analysis is a compile-time analysis technique that gathers information about the flow of data in the program. Data flow i..