Code Compression Based on Operand Factorization

This paper proposes a code compression technique called {\em operand factorization}. The key idea of operand factorization is the separation of program expression trees into sequences of {\em tree patterns} (opcodes) and {\em operand patterns} (registers and immediates). Using operand factorization we show that tree and operand patterns have exponential frequency distributions. A set of experiments is performed to determine the best encoding technique that explores this feature. The experimental results show an average compression ratio of 35$\%$ for SPEC CINT95 programs, when patterns are encoded using Huffman encoding. Another encoding method, that improves the performance of the decompression engine, results in an average compression ratio of 41$\%$. A decompression engine is proposed which assembles tree and operand patterns into uncompressed instruction sequences, using a combination of dictionaries and state machines.

1998