System and method for using hardware performance monitors to evaluate and modify the behavior of an application during execution of the application

There is provided a method, system and program storage device for utilizing a hardware performance monitors for improving performance of an application comprising a plurality of instructions while the application is executing on a micro-architecture, comprising: creating a machine internal representation (MIR) for the plurality of instructions or a subset thereof for the hardware and generating an executable (EXE) from the MIR for execution on the hardware; determining hardware performance monitor (HPM) information for an event associated with a resource of the hardware during execution of the EXE to identify one or more instructions of the application that affect the execution of the application on the hardware; re-computing the MIR according to the HPM information; and re-generating the EXE from the re-computed MIR for execution on the hardware if the MIR and the re-computed MIR are different, thereby improving utilization of the resource by the application. Also provided is a hardware performance monitor (HPM) subsystem for improving performance of an application comprising a plurality of instructions while the application is executing on a hardware.

BACKGROUND OF THE INVENTION

1. Technical Field of the Invention

The present invention generally relates to compiler systems. More particularly, the present invention is directed to an adaptive optimization system and method for utilizing hardware performance monitors to improve an application's performance during its execution on a particular micro-architecture.

2. Description of the Prior Art

With rapidly changing hardware, modem compilers have to target a variety of architectures or architecture implementations. To make this task easier, most compilers consist of an architecture-independent frontend section and an architecture-specific backend section the result of which is an executable application. More particularly, while the frontend section transforms a source application into an intermediate representation (i.e., “IR”), the backend section transforms the IR generated by the frontend section into a sequence of machine instructions (i.e., instruction schedule) for a particular instruction set architecture (i.e., “ISA”), such as PowerPC, which is to be executed on a specific implementation of the ISA (i.e., micro-architecture), such as PowerPC 604e.

Typically, the backend section views the particular ISA as a collection of resources (e.g., caches, registers and the like) and constraints between them, which comprise a micro-architectural model for the particular ISA. The backend section utilizes the micro-architectural model to select a “better” instruction schedule, which takes the fewest clock cycles to execute. In general, the more precise the micro-architectural model the better the instruction schedule that can be generated by the backend section, but the more time that is required by the backend section to generate the instruction schedule. It is noted that the increase in time associated with generating a better instruction schedule is often nonlinear. Notwithstanding the preciseness of the micro-architectural model actually used, it will nevertheless have some imprecision, if for no other reason than some facts that are dependent on the application's execution behavior are impossible to ascertain at compile time, such as the location of data in main memory and the like.

Various compilers exist: static and dynamic. For static compilers, where the instruction schedule is generated before the application executes and the cost of compilation is amortized over many application executions, the execution time of the backend section is less important and the precision of the micro-architectural model is more important because the static compiler has only one opportunity to guess the correct schedule of instructions. If the guess is wrong, the consequence is poor performance of the application during its execution. For dynamic compilers, the instruction schedule is generated at application execution time and the compilation time is counted as part of the application's execution time. Typically, with the dynamic compiler the precision of the micro-architectural model is not as important as the saving of the execution time and thus the precision of the micro-architectural model may be sacrificed in lieu of savings in the execution time. One such compiler is a just-in-time (i.e., “JIT”) compiler, which compiles/optimizes the application only once. Just like the static compiler, the JIT has only one opportunity to guess the instruction schedule and the making of an incorrect “guess” may also lead to poor application performance during application execution. An alternative dynamic compilation strategy is an adaptive optimization system (i.e., “AOS”). In the AOS, the backend section of the compiler has an opportunity to “guess” multiple times to try to get a better instruction schedule. After guessing, the AOS may evaluate the guess and guess again if appropriate, thereby helping to eliminate poor application performance due to one or more bad guesses. Furthermore, the backend section may only have to guess again for parts of the application that have the potential to make a performance difference, and for these parts the backend section can spend more time on compilation because they are a small fraction of the total application size.

Many of the currently available microprocessors provide hardware performance monitors (i.e., “HPMs”), which count a number of times that a micro-architectural event that captures some behavior of a particular micro-architectural resource occurs on the micro-architecture. For example, the typical micro-architectural resources that may be counted may include caches or functional units within a micro-architecture. Functional units represent stages in a pipelined superscalar micro-architecture. The stages may include fetch/decode, dispatch, execute and complete on the particular micro-architecture. The execute stage may include integer and floating-point units, as well as branch and load/store units. The typical events that may be counted include the number of times a micro-architectural resource starts, completes and stalls. For example, an instruction's execution may stall if a value that is an input to the instruction at the time of execution is not available, or if an underlying micro-architectural resource that is required by the instruction is not yet available. The HPMs may be used to generate offline information, which determines where execution time is spent in the application and which may be used to identify parts of the application that should be modified to improve micro-architectural resource utilization. In order to generate offline information, the application is executed to collect HPM data and after the application completes, the HPM data is analyzed to determine how to modify the application's behavior for subsequent executions of the application.

A drawback associated with utilizing offline HPM data from one execution to modify the behavior of an application for subsequent executions is that the modification may not result in improved performance of the application when subsequent executions have different behaviors. For example, the application's behavior may differ from one execution to the next because of the different input to the application. In addition, because offline information is aggregated, the behavior of individual application components may not be obvious. For example, if an application has phase shifts, the phases may not be apparent in the offline information that is collected across all phases. Therefore, offline information may be imprecise and thus may not be useful for modifying application behavior.

