Path-sensitive region analysis for mercury programs

ABSTRACT

Dividing the heap memory of programs into regions is the starting point of region-based memory management. In our existing work of enabling region-based memory management for Mercury, a program analysis was used to distribute data over the regions. An important goal of the analysis is to decide which program variables should end up in the same region. For a popular class of programs, it covetously puts program variables in the same region, while more memory could have been reused if they had been kept in separate ones. In this paper we define a new refined region analysis that is keen to keep program variables in separate regions by taking into account the different execution paths of a procedure. With the more precise, path-sensitive analysis we can reduce the memory footprint for several programs.

REFERENCES

• 1: L. Birkedal, M. Tofte, and M. Vejlstrup. From region inference to von Neumann machines via region representation inference. In Principles of Programming Languages., pages 171--183. ACM Press., 1996.
• 2: F. Henglein, H Makholm, and H. Niss. A direct approach to controlflow sensitive region-based memory management. In Principles and Practice of Declarative Programming., pages 175--186. ACM Press., 2001.
• 3: H. Makholm and K. Sagonas. On enabling the WAM with region support. In Proceedings of the 18th International Conference on Logic Programming. Springer Verlag., 2002.
• 4: Q. Phan and G. Janssens. Static region analysis for Mercury. In Proceedings of the 23rd International Conference on Logic Programming, pages 317--332. Springer, 2007.
• 5: Q. Phan and G. Janssens. Region-based memory management for Mercury programs. Part 1: Region analysis and transformation. Technical Report CW540, Department of Computer Science, Katholieke Universiteit Leuven, 2009.
• 6: Q. Phan, Z. Somogyi, and G. Janssens. Runtime support for regionbased memory management in Mercury. In Proceedings of the 2008 International Symposium on Memory Management, pages 61--70. ACM Press., 2008.
• 7: Z. Somogyi, F. Henderson, and T. Conway. The execution algorithm of Mercury, an efficient purely declarative logic programming language. The Journal of Logic Programming, 29(1-3):17--64, October-December 1996.
• 8: M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation., 132(2):109--176, February 1997.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

General Terms:
Languages, Performance

Keywords:
logic programming, mercury, region analysis, region reuse, region-based memory management