Computer system with logic for writing instruction identifying data into array control lists for precise post-branch recoveries

Having thus described my invention, what I claim as new and desire to secure by Letters Patent is:

1. A register management system for use in a computer having a first number of architected logical registers and provision for executing a stream of instructions following a conditional branch instruction based on a branch direction guess, and provision for determing correctness of said branch direction guess, wherein a plurality of said instructions in said stream comprise a field designating an address of a first one of said logical registers, said register management system comprising:

a register array coupled with said computer system, said register array comprising a second number of physical registers, said second number of physical registers being larger than said first number of logical registers,

a first list, comprising said first number of entries, each of said entries corresponding to one of said logical registers and comprising a field indicative of one of said physical registers,

a second lost comprising said first number of entries,

a third list comprising said second number of entries, each of said entries in said third list corresponding to one of said physical registers and comprising an instruction identification field indicative of one instruction in said stream of instructions, a branch status field indicative of presence of an unresolved branch instructions and a control field indicative of a state of use of one of said physical registers, and

logic means, coupled with said computer, said first list said second list, and said third list, for:

performing assignment of first and second ones of said physical registers to said first one of said logical registers responsive to said state of use, writing first data indicative of said assignments into said first list, and writing data indicative of first and second instructions in said plurality into respective ones of said instruction identification field corresponding to said first and second physical registers;

transferring said first data indicative of said assignments from said first list to said second list responsive to decoding of a conditional branch instruction by said computer, and writing third data indicative occurrence of said conditional branch instruction in said branch status field; and

transferring said first data indicative of said assignments from said second list to said first list responsive to a determination by said computer that said branch direction guess is not correct.

2. A system of claim 1 wherein in said second list is one of a plurality of back-up register assignment lists in said system, and wherein said logic means comprises means for copying the contents of said first list to a different one of said back-up register assignment lists upon decoding of each of a plurality of conditional branch instructions and for copying said contents back into said first list from each of said back-up register assignment lists, and

wherein said third at a comprises a plurality of bits, each of said bits corresponding to one of said back-up register assignment lists and being indicative of occurrence of one of said plurality of conditional branch instructions.

3. A register management system for use in a computer system having a first number of architected logical registers, provision for executing a stream of instructions following a conditional branch instruction based on a branch direction guess, and provision for determining correctness of said branch direction guess, comprising:

a register array coupled with said computer system, said register array comprising a second number of physical registers, said second number of physical registers being larger than said first number of logical registers,

a first list comprising said first number of entries, each of said entries in said first list corresponding to one of said logical registers and comprising a field indicative of one of said physical registers,

a second list comprising said first number of entries, logic means, coupled with said computer system, said first list, and said second list, for copying contents of said first list to said second list responsive to decoding of a conditional branch instruction by said computer system, and for copying back said contents from said second list to said first list responsive to a determination by said computer system that said branch direction guess is not correct.

4. The system of claim 3 wherein said second list is one of a plurality of back-up register assignment lists in said system, and wherein said logic means comprises means for copying the contents of said first list to a different one of said back-up register assignment lists upon decoding of each of a plurality of conditional branch instructions and for copying said contents back into said first list from each of said back-up register assignment lists.

5. A method of managing registers in a computer system having a first number of architected logical registers, a second number, greater than said first number, of physical registers, provision for processing a stream of instructions including a conditional branch instruction, provision for processing ones of said instructions following said conditional branch instruction based on a branch direction guess, and provision for determining whether said branch direction guess was correct, wherein a plurality of said instructions in said stream include a field addressing a first one of said logical registers, comprising the steps of:

decoding a first instruction in said plurality;

responsive to said decoding of said first instruction, performing assignment of a first one of said physical registers to receive data for said first one of said local registers;

storing first data indicative of said assignment of said first one of said physical registers in a first table;

decoding said conditional branch instruction;

responsive to said decoding of said conditional branch instruction, copying said first data indicative of said assignment from said first table into a second table;

after said copying, decoding a second instruction in said plurality;

responsive to said decoding of said second instruction, assigning a second one of said physical registers to receive data for said first one of said logical registers;

storing second data indicative of said assignment of said second one of said physical registers in said first table;

