page 1  (36 pages)
2to next section

Efficient Construction of Program Dependence Graphs

Mary Jean Harrold, Brian Malloy and Gregg Rothermel

Department of Computer Science

Clemson University

Clemson, SC 29634-1906

[email protected]

(803) 656-0809


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.