Empirical Studies of Control Dependence Graph Size forC Programs

Abstract

Many tools and techniques for performing software engineering tasks require control-dependence information, represented in the form of control-dependence graphs. Worst-case analysis of these graphs has shown that their size may be quadratic in the number of statements in the procedure that they represent. Despite this result, two empirical studies suggest that in practice, the relationship between control-dependence graph size and program size is linear. These studies, however, were performed on a relatively small number of Fortran procedures, all of which were derived from numerical methods programs. To further investigate control-dependence size, we implemented tools for constructing the two most popular types of control-dependence graphs, and ran our tools on over 3000 C functions extracted from a wide range of source programs. Our results support the earlier conclusions about control-dependence graph size.

Publication
Empirical Software Engineering