FIG. 1illustrates prior art compiler system100without use of hardware performance monitors. The compiler system100comprises a static compiler116, which includes frontend104, intermediate representation (i.e., “IR”)106, selection/scheduling heuristics108, machine model110and backend112, all of which are described in detail below. In the compiler system100, the source code102represents an application's source code, which is to be compiled by the static compiler116. The frontend section104of the static compiler116takes as input or reads in the application's source code102, parses the source code102and generates an IR106, which breaks down instruction in the source code102into a plurality of low-level abstract operations that are more conducive to optimization. The IR106is a sequence of operations that has implied data and control dependencies between the operations. For example, on a reduced instruction set computer (i.e., “RISC”) microprocessor, the low-level abstract operations comprise loads and stores of memory values into registers and subsequent computations on the values in the registers. It is noted that at this point, the registers are symbolic registers, which are subsequently translated into actual hardware registers by the backend section112. The backend section112of the static compiler116reads in the IR106and generates an executable (i.e., “EXE”)114, which represents a schedule of macro-architectural instructions, i.e., assembly language instructions for a particular instruction set architecture ISA, e.g., PowerPC. As aforementioned, the ISA defines a particular target architecture to which a user-level application must conform. More particularly, the backend section112selects micro-architectural instructions for the IR operations106, orders the instructions via instruction scheduling and maps symbolic registers into physical registers via register allocation.

Further with reference toFIG. 1, during EXE114generation, the backend section112consults the machine model110, which describes characteristics about the particular target micro-architecture, e.g., PowerPC 604e. For example, the machine model110may include micro-architectural resources that are available (e.g., fetch/decode, dispatch, execute, and complete phases of a pipelined superscalar microprocessor), a number of instances of a particular micro-architectural resource (e.g., there may be a number of integer functional units which partially comprise the execute stage), and clock cycles that are required for a value to flow from one micro-architectural resource to another (e.g., the number of cycles for an instruction to be executed after it has been dispatched). More particularly, the machine model110provides detailed information about the underlying micro-architecture that the backend112uses to determine latencies and constraints between instructions for a particular instruction schedule. For example, if the expected latency or delay of an instruction is d clock cycles for a particular micro-architectural resource, then the backend112will attempt to schedule all instructions that are dependent on the value generated by the instruction at least d clock cycles later. Furthermore, if there is more than one integer functional unit, the backend112may schedule more than one integer instruction to be executed in the same clock cycle.

Yet further with reference toFIG. 1, in addition to the machine model110, the backend112further consults selection/scheduling heuristics108, which are used for instruction selection and instruction scheduling in the EXE114. For example, there may be a plurality of instructions that could be selected at any given time and the heuristics108help the backend section112select the optimal instructions among the plurality of instructions so that the instruction schedule will finish executing in the fewest possible number of clock cycles on the particular target micro-architecture. One goal of the backend112is to generate a “valid” instruction schedule that orders the instructions so that their execution will maintain the data dependencies between instructions. For example, if the value generated by executing instruction A is used by instruction B, then instruction A must be scheduled for execution before instruction B.

In view of the foregoing, there is a need in the art for providing a system and method for utilizing hardware performance monitors to evaluate and modify the behavior of an application during its execution. More particularly, there is a need in the art for providing an adaptive optimization system and method for utilizing hardware performance monitors to improve an application's performance while the application is executing.

SUMMARY OF THE INVENTION

The present invention is directed to a system and method for utilizing hardware performance monitors to evaluate and modify the behavior of an application while the application is executing.

It is an object of the present invention to provide an adaptive optimization system and method for utilizing hardware performance monitors to improve an application's performance while the application is executing.

It is another object of the present invention to provide a dynamic compiler for utilizing hardware performance monitors to improve an application's performance while the application is executing.

It is a further object of the present invention to provide a dynamic compiler in an adaptive optimization system for utilizing hardware performance monitors to improve an application's performance while the application is executing.

It is a still a further object of the present invention to provide a controller in an adaptive optimization system for utilizing hardware performance monitors for directing a dynamic compiler to improve an application's performance while the application is executing.

According to an embodiment of the present invention, there is provided a method for utilizing a hardware performance monitor for improving performance of an application comprising a plurality of instructions while the application is executing on a micro-architecture, the method comprising the steps of: creating a machine internal representation (MIR) for the plurality of instructions or a subset thereof for the micro-architecture and generating an executable (EXE) from the MIR for execution on the micro-architecture; determining hardware performance monitor (HPM) information for an event associated with a micro-architectural resource of the micro-architecture during execution of the EXE to identify one or more instructions of the application that affect the execution of the application on the micro-architecture; re-computing the MIR according to the HPM information; and re-generating the EXE from the re-computed MIR for execution on the micro-architecture if the MIR and the re-computed MIR are different, thereby improving utilization of the micro-architectural resource by the application.

According to another embodiment of the present invention, there is provided a system for utilizing a hardware performance monitor for improving performance of an application comprising a plurality of instructions while the application is executing on a micro-architecture, the system comprising: a compiler for generating a machine internal representation (MIR) for the plurality of instructions or a subset thereof for the micro-architecture and generating an executable (EXE) from the MIR for execution on the micro-architecture; a hardware performance monitor (HPM) subsystem for determining HPM information for an event associated with a micro-architectural resource of the micro-architecture during execution of the EXE to determine one or more instructions of the application that affect the execution of the application on the micro-architecture; and a controller for re-computing the MIR according to the HPM information and directing the compiler to re-generate the EXE from the re-computed MIR for execution on the micro-architecture if the MIR and the re-computed MIR are different, thereby improving utilization of the micro-architectural resource by the application.

