Expression-tree-based algorithms for code compression on embeddedRISC architectures

摘要

Reducing program size has become an important goal in the designnof modern embedded systems targeted to mass production. This problem hasndriven efforts aimed at designing processors with shorter instructionnformats (e.g., ARM Thumb and MIPS16) or able to execute compressed coden(e.g., IBM PowerPC 405), This paper proposes three code compressionnalgorithms for embedded RISC architectures. In all algorithms, thenencoded symbols are extracted from program expression trees. Thenalgorithms differ on the granularity of the encoded symbol, which arenselected from whole trees, parts of trees, or single instructions.nDictionary-based decompression engines are proposed for each compressionnalgorithm. Experimental results, based on SPEC CINT95 programs runningnon the MIPS R4000 processor, reveal an average compression ratio ofn53.6% (31.5%) if the area of the decompression engine is (not)nconsidered