Dual state rename recovery using register usage

[0002] 1. Field of the Invention

[0003] This invention relates to computer architecture. In particular, the invention relates to register renaming.

[0004] 2. Description of Related Art

[0005] A processor employing out of order execution may experience data hazards with respect to register operands. A method for handling these hazards is register renaming. In register renaming, the processor implements a set of physical registers. Typically, the number of physical registers is greater than the number of logical registers referenced by instructions. As instructions are issued, physical registers are assigned to the destination register operands of the instructions. A physical register number identifying the assigned physical register is provided for each destination operand. The correspondence between the physical registers and logical registers is kept track of.

[0006] Register renaming presents difficulties when instructions experience branch misprediction or exception conditions. This refers to an error in the execution of instructions which requires subsequent instructions to be discarded and instruction fetch to be started at a different address. Processors may perform branch prediction to speculatively fetch, issue, and execute instructions subsequent to conditional branch instructions. If the prediction is incorrect or the exception is not handle properly, the instructions subsequent to the branch instruction are discarded and instructions are fetched according to execution of the branch instruction. Additional exception conditions may include address translation errors for addresses of memory operands and other architectural or micro-architectural error conditions.

[0007] Because register renaming may have been applied to instructions which are subsequently discarded due to an exception, the mapping of logical registers to physical registers should be recovered to a state consistent with the instruction experiencing the exception.

[0008] Existing techniques for rename recovery include recovery at retirement, use of a re-order buffer, and use of a branch rename table. The recovery at retirement approach transfers all state from a retire table to a speculative rename table. The disadvantages of this approach include penalty for additional time to prepare the retire table because rename recovery cannot be started until the mispredicted branch is retired.

[0009] The re-order buffer approach keeps track of rename information at each unresolved branch. This approach may require a large implementation area, resulting in inefficient use of area. The branch rename table approach stores the rename state at the oldest unresolved branch. This approach is generally not able to accommodate other exception recovery cases and may not offer the best performance speed.

[0010] The features and advantages of the present invention will become apparent from the following detailed description of the present invention in which:

[0011] FIG. 1 is a diagram illustrating a processor in which one embodiment of the invention can be practiced.

[0012] FIG. 2 is a diagram illustrating an update circuit shown in FIG. 1 according to one embodiment of the invention.

[0013] FIG. 3 is a flow chart illustrating a process for a rename recovery according to one embodiment of the invention.

[0014] In the following description, for purposes of explanation, numerous details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that these specific details are not required in order to practice the present invention. In other instances, well-known electrical structures and circuits are shown in block diagram form in order not to obscure the present invention.

[0015] FIG. 1 is a diagram illustrating a processor 100 in which one embodiment of the invention can be practiced. The processor 100 represents a central processing unit of any type of architecture, such as complex instruction set computers (CISC), reduced instruction set computers (RISC), very long instruction word (VLIW), or hybrid architecture. In one embodiment, the processor 100 is compatible with the Intel Architecture (IA) processor, such as the IA-32 and the IA-64. The processor 100 includes a processor core 110, a speculative rename table (SRT) 120, an execution pipeline 130, a re-order buffer 140, an update circuit 170, and a retire rename table (RRT) 180.

[0016] The processor core 110 includes circuits to fetch instructions, decodes, and dispatched instructions 103 for execution. The processor core 110 may also includes other circuits that are not necessary for the understanding of the invention. The processor core 110 generates reference information 102 regarding how and what registers are modified by an instruction. The processor core 110 dispatches the reference information 102 and instructions to the SRT 120, the update circuit 170, and the execution pipeline 130.

[0017] The SRT 120 stores speculative register information for the dispatched instructions 103. The instruction may include the mapping of registers, the registers themselves, or any combination thereof. Examples of mappings include mappings of logical register to physical registers The SRT 120 implements a dual state mechanism for the rename recovery. There are two possible classifications for each register: a frequently modified class and an infrequently modified class. The SRT 120 includes mapping and other information for frequent registers 122 and infrequent registers 124. The frequent registers 122 are frequently modified by instructions 103 dispatched from the processor core 110, and the infrequent registers are infrequently modified by the instructions. The criteria to determine the frequency may be set in advance or dynamically changed according to the dynamic usage of the registers. For examples, the number of registers may be divided into two groups. The register references can be dynamically kept tracked of and a threshold (e.g., the average value) of reference is computed. Registers that have frequency references above this threshold are the frequent registers and those below the threshold are infrequent registers. Other heuristics can be employed to determine the usage frequency. For example, registers used only by micro-code may be chosen as infrequent registers.

[0018] The execution pipeline 130 includes the pipeline stages to execute the instructions 103 as dispatched from the processor core 110. When an instruction execution is complete, the instruction is retired and the instruction information of the retired instruction is stored in the re-order buffer 140.

[0019] The re-order buffer 140 is a buffer that stores micro-ops of the instructions 103, associated memory addresses, and alias registers. The re-order buffer 140 includes a shadow array 150 and an instruction information block 160. The shadow array 150 stores N shadow registers 155_lto 155_N. Each of the shadow registers 155_lto 155_Ncontains a rename state of all frequent registers after a branch instruction. The instruction information block 160 contains information about an instruction including the retirement information. The instruction information block 160 provides information to update the RRT 180. In particular, when a branch instruction is retired, the instruction information block 160 sends out signals to the update circuit 170 for a rename recovery if a copy condition is met, as will be explained later.