According to a further embodiment of the present invention, there is provided a program storage device, tangibly embodying a program of instructions executable by a machine to perform a method for utilizing a hardware performance monitor for improving performance of an application comprising a plurality of instructions while the application is executing on a micro-architecture, the method comprising the steps of: creating a machine internal representation (MIR) for the plurality of instructions or a subset thereof for the micro-architecture and generating an executable (EXE) from the MIR for execution on the micro-architecture; determining hardware performance monitor (HPM) information for an event associated with a micro-architectural resource of the micro-architecture during execution of the EXE to identify one or more instructions of the application that affect the execution of the application on the micro-architecture; re-computing the MIR according to the HPM information; and regenerating the EXE from the re-computed MIR for execution on the micro-architecture if the MIR and the re-computed MIR are different, thereby improving utilization of the micro-architectural resource by the application.

According to yet a further embodiment of the present invention, there is provided a hardware performance monitor (HPM) subsystem for improving performance of an application comprising a plurality of instructions while the application is executing on a hardware, the HPM subsystem comprising: a means for receiving a request from a dynamic compiler system to determine HPM information for an event associated with a resource of the hardware during execution of an executable (EXE) associated with the plurality of instructions or a subset of the application to identify one or more instructions of the application that affect the execution of the application on the hardware; and a means for providing the determined HPM information to the dynamic compiler system to re-generate the EXE according to the HPM information for execution on the hardware, thereby improving utilization of the resource by the application.

The present invention is directed to an adaptive optimization system and method for utilizing hardware performance monitors to improve an application's performance while the application is executing.

FIG. 2is an exemplary illustration of a compiler system200, which comprises an adaptive optimization system (i.e., “AOS”)208that utilizes a hardware performance monitor (i.e., “HPM”) subsystem210to improve performance of an application, according to the present invention. It is noted that components102through114of the compiler system200are analogous with the like components of the prior art compiler system100, illustrated above inFIG. 1. A distinction between the compiler system200according to the present invention and the prior art compiler system100is that the components102through114according to the invention are part of a dynamic compiler202and analogous components of the prior art compiler system100are part of the static compiler116. Unlike the static compiler116, which compiles the entire source of an application before the application is executed, the dynamic compiler202compiles a portion of the source code102of the application when that portion is executed at the application's execution time. Consequently, each time the application executes on the micro-architecture, either different or the same portions of the source code102of the application are compiled. Typically, the portion or unit of compilation is a method. Thus, the EXE114generated by the dynamic compiler200represents an executable for a method. It is noted, however, that one skilled in the art may easily compile the source code102at different levels of granularity, i.e., greater or lesser portions of the source code than a method may be compiled based on particular requirements. An article by Whaley, John (“Partial Method Compilation using Dynamic Profile Information.”Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and ApplicationsOctober 2001: 166–179) discloses one of such techniques for identifying sub-method granularity for dynamic compilation, which may easily be utilized by the present invention to limit recompilation to only those sub-methods. The backend section112of the dynamic compiler202generates a machine internal representation (i.e., “MIR”)204, which is described inFIGS. 4–12below, in addition to the EXE114, which is described above with reference toFIG. 1. The MIR204is a data structure, which is used to communicate between the backend section112and the controller206, and vice versa. Depicted graphically, the MIR204is a graph where each node represents an instruction or a micro-architectural resource that is required to partially or fully execute an instruction, and each edge represents a constraint between two nodes in the graph. A constraint may be a data dependence or an underlying micro-architectural constraint for the particular target micro-architecture. As will be particularly described below with reference toFIGS. 4–12, weights may be associated with either nodes or edges or both, which represent a number of clock cycles that are expected to be needed to execute the node or to satisfy the edge's constraint. The expected time that it will take to execute an instruction schedule on target micro-architecture is a sum of the weights of a path through the instruction schedule, such that the sum is greater than or equal to the sum of weights along any other path.

The controller206communicates with the HPM subsystem210. In operation, the HPM subsystem210receives requests from a controller206to count micro-architectural events, and if necessary, to monitor the micro-architectural events that may adversely affect the application, i.e., to determine whether the application is non-efficiently utilizing micro-architectural resources of the particular target micro-architecture. The HPM subsystem210comprises one or more HPMs212via which the HPM subsystem210may either count or monitor micro-architectural events as an application executes on a particular target micro-architecture (e.g., PowerPC 604e) and generate HPM information214according to the present invention as particularly described below. More specifically, the HPM subsystem210counts the different micro-architectural events as an application executes to identify resource utilization, stalls and the like and records the counting information in HPM information214. As aforementioned, the execution of an instruction may stall if a value that is its input at the time of execution is not available, or if an underlying micro-architectural resource that is required by the instruction is not yet available. It is noted that for counting, the counted values are aggregated across all instructions that have executed for a determined period of time and recorder in HPM information214, while for monitoring, the instruction and the operand address that have caused the micro-architectural event to occur are recorded in HPM information214.

