Efficient calculation of data dependences in programs with pointers and structures

We describe a method to derive safe approximations for data dependences in programs with pointers and structures. In our approach, alias information and reaching definitions´ information at each program point is simultaneously covered by a single representation, called A/D graphs. We perform a single-pass data dependence analysis for a class of restricted imperative languages by solving a monotone data flow system, based on A/D graphs. The advantages of our method are improved accuracy, economical storage use, and reduced analysis time.