US 4,901,222 AGrant
Method and Apparatus for Backing Out of a Software Instruction After Execution Has Begun
Issue Date:1990-02-13
•11 Claims
•5 Drawing Sheets
Abstract
In a data processing system using a virtual memory addressing scheme, certain software instructions call for the virtual address to be stored in a base register. The virtual address stored in the base register is incremented or decremented during the read out cycle of the previous operand to address the next operand. If the operand is not in physical memory, then the contents of the base register is restored to its original value. This invention minimizes the amount of logic required to back out of a software instruction after execution has begun and is faster than checking if all resources are present before any state change is made during the execution of a software instruction.
Metadata
Assignee
- Bull NH Information Systems Inc.
Inventors
- Thomas F. Joyce
- Richard P. Kelly
- Jian-Kuo Shen
Application Information
Application Number:US 0521086
Filing Date:1987-05-19
Priority Date:1987-05-19
Art Unit:232
Classifications
IPC:
G06F 1100G06F 1700
Field of Search:
364200 MS File;900 MS File;300
Patent Drawings (5 sheets)
Description
Background of the Invention
1. Field of the Invention
This invention relates to the data processing field and more particularly to a means for undoing a partially executed software instruction to restore the central processing unit to the state it was in before the start of instruction execution.
2. Description of the Prior Art
In a data processing system using a virtual memory addressing scheme, conditions may arise during the execution of a software instruction in which an operand addressed by the software instruction is not present in physical memory and therefore must be read into physical memory by a software routine. In order to be able to execute the software routine, the execution of the current software instruction must be suspended in a manner which permits it to be restarted once the missing operand is brought into physical memory.
In order to improve the system throughput, the virtual memory address is incremented or decremented immediately after being transferred to virtual memory so that it is available during the next memory cycle. If the operand is not found, then the previous virtual memory address must be recomposed and used when the missing operand is found and stored in physical memory. This would require another register, one storing the original virtual address and the other storing the incremented or decremented virtual address. This would assure an improved throughput at the cost of a large register typically 24 or 32 bits.
Of course one may wait until the operand is read out of physical memory before incrementing or decrementing the virtual address. This approach would also have a detrimental impact on system performance.
Another approach is to perform the UNDO operation exclusively by firmware. This will also have a negative impact on performance.
Summary of the Invention
In a data processing system using a virtual memory addressing scheme, certain software instructions call for the virtual address to be stored in a base register. The virtual address stored in the base register is incremented or decremented during the read out cycle of the previous operand to address the next operand. If the operand is not in physical memory, then the contents of the base register is restored back to its original value.
This is accomplished by storing in a PUSH-POP stack, the low order three bits of the 32 bit virtual address from the base register, an address of the base register which is typically stored in a register file, and a bit indicating whether the contents of the base register was incremented or decremented. Since software instructions may include up to three descriptors, the stack on a first-in-first-out basis can accommodate them in three locations.
If the virtual address does not find the operand, then the contents of the base register must be incremented in the execution of the software instruction which required virtual addresses to be decremented, or must be decremented if the execution of the software address required the virtual address to be incremented.
In most cases all that is required is to transfer the three virtual address bits to the base register. However where there was a carry into, or borrow from, the fourth low order bit position, and where the virtual address was incremented, a binary ONE must be subtracted from the virtual address of which the fourth low order bit is now the low order bit of the remaining virtual address. Assuming the virtual address bits 0 through 31, the low order bits 29, 30 and 31 are stored in the PUSH-POP stack and must be stored back in the base register. The binary ONE is subtracted from the portion of the virtual address specified by bits 0 through 28.
Similarly if the virtual address were decremented and there was a borrow out of the bit 28 position of the virtual address, then binary ONE is added to the portion of the virtual address specified by bits 0 through 28.
The determination of whether or not there was a carry or a borrow from bit 28 is to subtract the original three lower order bits of the virtual address from the incremented or decremented value of the low order three bits. If a carry results then the bits 0 through 28 of the contents of the base register require adjustment for the increment operation. If a carry does not result, then, bits 0 through 28 of the contents of the base register do not require adjustment to the decrement operation. Accordingly, it is one of the objects of this invention to provide an improved apparatus and method for backing out of a software instruction after execution has begun using a minimum of logic.
Brief Description of the Drawings
FIG. 1 shows a block diagram of the logic which accomplishes the UNDO operation.
FIG. 2 shows the format of a typical virtual address software instruction.
FIG. 3 shows the contents of a location in the PUSH-POP stack.
FIG. 4 is a firmware block diagram of the steps of implementing the UNDO operation.
FIG. 5 shows the contents of the various registers of the register file.
Description of the Preferred Embodiment
FIG. 1 shows a block diagram of a portion of a data processing system which executes the UNDO portion of selected instructions, basic operating system instructions, commercial instructions and scientific instructions.
A virtual memory management unit (VMMU) 34, a cache memory 36 and the main memory 50 are all coupled to a 32 bit BP bus 32.
The VMMU 34 translates a virtual address described in the instruction being executed into a physical address of main memory 50. The virtual address includes a ring number, a segment number and a displacement. This locates a process stored in the VMMU 34 and enables the VMMU 34 to send the physical address out on BP bus 32 to main memory 50 and directly from VMMU 34 to cache 36. If the location specified by the physical address does not store the operand, then a VMMU interrupt signal indicating a page or segment fault is applied to a format branch unit 20. The VMMU 34 and cache 36 operations are conventional for the purpose of understanding the invention.
A register file 2 includes sixty four 32 bit registers. A number of program visible registers of register file 2 can be loaded and read by various instructions.
These include seven software visible general word operand registers, R1 through R7 which are 16 bits in length and may operate as general registers, accumulators or index registers; seven software visible 32 bit double word operand registers K1 through K7 which are used as general registers, accumulators or index registers; and seven software visible base registers B1 through B7 which store information for formulating addresses pointing to any instruction, data or arbitrary location in the virtual memory of a process. Also included are a number of other registers.
Register file 2 receives operands from a 32 bit BI bus 30 at an A.sub.i input port and from a shifter 8 at a B.sub.i input port. Operands read from ocations in register file 2 are transferred to a 32 bit A bus 40 from an A.sub.o output port and to a 32 bit B bus 28 from a B.sub.o output port. Each location in register file 2 may be addressed by A.sub.i address signals or B.sub.i address signals. The A.sub.o output port is active during a read operation when a location in register file 2 is addressed by the A.sub.i address signals. Similarly the B.sub.o output ports are active when the location is addressed by the B.sub.i address signals.
A binary arithmetic logic unit (BALU) 4 receives 32 bit operands from A bus 40 and B bus 28 at an A" operand input port and at a B" operand input port respectively. The BALU 4 applies a 32 bit A' operand to the BI bus 30 and a 32 bit B' operand to shifter 8. The BALU 4 performs binary arithmetic and logic operations on the A" and B" operands as specified by miscellaneous RDR signals.
A prefetch unit 18 receives the next instruction from the VMMU 34 or the cache 36 over the BP bus 32 and the DATA IN unit 16. The instruction is assembled and then transferred to the format branch unit 20. There the OP code is decoded and a number of OP code signals FR generated.
A control store (ROS) 38 receives address signals from the format branch unit 20 to read out the contents of ROS 38 locations to allow the system to execute the instruction. The contents of each location is stored in turn in a 104 bit ROS data register 39. Combinations of the 104 output signals identified as RDR signals perform the UNDO operation.
For this invention, the base address in registers B1 through B7 or the index value stored in registers R1 through R7 will be applied to the A" operand input of BALU 4 from A.sub.o output port of the register file 2 via A bus 40. The BALU 4 increments or decrements the base address or the index value and stores the incremented or decremented address or index value back in the same register in register file 2 from which it was read, via the A' operand port of BALU 4, and BI bus 30.
The Q register 6 and the shifter 8 operate in conjunction with the BALU 4 to perform various arithmetic and logic operations including binary multiplication and division under RDR signal control.
A PUSH POP UNDO stack 10 has 3 locations of 8 bits each and first-in-first-out (FIFO) logic pointers which cause the 3 locations to be read out in the same order in which they were written into stack 10. As shown in FIG. 3, the eight bits in each location include the low order 3 bits of the contents of a respective register read from register file 2, one bit indicating if the BALU 4 incremented or decremented the contents of that register, and four bits identifying the register.
If the instruction being executed is a two word or a three word instruction, then two locations or three locations respectively, of stack 10, store the appropriate information. This is particularly important when executing commercial instructions in which a first descriptor locates a first operand, a second descriptor locates a second operand and a third descriptor gives the location in which the result of the operation performed on the first and second descriptors is stored.
The SPLTR signal which represents a number of decoded control bit signals resets the stack 10.
The Q register 6 stores a constant, hexadecimal 7 which is shifted right one bit position when processing each word read from stack 10.
If during the execution of an instruction, the format branch unit 20 receives the interrupt signal from the VMMU 34, indicating that the requested operand is not in the segment or page, then instruction execution is aborted and the UNDO operation initiated.
Description of Operation
The system of FIG. 1 utilizes the load register instruction (LDR) of FIG. 2. The instruction stores the contents of the effective address of main 50, specified by the address syllable bits 9 through 15, in a general word operand R register specified by bits 1 through 3. Bit 0 at binary ONE specifies that the instruction contains an address syllable (AS). Bits 1 through 3 not at binary ZERO specifies a double operand instruction. Bits 4 through 7 specify the high order OP code number as hexadecimal 8. Bit 8 specifies the low order of the OP code number as binary 0.
Bits 9 through 11 of the address syllable at octal 7 indicates that bits 13 through 15 specify the single base register B1 through B7 that store the main memory address of the operand location.
Address signals RFA0 through RFA5 are applied to the register file 2 to read the contents of that location. Signals RFA0, RFA1 and RFA2 are selected RDR signals and signals RFA3 through RFA5 are the equivalent of the LDR instruction bits 13 through 15 (FR signals). The contents of the addressed B register appear on the A bus 40 and are applied to the A" operand port of BALU 4. In the BALU 4 the address is incremented by ONE and stored back into register file 2 at the same location specified by signals RFA0 through RFA5. If at this time the PUSH signal is activated, then the low order three bits, 29, 30 and 31 of the contents of the addressed B register, the low order four bits of A address signals RFA2 through RFA5, and a bit indicating that the contents of the B register was incremented are stored in stack 10. Also during this cycle the contents, of the addressed B register is applied to the VMMU 34 to generate the main memory 50 address. If that addressed location is not in a segment of a page of memory 50 or cache 36, then the execution of the load register instruction is interrupted by a VMMU interrupt signal applied to the format branch unit 20 and the contents of the addressed register is decremented to its original value.
The stack 10 stores the low order 3 bits, bits 29 through 31 (RA) as read from the addressed B registers 1 through 7. The contents of the addressed B register was incremented by binary ONE. Now assuming that the execution of the LDR instruction was interrupted, then a POP operation is required. The contents of the addressed B register must be decremented to the original value. In most cases transferring bits 5 through 7 (RA) from stack 10 and storing them in bit positions 29 through 31 of the addressed B register accomplishes this. However, in case there was a carry into bit position 28 of the addressed B register during the increment operation, then the portion of the address represented by bits 0 through 28 must be decremented.
The LDR instruction results in the addressed B register being incremented. The operation of some instructions calls for the contents of the addressed B register to be decremented. Therefore the UNDO operation would increment the contents of the addressed B register to restore it to its previous value.
The incrementing or decrementing of the addressed B register in register file 2 is accomplished by the firmware described in conjunction with the flow diagram of FIG. 4. FIG. 5 shows the contents of the various working registers.
Block A08 stores a constant, hexadecimal 7 in the Q register 6 forcing bits Q29, Q30 and Q31 to binary ONE. The constant hexadecimal 7 is loaded into Q register 6 via B bus 28, BALU 4 and shifter 8.
Three locations of stack 10 are always read out. After each readout, the contents of Q register 6 is shifted right one position and the low order bit, Q31 tested for binary ZERO to indicate that three locations of stack 10 were read.
Block A09 stores the contents of the first stack 10 location in a working register AW5 in register file 2 in bit positions 0-7 at a location specified by address signals RFA 0-5. This is shown in FIG. 5. Also the contents of Q register 6 is shifted right, one bit position by shifter 8.
Block A02 reads the contents of working register AW5 onto the B bus, through a multiplexer (MUX) 5, BALU 4, shifter 8 and stored back in working register AW5. AW5 shifted bits 0 through 7 into bit positions 24 through 31 of working register AW5 as shown in FIG. 5. In this block working register AW5 was addressed by address signals RFB 0-5 to enable the B port of register file 2. Address signals RFB 0-5 were generated by selected FR and RDR signals.
Block A03 loads a working register AW4 with the RA field. This is accomplished by a logical AND operation of the contents of working register AW5 applied to the A" operand port of BALU 4 and a hexadecimal 7 constant applied to the B" operand port of BALU 4. The result is stored in working register AW4 in register file 2.
Block A04 stores the RFA field of the stack 10 location in the CT2 counter 12 by reading the contents of working register AW5 out of the B port of register file 2, into the B" operand port of BALU 4, shifting the result 4 bit positions right in the shifter 8 and storing the shifted result, RFA into counter 12.
Block A78 performs a logical AND operation on the contents of the addressed B register and hexadecimal 7 and stores the result in working register AW3 in register file 2. The B register is addressed by the contents of the CT2 counter 12 which stores the RFA address. Working register AW3 store B.sub.n X bits 29, 30 and 31, the low order bits of the incremented contents of the addressed B register. The RFA address in counter 12 reads out the contents of the B register into the A" operand port of BALU 4. Hexadecimal 7 is applied to the B" operand port from the B bus 28 and the 3 bit logical AND result is stored in working register AW3.
Block A79 performs a logical AND operation on the contents of the B register addressed by the contents of the counter 12 (RFA) and hexadecimal FFFFFFF8. The result, bits 0 through 28 are stored back in the B register. Bits 29, 30 and 31 are at logical ZERO.
Block A7A stores a hexadecimal 8 in working register AW2 and stores the I and RA fields, bits 28 through 31, from working register AW5 into counter 12.
Block A7B subtracts the contents of working register AW3 (B.sub.n X) from the contents of working register AW4 (RA). Address signals RFA 0-5 addresses location AW3 and the contents applied to the A" operand port of BALU 4. On the same cycle, address signals RFB 0-5 addresses location AW4 and the contents applied to the B" operand port of BALU 4. If B.sub.n X is larger than RA, and this is an increment operation as indicated by bit 4 in counter 12 at logical ONE, then no carry would result.
In block A0D the contents of working register AW5, shifted four bits right is stored in counter 12 and the BALU 4 carry signal applied to the format branch unit 20. Since B.sub.n X is larger than RA, then in block A5E the contents of the B register is OR'd with the contents of working register AW4 and the result stored in the B register which is addressed by the contents of counter 12, RFA.
If in the increment operation, RA were larger than B.sub.n X, this would indicate that there was a carry into the bit 28 position of the addressed B register. Then in block A56 the contents of working register AW2, a hexadecimal 8 is subtracted from the contents of the addressed B register bits 0-28 in BALU 4, and the result is stored back in the addressed B register. (Note that this subtracts binary ONE from bit position 28.)
Then in block A5E, the contents of working register AW4, RA is OR'd with the contents of the addressed B register in BALU 4 and the result, the original memory address, is stored back in the addressed B register.
If in block A7B the "4 bit" in counter 12 indicates a decrement operation, then there would be a carry if B.sub.n X were greater than RA. Therefore, in block A02, the contents of working register AW2 is added to the contents of the addressed register. (Adding binary ONE to bit position 28)
And in block A06 the contents of register AW4, RA is OR'd with the contents of the addressed B register and the result, the original memory address, is stored back in the addressed B register.
Both blocks A06 and A5E test the Q31 bit of the Q register 6. If that bit is a binary ZERO indicating that this is the third entry in stack 10, then block A01 concludes the UNDO operation and the firmware returns to the background mode. Otherwise if Q31 were at binary ONE then the firmware branches to block A09 to continue the UNDO operation.
Note that if this were a three descriptor instruction and both the first and second operands were received from memory, but that the resulting third operand location was not in memory, the instruction would still be aborted and the three base registers storing the locations of the three operands restored to their original states.
While the invention has been shown and described with reference to the preferred embodiment thereof, it will be understood by those skilled in the art that the above and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.
Claims
What is claimed is:
1. In a data processing system for performing operations on operands as specified by instructions, apparatus for initializing execution of instructions whose operation is aborted, said apparatus comprising: control store means for storing sequences of control signals for controlling operation of said system as specified by said instructions, said control store means having address inputs connected to receive said instructions as address inputs and outputs for providing said sequences of control signals and being addressed by said instructions to provide from said outputs a first sequence of said control signals for controlling said execution of said instructions; register file means having address inputs coupled from said control signal outputs of said control store means and data inputs and data outputs for storing and receiving memory addresses of operands and being addressed by said control signal outputs of said first sequence of said control signals for storing and providing a first memory address for a first operand, said first memory address having a first low order portion and a first high order portion; stack means having data inputs coupled to said register file means data outputs and having address inputs connected from said control signal outputs and being addressed by said control signals of said first sequence for storing said first low order portion of said first memory address; memory means having address inputs coupled to said register file means data outputs for receiving said memory address and generating an interrupt signal if said first operand is not stored in said memory means, said interrupt signal indication that said operation of said instruction is aborted, arithmetic means having data inputs connected from said data outputs of said register file means and data outputs connected to said data inputs of said register file means and control input connected from said control signal outputs, said arithmetic means being controlled by said control signals of said first sequence to receive said memory address and increment or decrement said first memory address as controlled by said control signals to generate a a second memory address of a second operand stored in said memory means, said second memory address having a second low order portion and a second high order portion; said register file means being addressed by said control signal outputs of said first sequence of said control signals for storing said second memory address in place of said first memory address; said control store means having an address input connected from said memory means for receiving said interrupt signal and being addressed by interrupt signal for providing a second sequence of control signals; said data inputs of said arithmetic means being further coupled to data outputs of said stack means, said register file means and said stack means being addressed by said control signals of said second sequence to respectively provide said first low order portion and a second order portion from said second memory address to said data inputs of said arithmetic means, and said arithmetic means being controlled by said control signals of said second sequence of control signals to receive said first low order portion and a second low order portion and generate a carry signal if said second low order portion was smaller than said first low order portion; said control store means having an address input connected to receive said carry signal and being addressed by said carry signal to provide a third sequence of control signals, and said register file means being addressed by said third sequence of control signals for replacing said second memory address in said register file means by said first memory address.
2. The apparatus of claim 1 wherein said register file means includes: addressing means for addressing a base register and a plurality of working registers, said base register storing in turn said first memory address and said second memory address.
3. The apparatus of claim 2 wherein said stack means includes: a first-in-first-out stack having a plurality of locations, each of said locations storing said first low order portion, addressing bits specifying a location of said base register and an indicator bit specifying whether said first memory address was incremented or decremented to generate said second memory address.
4. The apparatus of claim 3 wherein said arithmetic means includes: means controlled by said control signal inputs for subtracting said second low order portion from said first low order portion and generating said carry signal having a first state if said first low order portion has a value greater than said second low order portion and having a second state if said first low order portion has a value less than said second low order portion.
5. The apparatus of claim 4 wherein said control store means has address input connected to receive said carry signal and said indicator bit and is addressed by said carry signal in said first state and said indicator bit in a state specifying that said first memory address was incremented to generate said second memory address to provide a segment of said third sequence of control signals, said arithmetic means being controlled by said control signals of said segment of said third sequence of control signals and said base register means being addressed by said control signals of said segment for subtracting a predetermined number from a second high order portion of said second memory address in said base register to genetrate a first high order portion of said first memory address in said base register.
6. The apparatus of claim 5 wherein said stack means and said register file means are addressed by said control signals of said segment of said third sequence of control signals for transferring said first low order portion from said stack means to a low order portion of said base register.
7. The apparatus of claim 4 wherein said control store means is addressed by said carry signal in said second state and by said indicator bit in a state specifying that said first memory address was incremented to generate said second memory address to provide a segment of said third sequence of control signals, said stack means and said register file means being addressed by said control signals of said segment of said third sequence of control signals for transferring said first low order portion to a low order portion of said base register.
8. The apparatus of claim 4 wherein said control store means is addressed by said carry signal in said first state and by said indicator bit in a state specifying that said first memory address was decremented to generate said second memory address to provide a segment of said third sequence of control signals, said stack means and said register file means being addressed by said control signals of said segment of said third sequence of control signals for transferring said first low order portion to a low order portion of said base register.
9. The apparatus of claim 4 wherein said control store means is addressed by said carry signal in said second state and by said indicator bit in a state specifying that said first memory address was decremented to generate said second memory address to provide a segment of said third sequence of control signals, said arithmetic means is controlled by said control signals of said segment of said third sequence of control signals for adding a predetermined number to a second high order portion to generate a first high order portion.
10. The apparatus of claim 9 wherein said stack means and said register file means are addressed by said segment of said third sequence of control signals for transferring said first low order portion to a low order portion of said base register.
11. The apparatus of claim 4 wherein certain of said instructions perform operations on a plurality of operands and wherein each said operand operated on by a said instruction has a corresponding memory address and each memory address has a low order portion and a high order portion, the operation of said initializing apparatus for initializing an instruction whose operations have been aborted is repeated for each operand operated on by a said instruction, wherein for each said operand operated on by a said instruction, said low order portion of said corresponding memory address, said addressing bits specifying a location of said base register, and said indicator bit of each said operand is stored in a corresponding one of said locations in said stack means, and is replaced in a corresponding one of said base register and said working registers of said register file means.