Article

Free access

Constructing call multigraphs using dependence graphs

Author:

Arun LakhotiaAuthors Info & Claims

POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 273 - 284

https://doi.org/10.1145/158511.158647

Published: 01 March 1993 Publication History

PDF eReader

References

[1]

Aho, A. V., Sethi, R., and Ullman, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.

Digital Library

Google Scholar

[2]

Allen, F. E. Interprocedural data flow analysis. In Proceedings IFIP Congress, 1974 (1974), North- Holland, pp. 398-402.

Google Scholar

[3]

Banning, J. P. An efficient way to find the side effects of procedure calls and the aliases of variables. In Proceedings of 6th Annual Symposium on Principles of Programming Languages (1979), ACM, pp. 29-41.

Digital Library

Google Scholar

[4]

Burke, M. An interval-based approach to exhaustive and incremental interprocedural analysis. Tech. Rep. RC 12702, IBM Research Center, Yorktown Heights, NY, Sept. 1987.

Google Scholar

[5]

Callahan, D., Carle, A., Hall, M. W., and Kennedy, K. Consm~cting the procedure call multigraph. IEEE Trans. Soflw. Eng. 16, 4 (Apr. 1990), 483-487.

Digital Library

Google Scholar

[6]

Callahan, D., Cooper, K. D., Kennedy, K., and Torczon, L. Interprocedural constant propagation. In Proceedings of the SIGPLAN' 86 Symposium on Compiler Construction (June 1986), pp. 152-161.

Digital Library

Google Scholar

[7]

Chikofsky, E. J., and Cross II, J. H. Reverse enghneering and design recovery: A taxonomy. IEEE Software (Jan. 1990), 13-17.

Digital Library

Google Scholar

[8]

Choi, S. C., and Scacchi, W. Extracting and restructuring the design of large systems. IEEE Software (Jan. 1990), 66-71.

Digital Library

Google Scholar

[9]

Cooper, K. D., and Kennedy, K. Efficient computation of flow insensitive interprocedural summary information. In Proceedings of the ACM SIGPLAN'84 Symposium on Compiler Construction (Jtme 1984), pp. 247-258.

Digital Library

Google Scholar

[10]

Hecht, M. S. Flow Analysis of Computer Programs. North-Holland, New York, 1977.

Digital Library

Google Scholar

[11]

Horwitz, S., Reps, T., and B inkley, D. Interprocedural slicing using dependence graphs. ACM Trans. Program. Lang. Syst. 12, 1 (1990), 26-60.

Digital Library

Google Scholar

[12]

Kam, J. B., and Ullman, J. D. Monotone data flow analysis frameworks. Acta Informatica 7 (1977), 305-317.

Digital Library

Google Scholar

[13]

Kildall, G. A unified approach to global program optimization. In Proceedings of the first ACM Symposium on Principle of Programming Languages (Oct. 1973), pp. 194-206.

Digital Library

Google Scholar

[14]

Kuck, D. J., Muraoka, Y., and Chen, S. On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up. IEEE Transactions on Computers C- 12, 12 (Dec. 1972).

Google Scholar

[15]

Myers, E. A precise interprocedural data flow algorithm. In Proceedings of the 8th Annual Symposium on Principles of Programming Languages (Jan. 1981), pp. 219-230.

Digital Library

Google Scholar

[16]

Ottenstein, K. J., and Ottenstein, L. M. The program dependence graph in a software development environment. ACM SIGPLAN Notices 19, 5 (May 1984).

Digital Library

Google Scholar

[17]

Ryder, B. G. Constructing the call graph of a program. IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 216-226.

Digital Library

Google Scholar

[18]

Shivers, O. Control-flow Analysis of Higher- Order Languages. Phi) thesis, School of Computer Science, Carnegie Mellon University, 1991.

Digital Library

Google Scholar

[19]

Spillman, T. C. Exposing side-effets in a PL/I optimizing compiler. In Proceedings IFIPS (Computer Software) Conference (1971), pp. 56-60.

Google Scholar

[20]

Wegman, M., and Zadeck, F. Constant propagation with conditional branches. ACM Trans. Program. Lang. Syst. 13, 2 (Apr. 1990), 181-210.

Digital Library

Google Scholar

[21]

Weihl, W. E. Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables. In Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages (Jan. 1980), pp. 83- 94.

Digital Library

Google Scholar

Cited By

View all

