October 28, 1992

1 of 24

Program Dependence Graphs

for the Rest of Us

Robert A. Ballance

Arthur B. Maccabe
Department of Computer Science
The University of New Mexico
Albuquerque, NM 87131
Technical Report 92-10

August 1992
Revised, October 1992

This work was supported in part by NSF under grant CCR-9110954, by Sandia National Laboratories under contract No. AC-6748,
and by Kachina Technologies, Inc.

Abstract

This report presents new control dependence analysis techniques that succeed in constructing a control dependence graph (CDG) in all of the common cases without requiring either the control flow graph or the auxiliary structures needed by the fully general algorithm. In the worst case, the intermediate structures built by our algorithms are used to derive a simplified form of the control flow graph that is then used by the general algorithm. In this eventuality, the general algorithm may run more quickly, since a portion of its analysis has already been performed.

The report also presents an adaptation of Tarjan?s interval analysis algorithm for data flow analysis that uses the control dependence graph instead of the control flow graph. Using the CDG-based analysis algorithm allows us to construct a program dependence graph (PDG) without first constructing a control flow graph.

This approach offers several advantages over the conventional models. It eliminates a complete program representation (the control flow graph), it simplifies the construction of the PDG and it supports efficient data flow analysis using the internal representations available. Also, understanding the direct construction of a control dependence graph increases one?s understanding of control dependence and its relation to control flow.

Finally, this report presents a case study of goto usage in C programs which confirms the assumptions that (1) gotos are relatively infrequent and (2) goto usage in C programs largely follows predictable patterns that can be exploited to produce PDGs without resorting to global control dependence analysis in many cases.

Keywords: Program dependence graph, control dependence, data flow analysis, elimination algorithms, goto usage, C programming language.