Automatic Accurate Live Memory Analysis for Garbage-Collected Languages

ABSTRACT

This paper describes a general approach for automatic and accurate live heap space and live heap space-bound analyses for high-level languages. The approach is based on program analysis and transformations and is fully automatic. The space-bound analysis produces accurate (tight) upper bounds in the presence of partially known input structures. The analyses have been implemented and experimental results confirm their accuracy.

REFERENCES

• 1: P. Altenbernd. On the false path problem in hard real-time programs. In Proceedings of the 8th EuroMicro Workshop on Real-Time Systems, pages 102-107, L'Aquila, June 1996.
• 2: Wei-Ngan Chin , Siau-Cheng Khoo, Calculating sized types, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.62-72, January 22-23, 2000, Boston, Massachusetts, United States
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Karl Crary , Stephnie Weirich, Resource bound certification, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-198, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325716]
• 5: Proceedings of the 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, May 1990.
• 6: Philippe Flajolet , Bruno Salvy , Paul Zimmermann, Automatic average-case analysis of algorithms, Theoretical Computer Science, v.79 n.1, p.37-109, Feb. 21, 1991 [doi>10.1016/0304-3975(91)90145-R]
• 7: Proceedings of the fourth international conference on Functional programming languages and computer architecture, November 1989
• 8: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 9: R. Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Department of Computer Science, Lund University, Sept. 1998.
• 10: John Hughes , Lars Pareto, Recursion and dynamic data-structures in bounded space: towards embedded ML programming, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.70-81, September 27-29, 1999, Paris, France
• 11: John Hughes , Lars Pareto , Amr Sabry, Proving the correctness of reactive systems using sized types, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.410-423, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.240882]
• 12: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• 13: T. P. Jensen , T. Æ Mogensen, A backwards analysis for compile-time garbage collection, Proceedings of the third European symposium on programming on ESOP '90, p.227-239, May 1990, Copenhagen, Denmark
• 14: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 15: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• 16: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 17: Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, May 1999
• 18: Daniel Le Métayer, ACE: an automatic complexity evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.248-266, April 1988 [doi>10.1145/42190.42347]
• 19: Yanhong A. Liu , Gustavo Gomez, Automatic Accurate Time-Bound Analysis for High-Level Languages, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.31-40, June 01, 1998
• 20: Margaret Martonosi , Anoop Gupta , Thomas Anderson, Effectiveness of trace sampling for performance debugging tools, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.248-259, May 10-14, 1993, Santa Clara, California, United States
• 21: Chang Yun Park, Predicting program execution times by analyzing static and dynamic program paths, Real-Time Systems, v.5 n.1, p.31-62, March 1993 [doi>10.1007/BF01088696]
• 22: Patrik Persson, Live memory analysis for garbage collection in embedded systems, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.45-54, May 05-05, 1999, Atlanta, Georgia, United States
• 23: W. Pugh. The Omega Test: A fast and practical integer programming algorithm for dependence analysis. Commun. ACM, 31(8), Aug. 1992.
• 24: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• 25: In Ryu, Issues and challenges in developing embedded software for information appliances and telecommunication terminals, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.104-120, May 05-05, 1999, Atlanta, Georgia, United States
• 26: D. Sands, Complexity analysis for a lazy higher-order language, Proceedings of the third European symposium on programming on ESOP '90, p.361-376, May 1990, Copenhagen, Denmark
• 27: L. Unnikrishnan, S. D. Stoller, and Y. A. Liu. Automatic accurate stack space and heap space analysis for high-level languages. Technical Report 538, Computer Science Dept., Indiana University, Apr. 2000.
• 28: Christian Ferdinand , Reinhard Wilhelm, On Predicting Data Cache Behavior for Real-Time Systems, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.16-30, June 01, 1998
• 29: P. Zimmermann and W. Zimmermann. The automatic complexity analysis of divide-and-conquer algorithms. In Computer and Information Sciences VI. Elsevier, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming

General Terms:
Experimentation, Languages, Performance, Verification