  Region-based memory management (RBMM) is a form of compile time memory
management, well-known from the functional programming world. In this paper we
describe our work on implementing RBMM for the logic programming language
Mercury. One interesting point about Mercury is that it is designed with strong
type, mode, and determinism systems. These systems not only provide Mercury
programmers with several direct software engineering benefits, such as
self-documenting code and clear program logic, but also give language
implementors a large amount of information that is useful for program analyses.
In this work, we make use of this information to develop program analyses that
determine the distribution of data into regions and transform Mercury programs
by inserting into them the necessary region operations. We prove the
correctness of our program analyses and transformation. To execute the
annotated programs, we have implemented runtime support that tackles the two
main challenges posed by backtracking. First, backtracking can require regions
removed during forward execution to be "resurrected"; and second, any memory
allocated during a computation that has been backtracked over must be recovered
promptly and without waiting for the regions involved to come to the end of
their life. We describe in detail our solution of both these problems. We study
in detail how our RBMM system performs on a selection of benchmark programs,
including some well-known difficult cases for RBMM. Even with these difficult
cases, our RBMM-enabled Mercury system obtains clearly faster runtimes for 15
out of 18 benchmarks compared to the base Mercury system with its Boehm runtime
garbage collector, with an average runtime speedup of 24%, and an average
reduction in memory requirements of 95%. In fact, our system achieves optimal
memory consumption in some programs.
