Article

Free access

An empirical study of static call graph extractors

Authors:

Gail C. Murphy,

Erica S.-C. LanAuthors Info & Claims

ICSE '96: Proceedings of the 18th international conference on Software engineering

Pages 90 - 99

Published: 01 May 1996 Publication History

PDF eReader Publisher Site

Abstract

Informally, a call graph represents calls between entities in a given program. The call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur an any execution of the program. Numerous software engineering tools also extract call graphs, with the expectation that they will help software engineers increase their understanding of a program. The requirements placed on software engineering tools when computing call graphs are typically more related than for compilers. For example, some false negatives-calls that can in fact take place in some execution of the program, but which are omitted from the call graph-may be acceptable, depending on the understanding task at hand. In this paper we empirically show a consequence of this spectrum of requirements by comparing the C call graphs extracted from three software systems (mapmaker, mosaic, and gee) by five extraction tools (cflow, CIA, Field, mk-functmap, and rigiparse). A quantitative analysis of the call graphs extracted for each system shows considerable variation, a result that is counterintuitive to many experienced software engineers. A qualitative analysis of these results reveals a number of reasons for this variation: differing treatments of macros, function pointers, input formats, etc. We describe and discuss the study, sketch the design space, and discuss the impact of our study on practitioners, tool developers, and researchers.

References

[1]

F.E. Allen. Interprocedural Data Flow Analysis. In Proceedings Information Processing 74 (Software), pages 398-402. North-Holland, August 1974.

[2]

J.P. Banning. An Efficient Way to Find the Side Effects of Procedure Calls and the Aliases of Variables. In Conference Record of the 6th ACM Sgmpostum on Principles of Programming Languages, pages 29-41. ACM Press, January 1979.

Digital Library

[3]

J.M. Barth. A Practical Interprocedural Data Flow Analysis Algorithm. Communications of the ACM, 21 (9):724-736, September 1978.

Digital Library

[4]

D. Callahan, A. Carle, M.W. Hall, and K. Kennedy. Constructing the Procedure Call Multigraph. IEEE Transactions on Software Engineering, SE-16(4):483- 487, April 1990.

Digital Library

[5]

Y.-F. Chen, M.Y. Nishlmoto, and C.V. Ramamoorthy.The C Information Abstraction System. IEEE Transactions on Sojtware Engineering, SE16(3):325- 334, March 1990.

Digital Library

[6]

K. Cooper and K. Kennedy. Efficient Computation of Flow Insensitive Interprocedural Summary Information. In Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction, pages 247- 258. ACM Press, June 1984.

Digital Library

[7]

K. Cooper, K. Kennedy, and L. Torczon. Interprocedural Optimization: Eliminating Unnecessary Recompilation. In Proceedings of the ACM SIGPLAN '86 Symposium on Compiler Construction, pages 58- 67. ACM Press, June 1986.

Digital Library

[8]

M. W. Hall and K. Kennedy. Efficient Call Graph Analysis. ACM Letters on Programming Languages and Systems, 1(3):227-242, September 1992.

Digital Library

[9]

L. Hatton and A. Roberts. How Accurate is Scientific Software? IEEE Transactions on Software Engineering, SE-2 O(1O):785-797, October 1994.

Digital Library

[10]

S.C. Johnson. Yacc-Yet Another Compiler Compiler. Technical Report Computing Science Technical Report 32, AT&T Bell Laboratories, 1975.

[11]

B. W. Kernighan and D.M. Ritchie. The C Programming Language. Prentice Hall, 2nd edition, 1988.

Digital Library

[12]

A. Lakhotia. Constructing Call Multigraphs using Dependence Graphs. In Conference Record of the 20th ACM Symposium on Principles of Programming Languages, pages 273-284. ACM Press, January 1993.

Digital Library

[13]

M.E. Lesk. Lex-A Lexical Analyzer Generator. Technical Report Computing Science Technical Report 39, AT&T Bell Laboratories, Murray Hill, N. J., 1975.

[14]

H.A. Miiller and K. Klashinsky. Rigi- A System for Programming-in-the-large. In Proceedings of the 10th International Conference on Sojlware Engineering, pages 80-86. IEEE Computer Society Press, April 1989.

Digital Library

[15]

E. Myers. A Precise Inter-procedural Data Flow Algorithm. In Conference Record oj the 8th ACM Symposium on Principles of Programming Languages, pages 219-230. ACM Press, January 1981.

Digital Library

[16]