Because the counted values are aggregated across all instructions, it is not known when the controller206counts micro-architectural events which instruction has caused a particular micro-architectural event to occur. Thus, in the worst-case scenario all instructions that possibly may have caused a particularly micro-architectural event (e.g., first level cache miss) to occur are recompiled according to the present invention. Preferably, however, the present invention utilizes known runtime measurements216techniques that generate online profiling information218to determine which methods of the source code102have caused the micro-architectural event to occur, thereby limiting the methods that need be recompiled according to the present invention. More particularly, the controller206requests a runtime measurements component216to generate online profile information218, detecting where the application is spending most of its execution time and identifying those methods where most of the execution time is spent as hot methods. It is noted that the hotness of the method is a ratio of the amount of time spent executing the method over the total amount of time spent so far executing the application. Once the hot methods are identified and returned to the controller206, the controller206will determine if those hot methods should be recompiled according to the present invention. An article by Arnold, Mathew, et al. (“Adaptive Optimization in the Jalapeno JVM.”Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and ApplicationsOctober 2000: 47–65) discloses one of such techniques for identifying hot methods, which may easily be utilized by the present invention to limit recompilation to only those methods that are hot.

Further with reference toFIG. 2, for either counting or monitoring, the controller206specifies via a request to the HPM subsystem210, a time interval, a micro-architectural resource (e.g., first level cache) and a micro-architectural event for the resource (e.g., cache miss) that is to be observed by the HPM subsystem210. Additionally, in the case of a monitoring request, the controller206also specifies a number of times the micro-architectural event occurs (i.e., a count value) before sampling an instruction. Given the controller's request to count or monitor, the HPM subsystem210via an HPM212counts or monitors the micro-architectual event for the spectified time interval. The HPM subsystem210via HPM212packages It's monitoring or counting information for the controller206in HPM information214. More particularly, for a controller's request to count, the HPM subsystem210generates HPM information214, which includes: 1) a micro-architectural event counted; 2) a time interval over which the micro-architectural event occured during the interval of time. After receiving a response to the counting request in the form of HPM information214, the controller206may determine to monitor the identified micro-architectural event to event to occur. The interaction between the counting and monitoring requests will be described in greater detail with reguard toFIG. 3below. However, for a controller's request to monitor, the HPM subsystem210via HPM212generates HPM information214, which includes: 1) a micro-architectural event monitored; 2) a time interval over which the micro-architectural event is counted; 3) a monitor's threshold that represents the number of times the micro-architectural event occurs before an instruction address and operand address are monitored; and 4) a list of triples each of ehich includes: i) the instruction address; ii) the operand address if the instruction's address includes a memory location; and iii) a count that represents the number of times the instruction address and the operand address were counted.

Still further with reference toFIG. 2, based on die MIR204, the controller206makes decisions about what micro-architectural events the HPM subsystem210counts and/or monitors. More particularly, the controller206re-computes a machine internal representation MIR204from HPM information214generated by the HPM subsystem210via HPM monitors212, compares the controller re-computed MIR204with the backend section generated MIR204, and makes decisions about when the backend section112should re-generate the EXE114. The controller206directs the backend section112of the dynamical compiler202to re-generate the EXE114from the re-computed MIR204when the weight of one or more nodes or edges or both in the re-computed MR204are different from the MIR204generated by the backend section112. This will become clear with reference to the description ofFIG. 3below. Additionally, the controller206further uses the machine model110to determine the micro-architectural specific delays in clock cycles that may occur for different micro-architectural events. For example, for a first level cache miss it may take10clock cycles to retrieve a value from a second level cache, and for a second level cache miss it may take100clock cycle to retrieve a value from main memory. Therefore, if the controller206determines from examining the HPM information214that a first level cache miss has occurred, the controller206uses the cost of a first level cache miss that is determined from the machine model110to change the weight of the appropriate nodes or edges or both in the controller re-computed MIR204and directs the backend section112of the dynamical compiler202to re-generate the EXE114from the re-computed MIR204.

FIG. 3is an exemplary illustration of a method flowchart300for the AOS208utilizing the HPM subsystem210ofFIG. 2to improve performance of an application according to the present invention. At step302, the frontend section104generates intermediate representation IR106from an application's source code102. At step304, the backend section generates MIR204from the IR106. At step306, the backend section112generates an executable EXE114from the MIR204. Thereafter, at step308, the EXE114is executed on particular target micro-architecture, e.g., PowerPC 604e. The MIR204generated by the backend section112, which is used to generate the EXE114at step306is subsequently used in a comparison steps314and320and may be replaced by a MIR204re-computed by the controller206. Thus, the MIR204that is utilized by the backend section at step306to generate the EXE114is hereinafter referenced as a current MIR204and the MIR that is re-computed by the controller206at steps312and318is hereinafter referenced as re-computed MIR204. It is noted that a unit of compilation generated by the backend section112of the dynamic compiler202is generally a code section in the application's source code102, and more typically is a method in the application's source code102. Thus, when a compiled method is invoked (i.e., executed) on the target micro-architecture at step308, a current MIR204, whether generated by the backend section112or re-computed by the controller206, is used at step306to generate the EXE114(i.e., compiled method). Sometimes an executing method may need to be replaced with a re-compiled method (i.e., from a re-computed MIR204) during execution of that method. There are generally two known mechanisms for dealing with a previous invocation of a method that has not yet completed executing and that has activation records on a call stack. The first mechanism directs that nothing be done while activation records are live on the call stack and the method invocation or execution has not yet completed. The second mechanism directs on-stack replacement of the activation records of the executing method with activation records associated with a newly generated executable method (i.e., EXE114), performing an appropriate mapping of data from the old activation records to the new activation records on the call stack. On-stack replacement is generally disclosed in U.S. Pat. No. 6,223,340 to Detlefs. Below is described the operation of the controller206with regard to: 1) counting micro-architectural events on the particular target micro-architecture; and 2) monitoring micro-architectural events on the particular target micro-architecture.

