Method and system for scope-based compression of register and literal encoding in a reduced instruction set computer (RISC)

A compression scheme for program executables that run in a reduced instruction set computer (RISC) architecture such as the PowerPC is disclosed. The method and system utilize scope-based compression for increasing the effectiveness of conventional compression with respect to register and literal encoding. First, discernible patterns are determined by exploiting instruction semantics and conventions that compilers adopt in register and literal usage. Additional conventions may also be set for register usage to facilitate compression. Using this information, separate scopes are created such that in each scope there is a more prevalent usage of a limited set of registers or literal value ranges, or there is an easily discernible pattern of register or literal usage. Each scope then is compressed separately by a conventional compressor. The resulting code is more compact because the small number of registers and literals in each scope makes the encoding sparser than when the compressor operates on the global scope that includes all instructions in a program. Additionally, scope-based compression reveals more frequent patterns within each scope than when considering the entire instruction stream as an opaque stream of bits.