Processor having a RAT state history recovery mechanism

Abstract

A mechanism is provided for allowing a processor to recover from a failure of a predicted path of instructions (e.g., from a mispredicted branch or other event). The mechanism includes a plurality of physical registers, each physical register can store either architectural data or speculative data. The apparatus also includes a primary array to store a mapping from logical registers to physical registers, the primary array storing a speculative state of the processor. The apparatus also includes a buffer coupled to the primary array to store information identifying which physical registers store architectural data and which physical registers store speculative data. According to another embodiment, a history buffer is coupled to the secondary array and stores historical physical register to logical register mappings performed for each of a plurality of instructions part of a predicted path. The secondary array is movable to a particular speculative state based on the mappings stored in the history buffer, such as to a location where a path failure may occur. The secondary array can then be copied to the primary array when a failure is detected in a predicted path of instructions near where the secondary array is located to allow the processor to recover from the predicted path failure.

What is claimed is:  
     
         1 . An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising: 
 a plurality of physical registers, each physical register to store either architectural data or speculative data;    a primary array to store a speculative state of the processor including mappings from logical registers to physical registers; and    a buffer coupled to the primary array to store information identifying which physical registers store architectural data.    
     
     
         2 . A method of allocating registers in a speculative processor comprising the steps of: 
 receiving an instruction;    allocating a physical register for an execution result of the instruction;    storing information in a buffer indicating whether an execution result stored in the allocated physical register is architectural data or speculative data.    
     
     
         3 . An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising: 
 a plurality of physical registers;    a primary array storing a first speculative state of the processor including a mapping from logical registers to physical registers,    a secondary array coupled to the primary array, the secondary array storing a second speculative state including a mapping from logical registers to physical registers, the second speculative state being behind or earlier than the primary speculative state; and    a history buffer coupled to the secondary array and storing historical physical register to logical register mappings performed for each of a plurality of instructions.    
     
     
         4 . The apparatus of  claim 3  wherein the secondary array being movable to a particular speculative state based on the mappings stored in the history buffer, wherein the secondary array can be copied to the primary array when a failure is detected in a predicted path of instructions to allow the processor to recover from the failure in the predicted path.  
     
     
         5 . The apparatus of  claim 3  wherein the history buffer identifies the following information for each instruction: 
 a logical register that is the logical destination for the execution results of the instruction;  
 a new physical register selected from available physical registers and that is allocated as the physical destination for the execution results of the instruction, the new physical register being mapped to the logical register; and  
 an old physical register previously mapped to the logical register.  
 
     
     
         6 . The apparatus of  claim 5  wherein the predicted path failure comprises at least one of the following: 
 a mispredicted branch instruction;  
 an instruction that generated a fault, and  
 an instruction that generated a trap.  
 
     
     
         7 . The apparatus of  claim 3  wherein the primary array includes a pointer to a physical register for each logical register.  
     
     
         8 . The apparatus of  claim 3  wherein the secondary array includes a pointer to a physical register for each logical register.  
     
     
         9 . An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising: 
 a plurality of physical registers;    a primary array storing a mapping from logical registers to physical registers, the primary array storing a current speculative state of the processor;    an allocator allocating an available physical register as the physical destination for storing the execution results of an instruction, the allocated physical register corresponding to a logical register;    a history buffer coupled to the secondary array and storing historical physical register to logical register mappings performed for each of a plurality of instructions of a predicted path;    a secondary array coupled to the primary array and the history buffer, the secondary array storing a secondary speculative state of the processor including a mapping from logical registers to physical registers, the secondary array being movable to any instruction between the point of physical register allocation and retirement based on the history buffer, the secondary array being movable to any location or instruction independent of which instructions have been executed;    wherein the secondary array can be copied to the primary array to allow the processor to recover from the failure in the predicted path.    
     
     
         10 . The apparatus of  claim 9  wherein said secondary array is moved to an estimated location of a next failure in the predicted path, the secondary array being adjusted to a correct state if necessary and then copied into the primary array if a path failure occurs to allow the primary array recover from the path failure to the correct state.  
     
     
         11 . The apparatus of  claim 9  wherein the processor attempts to maintain the secondary array at an estimate of the next mispredicted branch instruction or other instruction which may generate an event that would result in a failure of the subsequent path.  
     
     
         12 . The apparatus of  claim 9  wherein the secondary array comprises a plurality of secondary arrays, at least some of the secondary arrays being located at different locations, one of the secondary arrays being selected and copied into the primary array if predicted path failure occurs to restore the primary array to a correct state.  
     
     
         13 . The apparatus of  claim 11  wherein each of the secondary arrays is located at a different location in the history buffer.  
     
     
         14 . The apparatus of  claim 9  wherein the history buffer includes path information that allows the processor to distinguish between: a) register mappings for any instructions after a path failure which are part of failed or incorrect path which should not be executed, and b) register mappings for instructions after a path failure which are part of a correct path.  
     
     
         15 . The apparatus of  claim 9  wherein the history buffer includes a list of free or available physical registers.  
     
     
         16 . The apparatus of  claim 9  wherein the history buffer comprises one or more pointers to the history buffer, including: 
 an allocation pointer identifying the next available physical register to be allocated for the next instruction;  
 a retirement pointer identifying the entry in the history buffer corresponding to the next instruction to be retired; and  
 a secondary pointer identifying the current location or state of the secondary array.  
 
     
     
         17 . The apparatus of  claim 9  wherein the secondary array comprises a plurality of secondary arrays, each secondary array storing a secondary speculative state of the processor including a mapping from logical registers to physical registers, each of the secondary arrays being movable to any instruction between the point of physical register allocation and retirement based on the history buffer, each of the secondary arrays being movable to any location or instruction independent of which instructions have been executed; 
 wherein one of the secondary arrays can be copied to the primary array to allow the processor to recover from the failure in the predicted path.  
 
     
     
         18 . The apparatus of  claim 17  wherein each of the secondary arrays storing a speculative state at an estimate of where a path failure is likely to occur, the apparatus using branch prediction logic to identify estimates where the path failures are likely to occur.  
     
     
         19 . A method of recovering from a failure in a predicted path in a processor, the processor including a plurality of physical registers and a plurality of logical registers, the method comprising: 
 receiving an instruction;    allocating an available physical register as the physical destination for the instruction, the allocated physical register corresponding to a logical register;    storing in a primary array a current mapping between the logical register and the currently allocated physical register;    storing in a history buffer the logical register, the new allocated physical register corresponding to the logical register, and an old physical register previously corresponding to the logical register;    moving, based on the register mappings stored in the history buffer, a secondary array to a location in the predicted path of instructions where a failure may occur;    detecting whether a path failure occurs near the location of the secondary array;    copying the secondary array to the primary array if a predicted path failure occurs near the location of the secondary array to allow the primary array of the processor to recover from the path failure to a correct state.    
     
     
         20 . The method of  claim 19  wherein said step of moving the secondary array comprises moving, based on the register mappings stored in the history buffer, a secondary array to a next mispredicted branch instruction or other instruction where an event may be generated.  
     
     
         21 . The method of  claim 19  wherein said step of moving the secondary array comprises moving, based on the register mappings stored in the history buffer, a secondary array to a next branch instruction.  
     
     
         22 . The method of  claim 19  wherein said step of moving the secondary array comprises moving, based on the register mappings stored in the history buffer, a secondary array to a location in the predicted path of instructions where a failure may occur, the step of moving being performed independent of which instructions have been executed.  
     
     
         23 . The method of  claim 19  wherein said step of detecting whether a path failure occurs near the location of the secondary array comprises detecting whether a misprecdicted branch or other event occurs at or near the location of the secondary array.  
     
     
         24 . A method of a register alias table recovering from a failure in a predicted path in a processor, the processor including a plurality of physical registers and a plurality of logical registers, the method comprising: 
 using a primary array to store a current speculative state of logical register to physical register mappings;    using a history buffer to store old and new register mappings that allow each of several instructions in a predicted path to be performed or reversed;    using a secondary array to store a secondary speculative state of logical register to physical register mappings at a location in the predicted path where a path failure may occur; and    copying the secondary array to the primary array if a path failure occurs at or near the location where the secondary array is located.    
     
     
         25 . A register file provided in a processor, the register file including an array of the physical registers, the register file to store both temporary or unretired data as well as permanent or retired data, information being stored in the processor to identify whether a physical register in the register file stores temporary or permanent data.  
     
     
         26 . A register renaming processor comprising a unified speculative and committed space.  
     
     
         27 . The register renaming processor of  claim 26  and further comprising: 
 logic to store a plurality of states including a speculative state and at least one shadow state, each of said plurality of states including mappings from logical registers to physical registers in the plurality of registers.  
 
     
     
         28 . An apparatus comprising: 
 a plurality of registers, each one of said plurality of registers to store either architecturally committed data or speculative data;    logic to store a plurality of states including a speculative state and at least one shadow state, each of said plurality of states including mappings from logical registers to physical registers in said plurality of registers.    
     
     
         29 . The apparatus of  claim 28  and further comprising: 
 logic to advance a plurality of pointers, one of said plurality of pointers being an allocation pointer that indicates a primary state that is advanced by speculatively executed instructions, one of said plurality of pointers being a shadow pointer that indicates a shadow state having a lesser degree of speculation that said primary state.  
 
     
     
         30 . The apparatus of  claim 29  and further comprising: speculation recovery logic to copy said shadow state to said primary state to undo at least a portion of completed speculative execution.  
     
     
         31 . The apparatus of  claim 29  wherein said logic to advance said plurality of pointers is capable independently advancing each of said plurality of pointers.  
     
     
         32 . The apparatus of  claim 30  wherein said at least one shadow state comprises a plurality of shadow states, each of said plurality of shadow states reflecting a different degree of speculation that is lesser than said primary state, and wherein said speculation recovery logic is capable of copying any of said plurality of shadow states to said primary state to undo speculative execution.  
     
     
         33 . The apparatus of  claim 28  wherein said logic to store a plurality of states comprises: 
 a primary array to store said speculative state;  
 a secondary array to store said shadow state; and  
 logic to update said primary array upon retirement of an instruction.  
 
     
     
         34 . The apparatus of  claim 33  wherein the logic to update said primary array comprises a history buffer coupled to the secondary array, said history buffer to store historical physical to register to logical register mappings performed for each of a plurality of instructions of a predicted path.