Abstract:
The present invention provides a system and method for runtime updating of hints in program instructions. The invention also provides for programs of instructions that include hint performance data. Also, the invention provides an instruction cache that modifies hints and writes them back. As runtime hint updates are stored in instructions, the impact of the updates is not limited by the limited memory capacity local to a processor. Also, there is no conflict between hardware and software hints, as they can share a common encoding in the program instructions.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to computers and, more particularly, to computers that execute branch instructions. A major objective of the invention is to enhance performance by improving predictions required for speculative processing, e.g., as used for pre-fetching data and instructions. Related art is discussed below to help explain a problem addressed by the present invention. Related art labeled as “prior art” is admitted prior art; related art not labeled as “prior art” is not admitted prior art. 
     Much of modern progress is associated with the pervasiveness of computers that manipulate data in accordance with programs of instructions. Given a never-ending demand for increased speed, the computer industry has taken pains to minimize delays in processing. In some cases, operations can be performed out of program order so the results are available as soon as they are required. For example, certain instructions and data can be pre-fetched into a cache before their execution is required; when they are called for, they can be accessed quickly from a cache instead more slowly from main memory. Many operations are not fully specified or known until the results of logically preceding operations are known. For example, an address pre-fetch might require determination of the results of a conditional branch instruction that has not yet been executed. In such cases, some speculative pre-processing can be performed advantageously when the outcome of the prerequisite operations can be predicted with sufficient success. 
     In a software approach to prediction, a program can include prediction hints in the instructions themselves. Typically, a compiler program provides these either in response to a programmer&#39;s specifications or in accordance with the program&#39;s analysis of the program structure. For example, a branch instruction can include a field that denotes “this branch is usually (or, alternatively, rarely) taken”. In a hardware approach to prediction, processing results can be tracked and the resulting processing history can be used to predict future results. For example, if a branch instruction has resulted in repeated returns to the beginning of a loop, the processor can pre-fetch the beginning of the loop the next time the branch instruction is encountered. 
     The hardware approach has access to recent runtime data, which is not available at compilation time. On the other hand, the compiler has access to the program as a whole, while the hardware typically has access to only a small portion of a program at a time. In practice, a processor should be able to access prediction results within a processor cycle or two. However, the memory available to store such results within this time requirement is very limited. As programs have grown exponentially over time, the portion of a program that can be represented by stored prediction results is growing smaller. 
     SUMMARY OF THE INVENTION 
     The present invention provides a system and method for runtime updating of hints in program instructions. The invention also provides for programs of instructions that include hint performance data. Also, the invention provides an instruction cache that modifies hints and writes them back. As runtime hint updates are stored in instructions, the impact of the updates is not limited by the limited memory capacity local to a processor. Also, there is no conflict between hardware and software hints, as they can share a common encoding in the program instructions. These and other features and advantages of the invention are apparent from the description of specific embodiments below with reference to the following drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The figures below depict specific embodiments of the invention and are not depictions of the invention itself. 
         FIG. 1  is a block diagram of a first computer system in accordance with the present invention. 
         FIG. 2  is a block diagram of a second computer system in accordance with the present invention. 
         FIG. 3  is a block diagram of a third computer system in accordance with the present invention. 
         FIG. 4  is a flow chart of a method of the invention practiced in the context of the systems of  FIGS. 1-3 . 
     
    
    
     DETAILED DESCRIPTION 
     In accordance with the invention, a computer system AP 1  comprises a processor  101 , memory  103 , and a hint updater  105 . In this embodiment, hint updater  105  includes firmware that translated branch history data into hints to be incorporated in hint-type instructions. 
     Processor  101  includes an execution unit  111 , an address generator  113 , and a prediction-result tracker  115 . Address generator  113  generates addresses for accessing locations in memory holding programs, e.g., a program  117  and data  121 . Execution unit  111  executes instructions fetched from memory  103 . Prediction-result  115  tracks the results of conditional branch instructions. 
     Upon compilation, program  117  includes instructions with branch-prediction hints. For example, program  117  includes direct branch instructions that specify a condition for branching, a branch-target (i.e., branch-to) address, and a three-bit hint value, as indicated for direct branch instruction  121 , shown in  FIG. 1 . The compiler can introduce these hints either as directed by a programmer&#39;s source code or by its own analysis of the program structure. During execution, address generator  113  uses these hints to pre-fetch instructions that are likely to be branch targets in the near future. 
     When a branch instruction is executed, prediction tracker  115  determines whether or not the branch is actually taken. Hint updater  105  uses these branch-determination results to update hint information in program  117  as stored in memory  103 . In system AP 1 , each direct branch instruction has a three-bit branch prediction field indicating seven levels of branch prediction and a “don&#39;t track” indication. This field can be thought of as a counter that is initiated when the program is compiled. Generally, each time a branch is taken, hint updater increments the branch-prediction value up to a maximum; each time the branch is not taken, the updater decrements the branch prediction value down to a minimum. 
     Each direct branch instruction includes a 3-bit branch-prediction field that encodes branch prediction information as shown in the following Table I. 
     
       
         
               
             
               
               
             
           
               
                 TABLE I 
               
             
             
               
                   
               
               
                 Hint encoding 
               
             
          
           
               
                 Count 
                 Meaning 
               
               
                   
               
               
                 011 
                 very likely to branch 
               
               
                 010 
                 moderately likely to branch 
               
               
                 001 
                 somewhat likely to branch 
               
               
                 000 
                 equally likely to branch or not branch 
               
               
                 100 
                 somewhat unlikely to branch 
               
               
                 101 
                 moderately unlikely to branch 
               
               
                 110 
                 very unlikely to branch 
               
               
                 111 
                 do not track branching 
               
               
                   
               
             
          
         
       
     
     At program compilation, the compiler program sets these bits for each direct branch instruction either according to its analysis of the program structure or as directed by the programmer. During program execution, processor  101  generally pre-fetches branch targets when the branch instruction reads “001”, “010” or “011” and does not pre-fetch otherwise. However, for intermediate values such as “100”, “000” and “001”, the pre-fetch algorithm can take into account the availability of time and space required for the fetching. 
     Prediction-result tracker  115  tracks the result of each branch instruction. Hint updater  105  increments up to the maximum value (011 binary, 3 decimal) each time a branch is taken and decrements the hint count down to the minimum value (110 binary, −3 decimal) each time a branch is not taken. It is the copy of an instruction stored in memory  103  that is updated, as opposed to some ephemeral copy in a pipeline or execution unit. The next time the instruction is called, the new hint information guides the branch prediction to determine whether or not to pre-fetch. The exception is that if the field reads “111” (“do not track branching”), no change occurs. 
     In system AP 1 , both the software and hardware approaches to prediction are used. Moreover, the hardware-generated hints are encoded in the “language” of the software-generated hints, so compatibility issues between the approaches are minimized. Since the run-time hints are stored in the program instructions themselves, the storage capacity available for storing the hints can scale with the program size. A run-time result obtained early in program execution can benefit much later executions. Thus, the invention provides the relevancy advantage of the hardware approach to prediction and the capacity advantage of the software approach to prediction with negligible conflict between the approaches. 
     In system AP 1 , hint updater  105  is basically a firmware device that is separate from both processor  101  and memory  103 . Alternatively, a hint updater can be hardware or software; also, it can reside in memory on or on-chip with the processor. In addition to handling direct branch instructions, it can handle pre-fetching for indirect branch instructions (e.g., instructions with addresses that must be calculated), and data. In addition, the predictions are not limited to those that are used for pre-fetching, but can be used, for example, to make speculative calculations on a predicted operand. 
     A second embodiment of the invention in the form of a second computer system AP 2  is shown in  FIG. 2 . System AP 2  includes a processor  201 , memory  203 , a data cache  205 , and an instruction cache  207 . Processor  201  includes an execution unit  211 , an instruction pipeline  213 , an address generator  215 , a prediction-result tracker  217 , and a hint updater  219 . Memory  213  stores a program  221  and data  223 . 
     When processor  201  executes a branch instruction, tracker  217  captures the result including whether or not the branch was taken and, in the case of an indirect branch instruction, e.g.,  231 , the branch-target address. Hint updater  219 , in this case, built into processor  201 , updates a copy of the instruction in instruction cache  207 . In the case of a direct branch instruction, a hint field is incremented or decremented as it is for system AP 1  in  FIG. 1 . In the case of indirect branch instruction, it is an immediately preceding hint-type no-op instruction  233  that is updated. 
     The hint-type no-op instruction  233  specifies a predicted branch-target address, an address offset, and a hint count. The hint count can be set so that branches for the indirect branch instruction are not tracked; in that case, the branch-target address and offset fields are meaningless. A programmer or compiler can set an initial branch-target address, offset, and 3-bit hint count. During execution, hint updater  219  increments (up to a maximum) the counter when a branch is taken to a predicted branch-target address and decrements (down to a minimum) when the branch is not taken or is taken to an address that is not predicted. If the programmer or compiler does not provide an initial address and offset, the hint count can set to zero or to a negative number. 
     Hint updater  219  works with instructions that use the same branch-target address repeatedly and with instructions for which successive branch-target addresses form an arithmetic series. In the former case, the offset value is zero; in the later case, the offset value is the difference in bytes between successive addresses. If the difference in bytes exceeds the eight-bit coding range for the offset value, the possible existence of an arithmetic series is ignored. This algorithm is further explained by example below. 
     In an example with an indirect branch instruction in which tracking is enabled but the hint count is zero, a branch upon execution results in the hint count in a hint-type no-op instruction being incremented to one. The captured branch-target address is written in the branch-target (“branch-to) address field of the hint-type no-op. The offset is set or maintained at zero. These changes are made to the copy of the hint-type instruction in instruction cache  207 . The updated instruction is written back to program memory according to a write-back strategy if the copy in cache is to be invalidated or replaced. Note that instruction cache  207  differs from conventional instruction caches in providing for write-back. In an alternative embodiment, the hint updater copies the updated instruction to a data cache so that the data cache handles the write back. 
     An initialized hint-type no-op specifies no branch-target address, the offset value is meaningless, and the hint count is zero. Upon first execution of the associated indirect branch instruction, if the branch is not taken, the hint count is decremented to a value of negative one. If a branch is taken, the branch-target address is entered in the branch-target address field, the offset value is set to zero, and the hint count is set to one. The following discussion assumes a branch has been taken. 
     When the hint instruction is next executed, the indicated branch-target address is fetched if it is not already represented in the instruction cache. If, when the corresponding branch instruction is executed, it is determined that the instruction does not take the branch, the counter is decremented, in this case to zero. If a branch is taken to the predicted address, the hint count is incremented. If a branch is taken to a different address, the new branch-target address replaces the former one in the branch-target field of the hint-type no-op instruction. If the new address is within 128 bytes of the former address, an eight-bit offset value is entered that reflects the displacement and the hint count is incremented, in this case to two. If the new address is outside the 8-bit offset range, zero offset is retained and the hint count is decremented. 
     In the case of an instruction with a specified branch-target address and a non-zero offset and hint count, the specified predicted address is the sum of most recently taken branch-target address plus the offset. If this branch is taken, a new address (the old address plus the offset) replaces the former address, the offset is maintained, and the hint count is incremented up to a maximum value of 3. If the previously taken branch-target address (as identified by the predicted address less the offset) is taken, it overwrites the previously predicted branch-target address and the hint count is set to two and the offset is set to zero. If a new address for which an 8-bit offset can be specified is the branch-target address, this is entered as the new branch-target address, the newly determined offset is entered, and the count is set to two. If an out of range branch occurs, the new address, zero offset and count of one are entered. Whenever a branch is not taken, the hint count is decremented down to a minimum of −3. If it is decremented to zero or below (down to negative three), the specified branch-target address is not pre-fetched. 
     System AP 2  also provides for pre-fetching data. A data pre-fetch hint instruction  235  specifies a pre-fetch address, an offset, a history, and a decision. The pre-fetch address and offset work like the branch-target address and offset for instruction  233 . However, instead of a hint count, data pre-fetch instruction  235  has a history field and a decision field. This history field is effectively a 24-bit shift register is which each bit value corresponds to a result of the prediction. The decision field includes a decision bit indicating whether the prediction should be followed or not. A characteristic of the extended raw history over the count is that the former is more resistant to temporary failures of a prediction. The presence of the decision bit relieves the processor of the actual pre-fetch decision, while the history preserves information for the hint updater to use in setting the decision bit. 
     
       
         
               
             
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 Instructions Used by System AP2 
               
             
          
           
               
                 Instruction 
                   
               
               
                 [parameters] 
                 Comments 
               
               
                   
               
               
                 Branch-D 
                 Direct branch instruction 
               
               
                 [condition, branch-target 
               
               
                 address, branch prediction (3- 
               
               
                 bit)]. 
               
               
                 Branch-I 
                 Indirect branch instruction (hint 
               
               
                 [condition, pointer location]. 
                 is in separate instruction, see 
               
               
                   
                 next instruction). 
               
               
                 Hint-type NOP 
                 Applies to next indirect branch 
               
               
                 [Branch-target address, address 
                 instruction in program order. 
               
               
                 offset, and hint count (3-bits).] 
               
               
                 Data Pre-fetch 
                 Applies upon execution, not 
               
               
                 [pre-fetch address, offset, 
                 necessarily tied to a particular 
               
               
                 history, decision] 
                 load instruction. 
               
               
                   
               
             
          
         
       
     
     In systems AP 1  and AP 2 , branch history is represented in the instructions themselves. The storage demands on the prediction-result tracker and the hint updater are minimal. Thus, these embodiments combine the advantages execution-time branch tracking for a program as a whole, rather only for that part that can be managed locally. 
     In a third illustrated embodiment of the invention, the prediction history is not limited to data that can be represented in the instructions themselves. Computer system AP 3  comprises a processor  301 , memory  303 , an instruction cache  305 , and a data cache  307 . Processor  301  includes an execution unit  311 , an instruction pipeline  313 , an address generator  315 , and a prediction tracker  317 . Memory  303  stores an application program  321 , data  323 , and operating system  325 , prediction history data  327 , and a hint-updater program  329 . 
     In system AP 3 , prediction tracker  317  stores prediction results as branch history data  327  in memory  303 . The prediction can be whether or not certain data or instructions are actually required, whether or not the result of a calculation was predicted accurately, or whether or not some other predicted action or event occurred. An operating system  325  periodically interrupts application program  321  with hints and launches hint-updater program  329 . Hint-updater program  329  analyzes branch history data  327  and determines the changes that need to be made to the hints in application program  321 . The instructions needing changing are copied from instruction cache  305  to data cache  307 , and then modified in data cache  307 . The hint-modified cache copies of instructions can be written back to main memory according to the same rules applied to other data in data cache  307 . Once the changes have been effected, operating system  335  resumes application program  331 . 
     Systems AP 1 , AP 2 , and AP 3  ( FIGS. 1-3 ) all use program instructions for storing prediction history data in some form or other. This greatly expands the storage space available for prediction history relative to systems that are limited to on-processor storage. In many cases, these embodiments just make better use of instructions, e.g., no-op instructions, and do not require any expansion of program code. On the other hand, the amount of history data that can be stored in instructions without expanding the program (potentially reducing performance) is limited. System AP 3  overcomes this limitation by allowing for prediction history data to be stored in memory but outside the program. This allows more a more detailed history to be maintained. 
     In particular, system AP 3  more readily provides for more generalized hint-type instructions, such as prediction hint instruction  341 . The parameters are a prediction, an action to be taken if the prediction is correct (and perhaps an action if the prediction fails), prediction history data, and a decision. The prediction history data can be expanded each representing a prediction result. This allows more precise statistics and also allows for patterns to be identified; both of these factors can lead to better predictions. The better prediction can be encoded as a single decision bit-either the prediction is true or false. Note that the history data can actually be stored in branch history  327 , and the history field need only point to the location in which that history data is stored. In this case, the amount of history data is not constrained by the instruction width. 
     Note that parallel processing can be used to avoid the suspension of program  321  when updater  329  is running. For example, an auxiliary processor on the same integrated circuit as processor  301  can run updater  329 . Alternatively, another processor in a symmetric or asymmetric multiprocessor system can run updater  329  while program  321  is running. 
     In an alternative embodiment, prediction history can be stored elsewhere, e.g., “on-chip” with the processor. For data not being used to affect instructions as they are being executed, extremely fast access times are not required. Therefore, the memory for prediction history can be larger (as it need not be fast and need not be very close to the execution unit). This alternative avoids some of the memory accesses required by system AP 3 . 
     A method embodiment of the invention is flow-charted in  FIG. 4 . Variations of method M 1  can be practiced in the contexts of systems AP 1 , AP 2 , and AP 3  (of  FIGS. 1-3 ). Step S 1  involves including prediction hints in program instructions. The programmer(s) and/or compiler program are the likely sources of pre-runtime hints. In the case of branch instructions, the hints can include indications of which branches are likely to be taken and, (in the case of indirect branch instructions), which addresses are likely to be branch targets. In addition, offset values can be provided for indirect branch targets and data addresses that progress in an arithmetic fashion. Depending on the instruction format, the hints can be included in the branch instructions or other instructions to which the hints relate; in other cases, they can occur in hint-type no-op instructions that precede the subject instruction either immediately or otherwise. 
     Program execution begins with step S 2 . As the program is executing, prediction results are tracked at step S 3 . The prediction results specify whether or not a prediction is validated and, can provide a value, e.g., a branch target address for an indirect branch instruction. In systems AP 1  and AP 2  the tracking is a hardware only operation. In system AP 3 , step S 3  also involves storing a prediction history in main memory. 
     Hints are updated at step S 4 . The “hint updater” can be part of the processor (as in system AP 2 ), a program in memory (as in system AP 3 ), or hardware or firmware separate from both, as in system AP 1 . An important distinction from other approaches is that the modification is to the instructions in their stored form—not just en route in an instruction pipeline or in an execution unit. The hint update results in an instruction that can be called again and handled differently because of coding in the program instructions themselves. The hints can be inserted into a subject instruction or into some other instruction designed to hint the subject instruction. 
     In step S 4 , the changes can be made in main memory as they are in system AP 1 , in a cache only, or in both, or in a cache that is written back to main memory (as in systems AP 2  and AP 3 ). In the latter case, substeps S 4 A and S 4 B can be distinguished: step  4 A involves updating instructions in cache, while step S 4 B involves writing back updated instructions to main memory. The invention also provides for updating instructions in the cache and not writing back to main memory. In the case of system AP 2 , the cache size limits the amount of program code that can benefit from updating; however, in system AP 3 , branch results are stored in memory, so the memory space available to history data is generally much greater. 
     Herein two instructions are not the “same” if they occupy different positions in a program, even if the instructions are otherwise identical. For two execution instances of an instruction to involve the same instruction implies that both instances are based on the same instruction at the same position in the program. 
     At step S 5 , updated hint instructions are fetched (from cache or main memory) for execution at step S 6 . The instructions have been modified in a manner that will not affect substantive results, but actions based on the predictions can be affected at step S 7 . 
     The invention provides for generating hints “runtime”, which means during execution of a program or an interruption thereof. The hints can be decisions (e.g., “pre-fetch the branch target”) or factors (e.g., historical data) that can contribute to a decision to perform an action before it is known that the action will be required (or, in other words, before it is known that prerequisites for the action will be met). For example, a “pre-fetch hint” is a hint where the action is to fetch certain data or instructions before they are required according to the program order. For another example, a “value prediction” hint predicts a result of a calculation that has yet to be performed. “Hint performance data” is data representing with high or low precision how often a prediction represented in a hint is confirmed or disconfirmed. 
     An “outcome of execution”, as the phrase used herein, encompasses confirmation upon execution of a prediction embodied in a hint. The outcome can also include other information such as a target address or a calculated value. An “execution instance” of an instruction refers to an instance in which an instruction is executed. An instruction can have multiple execution instances over time if the address at which it is stored is called repeatedly. Two identical instances of the same instruction type at different positions in the program order do not constitute two execution instances of the same instruction. Also herein, “write back” means copying an instruction or data from a cache to a higher-level cache or to some other memory, typically main memory. These and other variations upon and modification to the illustrated embodiments are provided for by the present invention, the scope of which is defined by the following claims.