Reference Counting with Frame Limited Reuse (extended version, v2)

The recently introduced Perceus algorithm can automatically insert reference count instructions such that the resulting (cycle-free) program is garbage free: objects are freed at the very moment they can no longer be referenced. An important extension of Perceus is reuse analysis. This optimization pairs objects of known size with fresh allocations of the same size and tries to reuse the object in-place at runtime if it happens to be unique. Current implementations of reuse analysis are fragile with respect to small program transformations, or can cause an arbitrary increase in the peak heap usage. We present a novel drop-guided reuse algorithm that is simpler and more robust than previous approaches. Moreover, we give a novel formalization of the linear resource calculus where we can precisely characterize garbage-free and frame-limited evaluations. On each function call, a frame-limited evaluation may hold on to memory longer if the size is bounded by a constant factor. Using this framework we show that our drop-guided reuse is frame-limited and find that an implementation of our new reuse approach in Koka can provide significant speedups.