Method and computer program product for precise feedback data generation and updating for compile-time optimizations
First Claim
1. A method for precise feedback data generation and updating during compile-time optimizations, within an optimizing compiler, comprising:
- (a) accessing a first intermediate representation of source code of a computer program, wherein said first intermediate representation includes instructions instrumented into the source code of said computer program;
(b) annotating said first intermediate representation with previously-gathered frequency data from a plurality of sample executions of said computer program;
(c) performing an optimization of said first intermediate representation annotated with said frequency data, thereby producing a transformed intermediate representation;
(d) updating said frequency data to maintain accuracy of said frequency data during compilation in a direction of increasing exactness of frequency data based on the transformed intermediate representation caused by the optimization; and
(e) repeating steps (c) and (d) at least once during the same compilation pass.
8 Assignments
0 Petitions
Accused Products
Abstract
A method and computer program product, within an optimizing compiler, for precise feedback data generation and updating. The method and computer program uses instrumentation and annotation of frequency values to allow feedback data to stay current during the multiple optimizations that the program code undergoes during compilation. Global propagation of known precise feedback values are used to replace approximate and unavailable values, and global verification of feedback data after optimization to detect discrepancies is employed. The method and computer program also provides improved instrumentation to anticipate cloning when code is cloned during ceratin compiler optimizations and handles inlined procedures. The result is compiled executables with improved SPECint benchmarks.
41 Citations
51 Claims
-
1. A method for precise feedback data generation and updating during compile-time optimizations, within an optimizing compiler, comprising:
-
(a) accessing a first intermediate representation of source code of a computer program, wherein said first intermediate representation includes instructions instrumented into the source code of said computer program; (b) annotating said first intermediate representation with previously-gathered frequency data from a plurality of sample executions of said computer program; (c) performing an optimization of said first intermediate representation annotated with said frequency data, thereby producing a transformed intermediate representation; (d) updating said frequency data to maintain accuracy of said frequency data during compilation in a direction of increasing exactness of frequency data based on the transformed intermediate representation caused by the optimization; and (e) repeating steps (c) and (d) at least once during the same compilation pass. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that performs precise feedback data generation and updating during compile-time optimizations, within an optimizing compiler, said computer readable program code means comprising:
-
first computer readable program code means for causing the computer to access a first intermediate representation of source code of a computer program, wherein said first intermediate representation includes instructions instrumented into the source code of said computer program; second computer readable program code means for causing the computer to annotate said first intermediate representation with previously-gathered frequency data from a plurality of sample executions of said computer program; third computer readable program code means for causing the computer to perform an optimization of said first intermediate representation annotated with said frequency data, thereby producing a transformed intermediate representation; fourth computer readable program code means for causing the computer to update said frequency data to maintain accuracy of said frequency data during compilation in a direction of increasing exactness of frequency data based on the transformed intermediate representation caused by the optimization; and fifth computer readable program code means for causing the computer to re-execute said third and fourth computer readable program code means at least once during the same compilation pass. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method for compile-time optimization comprising:
-
(a) accessing a first intermediate representation of source code of a computer program, wherein the first intermediate representation includes instructions instrumented into the source code; (b) annotating the first intermediate representation with previously-gathered global and local frequency data from a plurality of sample executions of the computer program; (c) performing an optimization of the first intermediate representation annotated with the global and local frequency data to produce a transformed intermediate representation; (d) updating said local frequency data to maintain accuracy of said local frequency data during compilation in a direction of increasing exactness of local frequency data based on the transformed intermediate representation caused by the optimization; and (e) repeating steps (c) and (d) at least once during the same compilation pass. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A method for compile-time optimization comprising:
-
(a) accessing a first intermediate representation of source code of a computer program, wherein the first intermediate representation includes instructions instrumented into the source code; (b) annotating the first intermediate representation with previously-gathered frequency data from a plurality of sample executions of the computer program; (c) performing an optimization of the first intermediate representation annotated with the frequency data to produce a transformed intermediate representation; (d) updating said frequency data to maintain accuracy of said frequency data during compilation in a direction of increasing exactness of frequency data based on the transformed intermediate representation caused by the optimization; and (e) repeating steps (c) and (d) at least once during the same compilation pass. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
44. A method for compile-time optimization comprising the steps of:
-
(a) accessing a first intermediate representation of source code of a computer program, wherein the first intermediate representation includes instructions instrumented into the source code; (b) annotating the first intermediate representation with previously-gathered estimated frequency data from a plurality of sample executions of the computer program; (c) performing an optimization of the first intermediate representation annotated with the estimated frequency data to produce a transformed intermediate representation; (d) updating said estimated frequency data to maintain accuracy of said estimated frequency data during compilation in a direction of increasing exactness of frequency data based on the transformed intermediate representation caused by the optimization; and (e) repeating steps (c) and (d) at least once during the same compilation pass.
-
-
45. A method for precise feedback data generation and updating during compile-time optimizations, within an optimizing compiler, comprising:
-
(a) accessing an intermediate representation of source code of a computer program, wherein the intermediate representation includes instructions instrumented into the source code; (b) annotating the intermediate representation with frequency data from a plurality of executions of the computer program; (c) performing an optimization to produce a transformed intermediate representation; (d) re-annotating the transformed intermediate representation, wherein step (d) comprises; (i) constructing a control flow graph, wherein said control flow graph includes a plurality of nodes representing portions of the transformed intermediate representation, wherein said control flow graph further includes a plurality of edges, each edge representing a relationship between one of the nodes to another node; (ii) applying available frequency data to an edge to set an incoming edge frequency or an outgoing edge frequency for a node; (iii) propagating a known edge frequency to set an unknown edge frequency for a node; and (iv) re-annotating the transformed intermediate representation with the edge frequencies from the control flow graph; and (v) repeating steps (c) and (d), at least once during the same compilation pass, wherein step (c) includes performing an optimization of the re-annotated transformed intermediate representation from step (d) to produce a transformed intermediate representation for re-annotating at a subsequent execution of step (d). - View Dependent Claims (46, 47, 48)
-
-
49. A method for precise feedback data generation and updating during compile-time optimizations, within an optimizing compiler, comprising:
-
(a) accessing an intermediate representation of source code of a computer program, wherein the intermediate representation includes instructions instrumented into the source code; (b) annotating the intermediate representation with frequency data from a plurality of executions of the computer program; (c) performing an optimization to produce a transformed intermediate representation; (d) re-annotating and verifying the re-annotation of the transformed intermediate representation; and (e) repeating steps (c) and (d), at least once during the same compilation pass, wherein step (c) includes performing an optimization of the re-annotated transformed intermediate representation from step (d) to produce a transformed intermediate representation for re-annotating at a subsequent execution of step (d). - View Dependent Claims (50, 51)
-
Specification