Instruction-Steam Compression

Abstract

This thesis presents formal elements of instruction-stream compression. We introduce notions of instruction representations, compressors and the general "patternization" function for representations to sequences. We further introduce the Lua-ISC language, an implementation of these elements. Instruction-stream compression algorithms are expressed, independently of the target architecture, in Lua-ISC. The language itself handles instruction decoding and encoding, patternization and compression; programs within it are compact and readable. We perform experiments in instruction representation using Lua-ISC. Our results indicate that the choice of representation and patternization method affect compressor performance, and suggest that current design methodologies may overlook opportunities in lower-level representations. Finally, we discuss four instruction-stream compression algorithms and their expressions in Lua-ISC, two of which are our own. The first exploits inter-program redundancy due to static compilation; the second allows state-based compression techniques to function in a random-access environment by compressing instructions as sets of blocks.