Expression-tree-based algorithms for code compression on embedded RISC architectures

Reducing program size has become an important goal in the design of modern embedded systems targeted to mass production. This problem has driven effor ts aimed at designing processors with shorter instruction formats (e.g., AR M Thumb and MIPS16) or able to execute compressed code (e.g., IBM PowerPC 4 05), This paper proposes three code compression algorithms for embedded RIS C architectures. In all algorithms, the encoded symbols are extracted from program expression trees. The algorithms differ on the granularity of the e ncoded symbol, which are selected from whole trees, parts of trees, or sing le instructions. Dictionary-based decompression engines are proposed for ea ch compression algorithm. Experimental results, based on SPEC CINT95 progra ms running on the MIPS R4000 processor, reveal an average compression ratio of 53.6% (31.545) if the area of the decompression engine is (not) conside red.