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

• US 7,120,906 B1
• Filed: 04/28/2000
• Issued: 10/10/2006
• Est. Priority Date: 04/28/2000
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Stephenson, David L., Lo, Raymond, Chan, Sun, Ho, Wilson, Murthy, Chandrasekhar
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Wood, William H.
• Application Number:
  US09/560,555
• Time in Patent Office: 2,356 Days
• Field of Search: 717130-132, 717144-146, 717151-161, 717/140
• US Class Current: 717/158
• CPC Class Codes: G06F 8/443 Optimisation

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.

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.

2. The method of claim 1, wherein step (c) comprises the step of performing at least one of the following optimizations:

(i) dead code elimination;

(ii) dead store elimination;

(iii) branch elimination; and

(iv) code transformation.

3. The method of claim 1, wherein said first intermediate representation is a tree corresponding to a procedure within the source code of said computer program.

4. The method of claim 3, wherein step (b), comprises the steps of:

(i) constructing a control flow graph from said tree; and

(ii) annotating a frequency value to an edge of said control flow graph, wherein said frequency value corresponds to the number of times that said edge was traversed during said plurality of sample executions of said computer program.

5. The method of claim 4, wherein said frequency value annotated to said edge of said control flow graph is one of the following:

(a) EXACT;

(b) GUESS;

(c) UNKNOWN;

(d) UNINIT; and

(e) ERROR.

6. The method of claim 1, wherein said frequency data comprises both inexact and exact values.

7. The method of claim 1, wherein step (d) updates said frequency data from GUESS to EXACT values.

8. The method of claim 1, wherein step (d) updates said frequency data from UNKNOWN to GUESS values.

9. The method of claim 1, wherein step (d) updates said frequency data from UNINIT to GUESS values.

10. The method of claim 1, wherein said optimization is performed in a direction of decreasing exactness.

11. The method of claim 1, wherein said optimization is performed locally, and the updating is performed globally.

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.

13. The computer program product of claim 12, wherein said first intermediate representation is a tree corresponding to a procedure within the source code of said computer program.

14. The computer program product of claim 13, wherein said second computer readable program code means comprises:

sixth computer readable program code means for causing the computer to construct a control flow graph from said tree; and

seventh computer readable program code means for causing the computer to annotate a frequency value to an edge of said control flow graph, wherein said frequency value corresponds to the number of times that said edge was traversed during said plurality of sample executions of said computer program.

15. The product of claim 12, wherein said frequency data comprises both inexact and exact values.

16. The product of claim 12, wherein said fourth computer readable program code means includes:

computer readable program code means for causing the computer to update said frequency data from GUESS to EXACT values.

17. The product of claim 12, wherein said fourth computer readable program code means includes:

computer readable program code means for causing the computer to update said frequency data from UNKNOWN to GUESS values.

18. The product of claim 12, wherein said fourth computer readable program code means includes:

computer readable program code means for causing the computer to update said frequency data from UNINIT to GUESS values.

19. The product of claim 12, wherein said optimization is performed in a direction of decreasing exactness.

20. The product of claim 12, wherein said optimization is performed locally, and the updating is performed globally.

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.

22. The method of claim 21, wherein step (c) comprises the step of performing at least one of the following optimizations:

(i) dead code elimination;

(ii) dead store elimination;

(iii) branch elimination; and

(iv) code transformation.

23. The method of claim 21, wherein the first intermediate representation is a tree corresponding to a procedure within the source code.

24. The method of claim 23, wherein step (b) comprises the steps of:

(i) constructing a control flow graph from the tree; and

(ii) annotating a global or local frequency value of the global and local frequency data to an edge of the control flow graph, wherein the global or local frequency value corresponds to the number of times that the edge was traversed during the plurality of sample executions of the computer program.

25. The method of claim 24, wherein the global and local frequency value annotated to the edge of the control flow graph is one of the following:

(a) EXACT;

(b) GUESS;

(c) UNKNOWN;

(d) UNINIT; and

(e) ERROR.

26. The method of claim 21, wherein said frequency data comprises both inexact and exact values.

27. The method of claim 21, wherein step (d) updates said frequency data from GUESS to EXACT values.

28. The method of claim 21, wherein step (d) updates said frequency data from UNKNOWN to GUESS values.

29. The method of claim 21, wherein step (d) updates said frequency data from UNINIT to GUESS values.

30. The method of claim 21, wherein said optimization is performed in a direction of decreasing exactness.

31. The method of claim 21, wherein said optimization is performed locally, and the updating is performed globally.

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.

33. The method of claim 32, wherein step (c) comprises the step of performing at least one of the following optimizations:

(i) dead code elimination;

(ii) dead store elimination;

(iii) branch elimination; and

(iv) code transformation.

34. The method of claim 32, wherein the first intermediate representation is a tree corresponding to a procedure within the source code.

35. The method of claim 34, wherein step (b) comprises the steps of:

(i) constructing a control flow graph from the tree; and

(ii) annotating a global or local frequency value of the global and local frequency data to an edge of the control flow graph, wherein the global or local frequency value corresponds to the number of times that the edge was traversed during the plurality of sample executions of the computer program.

36. The method of claim 35, wherein the global or local frequency value annotated to the edge of the control flow graph is one of the following:

(a) EXACT;

(b) GUESS;

(c) UNKNOWN;

(d) UNINIT; and

(e) ERROR.

37. The method of claim 35, wherein the global or local frequency value annotated to the edge of the control flow graph is one of the following:

(a) GUESS; and

(b) UNKNOWN.

38. The method of claim 32, wherein said frequency data comprises both inexact and exact values.

39. The method of claim 32, wherein step (d) updates said frequency data from GUESS to EXACT values.

40. The method of claim 32, wherein step (d) updates said frequency data from UNKNOWN to GUESS values.

41. The method of claim 32, wherein step (d) updates said frequency data from UNINIT to GUESS values.

42. The method of claim 32, wherein said optimization is performed in a direction of decreasing exactness.

43. The method of claim 32, wherein said optimization is performed locally, and the updating is performed globally.

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

46. The method of claim 45, wherein step (d)(iii) comprises:

(a) setting an unknown edge frequency for an outgoing edge to a difference between a sum of all known incoming edge frequencies and a sum of all known outgoing edge frequencies when all incoming edge frequencies are known and all but one of the outgoing edge frequencies are known;

(b) setting an unknown edge frequency for an incoming edge to a difference between a sum of all known outgoing edge frequencies and a sum of all known incoming edge frequencies when all outgoing edge frequencies are known and all but one of the incoming edge frequencies are known;

(c) setting an unknown edge frequency for an outgoing edge to zero when all incoming edge frequencies are exact values and the sum of all incoming edge frequencies equals the sum of all outgoing edge frequencies; and

(d) setting an unknown edge frequency for an incoming edge to zero when all outgoing edge frequencies are exact values and the sum of all outgoing edge frequencies equals the sum of all incoming frequencies.

47. The method of claim 45, wherein step (d)(iii) comprises:

denoting a node as being a non-exception node when the total incoming edge frequency and the total outgoing edge frequency for the node are required to be equal.

48. The method of claim 47, wherein step (d)(iii) is only executed on the non-exception node.

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

50. The method of claim 49, wherein step (d) comprises:

evaluating a portion of the transformed intermediate representation to classify a corresponding frequency data annotation as being uninitialized or invalid.

51. The method of claim 49, wherein step (d) comprises:

evaluating a portion of the transformed intermediate representation to classify a corresponding frequency data annotation as being exact, estimated, or unknown.