Further with regard toFIG. 3, at step310the controller206determines whether to request the HPM subsystem210to count a micro-architectural event. More particularly, the controller206examines the current MIR204used by the backend section112at step306to get an indication of micro-architectural events that may be important to count. For example, if the current MIR204has a lot of load instructions, the controller206may request that the HPM subsystem210count cache misses; or, if the MIR204has a lot of integer instructions, the controller206may request that the HPM subsystem210count the number of times the integer unit stalls. If the controller206decides not to count any micro-architectural events currently, the controller206waits a predetermined amount of time before again determining whether to request the HPM subsystem210to count a micro-architectural event at step310. The controller206will determine not to request the HPM subsystem210to count any micro-architectural events if the “hot” code regions (i.e., hot methods) have not changed since the last time that the controller206made a request to count, which did not cause the backend section112to regenerate an executable EXE114. However, if the controller determines to request the HPM subsystem210to count an event, the controller206re-computes the MIR204using the HPM information214generated by the HPM subsystem210via one or more HPMs212. Thereafter, the current MIR204generated from step306and the re-computed MIR204from step312are compared at step314to determine whether any node or edge weight is different in the current and re-computed MIR204. If at step314, the current MIR204from step306and the re-computed MIR204from step312are not different, the method flowchart300continues at step310where the controller206determines whether it should count some other micro-architectural event or whether it should wait. However, if the current MIR204from step306and the re-computed MIR204from step312are determined to be different at step314, the controller206instructs the backend section112at step306to re-generate the EXE114from MIR204re-computed by the controller206at step312. The regenerated EXE114is then executed on the particular target micro-architecture, e.g., PowerPC 604e. After the backend section112re-generates the EXE114at step306, the MIR204re-computed by the controller206at step312becomes the current MIR204.

Yet further with regard toFIG. 3, the method flowchart300continues at step316where the controller206determines whether to request the HPM subsystem210to monitor the counted micro-architectural event to determine which instruction is causing the counted micro-architectural event to occur. If at step316, the controller206determines to not monitor the counted event, the method flowchart300continues at step310where the controller206determines whether to monitor some other event or to wait. Because of overhead considerations, it is preferable that the controller206does not request the HPM subsystem210to monitor a micro-architectural event if there is only one instruction that could have possibly caused the micro-architectural event to occur. Otherwise, the method flowchart300continues at step318, where the controller206utilizes HPM information214generated by HPM212of the HPM subsystem210during monitoring of the micro-architectural event to re-compute the MIR204. At step320, the re-computed MIR204generated by the controller206at step318is compared against the current MIR204from step306. If no node or edge weight in re-computed MIR204generated at step318is different from current MIR204from step306, then the method flowchart300continues at step310where the controller206determines whether some other event should be counted or whether it should wait. Otherwise, the method flowchart300continues at step306where the backend section112generates the EXE114from the re-computed MIR204generated by the controller206at step318, and the EXE114is executed on the particular target micro-architecture, e.g., PowerPC 604e. After the backend section112re-generates the EXE114at step306, the MIR204re-computed by the controller206at step312becomes the current MIR204.

FIGS. 4–12represent a series of exemplary illustrations that depict the adaptive optimization system utilizing hardware performance monitors to improve the performance of an application while the application executes, according to the present invention. More particularly,FIG. 4is an exemplary illustration of pseudo code400that comprises a doubly nested loop of high-level programming language statements, in which an inner loop401comprises statements402,404and406(i.e., in C/C++), which access a one-dimensional array A to successively compute a value of a point as a sum of its two neighbors and that access a two-dimensional array C to compute a value of a point as the loop index plus a value of another point. The inner loop401of pseudo code400is used throughoutFIGS. 5–12to demonstrate in exemplary fashion how an executable EXE114is generated from a machine internal representation MIR204with the help of the HPM subsystem210and controller206, as particularly described above with reference toFIGS. 1–3.

FIG. 5is an exemplary illustration of an instruction schedule500of statements of the inner loop401for pseudo code400ofFIG. 4. The left-hand-side of instruction schedule500depicts an executable502as a sequence of pseudo machine instructions506–520on a particular target micro-architecture that are generated by the backend section112to execute the statements402,404and406of the inner loop401depicted inFIG. 4. The instruction schedule500is an example of an executable EXE114that the backend section112generates. The backend section112generated the instructions by taking each statement402,404and406of the inner loop401one at a time and in order, and, for each statement, generating a sequence of one or more machine instructions506–520. For example, the statement402(i.e., A[i]=A[i−1]+A[i+1]) results in four machine instructions: load A[i−1]506; load A[i+1]508; add A[i−1] and A[i+1]510; and store A[i]512. Other statements404and406are similarly described by machine instructions514–520. For example, statement404(i.e., k=j_limit-j) results in one machine instruction514that subtracts j from j_limit, which are stored respectively in registers r4and r6, and stores the result in a register r13. The comment504lists assumptions for the contents of registers on the particular target micro-architecture at the start of the instruction schedule502. For example, register r2contains the value of the induction variable i, and register r3contains the address of array A at index1. The right-hand-side of instruction schedule500is a graphical representation522of the instruction schedule500in which instructions are depicted as nodes and data dependencies between nodes as edges. For example, in order to execute instruction510(i.e., A[i−1] +A[i+1]), both instructions506(i.e., load A[i−1]) and508(i.e., load A[i−1]) must first be executed because instruction510is data dependent on the values that are loaded by instructions506and508(i.e., load A[i−1] and load A[i+1]). The instruction schedule500(as depicted in representation522) is one example of a “valid” instruction schedule. An instruction schedule is valid as long as the data dependencies between instructions (or nodes) are maintained. That is, the node at the tail end of an edge must be scheduled before the node at the head end of an edge. Additionally in this regard, any instruction schedule that maintains the data dependencies represents a valid instruction schedule.

