|  | |||||||||
Efficient Construction of Program Dependence Graphs
Mary Jean Harrold, Brian Malloy and Gregg Rothermel
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
(803) 656-0809
Abstract
We present a new technique for constructing a program dependence graph that contains a program's control flow, along with the usual control and data dependence information. Our algorithm constructs a program dependence graph while the program is being parsed. For programs containing only structured transfers of control, our algorithm does not require information provided by the control flow graph or post dominator tree and therefore obviates the construction of these auxiliary graphs. For programs containing explicit transfers of control, our algorithm adjusts the partial control dependence subgraph, constructed during the parse, to incorporate exact control dependence information. There are several advantages to our approach. For many programs, our algorithm may result in substantial savings in time and memory since our construction of the program dependence graph does not require the auxiliary graph. Furthermore, since we incorporate control and data flow as well as exact control dependence information into the program dependence graph, our graph has a wide range of applicability. We have implemented our algorithm by incorporating it into the Free Software Foundation's GNU C compiler; currently we are performing experiments that compare our technique with the traditional approach.
1 Introduction
Structural testing techniques use intermediate representations of programs to select test data and
determine test adequacy. A common program representation is the control flow graph, in which
each node represents a program statement, and each edge represents a transfer of control between
statements. Several recent testing techniques make use of control dependence information, that is
not explicitly represented in a control flow graph. For example, control dependence information has
been used to select data and determine adequacy[13], and to extend data flow testing techniques[7].
Control dependence information has also been used to generate reduced test sets for programs[9].
Moreover, several techniques used for regression testing [4, 5, 10] need control dependence informa-
tion to identify the retesting required after changes are made to a program. Finally, both static and
dynamic slicing techniques require control dependencies[1, 2, 14]. Thus, a program representation
that contains explicit control dependence information is extremely useful for testing.