1. Field of the Invention
The present invention relates to a method and apparatus of removing unnecessary instructions, and more particularly, to a method and apparatus of removing unnecessary instructions utilized in a computer system.
2. Description of the Related Art
Under the reduced instruction set computer (RISC) structure, all instructions are designed to have the same length and a more simplified format. Therefore, the design rule of the processor and compiler under the reduced instruction set computer structure can be simplified accordingly.
However, in contrast to complicated instruction set computer (CISC) structure, the above-mentioned RISC structure has the disadvantages of more program codes and lower efficiency. Therefore, the program codes of the RISC structure are often compressed to reduce the requirement of the storage space of the memory.
But, the position of the instruction of the compressed program codes is not the same as that of the original program codes. Therefore, the most essential point of the compressing and decompressing technique is to find out the correct position of the instruction from the compressed program codes. To speak more specifically, the compressed program should be decompressed along with the execution flow of the program such that the program can be decompressed into correct program pieces to be executed in the correct time. If the entire program is decompressed before the program is executed, the benefit of decompressing the instruction codes is reduced. On the other hand, if the correct positions of instructions should be directly discovered from the decompressed program codes, the most-widely-used method is to build an index. The index stores the corresponding relationships between the original addresses in instructions in the uncompressed program codes and the addresses in instructions in the compressed program codes.
Therefore, through using the index, the decompressing unit can correctly find out the positions of the instructions and further perform an appropriate decompression operation to generate correct instruction codes. Unfortunately, in order to deal with the above-mentioned index, not only a complicated index circuit is required, but also the cost increases accordingly.
Please note, the above-mentioned program codes compressing technique can be referred to the following papers or patents: “Andrew Wolfe and Alex Chanin, “Executing Compressed Programs on An Embedded RISC Architecture,” in proc. Micro-25: The 25th Annual International Symposium on Microarchitecture, 1992.”, U.S Pat. No. 6,732,256 “Method and apparatus for object code compression and decompression for computer systems”, and U.S Pat. No. 6,892,292 “Apparatus for one-cycle decompression of compressed data and methods of operation thereof.”
Furthermore, there is another well-known instruction code compressing method, which extends the instruction set. This method utilizes an additional extension instruction having a shorter length to replace an original instruction. It can be referred to U.S Pat. No. 6,195,743 “Method and system for compressing reduced instruction set computer (RISC) executable code through instruction set expansion”.
In addition, other references includes U.S Pat. Nos. 6,199,126, 6,233,674, 5,852,741, 5,862,398, 5,878,267, 5,893,143, 6,131,152, 6,216,223, 6,442,680, and 6,859,870, and papers including M. Kozuch and A. Wolfe. “Compression of Embedded System Programs” IEEE International Conference on Computer Design: VLSI in Computers & Processors, 1994, Haris Lekatsas and Wayne Wolf. “Code Compression for Embedded Systems” 35th Design Automation Conference 1998, Charles Lefurgy, Eva Piccininni and Trevor Mudge. “Reducing Code Size with Run-Time Decompression, and NIHAR R. MAHAPATRA, JIANGJIANG LIU, KRISHNAN SUNDARESAN, SRINIVAS DANGETI and BALAKRISHNA V. VENKATRAO. “The Potential of Compression to Improve Memory System Performance, Power Consumption, and Cost”