FIG. 6is an exemplary data dependence graph600, which is an alternative to the graphical representation522of the instruction schedule500according toFIG. 5. Although the nodes and edges in the instruction schedule500, as depicted in the graphical representation522, are the same as the nodes and edges in the data dependence graph600, the nodes in the data dependence graph600are laid out topographically such that all nodes that have no data dependencies on other nodes are laid out first. The backend section112utilizes the data dependence graph600to generate an instruction schedule as follows: a node is scheduled for execution when all nodes that depend on that node have been scheduled for execution. For example, the node representing instruction518(i.e., add r15, r2, r14) may be scheduled only after the node representing instruction516(i.e., load r14, r5(r13)) is scheduled because one of the values that is added must first be loaded. Utilizing the data dependence graph600, the backend section112may interleave instructions506–520from different statements402–406. Interleaving the instructions provides the backend section112with more choices to generate a “valid” instruction schedule. For example, the node representing instruction512(i.e., store r3(r2), r12) may be scheduled after the node representing instruction518(i.e., add r15, r2, r14) or before the node representing instruction516(i.e., load r14, r5(r13)) because there are no data dependencies between instruction512and instructions516and518.

FIG. 7is an exemplary weighted data dependence graph (i.e., WDG)700, which represents an exemplary machine internal representation MIR204that a backend section112may utilize to generate an executable EXE114. In general, a weighted data dependence graph associates weights with nodes, or edges or both of a data dependence graph. In particular, the WDG700associates weights702–712with edges of the data dependence graph600. The weights associated with the edges represent latency or delay in clock cycles that indicate how soon a node at the head of an edge may start to execute after a node at the tail end of the edge has started to execute on a particular target micro-architecture. Weights help the backend section112generate an executable EXE114by choosing a node available to be scheduled for execution, such that the weight of its highest incoming edge is lower than the highest weight of any incoming edge to other nodes that are available to be scheduled for execution on the target micro-architecture. For example, assuming for the moment that edge602of node506has a weight702equal to 10 clock cycles and edge604of node508has a weight704equal to 100 clock cycles and edge608of node514has a weight708equal to 10 clock cycle, if nodes510and516are available to be scheduled, then node516will be scheduled, because the highest weight of an incoming edge to node516is lower than the highest incoming weight of node510. As will be described in more detail with reference toFIGS. 9–12, because there is no dynamic or run-time information about the latency of instructions, the backend sections112generates the weights from consulting the machine model110, which provides latency information about the underlying target micro-architecture. Although some instructions may have variable latencies, the backend section112initially chooses the most optimistic latencies for the outgoing edges of these instructions. An example of an instruction with variable latency is a load instruction. A load instruction's latency depends on where the value, which is loaded, resides in a memory hierarchy. For example, it may take one (1) clock cycle to load a value from a first level cache; ten (10) clock cycles from the second level cache; and one hundred (100) clock cycles from main memory. Therefore, the backend section112makes an optimistic assumption that all values are stored in a first level cache and take only one clock cycle to load. As particularly illustrated in the WDG700ofFIG. 7, weights702,704and710of outgoing edges602,604, and610for load instructions506,508and516have a weight of one.

FIG. 8is an exemplary illustration of an instruction schedule800utilizing the weights of the weighted dependence graph WDG700(assuming weights=1) and heuristics108to generate the instruction schedule. Although weights help the backend section112to schedule execution of a node when there is a plurality of nodes whose incoming edges have different weights, the backend section112utilizes heuristics108when there is a plurality of nodes whose incoming edges have the same weights. For example, the backend section112may schedule either instruction506(i.e., load of A[i−1]), or instruction508(i.e., load of A[i+1]), or instruction514(i.e., k=j_limit-j) as a first instruction for execution. Because a goal of the backend section112is to generate an instruction schedule that minimizes the time necessary to execute the instructions506–520on the target micro-architecture, the heuristics108provide help necessary to determine which instruction is scheduled first when all possible nodes representing instructions have the same associated weight. ForFIG. 8the following exemplary heuristics108are used: schedule load instructions before arithmetic instructions; and schedule arithmetic instructions before store instructions. The left-hand-side of instruction schedule800depicts an executable802as a sequence of pseudo machine instructions506–520that are generated when the backend section112utilizes the WDG700ofFIG. 7and the simple heuristics108noted above. The right-hand-side of instruction schedule800is a graphical representation804of the executable802in which nodes representing instructions506–520are linearized according to the executable802. The edges in the graphical representation804depict data dependencies and the weights depict latencies.

