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

[0002] This application relates to co-pending applications, entitled “METHOD AND SYSTEM FOR COMPRESSING REDUCED INSTRUCTION SET COMPUTER (RISC) EXECUTABLE CODE THROUGH INSTRUCTION SET EXPANSION” U.S. Ser. No. 09/239,260, filed Jan. 29, 1999, “METHOD AND SYSTEM FOR CLUSTERING INSTRUCTIONS WITHIN AN EXECUTABLE CODE FOR COMPRESSION” U.S. Ser. No. 09/239,261, filed Jan. 29, 1999, and “METHOD AND SYSTEM FOR COMPRESSING REDUCED INSTRUCTION SET COMPUTER (RISC) EXECUTABLE CODE” U.S. Ser. No. 09/239,259, filed Jan. 29, 1999, all filed of even date herewith and assigned to the assignee herein named, the subject matter of each of which is incorporated herein by reference.

[0003] 1. Technical Field

[0004] 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.

[0005] 2. Description of the Prior Art

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for compressing data.

[0013] 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.

[0014] 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.

[0015] 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.

[0016] 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.

[0017] 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.

[0018] 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.

[0019] All objects, features, and advantages of the present invention will become apparent in the following detailed description.

[0020] The invention itself, as well as a preferred mode of use, further objects, and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0021] FIG. 1 is a block diagram of a compressor unit in which a preferred embodiment of the present invention may be incorporated; and

[0022] FIG. 2 is a high-level flowchart showing the steps for the compression algorithm in which a preferred embodiment of the present invention may be incorporated.

[0023] Those skilled in the art appreciate that the invention described herein can be implemented in either hardware or software. With reference now to the figures and in particular with reference to FIG. 1, there is depicted a block diagram of a data compressor unit in which a preferred embodiment of the present invention may be incorporated. As shown, compressor unit 52 is coupled to a controller 54 and a random-access memory (RAM) 56. All data structures associated with the combination of the different compression algorithms are maintained within RAM 56. Controller 54 stores in non-volatile memory the specifications for the separate scopes to be used by the compressor unit 52. During operation, compressor unit 52 receives from a data source 58 an uncompressed executable program. After data encoding using the specifications for the separate scopes stored in controller 54 in accordance with the preferred embodiment of the present invention, a compressed executable program is then transmitted to a data sink 60. The data sink could be a storage device or a communication link.

[0024] Following is described, without loss of generality, an illustrated sample specification of separate scopes within the PowerPC instruction set that may be stored in controller 54. This subdivision is in accordance with the present invention and is provided here by way of example, but not of limitation. In the following description, we use the convention of numbering bits as defined in the PowerPC manual book, in which the most significant bit is numbered 0, while the least significant bit is numbered 31.

[0025] Scope 1: First register in load/store instructions, bits 11-15 from within each 32-bit load/store instruction.

[0026] Scope 2: Second, and optionally third register, in load/store instructions, bits 16-20, and possibly bits 21-25 from within each 32-bit load/store instruction.

[0027] Scope 3: First, second and possibly third registers, in fixed point arithmetic and logic instructions, bits 11-15, 16-20, and possibly 21-25 from within each 32-bit fixed point arithmetic and logic instruction.

[0028] Scope 4: First, second, and possibly third floating point registers in floating point arithmetic instructions, bit ranges 11-15, 16-20, and possibly 21-25 from within each 32-bit floating point arithmetic instruction.

[0029] Scope 5: All registers in any instruction containing a register encoding that is not covered by scopes 1 through 4.

[0030] Scope 5: Load/store offset in load/store instructions, bit ranges 16-31 from within each 32-bit load/store instruction.

[0031] Scope 6: Branch offsets in one branch instruction with absolute targets, bits 6-29 from within the branch absolute instruction (only one in the PowerPC architecture) .

[0032] Scope 7: Branch offsets in one branch instruction with relative address target, bits 6-29 from within the branch relative instruction (only one in the PowerPC architecture).

[0033] Scope 8: Branch offsets in conditional branch instructions with absolute targets, bits 16-29 from within each conditional branch 32-bit instruction with absolute addressing.

[0034] Scope 9: Branch offsets in conditional branch instructions with relative address targets, bits 16-29 from within each 32-bit conditional branch instruction with relative addressing.

[0035] Scope 10: Immediate constants in arithmetic and logic fixed point instructions, bits 16-31 from within each 32-bit arithmetic/logic fixed point instruction with an immediate constant.

[0036] Scope 11: Load and store offsets in load/store instructions, bits 16-31 from within each 32-bit load/store instruction.

[0037] These eleven scopes constitute a plausible subdivision of the PowerPC instruction and are provided by way of example, but not of limitation. Other specifications and refinements are possible and would not depart from the spirit and goals of the present invention. Empirical results available from measurements of a preferred embodiment of this invention show that this subdivision is effective.

[0038] Scope 1 covers the first register that is used as base register for load and store instructions. By convention, register R1 is mostly used for this purpose. By limiting the scope to this register, the relative frequency of using register R1 increases within this scope compared to its usage over the entire program. This helps conventional compression produce more compact encoding for register R1 within these instructions.

