Abstract:
A computer architecture to process load instructions by allowing multiple mappings between logical registers and the same physical register is disclosed. The computer architecture includes a processor having a physical registers. The processor also includes a decoder to decode a load instruction that names a destination logical register. The processor also includes a register allocation table to map the destination logical register to a physical register within the plurality of physical registers. If the load instruction is predicted to collide with a prior load instruction that names a destination logical register, then the register allocation table maps the destination logical register to the physical register allocated to the first load instruction.

Description:
FIELD OF THE INVENTION 
     The present invention relates to executing load instructions within a processor. More particularly, the present invention relates to a method and apparatus for optimizing load memory accesses using load reuse operations. 
     BACKGROUND OF THE INVENTION 
     Most instructions in a computer instruction set operate on several source operands to generate results. The instructions name, either explicitly or through an indirection, the source and destination locations where values are read from or written to. A name may be either a logical, or architectural, register or a location in memory. 
     Instructions involving register operands are faster than those involving memory operands. For some microprocessor architectures, instructions naming memory operands are translated, or decoded, into microinstructions that transfer operand values from memory to logical registers and then perform the decoded computations. The number of logical registers, however, often is limited, and, as a result, compilers should efficiently utilize logical registers to generate efficient code. 
     The number of physical registers available in a microprocessor typically exceeds the number of logical registers, so that register renaming may be utilized to increase performance. In particular, for out-of-order processors, register renaming allows instructions to be executed out of their original program order. Thus, for many out-of-order processors, an instruction is renamed so that logical registers named in the original instruction are renamed to physical registers. 
     Renaming a logical register involves mapping a logical register to a physical register. These mappings are stored in a Register Alias Table (“RAT”). A RAT maintains the latest mapping for each logical register. A RAT is indexed by logical registers, and provides mappings to corresponding physical registers. This activity may be called dependency tracking. 
     FIG. 1 depicts a register renaming and dependency tracking scheme involving three structures: RAT  110 , active list  102 , and free list  104 . For each logical register specified by a renamed instruction, an unused physical register from free list  104  is allocated. RAT  110  is updated with this new allocation. Physical registers are free to be used again, or reclaimed, once they cannot be referenced by instructions in the current instruction window. 
     Based upon the data structures depicted in FIG. 1, one method for register reclaiming is to reclaim a physical register when the instruction that evicted it from RAT  110  retires. Thus, the instruction that created the new allocation to the physical register is retired. As a result, whenever a new allocation updates RAT  110 , the evicted old allocation is pushed into active list  102 . An active list  102  entry is associated with each instruction in the instruction window. When an instruction retires, the physical register of the old allocation recorded in active list  102 , if any, is reclaimed and pushed into free list  104 . The cycle is depicted in FIG.  1 . 
     A scheme known as “result reuse” may be used to optimize the above-discussed process. Result reuse transforms the internal representation of the data-flow graph to significantly increase the level of instruction-level parallelism. Prior to renaming, whenever the result of an instruction is recognized to match the result of another instruction, the same physical register is used for both instructions. This scheme redirects all dependencies on both instructions towards the instruction that dynamically executes first. Result reuse relies on value-identity detectors. The detector outcome can be either safe or speculative. An example of a safe detector outcome is one directed to move instructions. Using value-identity detection, a move instruction can be completely eliminated from the execution stream. In such a case, it is safe to reallocate the physical register holding the source value because, by definition, the source and destination values are identical. An example of a speculative detector outcome is one directed to memory bypassing. Load instructions often collide with older store instructions in the instruction window of a processor. In such cases, the result of the load instruction is identical to the result that was stored in memory by the colliding store instruction. Predicting such value-identities for load instructions makes it possible to bypass memory accesses completely. 
     For any incoming instruction, the value-identity prediction structures may predict the location in the instruction window, or anywhere in the physical register space, of another instruction that produces the same result. In this case, the physical register allocated to this older instruction is retrieved from the instruction window, and reallocated for the incoming instruction. 
     The value identity predictor includes three parts. The first part establishes a potential identity relation between a pair of instructions. The second and third parts record and retrieve this value identity relation into/from the prediction structures. While general methods and structures exist for implementing the second and third parts, the first part typically is still done by an assortment of ad hoc methods for establishing the value identity. 
     Load instructions access memory locations to load data to the physical registers. The loaded data is, in turn, used in computations with the logical registers. The load instruction execution time is greater than accessing the physical registers. As a result, the number of load instructions may be significant in programs written for processor architectures. Therefore, it may be useful to provide for the efficient execution of load instructions with optimized register renaming and reclaiming schemes. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a system for register reallocation as know in the art. 
     FIG. 2 is an out-of-order processor including a system for register allocation constructed according to an embodiment of the present invention. 
     FIG. 3 is a flow diagram of a method according to an embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention may be described by referring to out-of-order processor  200 , depicted in FIG.  2 . Not all functional units of processor  200  are depicted in FIG.  2 . Fetch unit  202  fetches instructions from instruction cache  204  and decode unit  206  decodes these instructions. For a Complex Instruction Set Computer (“CISC”) architecture, decode unit  206  decodes a complex instruction into one or more micro-instructions. Usually, these micro-instructions define a load-store type architecture, so that micro-instructions involving memory operations may be practiced for other architectures, such as Reduced Instruction Set Computer (“RISC”) or Very Large Instruction Word (“VLIW”) architectures. 
     In a RISC architecture, instructions are not decoded into micro-instructions. Because the present invention may be practiced for RISC architectures as well as CISC architectures, no distinction is made between instructions and micro-instructions unless otherwise stated, and simply refer to these as instructions. 
     In FIG. 2, the register renaming functional unit is indicated by renamer unit  208 , where Register Allocation Table (“RAT”)  210  stores current mappings between logical registers and physical registers. The physical registers are indicated by register file  212 , which is coupled to execution units  220 , as described below. Every logical register has a mapping to a physical register in physical register file  212 , where the mapping is stored in RAT  210  as an entry. An entry in RAT  210  is indexed by a logical register and contains a pointer to a physical register in physical register file  212 . Some register in physical register file  212  may be dedicated for integers whereas others may be dedicated for floating point numbers, but for simplicity these distinctions are not indicated in FIG.  2 . 
     During renaming of an instruction, current entries in the RAT provide the required mapping for renaming the source logical register(s) of the instruction, and a new mapping is created for the destination logical register of the instruction. This new mapping evicts the old mapping in the RAT  210  and RAT  210  is updated with the new mapping. 
     Table 1 depicts an example of register renaming. In Table 1, four instructions in original program order are provided in the first column. Renamed instructions are indicated in the second column. Next to each renamed instruction are the current entries in the RAT  210  after instruction renaming. The final column provides the mapping evicted by instruction renaming. For simplicity, only three logical registers, LRa, LRb, and LRc, are considered. A physical register is denoted by PRi where i is an integer. The first entry in Table 1 provides the current state of the RAT  210  before the first listed instruction is renamed. 
     For example, the first instruction LRa+2→LRa (indicating that the immediate 2 is added to the value of the logical register LRa and the result is stored in logical register Lra) is renamed to PR 1 +2→PR 2 , where physical register PR 2  was assumed to be available. For this instruction, a new mapping LRa→PR 2  was created and the old mapping LRa→PR 1  was evicted from RAT  210 . Note that there is a true dependence of the second and fourth instructions upon the first instruction, and a true dependence of the third instruction upon the second instruction. Register renaming, however, has removed the output dependency between the second and fourth instructions, as well as the anti-dependence between the third and fourth instructions, so that the second, third and fourth instructions may be executed out of order provided the execution order follows the various true dependencies. 
     
       
         
               
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                   
                 Renamed 
                   
                 Evicted 
               
               
                 Instruction 
                 Instruction 
                 RAT 
                 Mapping 
               
               
                   
               
             
             
               
                 . . . 
                 . . . 
                 LRa → PR1 
                 . . . 
               
               
                   
                   
                 LRb → PR11 
               
               
                   
                   
                 LRc → PR10 
               
               
                 LRa + 2 → LRa 
                 PR1 + 2 → PR2 
                 LRa → PR2 
                 LRa → PR1 
               
               
                   
                   
                 LRb → PR11 
               
               
                   
                   
                 LRc → PR10 
               
               
                 LRa + 3 → LRb 
                 PR2 + 3 → PR12 
                 LRa → PR2 
                 LRb → PR11 
               
               
                   
                   
                 LRb → PR12 
               
               
                   
                   
                 LRa → PR10 
               
               
                 LRb + 2 → LRc 
                 PR12 + 2 → PR13 
                 LRa → PR2 
                 LRc → PR10 
               
               
                   
                   
                 LRb → PR12 
               
               
                   
                   
                 LRc → PR13 
               
               
                 LRa + 5 → LRb 
                 PR2 + 5 → PR14 
                 LRa → PR2 
                 LRb&gt;PR12 
               
               
                   
                   
                 LRb → PR14 
               
               
                   
                   
                 LRc → PR13 
               
               
                   
               
             
          
         
       
     
     Renamed instructions are placed in instruction window buffer  216 . Entries in instruction window buffer  216  contain the opcode of the renamed instruction, as well as other fields to be described later. For this example, however, the results of instructions are not stored in buffer  216  but reside in physical register file  212 . The ctive list  217  is one of the fields of the instruction window  216 . 
     Instruction window buffer  216  allows for instruction retirement in original program order. By managing the active list  217 , the instruction window buffer  216  is managed as well because of the correlation between the two. In this case the active list is a mapping to the active list field in the instruction window buffer  216 . Buffer  216  is operated as a circular buffer, where a first pointer points to the next instruction to be retired and a second pointer points to the next available entry for a newly decoded instruction. Incrementing the pointers is done in modulo-N arithmetic, where N is the number of available entries in buffer  216 . When an instruction retires, the first pointer is incremented. When a decoded instruction is placed in buffer  216 , the second pointer is incremented. The pointers are incremented by one for each processed instruction. 
     Scheduler  218  schedules instructions to execution units  220  for execution. The scheduling function, for example, may be realized by reservation stations (not shown) implementing a known algorithm. Execution units  220  may retrieve data from or send data to data cache  224  or physical register file  212 , depending upon the instruction to be executed (e.g., read or write operations). 
     In other embodiments of the present invention, the information content contained in the data structures of physical register field  212  and instruction window buffer may be realized by different functional units. For example, a re-order buffer may replace instruction window buffer  216  and physical register file  212 , so that results are stored in the re-order buffer, and in addition, registers in a register file are dedicated as logical registers. For this type of embodiment, the result of an instruction specifying a write to a logical register is written to a logical register upon instruction retirement. 
     Load instructions move the value held in a memory location into a logical register. If it happens that two load instructions in the instruction window access the same memory location, and if there is no intervening store instruction (or snoop) for the same memory location, both load instructions produce the same result. A detection system, such as one known in the art, may be used to predict or ascertain two such load instructions in the code. The result reuse scheme can be applied to eliminate the second load. Performance may be increased because latency of the second load should not be incurred and the load memory traffic to memory is reduced. Embodiments of the present invention speculate on such events to perform result reuse for load instructions from memory. 
     Whenever it is determined or predicted that two loads access the same location with no store to this location in between, load reuse performs result reuse by re-allocating the physical register that has already been allocated to the first load to the second load. Multiple mappings indicates the action where more than one logical register may be mapped to the same physical register. Effectively, such load instructions are performed during the renaming stage. These instructions remain in instruction window buffer  216  ready to be retired. Dependency graphs are collapsed because instruction dependent on such load instructions are made dependent directly on the real producer, such that the dependencies are redirected. There also may be a reduction in the requirement for physical registers, and there may be fewer writes into the register file. 
     Embodiments of the present invention provide a mechanism for mapping more than one logical register to the same physical register, or a many-to-one mapping. These mappings may be facilitated by utilizing a set of counters  222 , where a counter is provided for each physical register in physical register file  212 . The value of a counter indicates whether its associated physical register is free. For simplicity of discussion, we may take a counter value of zero (0) to imply that there are no current mappings to the physical register and that it is free. Embodiments of the present invention, however, are not limited to using counter values of zero (0) to indicate that a physical register is free. 
     Each time a new mapping between a logical register and a physical register is created, the counter associated with that physical register is changed by a first increment. In some embodiments, the first increment is positive, so that the counter is incremented for each new mapping. When a mapping to a physical register is no longer needed, its counter is changed by a second increment, opposite in sign to the first increment. 
     A physical register becomes free again if there are no longer any mappings to it that are needed by in-flight instructions. A counter associated with a physical register is changed by the second increment, such as being decremented, each time an instruction that evicted a mapping to a physical register retires. When a counter reaches a pre-determined value, such as zero (0), then that physical register is free. 
     In some embodiments of the present invention, the active list  217  (which represents fields in instruction window buffer  216 ) has pointer fields for pointing to physical registers. When an instruction placed in instruction window buffer  216  has evicted a mapping in RAT  210 , a pointer field associated with the instruction is set to point to the physical register of the evicted mapping. These pointer fields comprise an active list. A free list may be a queue of pointers pointing to free physical registers. As each instruction retires in instruction window buffer  216 , the counter associated with the physical register recorded in the active list  217  for the retiring instruction is changed by the second increment, such as being decremented. When the counter reaches 0, then the physical register is moved to the free list  214 . 
     In this way, the use of a set of counters  222  ensures that no physical register is lost during the cycle depicted in FIG.  1 . The maximum number of concurrent mappings to a given physical register depends upon the number of bits allocated to its associated counter. Note that there may be more mappings than there are logical registers because the number of instructions in flight may be larger than the number of logical registers. 
     Table 2 provides an example of register re-use for load reuse instructions. In Table 2, two load instructions are provided that access the same memory location without an intervening store or snoop instruction. Table 2 is similar to Table 1, except that an additional column is added to indicate the current state of the physical register counters. 
     The first entry in Table 2 provides the current state of the RAT  210 , and the physical register counters before the first displayed instruction is renamed. In this example, a counter value of zero (0) indicates that its associated physical register is free. Note that initially, physical registers PR 2  and PR 12  are free and available for new mappings because their counter values are zero (0). 
     Next to each renamed instruction is a pointer indicating the physical register named in the evicted mapping. For example, when the first displayed instruction is placed in the instruction window buffer  216 , the pointer field associated with its entry is set to point to physical register PR 1  because the renamed instruction evicted the mapping LRa→PR 1 . Furthermore, because physical register PR 2  now has been allocated in the new mapping LRa→PR 2 , its counter is incremented by one (1). As seen in Table 2, the first displayed instruction loads the value stored at memory address A into logical register LRa. The second displayed instruction loads the same value stored at memory address A into logical register LRb. The third displayed instruction adds the immediate value 2 to the value stored in LRb and stores it in Logical Register LRc. In accordance with an embodiment of the present invention, the second displayed instruction reuses physical register PR 2  so that its destination logical register is mapped to the same physical register mapped by the destination logical register in the first displayed instruction. Execution of the load instruction is performed by the renaming, but the entry in the instruction window buffer  216  is still provided so that the pointer field associated with its entry is set to point to physical register PR 2 . Note that the counter for physical register PR 2  is incremented from one (1) to two (2) as its value was set to one (1) in the previous instruction. The third instruction instead of being dependent on the second instruction is made dependent on the first instruction. As described previously, for some embodiments of the present invention, when an instruction retires, the counter pointed to by its associated pointer is decremented. As a simple example, suppose in Table 2, the instruction window has only the three instructions displayed, and the third displayed instruction is retired. Because the third renamed instruction has a pointer to physical register PR 12 , the counter for physical register PR 12  is decremented from one (1) to zero (0) upon retirement of this instruction, and physical register PR 12  is free to be used again. 
     
       
         
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                   
                 Renamed 
                   
                   
                 Counters 
               
               
                   
                 Instruction 
                   
                 Evicted 
                 after 
               
               
                 Instruction 
                 with pointer 
                 RAT 
                 Mapping 
                 Renaming 
               
               
                   
               
             
             
               
                 . . . 
                 . . . 
                 Lra → PR1 
                 . . . 
                 C 1  = 1 C 11  = 1 
               
               
                   
                   
                 LRb → PR11 
                   
                 C 2  = 0 C 12  = 0 
               
               
                   
                   
                 LRc → PR10 
                   
                 C 10  = 2 
               
               
                 [A] → 
                 [A] → 
                 Lra → PR2 
                 LRa → PR1 
                 C 1  = 1 C 11  = 1 
               
               
                 Lra 
                 PR2;1 
                 LRb → PR11 
                   
                 C 2  = 1 C 12  = 0 
               
               
                   
                   
                 LRc → PR10 
                   
                 C 10  = 2 
               
               
                 [A] → 
                 [A] → 
                 Lra → PR2 
                 LRb → 
                 C 1  = 1 C 11  = 1 
               
               
                 LRb 
                 PR2;11 
                 LRb → PR2 
                 PR11 
                 C 2  = 2 C 12  = 0 
               
               
                   
                   
                 LRc → PR10 
                   
                 C 10  = 2 
               
               
                 LRb + 
                 PR2 + 2 → 
                 Lra → PR2 
                 LRc → 
                 C 1  = 1 C 11  = 1 
               
               
                 2 → LRc 
                 PR12;10 
                 LRb → PR2 
                 PR10 
                 C 2  = 2 C 12  = 1 
               
               
                   
                   
                 LRc → PR12 
                   
                 C 10  = 2 
               
               
                   
               
             
          
         
       
     
     Embodiments of the present invention include a detection mechanism to determine whether two loads access the same location with no store to this location between the two load instructions. A detector may be a value identity detector to determine, or predict, whether two load instructions access the same location. For a given load instruction, embodiments of the present invention may detect, either speculatively or not, before renaming the location in the instruction window of another load that accesses the same memory location. There are various detection mechanisms known in the art that can be modified in accordance with embodiments of the present invention to achieve this result. 
     In one embodiment of a detection system, a distance value may be associated with a second load instruction. This distance value, which is negative in this embodiment, would indicate a number of instructions from the first load instruction to the second load instruction that is from the same memory location. As stated above, the register renaming feature of the present invention may be used when there is no intervening store or snoop instructions between two load instructions from the same memory address. Also, the distance value may indicate where a potential (e.g., predicted) first load instruction meeting this instruction can be found. 
     In the case of a prediction, it is desirable to verify the accuracy of the prediction. To this end, the second load instruction is executed in due course even though its dependent instructions may have been executed already. Upon execution of the second load instruction, the processing logic verifies that the result of the instruction was, in fact, the same as the result of the instruction identified by the prediction. If the verification is successful, no further action need be taken. If the verification indicates that the prediction was wrong, the register renaming should be changed so that a different physical location is assigned. Moreover, all of the instructions dependent on the load will have to be re-executed to reflect the correct load result. It may be seen that accuracy in predictions is of critical importance given the cost of incorrect predictions. An alternative of a verification system is to first compute the address of the second load instruction (it would be unnecessary to access the data cache  224  in this operation). The addresses of the first and second load instructions are then compared to make sure that they are the same and that there are no intervening store or snoop instructions between them to the same address. 
     The detection system may track events in instruction execution to identify unpredicted memory collisions. This may be done by comparing newly-generated addresses for all incoming loads to the addresses of prior load instructions. When a match is found, indicating a memory collision has occurred, the detection system can take note of it. In view of the foregoing, it will be appreciated that some period of “training time” may be required to build up information in the detection system to accurately predict second load instructions that will benefit from the renaming feature of the present invention. 
     Updates of information for making predictions are performed based on the outcomes of the second load operations. The distance value between first and second load instructions with path information enables the overlapping of multiple dynamic instances of the same static load-load pair, thus increasing the predictor&#39;s coverage. This may be a benefit provided by embodiments of the present invention, because overlapping is a frequent behavior, particularly in tight loops. 
     A flow diagram illustrating the execution of load instructions for some embodiments is depicted in FIG.  3 . In block  301  one or more instructions are fetched in a known manner. In block  303 , it is detected whether one of the fetched instructions is a second load instruction from the same memory location. As stated previously, this can be a determinative result or a predicted result. In decision block  305 , it is determined whether there are any intervening store or snoop instructions between the two load instructions that access the same memory location. If there are, then the second load instruction that has recently been fetched will not benefit from the renaming feature of the present invention. Control passes to block  307  where a free physical register is allocated for this load instruction. In block  308 , the RAT is updated and in block  309 , the appropriate counter corresponding to, or assigned to, the allocated physical register is incremented (or decremented if by design choice). If there are no intervening store or snoop instructions to the same memory location between the two load instructions then control passes to block  311  where a physical register corresponding to the first load instruction is reallocated to the second load instruction as well. In block  313 , the RAT is updated and the appropriate counter for the physical register is incremented (or decremented as the case may be). As stated above, when instructions are retired, the appropriate counter needs to be adjusted so that available physical registers can be identified. Also, in the case of prediction, if the prediction is wrong (i.e., the second load instruction is not loading the same value from the common memory location), then a new physical register must be allocated to the second load instructions and the counters adjusted accordingly. 
     Although the present invention has been disclosed in detail, it should be understood that various changes, substitutions, and alterations may be made herein. Moreover, although software and hardware are described to control certain functions, such functions can be performed using either software, hardware or a combination of software and hardware, as is well known in the art. Other examples are readily ascertainable by one skilled in the art and may be made without departing from the spirit and scope of the present invention as defined by the following claims.