Further with reference toFIG. 8, the instruction schedule800is generated as follows. From WDG700, either load instruction506(i.e., load A[i−1]) or load instruction508(i.e., load A[i+1]) may initially be scheduled because neither instruction's data depends on any other scheduled instruction. The backend section112then non-deterministically schedules instruction506(i.e., load A[i−1]) to be executed before load instruction508(i.e., load A[i+1]). That is, either instruction506or508is available to be scheduled for execution, and the backend section112non-deterministically or randomly chooses one instruction to be executed first. However, because the heuristics108directs load instructions to be scheduled before arithmetic instructions, the subtract instruction514(i.e., k=j_limit-j) may not be scheduled before the two load instructions even though the subtract instruction514had no data dependency on any other instruction. Thus, after the two scheduled load instructions506and508are scheduled, the WDG700illustrates that either subtract instruction514(i.e., k=j_limit−j) or add instruction510(i.e., A[i−1]+A[i+1]) may be scheduled next. The backend then non-deterministically (i.e., randomly) schedules the subtract instruction514(i.e., k=j_limit-j) as the next instruction for execution. From WDG700, either the add instruction510(i.e., add A[i−1]+A[i+1]) or the load instruction516(i.e., load C[i,k]) may be scheduled next. Because the heuristics108directs that load instruction be scheduled before arithmetic instructions, the backend section112schedules the load instruction516as the fourth instruction for execution. At this point from the WDG700, either the add instruction510(i.e., add A[i−1]+A[i+1]) or the add instruction518(i.e., add i+C[i,k]) may be scheduled next. The backend section112non-deterministically schedules instruction518as the fifth instruction for execution. Now the WDG700illustrates that either the add instruction510(i.e., add A[i−1]+A[i+1]) or the store instruction520(i.e., store C[i,j]) may be scheduled next. It is noted, however, that store instruction512(i.e., store A[i]) cannot yet be scheduled because it has a data dependency based on the execution of instruction510(i.e., add A[i−1]+A[i+1]). Because the heuristics108direct that store instructions should be scheduled before arithmetic instructions, the backend section112non-deterministically schedules the store instruction520(i.e., store C[i,j]) as the sixth instruction for execution. Finally, the WDG700forces the backend section112to schedule the add instruction510and then the store instruction512because of the data dependency between the two instructions.

FIG. 9is an exemplary weighted data dependence graph (i.e., WDG)900in which latencies (i.e., weights) of edges, which represent data dependencies between instructions506–520, are inferred from the counts (i.e., in the form of HPM information214) generated by HPM subsystem210via HPMs212. InFIGS. 7 and 8above, backend section112used optimistic assumptions about latency (i.e., weights=1) to schedule instructions506–520, i.e., the backend section112assumed that all values were loaded from a first level cache. However, sometimes the optimistic assumptions are incorrect and may result in first level cache misses. The HPM subsystem206may help to determine when the assumptions utilized by the backend section112in scheduling instructions are incorrect. More particularly, assume that the controller206has knowledge from the HPM subsystem210that there is an unusually high number of first level cache misses. Although the controller206does not know which instruction or instructions are causing the cache misses, the controller206now assumes that all values are loaded from the second level cache, thereby attempting to hide latencies associated with accessing the second level cache (e.g., 10 clock cycles) as compared to a first level cache (e.g., 1 clock cycle). As mentioned above, an edge's weight represents the latency or delay in clock cycles before the node at the head of the edge may execute after the node at the tail of the edge has started to execute. Thus, the controller206generates the WDG900in which the outgoing edges602,604, and610associated with nodes representing load instructions506,508and516have respective weights902,904and910of 10 clock cycles, i.e., the number of clock cycles required to retrieve a value from the second level cache. As described with reference toFIGS. 2 and 3above, because the WDG900generated by the controller206is different from the WDG700generated by the backend section112, the controller206notifies the backend section112to re-generate the executable EXE114from the WDG900(instead of the WDG700), thereby attempting to hide latencies associated with accessing data from the second level cache.

FIG. 10is an exemplary illustration of an instruction schedule1000generated by utilizing the weights of the weighted dependence graph WDG900, which are inferred from the counts (i.e., in the form of HPM information214) generated by the HPM subsystem210via HPM212. The left-hand-side of instruction schedule1000depicts an executable1002as a sequence pseudo machine instructions506–520generated when the backend section112utilizes the WDG900and the heuristics108. The weights help the backend section112generate an executable EXE114by choosing a node available to be scheduled for execution, such that the weight of its highest incoming edge is lower than the highest weight of any incoming edge to other nodes that are available to be scheduled for execution on the target micro-architecture. Referring for a moment to the WDG900, all incoming edges to instructions that are data dependent on a load instruction have a greater weight (i.e., weight=10) than the weight of all other edges (i.e., weight=1). The load instructions506and508are scheduled before the subtraction instruction514because load instructions are to be scheduled before arithmetic instructions according to heuristics108. Now the add instruction510and the subtraction instruction514are to be scheduled next. Because the weight of the highest incoming edge to instruction510is equal to ten (weights associated with instructions506and508), while the weight of the highest incoming edge to instruction514is zero because instruction514has no incoming edges, instruction514is scheduled for execution before instruction510. Due to the heuristics108, which directs load instructions to be scheduled for execution before arithmetic instructions, the load instruction516is scheduled for execution before the add instruction510. After instruction516is scheduled, the WDG900illustrates that only the add instruction510or add instruction518can be scheduled and both are dependent on load instructions. Therefore, the backend section112non-deterministically (i.e., randomly) chooses instruction518which then causes instruction520, which is not data dependent on a load instruction, to be scheduled before the add instruction510.

