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

Article

A Graph-Free Approach to Data-Flow Analysis

Author:

Markus MohnenAuthors Info & Claims

CC '02: Proceedings of the 11th International Conference on Compiler Construction

Pages 46 - 61

Published: 08 April 2002 Publication History

Abstract

For decades, data-flow analysis (DFA) has been done using an iterative algorithm based on graph representations of programs. For a given data-flow problem, this algorithm computes the maximum fixed point (MFP) solution. The edge structure of the graph represents possible control flows in the program. In this paper, we present a new, graph-free algorithm for computing the MFP solution. The experimental implementation of the algorithm was applied to a large set of samples. The experiments clearly show that the memory usage of our algorithm is much better: Our algorithm always reduces the amount of memory and reached improvements upto less than a tenth. In the average case, the reduction is about a third of the memory usage of the classical algorithm. In addition, the experiments showed that the runtimes are almost the same: The average speedup of the classical algorithm is only marginally greater than one.

References

[1]

S. Abramsky and C. Hankin. An Introduction to Abstract Interpretation. In S. Abramsky and C. Hankin, editors, Abstract Interpretation of Declarative Languages , chapter 1, pages 63-102. Ellis Horwood, 1987.

[2]

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

[3]

B. Bokowski and M. Dahm. Byte Code Engineering. In C. H. Cap, editor, Java-Informations-Tage (JIT) , Informatik Aktuell. Springer-Verlag, 1998. See also at http://bcel.sourceforge.net/.

[4]

B. Blanchet. Escape Analysis: Correctness Proof, Implementation and Experimental Results. In Proceedings of the 25th Symposium on Principles of Programming Languages (POPL) . ACM, January 1998.

[5]

B. Blanchet. Escape Analysis for Object Oriented Languages: Application to Java. In Proceedings of the 14th Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA) , volume 34, 10 of ACM SIGPLAN Notices , pages 20-34. ACM, 1999.

[6]

P. Cousot and R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixed Points. In Proceedings of the 4th Symposium on Principles of Programming Languages (POPL) , pages 238-252. ACM, January 1977.

[7]

T. M. Chilimbi, B. Davidson and J. R. Larus. Cache-conscious structure definition. In PLDI'99 {PLD99}, pages 13-24.

[8]

T. M. Chilimbi, M. D. Hill and J. R. Larus. Cache-Conscious Structure Layout. In PLDI'99 {PLD99}, pages 1-12.

[9]

A. Deutsch. On the Complexity of Escape Analysis. In Proceedings of the 24th Symposium on Principles of Programming Languages (POPL) , pages 358-371. ACM, January 1997.

[10]

J. Gosling, B. Joy and G. Steele. The Java Language Specification . The Java Series. Addison Wesley, 1996.

[11]

A. Geser, J. Knoop, G. Lüttgen, O. Rüthing and B. Steffen. Chaotic Fixed Point Iterations. Technical Report MIP-9403, Fakultät für Mathematik und Informatik, University of Passau, 1994.

[12]

J. Knoop, D. Koschützki and B. Steffen. Basic-Block Graphs: Living Dinosaurs? In K. Koskimies, editor, Proceedings of the 7th International Conference on Compiler Construction (CC) , number 1383 in Lecture Notes in Computer Science, pages 65-79. Springer-Verlag, 1998.

[13]

T. Lindholm and F. Yellin. The Java Virtual Machine Specification . The Java Series. Addison Wesley, 1997.

[14]

S. S. Muchnick and N. D. Jones. Program Flow Analysis: Theory and Applications . Prentice-Hall, 1981.

[15]

M. Mohnen. Optimising the Memory Management of Higher-Order Functional Programs. Technical Report AIB-97-13, RWTH Aachen, 1997. PhD Thesis.

[16]

S. S. Muchnick. Advanced Compiler Design and Implementation . Morgan Kaufmann Publishers, 1997.

[17]

Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation (PLDI) , SIGPLAN Notices 34(5). ACM, 1999.

[18]

Standard Performance Evaluation Corporation. SPECjvm98 documentation, Relase 1.01. Online version at http://www.spec.org/osg/jvm98/jvm98/doc/.

Cited By

Artho CBiere A(2019)Subroutine Inlining and Bytecode Abstraction to Simplify Static and Dynamic AnalysisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.02.034141:1(109-128)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.entcs.2005.02.034
Shabalin DOdersky MErdweg SOliveira B(2018)Interflow: interprocedural flow-sensitive type inference and method duplicationProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241660(61-71)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241660
Artho CBiere A(2005)Combined Static and Dynamic AnalysisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.01.018131(3-14)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.entcs.2005.01.018
Show More Cited By

A Graph-Free Approach to Data-Flow Analysis
1. Theory of computation
  1. Semantics and reasoning

Recommendations

Pushdown control-flow analysis for free
POPL '16

Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...
Hybrid approach for data-flow analysis of MPI programs
ICS '13: Proceedings of the 27th international ACM conference on International conference on supercomputing

With the increasing cost of developing robust HPC software, precise data-flow analysis for MPI programs -- the mainstay of HPC programming -- are essential. The knowledge of communication is essential for precise data-flow analysis and the difficulty of ...
Pushdown control-flow analysis for free
POPL '16: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC '02: Proceedings of the 11th International Conference on Compiler Construction

April 2002

343 pages

ISBN:3540433694

Editor:
R. Nigel Horspool

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 April 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Artho CBiere A(2019)Subroutine Inlining and Bytecode Abstraction to Simplify Static and Dynamic AnalysisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.02.034141:1(109-128)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.entcs.2005.02.034
Shabalin DOdersky MErdweg SOliveira B(2018)Interflow: interprocedural flow-sensitive type inference and method duplicationProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241660(61-71)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241660
Artho CBiere A(2005)Combined Static and Dynamic AnalysisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.01.018131(3-14)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.entcs.2005.01.018
Mohnen MWaldron JPower J(2002)An open framework for data-flow analysis in JavaProceedings of the inaugural conference on the Principles and Practice of programming, 2002 and Proceedings of the second workshop on Intermediate representation engineering for virtual machines, 200210.5555/638476.638508(157-161)Online publication date: 13-Jun-2002
https://dl.acm.org/doi/10.5555/638476.638508

View Options

View options

Media

Figures

Other

Tables

View Table of Contents