Dorta EYan YLiao C(2022)Generating and Analyzing Program Call Graphs using Ontology2022 IEEE/ACM Workshop on Programming and Performance Visualization Tools (ProTools)10.1109/ProTools56701.2022.00008(11-20)Online publication date: Nov-2022
https://doi.org/10.1109/ProTools56701.2022.00008
Jalan RKejariwal A(2012)Trin-Trin: Who’s Calling? A Pin-Based Dynamic Call Graph Extraction FrameworkInternational Journal of Parallel Programming10.1007/s10766-012-0193-x40:4(410-442)Online publication date: 12-May-2012
https://doi.org/10.1007/s10766-012-0193-x
Costa JFeitosa RSouza C(2008)RaisAwareProceedings of the 2008 Simpósio Brasileiro de Sistemas Colaborativos10.1109/SBSC.2008.34(254-264)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1109/SBSC.2008.34
Show More Cited By

Index Terms

Constructing call multigraphs using dependence graphs

Recommendations

Interval Non-edge-Colorable Bipartite Graphs and Multigraphs

An edge-coloring of a graph G with colors 1,...,t is called an interval t-coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erdï s constructed a bipartite graph ...
Constructing connected bicritical graphs with edge-connectivity 2

A graph G is said to be bicritical if the removal of any pair of vertices decreases the domination number of G . For a bicritical graph G with the domination number t , we say that G is t -bicritical. Let λ ( G ) denote the edge-connectivity of G . In 2]...
Constructing Graphs with No Immersion of Large Complete Graphs

In 1989, Lescure and Meyniel proved, for d=5,6, that every d-chromatic graph contains an immersion of Kd, and in 2003 Abu-Khzam and Langston conjectured that this holds for all d. In 2010, DeVos, Kawarabayashi, Mohar, and Okamura proved this conjecture ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

March 1993

510 pages

ISBN:0897915607

DOI:10.1145/158511

Chairmen:
Mary Van Deusen
IBM Watson Research Center
,
Bernard Lang
INRIA Rocquencourt

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL93

Sponsor:

POPL93: 20th ACM Symposium on Principles of Programming Languages

South Carolina, Charleston, USA

Acceptance Rates

POPL '93 Paper Acceptance Rate 39 of 199 submissions, 20%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
458
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)10

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dorta EYan YLiao C(2022)Generating and Analyzing Program Call Graphs using Ontology2022 IEEE/ACM Workshop on Programming and Performance Visualization Tools (ProTools)10.1109/ProTools56701.2022.00008(11-20)Online publication date: Nov-2022
https://doi.org/10.1109/ProTools56701.2022.00008
Jalan RKejariwal A(2012)Trin-Trin: Who’s Calling? A Pin-Based Dynamic Call Graph Extraction FrameworkInternational Journal of Parallel Programming10.1007/s10766-012-0193-x40:4(410-442)Online publication date: 12-May-2012
https://doi.org/10.1007/s10766-012-0193-x
Costa JFeitosa RSouza C(2008)RaisAwareProceedings of the 2008 Simpósio Brasileiro de Sistemas Colaborativos10.1109/SBSC.2008.34(254-264)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1109/SBSC.2008.34
Trainer EQuirk Sde Souza CRedmiles DStorey MBurke MCheng Lvan der Hoek A(2005)Bridging the gap between technical and social dependencies with AriadneProceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange10.1145/1117696.1117702(26-30)Online publication date: 16-Oct-2005
https://dl.acm.org/doi/10.1145/1117696.1117702
Xu BQian JZhang XWu ZChen L(2005)A brief survey of program slicingACM SIGSOFT Software Engineering Notes10.1145/1050849.105086530:2(1-36)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1145/1050849.1050865
Muth RDebray S(2005)On the complexity of function pointer may-alias analysisTAPSOFT '97: Theory and Practice of Software Development10.1007/BFb0030612(381-392)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030612
Burke MCarini PChoi JHind M(2005)Flow-insensitive interprocedural alias analysis in the presence of pointersLanguages and Compilers for Parallel Computing10.1007/BFb0025882(234-250)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0025882
Cheng BHwu W(2001)An Empirical Study of Function Pointers Using SPEC BenchmarksLanguages and Compilers for Parallel Computing10.1007/3-540-44905-1_38(490-493)Online publication date: 12-Jun-2001
https://doi.org/10.1007/3-540-44905-1_38
Sundaresan VHendren LRazafimahefa CVallée-Rai RLam PGagnon EGodin C(2000)Practical virtual method call resolution for JavaACM SIGPLAN Notices10.1145/354222.35318935:10(264-280)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1145/354222.353189
Sundaresan VHendren LRazafimahefa CVallée-Rai RLam PGagnon EGodin CRosson MLea D(2000)Practical virtual method call resolution for JavaProceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications10.1145/353171.353189(264-280)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1145/353171.353189
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Interval Non-edge-Colorable Bipartite Graphs and Multigraphs

Constructing connected bicritical graphs with edge-connectivity 2

Constructing Graphs with No Immersion of Large Complete Graphs