Hewlett-packard Company

Hewlett-packard Development Company, L.p.

Wei C Hsu

Manuel Enrique Benitez

Lacky V Shah

Anne M Holler

Loren P Staley

Edward H Gornish

The inventive mechanism provides fast profiling and effective trace selection. The inventive mechanism partitions the work between hardware and software. The hardware automatically detects which code is executed very frequently, e.g. which code is hot code. The hardware also maintains the branch history information. When the hardware determines that a section or block of code is hot code, the hardware sends a signal to the software. The software then forms the trace from the hot code, and uses the branch history information in making branch predictions.

Hardware/software system for profiling instructions and selecting a trace using branch history information for branch predictions

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.

System and method using a hardware embedded run-time optimizer

The inventive mechanism uses a cache table to map branch targets. When a fetch instruction is initiated, the inventive mechanism searches the IP-to-TM cache to determine whether the branch target instruction has been optimized and placed into the trace memory. If there is a match with the P-to-TM cache, then the code in the trace is executed. This cache is examined in parallel with Instruction Translation Lookup Buffer (ITLB). If not a match is found in the IP-to-TM cache, the original binary in the physical address provided by the ITLB will be executed.

Hardware system for fetching mapped branch target instructions of optimized code placed into a trace memory

Hardware/software system for instruction profiling and trace selection using branch history information for branch predictions

The present invention relates to a method and an apparatus for patching program text to improve performance of applications running on a computer through the elimination of table lookup and emulation.

Method and apparatus for patching program text to improve performance of applications

The inventive mechanism uses a cache table to map branch targets. When a fetch instruction is initiated, the inventive mechanism searches the IP-to-TM cache to determine whether the branch target instruction has been optimized and placed into the trace memory. If there is a match with the IP-to-TM cache, then the code in the trace is executed. This cache is examined in parallel with Instruction Translation Lookup Buffer (ITLB). If not a match is found in the IP-to-TM cache, the original binary in the physical address provided by the ITLB will be executed.

System for fetching mapped branch target instructions of optimized code placed into a trace memory

An array padding technique is described that increases memory throughput in the presence of dirty misses. The technique pads arrays so that the starting addresses of arrays within a target loop are separated by P memory banks where P is a rounded integer equal to the number of memory banks divided by the number of arrays. The number of banks of separation can be incremented or decremented by 1 to also avoid path conflicts due to the sharing of buses in a typical hierarchical memory subsystem.

Array padding for higher memory throughput in the presence of dirty

An optimizing compiler for optimizing code in a computer system having a CPU and a memory. The code has a loop wherein the loop includes statements conditionally executed depending on the evaluation of a control flow statement. The inventive compiler separates the code into a index collection phase and an execution phase. The index collection phase collects array indices indicating whether the control flow statement evaluates true for each particular loop iteration. The execution phase builds self loops without conditional statements. The self loops use the array indices to execute only the loop instructions that should be executed. Since those instruction are predetermined by the index collection phase, performance enhancement features of the CPU, such as branch prediction, pipelining, and a superscalar architecture can be fully exploited.

Method and system for optimizing code

A method of scheduling prefetch instructions in a compiler is described that improves performance by minimizing the performance degradation due to dirty cache misses. The method determines the length N of a loop (step 66). The number of prefetch instructions were M within that loop are then determined (step 68). A prefetch spacing P is then calculated according to the formula P=N/M, where the length of the loop is expressed in cycles (step 70). This prefetch spacing is then attached to each prefetch instruction and the instruction scheduler schedules the prefetch instructions so as to space the prefetch instructions apart by approximately the prefetch spacing P (step 72). After the scheduler arranged for P cycles, a prefetch instruction will be assigned a higher priority for scheduling in the next lot.

Optimizing compiler having data cache prefetch spreading

There are two separate, yet related, prefetching strategies used for data references used having multiple strides, which typically occur in data references within nested loop structures. The first approach attempts to reverse one or more of the nested loops so that the strides of the reference are in the same direction. Once the loop or loops are reversed, data elements can be prefetched in the common loop direction. Preferably, the inner loops are reversed as compared with the outer loops, but this is not essential. The second approach is used where the data reference has multiple strides and the loops cannot be reversed. In this case, the prefetching method prefetches in the opposite direction of the innermost loop that surrounds the data reference. The second approach is used when the first approach cannot be used and where the strides of the reference have different directions and the inner loop is expected to iterate relatively few times. In such a case the second approach produces better results than the prior art.

Growing community of inventors

Cupertino, CA, United States of America

Wei C Hsu