Algorithms for Compile-Time Memory Optimization

The compiler can use control-flow analysis and similar techniques to
determine pairs of source-code objects in P (eg arrays, records) such
that the objects in each pair cannot ``interfere'' with each other at
run-time and, hence, can share memory. The Compile-Time Memory Allocation
problem is to construct a memory allocation for the objects in P such that
the memory usage is minimized and memory regions of objects that do not
``interfere'' at run-time are allowed to overlap.

We propose the first polynomial-time algorithm for this problem with a
performance guarantee as well as a new and simple O(nlog(n)) time
3-approximation for off-line Dynamic Storage Allocation (DSA). The latter
result improves the best previous approximation ratio of 5 for DSA.