Region Analysis: A Parallel Elimination Method for Data Flow Analysis

Parallel data flow analysis methods offer the promise of calculating detailed semantic information about a program at compile-time more efficiently than sequential techniques. Previous work on parallel elimination methods [1, 2] has been hampered by the lack of control over interval size; this can prohibit effective parallel execution of these methods. To overcome this problem, we have designed the region analysis method, a new elimination method for data flow analysis. Region analysis emphasizes flow graph partitioning to enable better load balancing in a more effective parallel algorithm. In this paper, we present the design of region analysis and the empirical results we have obtained that indicate (1) the prevalence of large intervals in flow graphs derived from real programs, and (2) the performance improvement of region analysis over parallel Allen-Cocke interval analysis. Our implementation analyzed programs from the Perfect Benchmarks [3] and netlib [4] running on a Sequent Sym..