A/D graphs-a data structure for data dependence analysis in programs with pointers

摘要

We describe a new method to determine data dependences in programs with pointers-a mandatory step in parallelization. The use of A/D graphs for data dependence analysis promises a significant improvement on other known methods. We perform a single-pass data dependence analysis by solving a monotone data flow system for a class of restricted imperative languages. Based on an intraprocedural analysis with A/D graphs that is optimal with respect to static analysis, we develop a method to derive a safe approximation of the data dependences by employing k-bounded A/D graphs. Using this method we can perform interprocedural data dependence analysis with storage quadratic in the number of program statements. Our method is fast, uses storage more economical than others, and is able to check the modules of a program separately.