after said decoding of said second instruction, determining if said branch direction guess was correct; and

responsive to a determination by said determining step, that said branch direction guess was not correct, copying said first data back from said second table into said first table.

6. A register management system for use in a computer system having a first number of architected logical registers, provision for processing a stream of instructions following a conditional branch instruction based on a branch direction guess, and provision for determining correctness of the branch direction guess, comprising:

an array of storage elements coupled to the computer system, said array comprising a second number of said storage elements, said second number being larger than said first number of logical registers;

assignment means, coupled to the computer system, for assigning ones of said storage elements to receive data for the logical registers;

maintenance means, coupled to said assignment means, for maintaining information indicative of which of said storage elements is assigned to receive data for which of said logical registers; and,

backup means, coupled to said maintenance means and the computer system, for making a backup copy of said information, responsive to detection of conditional branch instruction by the computer system and for restoring said information to said maintenance means responsive to a determination by the computer system that the branch direction guess was not correct.

7. The register management system of claim 6, wherein said storage elements are physical registers.

8. The register management system of claim 6, wherein said backup means is responsive to decoding of said conditional branch instruction by said computer system.

9. The register management system of claim 6, further comprising availability means for storing data indicative of available ones of said storage elements, said availability means being coupled to said assignment means.

10. The register management system of claim 6, further comprising interrupt means, for detecting an interrupt in said computer system and for restoring said maintenance means to a state existing just prior to said interrupt, said interrupt means being coupled to said computer system and said maintenance means.

11. The register management system of claim 6 wherein said maintenance means comprises a register assignment list having said second number of entries, each of said entries corresponding to a respective one of said storage elements and comprising a field indicative of at least one of said logical registers.

12. The register management system of claim 11 wherein said backup means comprises a backup register assignment list having said first number of entries.

13. The register management system of claim 11 wherein said backup means comprises a plurality of backup register assignment lists, each having said first number of entries.

Description Submit all comments and votes

FIELD OF THE INVENTION

This invention relates to the management of addressable registers in a computer central processor. More particularly, this invention relates to a control system and monitoring system for a register array for processing out-of-sequence instructions and providing a register content restoration process in branch instructions and interrupts. Such a system requires the retention of both the old and new contents of an addressable register while a sequence of instructions is completed. Addressable registers may include but are not limited to general purpose registers and floating point registers. An embodiment of the invention is shown relating to a computer processor conforming to the IBM 370 System architecture having a plurality of physical array registers to serve the function of a fixed number of addressable registers.

BACKGROUND OF THE INVENTION

