Address trace compression through loop detection and reduction

Abstract

This paper introduces a new technique for compressing memory address traces. The technique relies on the simple observation that most programs spend their time executing loops, and therefore the trace will follow the structures of such loops. We adapt classic control flow analysis to detect the loops within an address trace, then analyze them to identify constant and loop-varying memory references. These references are efficiently encoded to reduce the size of the trace, often resulting in an order of magnitude reduction in size compared to the most compact trace format known to date.