[0020] The update circuit 170 updates the SRT 120 according to a selection condition. The update circuit 170 essentially performs the rename recovery on the speculative frequent and infrequent registers 122 and 124, respectively, in the SRT 120. The update circuit 170 receives reference information 102 regarding register references and instruction exception condition from the processor core 110 and the re-order buffer 140.

[0021] The RRT 180 stores retire register information 181 for registers corresponding to instructions that are retired. The retire register information may include the mappings of registers themselves, or any combination thereof. The retire registers 181 corresponding to the frequent and infrequent registers 122 and 124, respectively, in the SRT 120. The retire register information or retire registers 181 contain rename states of the corresponding frequent and infrequent registers 122 and 124, respectively, at instruction retirement.

[0022] The SRT 120, the shadow array 150, the update circuit 170 form a rename recovery circuit to recover rename states of registers at branch misprediction. It is contemplated that the present invention can be used in exception situations other than branch misprediction.

[0023] FIG. 2 is a diagram illustrating the update circuit 170 shown in FIG. 1 according to one embodiment of the invention. The update circuit 170 includes a selector 210, a retire copy circuit 220, and a shadow transfer circuit 230.

[0024] The selector 210 receive the reference information 102 and branch misprediction 101 from the processor core 110. The selector 210 asserts a shadow transfer condition 201 to the shadow transfer circuit 230 and a retire copy condition 202 to the retire copy circuit 220. The shadow transfer condition 201 and retire copy condition 202 may be control signals that trigger a transfer or a copy operation. The selector 210 asserts the shadow transfer condition 201 when a branch misprediction 101 is detected and there is no modification to an infrequent register in the SRT 120 by a non-retiring instruction. The selector 210 asserts the retire copy condition 202 when one of the infrequent registers is modified by a non-retiring instruction and a mispredicted branch instruction 101 is retired. The detection of branch misprediction 110 may be provided by the processor core 110 (FIG. 1), the execution pipeline 130, the re-order buffer 140, or any other appropriate circuit in the processor 100.

[0025] The shadow transfer circuit 230 transfers contents all frequent registers 122 after a branch instruction to the SRT 120 when the shadow transfer condition 201 is asserted. The shadow transfer circuit 230 may include a read circuit to read the contents of the shadow array 150, and a write circuit to write the contents to the corresponding frequent registers in the SRT 120 (FIG. 1). The retire copy circuit 220 copies contents of the retire registers 181 in the RRT 180 to the SRT 120 when the retire copy condition 202 is asserted. The copy of the RRT 180 to the SRT 120 is normally performed as a flash copying process which takes place very fast. The flash copy process essentially transfer contents of all the retire registers 181 in the RRT 180 to the corresponding frequent and infrequent registers 122 and 124, respectively, in the SRT 120.

[0026] In essence, the update circuit 170 needs only to update the frequent registers when the shadow transfer condition 201 is asserted. Since the number of frequent registers is much less than the total number of registers, this process can take place quickly, leading to enhanced performance. In addition, the amount of silicon area to implement the shadow array is also reduced because of reduced number of registers.

[0027] The shadow transfer condition 201 is based on the observation that there is no modification to an infrequent register by a non-retiring instruction when a branch misprediction 101 is detected. This is to undo the effect of a speculative (incorrect) write having occurred to a frequently modified registers. The transfer of the content of a shadow register to the frequent registers 122 (FIG. 1 )in the SRT 120 essentially is to undo this erroneous effect.

[0028] FIG. 3 is a flow chart illustrating a process 300 for a rename recovery according to one embodiment of the invention.

[0029] Upon START, the process 300 stores frequent and infrequent registers in the SRT at instruction dispatch from the processor core (Block 310). Then, the process 300 stores the shadow registers in the shadow array (Block 315). Each of the shadow registers corresponds to a frequent register in the SRT after a branch instruction. Then, the process 300 stores the retire registers in the RRT at instruction retirement (Block 320).

[0030] Next, the process 300 determines if a branch misprediction is detected (Block 330). If no, the process is terminated. Otherwise, the process 300 determines if there is a modification (e.g., a write) to an infrequent register by a non-retiring instruction (Block 335). If no, the process 300 asserts the shadow transfer condition (Block 340). Then, the process 300 transfers the contents of the shadow registers to the frequent registers in the SRT (Block 345) and is then terminated. Otherwise, the process 300 determines if a mispredicted branch instruction is retired (Block 350). If no, the process 300 is terminated. If yes, the process 300 asserts the retire copy condition (Block 360). Then, the process 300 copies the retire registers in the RRT to the SRT (Block 370) and is then terminated.

[0031] While this invention has been described with reference to illustrative embodiments, this description is not intended to be construed in a limiting sense. Various modifications of the illustrative embodiments, as well as other embodiments of the invention, which are apparent to persons skilled in the art to which the invention pertains are deemed to lie within the spirit and scope of the invention.