More Web Proxy on the site http://driver.im/

Article

Free access

Fast interprocedural class analysis

Authors:

Craig ChambersAuthors Info & Claims

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

Pages 222 - 236

https://doi.org/10.1145/268946.268965

Published: 21 January 1998 Publication History

Abstract

Previous algorithms for interprocedural control flow analysis of higher-order and/or object-oriented languages have been described that perform propagation or constraint satisfaction and take O(N³) time (such as Shivers's O-CFA and Heintze's set-based analysis), or unification and take O(Nα (N,N) time (such as Steensgaard's pointer analysis), or optimistic reachability analysis and take O(N) time (such as Bacon and Sweeney's Rapid Type Analysis). We describe a general parameterized analysis framework that integrates propagation-based and unification-based analysis primitives and optimistic reachability analysis, whose instances mimic these existing algorithms as well as several new algorithms taking O(N), O(Nα(N,N)), O(N²), and O(N²α(N,N)) time; our O(N) and O(Nα(N,N)) algorithms produce more precise results than the previous algorithms with these complexities. We implemented our algorithm framework in the Vortex optimizing compiler, and we measured the cost and benefit of these interprocedural analysis algorithms in practice on a collection of substantial Cecil and Java programs.

References

[1]

Oie Agesen. The Cartesian Product Algorithm: Simple and Precise Type Inference of Parametric Polymorphism. In Proceedinga ECOOP "95, Aarhus, Denmark, August 1995. Springer-Verlag.

Digital Library

[2]

Oie Agesen, lens Palsberg, and Michael/. Schwartzbaek. Type Inference of Self: Analysis of Objects with Dynamic and Multiple Inheritance. In Proceedings ECOOP "93, July 1993.

Digital Library

[3]

Hassan A"it-Kaci, Robert Buyer, Patrick Lincoln, and Roger Nasr. Efficient Implementation of Lattice Operations. A CM Transactions on Programming Languages and Systems, 11(1):115-t,16, January 1989.

Digital Library

[4]

J. Michael Ashley. A Practical and Flexible Flow Analysis for Higher-Order Languages. In Conference Record of the 23rd A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages, pages 184-194.

Digital Library

[5]

L Michael Ashley. The Effectiveness of Flow Analysis for Inlining. In Proceedings of the 1997 A CM SIGPLAN International Conference on Functional Progranuning, pages 99-111, Amsterdam, The Netherlands, June I997.

Digital Library

[6]

David F. Bacon and Peter F. Sweeney. Fast Static Analysis of C++ Virtual Function Calls. In OOPS- LA'96 Conference Proceedings, San Jose, CA, October 1996.

Digital Library

[7]

Craig Chambers and David Ungar. Customization: optimizing Compiler Technology for SELF, a Dynamically-Typed Object-Oriented Progratmuing Language. In Proceedings of the S1GPLAN "89 Conference on Programming Language Design and Implementation, pages 146-160, June I989.

Digital Library

[8]

Craig Chambers and David Ungar. Iterative Type Analysis and Extended Message Splitting: Optimizing Dynamically-Typed Object-Oriented Programs. In Proceedings of the ACM SIGPtAN '90 Conference on Programming Language Design and Implementation, pages 150--164, Jane 1990.

Digital Library

[9]

Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report TR-93-03-1)5, Department of Computer Science and Engineering. University of Washington, March 1993.

[10]

Jeffrey Dean. Whole Program Optimization of Object- Oriented Languages. PhD thesis, University of Washington, November 1996. TR-96-11-05.

Digital Library

[11]

Jeffrey Dean, Da'vid Grove, and Craig Chambers. Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis. in Proceedings ECOOP "95, Aarbus, Denmark, August 1995. Springer-Verlag.

Digital Library

[12]

Jeffrey Dean, Greg DeFouw, Dave Grove, Vassily Litvinov, and Craig Chambers. Vortex: An Optimizing Compiler for Object-Oriented Languages. In OOPSLA'96 Conference Proceedings, San Jose, CA, October. 1996.

Digital Library

[13]

Greg DeFouw, David Grove, and Craig Chambers. Fast Interproeedural Class Analysis. Technical Report TR-97-07-02, Department of Computer Science and Engineering. University of Washington, July 1997.

