Adaptive object code compression

Abstract

Previous object code compression schemes have employed static and semi-adaptive 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 suggestion has arisen due to erroneous claims that decompression at run-time from arbitrary branch targets or from arbitrary instruction cache line boundaries in the code is required since control passes from one part of a program's code to another during execution. This thesis investigates adaptive approaches to code compression which operate at the granularity of a program's basic blocks and cache lines, where the context for compression is determined by an analysis of control flow in the code being compressed.