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 (Zobel, 1990) 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. We present the design of region analysis and the empirical results we have obtained that indicate: the prevalence of large intervals in flow graphs derived from real programs; and the performance improvement of region analysis over parallel Allen-Cocke interval analysis. Our implementation analyzed programs from the Perfect Benchmarks and netlib running on a Sequent Symmetry S81