S.P. Reiss. The Field Programming Environment: A Friendly Integrated Environment for Learning and Development. Kluwer Academic Publishers, 1995.

Digital Library

[17]

B.G. Ryder. Constructing the Call Graph of a Program. IEEE Transactions on Software Engineering, SE-5(3):216-226, May 1979.

Digital Library

Cited By

Gharibi GTripathi RLee YHuchard MKästner CFraser G(2018)Code2graph: automatic generation of static call graphs for Python source codeProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3240484(880-883)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3240484
Murphy-Hill EGlinz MMurphy GPezzè M(2012)Continuous social screencasting to facilitate software tool discoveryProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337406(1317-1320)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337406
Lhoták ODas MGrossman D(2007)Comparing call graphsProceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering10.1145/1251535.1251542(37-42)Online publication date: 13-Jun-2007
https://dl.acm.org/doi/10.1145/1251535.1251542
Show More Cited By

Index Terms

An empirical study of static call graph extractors
1. Software and its engineering
  1. Software creation and management
    1. Designing software
    2. Software development techniques
  2. Software notations and tools
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

An empirical study of static call graph extractors

Informally, a call graph represents calls between entities in a given program. The call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur in ...
On the Efficient Engineering of Ambitious Program Analysis

Recent advances in languages, software design methodologies, and architecture have prompted the development of improved compile-time methods for analyzing the effects of procedure calls, pointer references, and array accesses. Such sophistication, ...
Interprocedural Def-Use Associations for C Systems with Single Level Pointers

Def-use analysis links possible value-setting statements for a variable (i.e. definitions) to potential value-fetches (i.e. uses) of that value. This paper describes the first algorithm that calculates accurate interprocedural def-use associations in C ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '96: Proceedings of the 18th international conference on Software engineering

May 1996

590 pages

ISBN:0818672463

Chairman:
H. Dieter Rombach
Univ. of Kaiserslautern, Germany

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

German Comp Soc: GI - Gesellshaft for Informatik
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\TCSE: TC on Software Engineering

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 1996

Check for updates

Author Tags

Qualifiers

Article

Conference

ICSE96

Sponsor:

German Comp Soc
SIGSOFT
IEEE-CS\TCSE

ICSE96: 18th International Conference on Software Engineering

March 25 - 29, 1996

Berlin, Germany

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)13

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gharibi GTripathi RLee YHuchard MKästner CFraser G(2018)Code2graph: automatic generation of static call graphs for Python source codeProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3240484(880-883)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3240484
Murphy-Hill EGlinz MMurphy GPezzè M(2012)Continuous social screencasting to facilitate software tool discoveryProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337406(1317-1320)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337406
Lhoták ODas MGrossman D(2007)Comparing call graphsProceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering10.1145/1251535.1251542(37-42)Online publication date: 13-Jun-2007
https://dl.acm.org/doi/10.1145/1251535.1251542
Atkinson DGriswold W(2006)Effective pattern matching of source code using abstract syntax patternsSoftware—Practice & Experience10.5555/1122563.112256736:4(413-447)Online publication date: 1-Apr-2006
https://dl.acm.org/doi/10.5555/1122563.1122567
Terada M(2005)ETVACM SIGCSE Bulletin10.1145/1151954.106748037:3(118-122)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1145/1151954.1067480
Ohba MGondow K(2005)Toward mining "concept keywords" from identifiers in large software projectsProceedings of the 2005 international workshop on Mining software repositories10.1145/1083142.1083151(1-5)Online publication date: 17-May-2005
https://dl.acm.org/doi/10.1145/1083142.1083151
Ohba MGondow K(2005)Toward mining "concept keywords" from identifiers in large software projectsACM SIGSOFT Software Engineering Notes10.1145/1082983.108315130:4(1-5)Online publication date: 17-May-2005
https://dl.acm.org/doi/10.1145/1082983.1083151
Terada MCunha JFleischman WProulx VLourenço J(2005)ETVProceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education10.1145/1067445.1067480(118-122)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1145/1067445.1067480
Finnigan PHolt RKallas IKerr SKontogiannis KMüller HMylopoulos JPerelgut SStanley MWong K(2002)The software bookshelfAdvances in software engineering10.5555/505630.505644(295-339)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.5555/505630.505644
Ernst MBadros GNotkin D(2002)An Empirical Analysis of C Preprocessor UseIEEE Transactions on Software Engineering10.1109/TSE.2002.115828828:12(1146-1170)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1109/TSE.2002.1158288
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents