Empirical Studies of Program Dependence Graph Size for C 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, and also suggest that the difference in size between the two types of control dependence graph is insignificant.


Related research categories:
(1) Program Analysis
(2) Control Dependence
(3) Empirical Studies

Go To Publications