Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-11-20
2001-08-14
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C717S152000
Reexamination Certificate
active
06275984
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the execution of instructions by computer systems and more particularly to delaying indirect register offset resolution in a computer.
2. Description of the Background Art
Implementing an efficient and effective method for the utilization of registers in compilers to generate “good code” (code that is accurate, efficient, and fast) is a significant consideration of system designers and manufacturers. However, the techniques for register utilization in reduced instruction word compilers often produce cumbersome and slow object code.
Compilers are used to translate high-level languages, such as Pascal or C++, into executable object code. Typically, the compiler achieves this translation in a series of phases or passes through the code. First, the compiler translates the high-level language source code into intermediate code (usually, assembler code), which may take one or more passes through the code. The compiler then optimizes the intermediate code into assembler code. The optimization may be accomplished in one or more passes through the code. Finally, the compiler translates the output of the optimization phases into object code that is suitable for execution by the computer system.
In order to reduce the memory requirements for microprocessors, system designers and manufacturers are designing high-speed microprocessors for embedded applications with 16-bit instruction words rather than 32-bit instruction words. For example, the Hitachi-SH microprocessor is such a 16-bit instruction word microprocessor. With reduced instruction words, the offset value in indirect offset addressing is reduced, resulting in a reduced amount of contiguous memory addressable for a given instruction. Indirect offset (or indexed) addressing is an addressing mode incorporated in many microprocessor instruction sets.
In an indirect addressing mode instruction (for example, “mov.l@r4,r8”), the indirectly addressed register (r4) contains the address (effective address) within memory to be operated on. For example, if r4 contains 1024, then the instruction above would move the contents of memory address 1024 into register eight (r8). In an indirect offset (or indexed) addressing mode instruction, an offset value is first added to the contents of the indirectly addressed register to arrive at the effective address before the operation takes place. For example, for the instruction “mov.l@(8,r4),r8” (in which “@(8,r4)” is the indirect offset address reference), the offset value “8” is added to the value found in r4, resulting in the effective address. If r4 contains 1024, the effective address is 1032, and the contents of memory address 1032 is moved into r8.
Typically, indirect offset addressing is an efficient method for referencing fields within large data structures as the offset need only be manipulated to move through the fields. In 32-bit instruction word microprocessor systems, the offset field in the instruction word is usually adequate to access the entire range of addressable memory. However, in reduced instruction word systems, because of the reduced offset, the compiler must load a new value into the indirectly addressed register (r4) for the microprocessor to access the full range of addressable memory.
Typically, reduced instruction word compilers have overcome the problem of a reduced offset by the compiler generating address calculations for each indirect offset register reference during optimization. However, this approach reduces the efficiency of the reduced instruction word system. For example, a typical compiler would translate the out-of-range instruction “mov.l@(8,r4),r8” into three instructions: (1) “mov r4,r5”, (2) “add #8,r5” and (3) “mov.l@r5,r8”. The original instruction requires only one register access whereas the three resulting instructions now require three register accesses. Thus, a single instruction is replaced with three instructions, resulting in cumbersome and slow object code.
Thus, the foregoing problems present significant obstacles to effectively implementing an efficient method for using registers in compilers to generate good code.
SUMMARY OF THE INVENTION
The present invention provides a system and method for delaying indirect register offset resolution in a computer. Initially, a compiler creates an offset register linked list for each general-purpose register in a computer system. Alternatively, any suitable data structure, such as a queue, may be used. In the preferred embodiment, the compiler creates a null list for each general-purpose register. Alternatively, the offset register linked lists may be created when the compiler encounters a first line of compiler intermediate code containing an indirect register instruction.
Next, the compiler retrieves a block of compiler intermediate code from memory that was output from a prior phase of the compiler. Preferably, each block of compiler intermediate code represents a basic block of a high-level programming language program (for example, a loop body).
If the line of compiler intermediate code contains an indirect register instruction, then the compiler creates a linked list entry in the appropriate offset register linked list. The compiler stores the indirect-address offset value of the line of compiler intermediate code into an offset value and stores the address of the line of code into an instruction pointer. The compiler also stores the address of the current linked list entry into a list pointer of the previous linked list entry (the linked list entry created in the offset register linked list in the immediately prior pass through the method steps).
Next, the compiler scans the offset register linked list and extracts as a maximum indirect-address offset value and a minimum indirect-address offset value. The compiler then determines if the difference between the two values is greater than an indirect-address offset range. If the difference is less than the indirect-address offset range, the compiler reads the next line of compiler intermediate code and repeats the steps as described above.
However, if the difference is greater than the indirect-address offset range, the compiler outputs assembler code for the given offset-register linked list. The compiler first outputs an initial line of assembler code. The initial line of assembler code is the instruction “add #minimum indirect-address offset value, rx” in which rx is the general-purpose register of the current offset register linked list (the offset register linked list being traversed).
Next, the compiler retrieves the next linked list entry from the current offset register linked list and determines if the linked list entry retrieved is the out-of-range entry (that is, if the offset value of the retrieved linked list entry causes the difference between the maximum and minimum indirect-address offset values to exceed the indirect-address offset range), or if there are no more linked list entries in the offset register linked list. If the current offset value is not the out-of-range entry, then, the compiler resolves the offset value by subtracting the minimum indirect-address offset value for the offset register linked list from the offset value. The compiler uses the resolved offset value to output the line of assembler code and removes the current linked list entry from the offset register linked list.
If the compiler determines that the current linked list entry is the out-of-range entry or that no more linked list entries remain in the offset register linked list, then the compiler outputs a final line of assembler code. This final line of assembler code is the instruction “add #−minimum indirect-address offset value, rx” which is a reversal of the initial line of assembler code. Thus, the final line of assembler code resets rx to its initial value. The compiler then retrieves the next line of compiler intermediate code and repeats the steps as described above.
If the retrieved line of compile
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Ingberg Todd
Powell Mark R.
Sega of America, Inc.
LandOfFree
System and method for delaying indirect register offset... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for delaying indirect register offset..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for delaying indirect register offset... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444259