Electrical computers and digital processing systems: processing – Processing control – Specialized instruction processing in support of testing,...
Reexamination Certificate
1999-01-29
2001-05-15
Ellis, Richard L. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Specialized instruction processing in support of testing,...
C712S209000
Reexamination Certificate
active
06233674
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for compressing data in general and in particular to a method and system for compressing executable code. Still more particularly, the present invention relates to a method and system for compressing executable code in the context of a Reduced Instruction Set Computer (RISC) architecture.
2. Description of the Prior Art
Reduced Instruction Set Computer (RISC) architectures simplify hardware implementation and compiler design by making all instructions have the same size and follow a few simple formats. A price to pay for these advantages is the large size of executable code written in these instruction sets. The large code size reduces instruction cache effectiveness on modern processors and utilization of memory resources. It also increases program-loading time when code is shipped over in a network environment or retrieved from a slow mechanical device like a disk.
Currently, network computers, embedded controllers, set-top boxes, hand held devices and the like receive executables over a network or possibly through slow phone links or communication channels. Furthermore, these devices may have very limited memory capacity and when their memory is constrained, large programs may not fit in the available memory to run on the device. Therefore, for devices having RISC processors to be competitive in their segment of the market place, they may require highly efficient code compression that mitigates the disadvantage of large executable sizes. Traditionally, however, it has been difficult to compress executable code for RISC processors.
The difficulty in compressing executable code for RISC processors is partly due to the relatively high frequency of using registers in instruction encoding. A typical RISC architecture such as the International Business Machines' PowerPC processor implements 32 integer and 32 floating point registers. The instruction set encodes these registers using 5-bit codes to express a register number from 0 to 31. This encoding poses problems when compressing an executable for two reasons. First, the encoding is dense since all possible values for a register code are valid, resulting in high entropy encoding that is difficult to compress. Second, compilers for RISC processors use all registers. Therefore all possible register codes may appear uniformly throughout the code, making it difficult for a conventional compressor to find frequent patterns and produce effective compression.
The problem stated above is substantial because register fields occupy a large chunk of the instruction code, and because RISC instruction sets use registers as the primary data operands. An instruction may contain one, two or three register fields consuming between 5 to 15 bits of a 32-bit instruction code. In a typical program, register codes account for 20% to 40% of the total code size.
Compressing literals also poses a similar problem to that of compressing registers. Literals are data constants that appear in an instruction set. For example, literals may specify the values of branch addresses, pointer offsets, and constant data values. Literals complicate compression because they cover a wide range of integers. Combined, registers and literals contribute between 50% to 75% to the size of a typical executable code on a RISC processor.
Therefore there is a need for a method and system to increase the effectiveness of compressing register and literal encodings for RISC processor such as the PowerPC family. The present invention solves these problems in a novel and unique manner, which is not previously known in the art.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for compressing data.
It is another object of the present invention to provide an improved method and system for compressing executable code in the context of a Reduced Instruction Set Computer (RISC) architecture.
It is yet another object of the present invention to provide an improved method and system for compressing executable code in the context of a RISC architecture by creating separate scopes for register and literal encoding for enhancing conventional code compression.
In accordance with a method and system of the present invention, 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 use separate scopes for encoding registers and literals according to the semantics of the instructions. A conventional compressor then treats each scope separately to produce better encoding than if it were to consider the program code as an opaque stream of bits as is common in prior art.
In a one-time step, discernible usage patterns are determined by examining the semantics of instructions and conventions that compilers adopt in using registers and literals. The result of this step is an identification and specification of scopes that should be treated separately during compression. For example, load/store instructions often use the stack pointer as a base address with an offset for loading (storing) data from (into) memory into (from) registers. Thus, by creating a separate scope for the base register in the load/store instructions, the frequency of using the stack pointer within the scope is very high. A traditional compressor then can easily discerns the high pattern of using the stack pointer and produce much more efficient compression than if it were to consider the occurrences of the same register within the general instruction stream. Additional conventions may also be set for register usage to facilitate compression. The compiler could impose these conventions during code generation. For example, the compiler could try to associate certain registers with certain instructions, such that this association would render the encoding unnecessary for these registers. Additionally, such additional conventions could be enforced by a binary rewriting system should the original source of the executable be unavailable for recompilation.
Literals are treated similarly. For example, load/store offsets are found in our implementation to occur more frequently in the range of −64/+64 than in other ranges. By considering a separate scope for the literals that appear in load/store instructions, there is a higher frequency of occurrences of values within the aforementioned data range than if the same literals were to be treated anonymously within the instruction stream as in prior art. Similar treatment is possible for other types of literals.
Once the scopes have been identified and specified, a compressor is built to parse the instructions and indentify the registers and literals belonging to each scope. The compressor then applies different traditional compression algorithms to the different scopes. Since in each scope there is a more prevalent usage of a limited set of registers and/or literals, the traditional compression scheme will be far more effective in producing more compact code than if it were to consider the executable code as an opaque stream of bits.
REFERENCES:
Kirovski, Darko et al.,Procedure Based Program Compression, IEEE, 1997, pp. 204-213.*
Araujo, Guido et al.,Code Compression Based on Operand Factorization, IEEE, 1998, pp. 194-201.*
Okuma, T. et al.,Instruction Encoding Techniques for Area Minimization of Instruction ROM, IEEE, 1998, pp. 125-130.*
Lefurgy, Charles et al.,Improving Code Density Using Compression Techniques, IEEE, 1997, pp. 194-203.*
Tong Lai Yu, “Data Compression for PC Software Distribution,” Software-Practice and Experience, vol. 26(11), pp. 1181-1195, Nov. 1996.
Christopher Fraser et al., “Custom Instruction Sets for Code Compression,” p. 9, Oct. 19, 1995.
Michael Franz et al., “Slim Binaries,” Department of Information and Computer Science, University of California at Irvine, pp. 1-16.
Jens Ernst et al., “Code Compression,” pp. 358-365.
Ellis Richard L.
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
Salys Casimer K.
LandOfFree
Method and system for scope-based compression of register... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for scope-based compression of register..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for scope-based compression of register... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2566475