CW 540

Quan Phan and Gerda Janssens
Region-based memory management for Mercury programs. Part 1: Static analysis and transformation

Abstract

Region-based memory management is a technique to do compile-time memory management based on the idea of dividing the heap memory into different regions such that, at runtime, memory can be reclaimed automatically by destroying regions in their entirety. This report contains a static region analysis for the logic programming language Mercury. We define region points-to graphs, which represent the locations of terms and the sharing among them, to model the partitioning of the memory used by a program into separate regions. The static analysis starts with a region points-to analysis that determines the different regions in the program. We then compute the liveness of the regions by a region liveness analysis.

Finally, a program transformation adds sufficient region annotations to the program for region support. In this report we also give the correctness proofs for the analysis, so that the safety of memory accesses can be guaranteed. The implementation of the runtime support for region-based memory management in the Mercury compiler will be described in a second report.

report.pdf (331K) / mailto: Q. Phan