US 7,120,906 B1 · Method and computer program product for precise feedback data generation and updating for compile-time optimizations

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.

Claims51

Dependent claims

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.

3 more elements

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.

3 more elements

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).

8 more elements

Dependencies are inferred from the claim text.

Method and computer program product for precise feedback data generation and updating for compile-time optimizations

Life of this patent

Method and computer program product for precise feedback data generation and updating for compile-time optimizations

Life of this patent

Abstract

Claims51