Treffer: Adaptive object code compression

Previous object code compression schemes have employed static and semiadaptive compression algorithms to reduce the size of instruction memory in embedded systems. The suggestion by a number of researchers that adaptive compression techniques are unlikely to yield satisfactory results for code compression has resulted in virtually no investigation of their application to that domain. This paper presents a new adaptive approach to code compression which operates at the granularity of a program's cache lines, where the context for compression is determined by an analysis of control flow in the code being compressed. We introduce a novel data structure, the compulsory miss tree, that is used to identify a partial order in which compulsory misses will have occurred in an instruction cache whenever a cache miss occurs. This tree is used as a basis for dynamically building and maintaining an LZW dictionary for compression/decompression of individual instruction cache lines. We applied our technique to eight benchmarks taken from the MiBench and MediaBench suites, which were compiled with size optimization and subsequently compacted using a link-time optimizer prior to compression. Results from our experiments demonstrate object code size elimination averaging between 7.7% and 18.3% of the original linked code size, depending on the cache line length under inspection.