[0039] Scope 2 covers the remaining registers in a load/store instruction. By convention, there is a tendency to use registers R31 through R24, R0, and R3 through R8 for this purpose, more so than other registers. Again, this scope will reveal more frequent use of these registers, simplifying the job of a subsequent conventional compressor to come up with more compact encoding for this register field.

[0040] Scope 3 covers the registers used for fixed point arithmetic and logic instructions, while Scope 4 covers the those used for floating point arithmetic instructions. The empirical measurements from a preferred embodiment of this invention have shown that compilers tend to treat floating point registers in a different manner from fixed point registers.

[0041] Scope 5 covers all other registers that occur in instructions that are otherwise not covered by Scope 1 through Scope 4. Further refinement of that scope should be straightforward to someone skilled in the art, and depending upon empirical measurements drawn from a particular implementation of the invention described herein. Such a refinement conforms to the spirit and goals of this invention.

[0042] Scope 6 and Scope 7 respectively cover the branch offsets in absolute and relative addressing branch instructions. For absolute address branches, the encoded offsets are always drawn from the addresses of internal program functions, and therefore they tend to cluster around a few specific, although scattered, values. On the other hand, relative address offsets tend to range between the +/−1024 data range. Again, these separations make it easy for a conventional compressor to find the pattern of frequent use.

[0043] Scope 8 and Scope 9 do the same as Scopes 6 and 7, but with conditional instructions.

[0044] Scope 10 covers data literals that appear in arithmetic and logic instructions. Empirical measurements from a preferred embodiment of this invention showed that they tend to cluster around the range of values from −256 to +256 with large frequency.

[0045] Finally, Scope 11 covers data literals that appear as offsets in load/store instructions. These tend to cluster in the +/−64 value range with large frequency. Again, by treating these separately from the other literals, better compression becomes possible.

[0046] In addition to creating separate scopes for compressing registers, a compressor becomes even more effective when it imposes register usage conventions of its own. These conventions create associations between instructions and registers, creating more scopes, or obviating the need for an encoding of the register. The compiler could enforce these conventions, or a binary rewriting system could reallocate the registers for this purpose. For example, registers contain pointer addresses or data variables. A simple convention is to allocate pointer addresses from a certain range of registers and to allocate data variables from a different range. Note that a data variable could be allocated a register from the range of address registers if the range of data variable registers is exhausted, and vice versa. The purpose is not to enforce hard limits or strict usage conventions, but to increase the frequency of register usage for each category so as to increase the frequency of occurrences of particular registers within each category. The resulting code will be more amenable to compression than in the case of a compiler that allocates registers with no regard to compression needs.

[0047] Referring now to FIG. 2, there is a high-level flowchart showing the steps for performing the compression technique by compressor depicted in FIG. 1 as described herein. The compressor receives as input a specification for subdividing the instruction set into scopes as described above (step 142), and an executable program to be compressed (step 144). Then, the compressor initializes a number of Huffman encoder. Such encoders could be implemented as established in the art. Additionally, other encoders could also be used, such as Ziv-Lempel. Huffman encoders, however, enable decompression to start anywhere in the middle of the code, unlike many other traditional methods. If this feature is not necessary, that is, the compressed program is to be decompressed entirely before running, then other traditional encoders could be used as well.

[0048] The number of Huffman encoders to use is equal to the number of scopes supplied in the specifications, and additionally, two more Huffman encoders are needed. The first is used to compress the opcodes of the instructions. These opcodes serve as anchors for the instructions and facilitate decompression, as would be appreciated by those skilled in the art. The second Huffman encoder is used to compress the remaining fields within instructions, that is, those fields that are not part of the opcode or those that are not falling under any scope specification.

[0049] Once input is initialized, as shown in FIG. 2, in step 148, the compressor starts a loop in which it compresses each instruction in the program in order. The loop consists of steps 150, 152 and 154, and continues until there are no more instructions to compress, in which case the compressor stops (step 160).

[0050] To compress each instruction, the compression first starts with compressing the opcode using the corresponding Huffman encoder (step 150). Then, for each register and literal (as applicable) that fall under a scope specification within the instruction, the corresponding Huffman encoder generates the appropriate compressed code in step 152. Finally the remainder of the instruction that has not been compressed thus far is compressed with the corresponding Huffman encoder in step 154.

[0051] By limiting the scope of values that each Huffman encoder has to work on, and by using the opcode as anchors to facilitate decompression, it should be appreciated that each Huffman encoder will find it easier to compress the stream of bits allocated to it. Additionally, the resulting size of the entire program is smaller than if it were to be compressed by a conventional compressor that treated the entire program stream as a string of opaque bits without exploiting the semantics of the instructions to its advantage.

[0052] It is also important to note that although the present invention has been described in the context of a hardware compressor, those skilled in the art will appreciate that the mechanisms of the present invention can be implemented in software and be distributed as a program product in a variety of forms, and that the present invention applies equally regardless of the particular type of signal bearing media utilized to actually carry out the distribution. Examples of signal bearing media include but are not limited to recordable type media such as floppy disks or CD ROMs, and transmission type media such as analog or digital communications links.

[0053] While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.