Proc. of the ACM Int'l. Symp. on Softw. Testing and Analysis, Boston, MA, June, 1993, pages 139-148
Ecient Construction of Program Dependence Graphs*
Mary Jean Harrold, Brian Malloy and Gregg Rothermel
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
Abstract
We present a new technique for constructing a
program dependence graph that contains a program's
control
ow, along with the usual control and data
dependence information. Our algorithm constructs a
program dependence graph while the program is be-
ing parsed. For programs containing only structured
transfers of control, our algorithm does not require in-
formation provided by the control
ow 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 dur-
ing the parse, to incorporate exact control dependence
information. There are several advantages to our ap-
proach. 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
ow as well as ex-
act control dependence information into the program
dependence graph, our graph has a wide range of ap-
plicability. We have implemented our algorithm by
incorporating it into the Free Software Foundation's
GNU C compiler; currently we are performing experi-
ments that compare our technique with the traditional
approach.
*This work was partially funded by NSF under grant CCR-
9109531 to Clemson University.
1 Introduction
Structural testing techniques use intermediate
representations of programs to select test data and
determine test adequacy. A common program rep-
resentation is the control
ow 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 o