Further with reference toFIG. 10, the right-hand-side of instruction schedule1000is a graphical representation1004of the executable1002in which nodes representing instructions506–520are linearized according to the executable1002. As before, edges depict data dependencies and edge weights depicts latencies. The backend section112assumes that all load instructions506,508and516miss in the first level cache and hit in the second level cache. The controller206may instruct the HPM subsystem210to count second level cache misses to determine whether the load instructions506,508and516also miss in the second level cache. However, assuming that all values reside in the second level cache, the HPM subsystem210determines via monitoring which particular load instruction or instructions miss in the first level cache. More particularly, once the controller206knows that there is a high first level cache miss rate for the execution of the inner loop401and there are multiple loads that could miss, it instructs the HPM subsystem210to monitor first level cache misses to determine which instruction or instructions cause the misses. As described with reference toFIGS. 2 and 3above and with reference toFIG. 11below, the controller206then uses monitoring information (i.e., HPM information214) to generate a weighted data dependence graph in which only the load instruction or instructions that have been identified to miss the first level cache have assigned outgoing edges of weight10.FIG. 11is an exemplary weighted data dependence graph (i.e., WDG)1100generated by controller206in which weights of edges, which represent the data dependencies between instructions506–520, are inferred from monitoring information (i.e., in the HPM information214) generated by HPM subsystem210via HPM212. More particularly, assume that the RPM subsystem210monitoring information reveals that only the load instruction516(i.e., load C[i,k]) causes misses in the first level cache. Therefore, outgoing edges602and604from instructions506and508are assigned respective weights1102and1104(i.e., one clock cycle each) because they do not miss in the first level cache, while edge610retains weight910(i.e., ten clock cycles) because it misses in the first level cache and is assumed to be in a second level cache. It is noted that controller206consults the machine model110to determine what is the latency of load instruction that misses in the first level cache.

FIG. 12is an exemplary illustration of an instruction schedule1200that utilizes the weights of the weighted dependence graph WDG1100ofFIG. 11using monitoring information (i.e., HPM information214) generated by the HPM subsystem206and heuristics108to generate the instruction schedule. The left-hand-side of instruction schedule1200depicts an executable1202as a sequence of pseudo machine instructions506–520that are generated when the backend section112utilizes the heuristics108and the WDG1100ofFIG. 11, where the weights assigned are based on monitoring information (i.e., HPM information214), and machine model110. The right-hand-side of instruction schedule1200is a graphical representation1204in which nodes representing instructions506–520are linearized according to the executable1202. It is noted that inFIG. 11it was assumed that the load instruction516(i.e., load C[i,k]) causes misses in the first level cache. Thus, the executable1202clearly depicts that the load instruction516(i.e., load C[i,k]) and the use of the value (i.e., C[i,k]) loaded by instruction516at instruction518are scheduled as far apart as possible, thereby hiding some of the latency caused by the first level cache miss of the load instruction516. Therefore, when the instructions516and518are executed according to the instruction schedule1200, a savings in execution time will be observed by utilizing the hardware performance monitors according to the present invention.

FIG. 13is an exemplary micro-architecture1300that can be employed by the present invention described with reference toFIGS. 2–12above. The micro-architecture1300includes a central processing unit (i.e., “CPU”)1312, which may be a RISC microprocessor such as the PowerPC by International Business Machines (i.e., “IBM”). The CPU1312comprises one or more caches1302, which communicate with a branch processor1304, one or more fixed-point processors (i.e., “FXU”)1306and one or more floating-point processors (i.e., “FPU”)1308of the CPU1312and with other components of the micro-architecture1300via a bus interface1310over a system bus1314. The branch processor1304, the FXU1306and the FPU1308execute one or more instructions of an application based on data supplied by the one or more caches1302. It is noted that the branch processor1304executes only branch instructions from the one or more cache1302. Additionally, the CPU1312further communicates with other components of the micro-architecture1300over the system bus1314. To the system bus1314are attached: a read only memory (i.e., “ROM”)1316; a random access memory (i.e., “RAM”)1318; an input/output (i.e., “I/O”) adapter1322; a user interface adapter1328; and a display adapter1332. The RAM1318functions as main memory to the CPU1312and provides temporary storage for an application's code and data, while the ROM1316typically includes the basic input/output system (i.e., “BIOS”) code and may be implemented with flash memory or electronically programmable memory. The I/O adapter1322, such as a small computer system interface (i.e., “SCSI”) adapter, is connected to one or more disk drives1320, such as direct access storage devices (i.e., “DASD”). The disk drive1320typically stores the micro-architecture's operating system (i.e., “OS”), such as IBM's AIX operating system, as well as one or more applications, which may be loaded into RAM1318via the system bus1314for execution. The user interface adapter1328interfaces the micro-architecture1300via system bus1314to attached keyboard1326, mouse1330and other user interface devices such as a touch screen device (not shown). The display adapter1332interfaces the micro-architecture1300via system bus1314to a display device1334, such as a cathode ray tube (“CRT”), a liquid crystal display (“LCD”) or other suitable display device.