System and method using a hardware embedded run-time optimizer

Abstract

The inventive mechanism has a run-time optimization system (RTOS) embedded in hardware. When the code is first moved into Icache, a threshold value is set into a counter associated with the instruction or instruction bundle of the particular cache line of the Icache. Each time the instruction or instruction bundle is executed and retired, the counter is decremented by one. When the counter reaches zero, a trap is generated to inform that the code is hot. A trace selector will form a trace starting from the hot instruction (or instruction bundle) from the Icache line. The Icache maintains branch history information for the instructions in each cache line which is used to determine whether a branch should be predicted as taken or fall through. After the trace is formed, it is optimized and stored into a trace memory portion of the physical memory. The mapping between the original code of the trace and the optimized trace in the trace memory is maintained in a mapping table. The processor consults the mapping table to lead the execution to the optimized code in trace memory. Thus, subsequent execution uses the code in trace memory.

What is claimed is:  
     
         1 . A system for optimizing a portion of a program during run-time of the program, the system comprising: 
 a hardware portion for detecting which instructions of the program are more frequently executed and maintaining a history of targets chosen by branch instructions of the program;    a software portion for forming an optimized trace of instructions from the most frequently executed instructions and using the history in making branch predictions for branch instructions encountered in forming the trace; and    a trace memory portion that stores the optimized trace.    
     
     
         2 . The system of  claim 1 , further comprising: 
 a table memory portion that stores a map of instruction pointers of the program to corresponding addresses in the trace memory.    
     
     
         3 . The system of  claim 2 , wherein the software portion further comprises: 
 a trace manager that controls usage of the trace memory.    
     
     
         4 . The system of  claim 1 , wherein the software portion comprises: 
 an optimizer which performs at least one predetermined optimization on the trace to form the optimized trace.    
     
     
         5 . The system of  claim 1 , wherein the hardware portion comprises: 
 a processor cache for holding a mapping of instruction pointers to addresses of optimized trace instructions.    
     
     
         6 . The system of  claim 1 , wherein 
 the hardware portion includes an instruction cache with a first portion that maintains a plurality of values, each indicating a number of executions of a particular instruction of the program, and a second portion that stores information detailing performance of branch instructions of the program; and    the software portion includes a trace selector that forms the trace and is invoked when the one value of the plurality of values reaches a predetermined number, and the trace selector begins the trace with the instruction associated with the one counter and ends the trace with an instruction selected by a predetermined criteria.    
     
     
         7 . A method for optimizing a portion of a program during run-time of the program, the method comprising the steps of: 
 detecting via hardware, which instructions of the program are more frequently executed;    maintaining, via hardware, a history of targets chosen by branch instructions of the program;    forming, via software, an optimized trace of instructions from the most frequently executed instructions, wherein the step of forming includes the step of using the history in making branch predictions for branch instructions encountered in forming the trace; and    storing the optimized trace in a trace memory portion.    
     
     
         8 . The method of  claim 7 , further comprising the step of: 
 storing a map of instruction pointers of the program to corresponding addresses in the trace memory in a table memory portion.    
     
     
         9 . The method of  claim 8 , further comprising the step of: 
 controlling, via software, usage of the trace memory.    
     
     
         10 . The method of  claim 7 , further comprising the step of: 
 performing at least one predetermined optimization on the trace to form the optimized trace.    
     
     
         11 . The method of  claim 7 , further comprising the step of: 
 storing, via a processor cache, a mapping of instruction pointers to addresses of optimized trace instructions.    
     
     
         12 . The method of  claim 7 , wherein the hardware includes an instruction cache with a first portion that maintains a plurality of values, each indicating a number of executions of a particular instruction of the program, and a second portion that stores information detailing performance of branch instructions of the program; and 
 the software includes a trace selector that forms the trace and is invoked when one value of the plurality of values reaches a predetermined number and the trace selector begins the trace with the instruction associated with the one counter and ends the trace with an instruction selected by a predetermined criteria.