The design of a typical computer system requires the establishment of a fixed number of addressable registers such as general purpose registers (GPR's) for the programmer to use in designing programs for the machine. Changing the number of architecturally available GPR's once a system is available would require substantial rewriting of programs to make use of the new number of GPR's.

Similarly, the design of computers and computer programs is based on the assumption that computer program instructions are executed by the computer in the order in which they are written and entered into the system. While instructions must logically appear to the computer system to have been executed in sequence, it has been learned in an effort to improve computer performance that some instructions do not have to be physically performed in sequence, provided that certain dependencies do not exist with other instructions. Further, if some instructions are executed out of order, and such an instruction is a branch instruction, where a branch prediction is made to select the instruction sequence, a need to restore the involved register to original values can occur if a wrong branch is predicted. In such a case the system is restored to the point where the branch is taken. The process of executing an instruction out of order efficiently requires that an established or old value be maintained for GPR's affected by the instruction while provision is made to contingently receive new values for the affected GPR's. The contingency is removed and the new value becomes the established value for the GPR's when intervening instructions have completed and branch instructions are resolved.

Large processors have for many years employed overlapping techniques under which multiple instructions are in various states of execution at the same time. Whenever such a technique is employed, it carries with it a need to implement control logic which detects dependencies between instructions and is able to alter the usual overlapped operation so that the results achieved are those described by the "one instruction at a time" architectural model. There are many different forms which overlapping can take, and each one has its own unique set of control problems.

A common form of overlapping is what is called pipelining. Oversimplified, a pipelined machine provides separate hardware for different stages of an instruction's processing. When an instruction finishes its processing at one stage, it moves to the next stage, and the following instruction may move into the stage just vacated. In such a machine, the instructions are kept in sequence with regard to any particular stage of their processing, even though different stages of processing for different instructions are occurring at the same time. In such a processor if the controls detect that a result which has not yet been generated is needed by some other instruction, then the controls must stop part of the pipeline until the result is generated and passed back to where it is needed. Although this control logic can at times be complex, the fact that instructions are kept in sequence in the pipeline is of definite help in keeping the complexity under control.

A more complex form of overlapping occurs if the processor includes separate execution units. Although less common, this technique has also been known and used for many years. Because different instructions have different execution times, and because the inter instruction dependencies will be variable, it is almost inevitable in such a processor that instructions will execute and produce their results in a sequence different from their sequence in the program. Keeping such a processor operating in a logically correct way requires a more complex control mechanism than that for the pipeline organization.

However, multiple execution units in the prior art do not allow precise interruptions to be taken at an arbitrary point. For example, if an instruction creates an overflow condition, by the time this is detected, it is entirely possible that a later instruction in the program is already executed and the result placed in a register or in main storage. This makes it impossible to take an interruption and preserve status of the processor with all prior but no subsequent instructions having executed. In this example, the overflow interrupt will actually be recognized later than it occurred. Other similar situations are possible in the prior art.

The designers of some prior machines chose to handle this situation by allowing all instructions which were in some state of execution to complete their execution as best they could, and then take an "imprecise" interruption which reported that some instruction in the recent past had an overflow condition. This is a reasonable way to handle interruptions for conditions like overflow where the results will be returned to a programmer who will fix a bug or correct the input data and then rerun the program from the beginning. However, it is an unacceptable way to handle interruptions-like page faults where the system program will take some corrective action and then resume execution from the point of interruption.

Applicant is aware of U.S. Pat. No. 4,574,349 assigned to the same assignee as the present invention, in which additional registers are provided to be associated with each GPR and in which register renaming occurs with use of a pointer value. However, this patent does not solve the problem of precise recovery from interrupts or incorrectly guessed branches during out of sequence execution.

An article in the IBM Technical Disclosure Bulletin, entitled "General Purpose Register Extension", August 1981, pages 1404-1405 shows a system for switching between multiple GPR sets to avoid use of storage when switching subroutines. Another article in the IBM Technical Disclosure Bulletin, entitled "Vector-Register Rename Mechanism", June 1982, pages 86-87 shows the use of a dummy register during instruction execution. When execution is complete the register is renamed as the register named by the instruction for receiving results. During execution, the register is transparent and this allows for extra physical registers. However, neither of these articles deals with out-of-sequence instruction execution.

An article in the IBM Technical Disclosure Bulletin, entitled "Use of A Second Set of General Purpose Registers to Allow Changing General-Purpose Registers During Conditional Branch Resolutions", August 1986, pages 991-993 shows a one-for-one matched secondary set of GPRs to hold the original GPR contents during conditional branch resolution and restore the system status if necessary. Conditional mode tags are used with the GPRs to regulate status of the registers or to restore the original contents of the register.

SUMMARY OF THE INVENTION

The present invention provides a register management system for the addressable registers associated with the processor in a computer. The register management system provides for out of sequence execution of instructions and includes mechanisms for precise recovery from a wrong branch prediction or an interrupt where instructions are out of sequence.

The present invention assumes a central processor with an architecture having a fixed number of addressable registers for use by programs. A typical system would, for example, conform to the IBM System/370 architecture and the embodiment shown deals primarily with the GPRs in that architecture.

The present invention provides a register array (RA) having a plurality of registers which is greater than the number of architected registers. The number of registers actually provided may vary, and may be, for example, twice the number of architected registers.

As computer program instructions call for use of an addressable register in the architecture, a register in the RA is assigned to perform the function of the addressable register such as a System/370 GPR. The instruction also receives an Instruction Identifier (IID) number. A circular rotation of IID's may be used. An array control list (ACL) is provided which has an entry for each register in the RA. Each position in the ACL has several status fields relating to the associated register including a field indicating the availability status of the register, the IID assigned to the register and the name of the GPR assigned to the register. For purposes of the system architecture, once a register in the RA is assigned as a GPR it looks to the program the same as a permanent physical register with the same GPR number.

The register management system also includes a Decode Register Assignment List (DRAL) and one or more Back Up Register Assignment Lists (BRAL) associated with the RA and having one position for each GPR. Each position in the DRAL contains the number of the RA position assigned to the associated GPR. As each instruction is decoded, the GPR's it references are looked up in the DRAL to determine what RA positions are assigned to the GPR's referenced by the instruction. As new RA positions are assigned to receive results for GPR's, the DRALs are continuously updated with the new assignments.

There are one or more BRALs associated with the DRAL to freeze and preserve the status of the DRAL at a precise point in the program execution to restore the DRAL to that precise point when necessary. When a conditional branch is encountered, the DRAL at that point is copied into the BRAL. If a second branch is encountered, the DRAL at that point is copied into the second BRAL, if one is provided, or held up if one is not. A third BRAL, or even additional BRAL's may be provided as desired. Each BRAL serves to preserve the system status at a particular fixed time while the system goes forward with processing. The actual number of BRAL's provided is based on the system designers perception of the maximum number of possible situations requiring restoration of an earlier system status that may be in progress at one time. If enough BRAL's are not provided, execution would stop until a condition is resolved.

The ACL and the DRAL work together as instructions are decoded and completed to manage the contents of the RA according to the architected GPR which is the resource recognized by the program. When a new instruction is decoded, the registers which it references are looked up in the DRAL to find out what RA positions are assigned to them. Thereafter, the RA position addresses are used by the execution units rather than the GPR name. After the RA assignment is located in the DRAL, the ACL is accessed to determine the status and that information is forwarded to the execution unit.

When an instruction is completed, its IID is sent by the execution unit to the ACL for a compare with the IID's in the RA. For each RA position which has received a result from the same IID, control tags are changed to represent the completed status.

When a conditional branch is encountered, instructions are decoded in the direction of the guessed branch. As a requirement for completing instructions in sequence, the processor does not issue a completion signal for any instructions in a guessed branch before the branch taken is resolved. The control field in each ACL position is set for each new assigned RA position after the branch guess is taken so that each such assignment may be voided, if necessary.

The branch recovery technique when a branch guess is incorrect has implications for all parts of the processor. What it means for the register management process is that it is necessary to restore the GPR status to what it would have been if instruction decoding had stopped after the branch was reached. This process recognizes that since the branch was decoded, two types of updating to the GPR control status have taken place. One type reflects progress toward completion and actual completion of instructions prior to the branch, the effects of this updating must be retained. The second type of updating reflects the decoding and execution of instructions which follow the branch; this updating must be removed from the GPR status.

Since (except for interruptions) the DRAL is only updated when instructions are decoded and is not affected in any way by their completion, the contents of the DRAL would not have changed if no instructions had been decoded after the branch. Therefore, what is desired for the DRAL is to restore it to its status immediately following the decode of the branch. To accomplish this, the RA assignments revert to the correct status by restoring the appropriate BRAL if there is more than one, into the DRAL. Whenever a conditional branch is decoded, the contents of the DRAL immediately following the decode of the branch is moved to the BRAL. When the branch guess is resolved, the BRAL is either discarded or used to restore the DRAL.

An interruption control is provided to prevent any instructions beyond the point of interruption from completing. An interrupt can call for either the completion or suppression of the instruction that caused it. Prior instructions are allowed to complete to the point allowed by the particular interrupt. At this point the DRAL is in a non-current or irrelevant state because it contains entries which go beyond the interrupt. The ACL however, contains correct information for all RA positions in the assigned state. The ACL positions are cancelled and returned to available status for instructions beyond the interruption. The ACL is then used to provide current status values to the DRAL to recover from the interrupt.

In summary, the register management system of the present invention handles out of order instructions and branch instructions using a RA and a dual function control system. The first part of the control system, the DRAL, manages instructions from the viewpoint of the architectural GPR's. The second part of the control system, the ACL, manages the actual contents of the register array. This way a branch condition or an interrupt can be restored even if instructions are executed out of order.

BRIEF DESCRIPTION OF THE DRAWINGS

FIGS. 1A and 1B are the left and right halves, respectively,