[14]

L. Peter Deatseh and Allan M. Schiffman. Efficient Implementation of the Smalltalk-80 System. In Conference Record of the Eleventh Annual A CM Symposium on Principles of Programming Languages, pages 297- 302, January 1984.

Digital Library

[15]

Cormac Flanagan and Matthias Felleisen. Componential Set-Based Analysis. In Proceedings of zhe A CMSIGPLAN '97 Conference on Programming Language Design and Implementation, pages 235-248,

Digital Library

[16]

James Gosling, Bill Joy, and Guy Steele. The Java Language Specification. Addison-Wesley, Reading, MA, 1996.

Digital Library

[17]

David Grove, Greg DeFouw, Jeffrey Dean, nnd Craig Chambers. Call Graph Construction in Object Orlonted Languages. In OOPSLA "97 Conference Proceedings, Atlanta, GA, October 1997.

Digital Library

[18]

Nevin Heintze and David McAllesler, Linear-Time Subtransitive Control Flow Analysis, In Pro. ceedings of the A CM SIGPLAN "97 Conference on Programming Language Design and Implementation I~PLD97}, pages 261-272.

Digital Library

[19]

Nevin Heintze. Set-Based Analysis of ML Programs. In Proceedings of the ACM Conference on LISP and Function. at Programming "94, pages 306--317, Odanda, FL, junt~ I994.

Digital Library

[20]

Fritz Henglein. Efficient Type Inference for Higher- Order Binding-Time Analysis. in Functional Programmhrg and Computer Architecture, 1991.

Digital Library

[21]

Suresh Jagannathan and Stephen Weeks, A Unified Treatment of Flow Analysis in Higher-Order Languages. In Conference Record of the 22nd A CM SIGPLAN- StGACT Symposium on Principles of Programming Languages, pages 393-407, January 1995.

Digital Library

[22]

Ralph Johnson. T$: AN Optimizing Compiler for SmalItalk. In Proceedings OOPSLA '88, pages 18-26, November 1988. Published as ACM SIGPLAN Notices, volume 23, number 11.

Digital Library

[23]

Hemming Nielsen and Hanne Riis Nidson, Infinitary Control Flow Analysis: A Collecting Semantics for Closure Analysis. In Conference Record of lhe 24lh A CM SIGPLAN-SIGACT Symposium on Principles of Program. ruing Languages, pages 332--345, January 1997.

Digital Library

[24]

Nicholas Oxh~j, Jens Palsberg, and Michael I, Schwartzbach. Making Type Inference Practical, In O.Lehrmann Madsen, editor, Proceedings ECOOP "92, LNCS 615, pages 329-349, Utrecht, The Netherlands, June I992. Spfinger-Veflag.

Digital Library

[25]

John Plevyak and Andrew A. Chien. Preeis~ Concrete Type Inference for Object-Oriented Languages. In Proceedings OOPSLA "94, pages 324-340, Portland, OR, October i994.

Digital Library

[26]

Olin Shivers. Control-Flow Analysis in Scheme. In Pro. ceedings of the SIGPLAN "88 Conference on Programming Language Design and Implementation, pages 164-174, June 1988. '

Digital Library

[27]

