Empirical studies of control dependence graph size for C programs

被引：4

作者：

Harrold M.J. ^{[1
]}

Jones J.A. ^{[1
]}

Rothermel G. ^{[2
]}

机构：

[1] Computer and Information Science, Ohio State University, 395 Dreese Lab, Columbus

[2] Computer Science, Oregon State University, 307A Dearborn Hall, Corvallis

来源：

Empirical Software Engineering | 1998年 / 3卷 / 2期

基金：

美国国家科学基金会;

关键词：

Control dependence; Program analysis; Software engineering; Static analysis;

D O I：

10.1023/A:1008088300124

中图分类号：

学科分类号：

摘要：

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.

引用

页码：203 / 211

页数：8

共 18 条

[1]

Agrawal, H., DeMillo, R., Spafford, E., Dynamic slicing in the presence of unconstrained pointers (1991) Proceedings of the Symposium on Testing, Analysis and Verification, pp. 60-73

[2]

Agrawal, H., Horgan, J., Krauser, E., London, S., Incremental regression testing (1993) Proceedings of the Conference on Software Maintenance - 1993, pp. 348-357

[3]

Agrawal, H., Horgan, J.R., Dynamic program slicing (1990) Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, pp. 246-256

[4]

Bates, S., Horwitz, S., Incremental program testing using program dependence graphs (1993) Proceedings of the 20th ACM Symposium on Principles of Programming Languages, pp. 384-396

[5]

Binkley, D., Using semantic differencing to reduce the cost of regression testing (1992) Proceedings of the Conference on Software Maintenance - 1992, pp. 41-50

[6]

Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K., An efficient method of computing static single assignment form (1989) POPL89, pp. 25-35

[7]

Cytron, R., Ferrante, J., Sarkar, V., Compact representations for control dependence (1990) Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 337-351

[8]

Duesterwald, E., Gupta, R., Soffa, M.L., Rigorous data flow testing through output influences (1992) Second Irvine Software Symposium, pp. 131-145

[9]

Ferrante, J., Ottenstein, K.J., Warren, J.D., The program dependence graph and its use in optimization (1987) ACM Transactions on Programming Languages and Systems, 9 (3), pp. 319-349

[10]

Gupta, R., Harrold, M.J., Soffa, M.L., An approach to regression testing using slicing (1992) Proceedings of the Conference on Software Maintenance - 1992, pp. 299-308

← 1 2 →