Code compression techniques using operand field remapping

Abstract

Dictionary-based code compression stores the most frequently used instruction sequences in a dictionary, and replaces the occurrences of these sequences in the program with codewords. The large dictionary size is due mainly to many instruction sequences which are different only in operands, but are otherwise the same. The operand factorisation technique divides the expression tree into tree-pattern (opcode sequence) and operand-pattern (operand sequence) to reduce this redundancy; instruction sequences with the same opcodes but different operands may thus share the same tree-pattern dictionary entry. The paper proposes an operand field remapping method to further reduce dictionary size. The key idea is to explore the relations between the current operand to be compressed with those already compressed. The operand-pattern dictionary is therefore divided into an operand remapping dictionary and an operand list dictionary. Each entry in the operand remapping dictionary indicates whether the operand (register or immediate value) to be compressed is the most used operand, the same as the destination register of the previous instructions, or otherwise. With this remapping technique, the operand dictionary size is greatly reduced. An average 46% compression ratio can be achieved where compression ratio = (dictionary size + compressed code size)/(original program size).