Olin Shivers. Control-Flow Analysis o{ Higher-Order Languages. PhD thesis, Carnegie Mellon University, May 1991. CMO-CS-91-145.

Digital Library

[28]

Bjame Steensgaard. Points-to Analys~s in Almost Linear Time. In Conference Record o{ the 23rd A CM SIG. PLAN-SIGACT Symposium on Principles o{ Programming Languages {POP96}, pages 32--41.

Digital Library

[29]

Dan Stefanescu and Yuli Zhou. An Equational Framework for the Flow Analysis of Higher-Order Functional Programs. In Proceedings of the A CM Symposium on Lisp and Funclionat Programming, pages 191)--198, June 1994.

Digital Library

[30]

Robert IS. Tarjan. Efficiency of a good but not linear set union union algorithm. Journal of the ACM, :22(2):215-225, 1975.

Digital Library

Cited By

Ferraiuolo AXu RZhang DMyers ASuh G(2017)Verification of a Practical Hardware Security Architecture Through Static Information Flow AnalysisACM SIGARCH Computer Architecture News10.1145/3093337.303773945:1(555-568)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037739
Ge XCui WJaeger T(2017)GRIFFINACM SIGARCH Computer Architecture News10.1145/3093337.303771645:1(585-598)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037716
Holder LCaceres RGleich DRiedy JKhan MChawla NKumar RWu YKlymko CEliassi-Rad TPrakash A(2016)Current and Future Challenges in Mining Large NetworksACM SIGKDD Explorations Newsletter10.1145/2980765.298077018:1(39-45)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1145/2980765.2980770
Show More Cited By

Index Terms

Fast interprocedural class analysis
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Flowcharts
  2. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
      2. Language types
        Object oriented languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Control primitives
      2. Functional constructs

Recommendations

Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Precise interprocedural analysis using random interpretation
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We describe a unified framework for random interpretation that generalizes previous randomized intraprocedural analyses, and also extends naturally to efficient interprocedural analyses. There is no such natural extension known for deterministic ...
Precise interprocedural analysis using random interpretation
POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We describe a unified framework for random interpretation that generalizes previous randomized intraprocedural analyses, and also extends naturally to efficient interprocedural analyses. There is no such natural extension known for deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

January 1998

403 pages

ISBN:0897919793

DOI:10.1145/268946

Chairmen:
David B. MacQueen
Bell Labs
,
Luca Cardelli
Digital Equipment Corp.

Copyright © 1998 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL98

Sponsor:

POPL98: Symposium on Principles of Programming Languages

January 19 - 21, 1998

California, San Diego, USA

Acceptance Rates

POPL '98 Paper Acceptance Rate 32 of 175 submissions, 18%;

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

62
Total Citations
View Citations
135
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)5

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ferraiuolo AXu RZhang DMyers ASuh G(2017)Verification of a Practical Hardware Security Architecture Through Static Information Flow AnalysisACM SIGARCH Computer Architecture News10.1145/3093337.303773945:1(555-568)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037739
Ge XCui WJaeger T(2017)GRIFFINACM SIGARCH Computer Architecture News10.1145/3093337.303771645:1(585-598)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037716
Holder LCaceres RGleich DRiedy JKhan MChawla NKumar RWu YKlymko CEliassi-Rad TPrakash A(2016)Current and Future Challenges in Mining Large NetworksACM SIGKDD Explorations Newsletter10.1145/2980765.298077018:1(39-45)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1145/2980765.2980770
Samrit SNasre RZeller ARoychoudhury A(2016)EagerMerge: an optimistic technique for efficient points-to analysisProceedings of the 25th International Symposium on Software Testing and Analysis10.1145/2931037.2931045(47-58)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2931037.2931045
Cai FReinanda RRijke M(2016)Diversifying Query Auto-CompletionACM Transactions on Information Systems10.1145/291057934:4(1-33)Online publication date: 9-Jun-2016
https://dl.acm.org/doi/10.1145/2910579
Mahmoud ABradshaw G(2015)Estimating Semantic Relatedness in Source CodeACM Transactions on Software Engineering and Methodology10.1145/282425125:1(1-35)Online publication date: 2-Dec-2015
https://dl.acm.org/doi/10.1145/2824251
Ali KRapoport MLhoták ODolby JTip F(2015)Type-Based Call Graph Construction Algorithms for ScalaACM Transactions on Software Engineering and Methodology10.1145/282423425:1(1-43)Online publication date: 2-Dec-2015
https://dl.acm.org/doi/10.1145/2824234
Chierichetti FKumar R(2015)LSH-Preserving Functions and Their ApplicationsJournal of the ACM10.1145/281681362:5(1-25)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2816813
Ali KRapoport MLhoták ODolby JTip F(2014)Constructing Call Graphs of Scala ProgramsProceedings of the 28th European Conference on ECOOP 2014 --- Object-Oriented Programming - Volume 858610.1007/978-3-662-44202-9_3(54-79)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-662-44202-9_3
Cortesi AFerrara PChaki N(2013)Static analysis techniques for robotics software verificationIEEE ISR 201310.1109/ISR.2013.6739742(1-6)Online publication date: Oct-2013
https://doi.org/10.1109/ISR.2013.6739742
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