Method and apparatus for managing profile data

• US 5,768,592 A
• Filed: 09/27/1994
• Issued: 06/16/1998
• Est. Priority Date: 09/27/1994
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chang, Pohua
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/313,455
• Time in Patent Office: 1,358 Days
• Field of Search: 395/600, 395/700, 395/183.11, 395/183.14, 395/704, 395/705
• US Class Current: 438/758
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A heuristic prediction method of generating profile information for compilers in a computer system that associates profile information to attribute-vectors of a source code derived from observation points in the code during compilation. The prediction method of the present invention enables the compiler to predict the code run-time behavior even before the code has been compiled, therefore providing an ideal way to maintain profile information. In addition to heuristically predicting code run-time behavior, the compiler of the present invention includes features that allow the compiler user to generate profile information of code being compiled using conventional profile generation methods.

Claims

1. In a computer system having a compiler for compiling source code, a method for developing and providing a heuristic predicting compiler for predicting run-time behavior of source code being compiled comprising the steps of:

(a) compiling a plurality of source programs;

(b) generating profile data for each said plurality of programs compiled;

(c) generating attribute-vectors for each said programs compiled;

(d) forming rules responsive to said attribute-vectors generated for each of said compiled programs and said profile data corresponding to each of said compiled programs; and

(e) creating a database of said rules, wherein said database is incorporated in said compiler to predict said run-time behavior of programs being compiled.

2. The method of claim 1, wherein said plurality of programs includes a plurality of program categories including scientific, non-scientific, integer, and non-integer categories, and wherein a separate database of rules is created responsive to attribute-vectors and profile data from programs in each of said program categories.

3. The method of claim 1, wherein said step (c) includes the steps of:

(c1) determining loop nesting levels of a basic block in each of said compiled programs;

(c2) determining loop depth levels of said basic block in each of said compiled programs;

(c3) determining "if-statements" nesting levels in each of said programs being compiled;

(c4) determining said "if-statement" depth levels in each of said programs being compiled;

(c5) determining the size of a loop body;

(c6) determining the direction of a branch instruction in each of said programs being compiled; and

(c7) determining the contents of each of said programs being compiled.

4. The method of claim 3, wherein upon completing said step (c) each said steps further includes consolidating the data from said steps to generate a static attribute-vector of said program being compiled.

5. The method of claim 1, wherein said step (d) includes a step of mapping said attribute-vectors generated for each of said programs with a corresponding profile data to form a rule comprising an attribute-vector and associating profile data.

6. The method of claim 1, wherein said step (e) includes a step of concatenating a list of said rules and combining said rules with the same attribute-vector to form a single rule.

7. The method of claim 1, wherein said step (e) further includes a step of creating a predictor responsive to said rules, by creating a hash table of said rules, so that said predictor uses said attribute-vector as an index to said hash table to determine whether said run-time behavior of said compiled program matches said rules.

8. In a computer system, a method for compiling source code comprising the steps of:

(a) identifying observation points in said source code;

(b) assigning one or more attribute-vectors to said observation points, wherein said assigned attribute-vectors uniquely identify said observation points;

(c) comparing said attribute-vectors of said code with rules in a heuristic predictor table comprising a map of attribute-vectors with accompanying profile data;

(d) if said attribute-vectors of said code in said step (c) matches said rules in said predictor table, said profile data for said attribute-vectors of said code are predicted; and

(e) if said attribute-vectors in said step (c) mismatches said rules in said predictor table, said code is then compiled using an alternate method of profiling.

9. The method of claim 8, wherein said observation points includes program entities including basic blocks, branch statements, and control flow statements.

10. The method of claim 8 further comprising the step of selecting a switch to alternately compile said code using said alternate method of compiling of said compiler.

11. The method of claim 8, wherein said alternate method of compiling comprises the step of profiling said code to generate rules specific to said code so that said rules a reused in subsequent compilation of said code.

12. A heuristic predicting compiler for predicting the run-time behavior of source programs being compiled by said compiler comprising:

(a) a heuristic predicting means for heuristically predicting run-time behavior of source programs, said heuristic predicting means including generating means for generating attribute vectors responsive to each of said source program;

(b) a switching logic means for allowing said compiler to alternate between said predicting means and an alternate means of generating profile data for said program being compiled; and

(c) a logic circuit means for conventionally generating profile data for said source program responsive to said predicting means mispredicting said run-time behavior of said source program, said logic circuit means includes a rule creating means for creating rules responsive to said conventionally compiled source program, and wherein said rules are used in subsequent compilation of said source program by said compiler.

13. The compiler of claim 12 wherein said heuristic predicting means comprises:

(a1) a mapping means for mapping said attribute-vectors generated for each of said source programs to a corresponding profile data of each of said source program to form a rule;

(a2) a merging means for merging said rules with the same attribute-vector into a single rules list; and

(a3) a predictor generation means for generating a heuristic predictor responsive to said source programs, wherein said predictor is created from a hash table of said rules using said attribute-vector as an index.

14. The compiler of claim 12, wherein said logic circuit means further includes a code modification option means for allowing minor source program changes without having to instrument said source program.

15. A heuristic profile prediction compiler for predicting run-time behavior of source programs being compiled, said compiler comprising:

(a) a heuristic predictor for predicting said run-time behavior of said source program, (b) attribute-vectors responsive to static program regions of said source program;

(c) a logic switch circuit for allowing said compiler alternate between a heuristic predicting mode and a conventional compilation mode; and

(d) a conventional profile data generating circuit for conventionally generating profile data of said source program in response to said predictor failing to predict said run-time behavior of said source program, wherein said conventional profile data generating circuit includes a database of execution counter values of said source program, and wherein said counter values are used as said compiler directives in subsequent source program compilations.

16. The compiler of claim 15, wherein said heuristic predictor comprises:

(a1) a rule responsive to a pair of said attribute-vectors and profile data responsive to said source program; and

(a2) a database of said rules responsive to merging said rules from a variety of said source programs with the same attribute-vectors, wherein a hash table of said predictor is formed responsive to concatenating said database of said rule.

17. In a computer system having a compiler, a method for developing and providing a heuristic predictor for predicting run-time behavior of programs being compiled, the method comprising the steps of:

(a) compiling a variety of programs within different programming categories to generate profile data and static attribute-vectors responsive to each of said compiled programs;

(b) generating said heuristic predictor based on said compiled variety of programs, said heuristic predictor being incorporated into said compiler to predict said run-time behavior of programs, the generating of said heuristic predictor including the step of creating a rules list from said compiled programs, said step of creating rules including;

(b1) mapping said attribute-vector, for code entities including basic blocks, branch instructions, and control flow statements, within each of said programs with said profile data for each of said compiled programs into an attribute-vector, profile data pair;

(b2) forming a rule by consolidating said profile data from each of said variety of programs associated with the same attribute-vector;

(b3) merging rules from said variety of programs by concatenating said rules and combining rules with the same attribute-vectors;

(b4) creating a hash table of said rules using said attribute-vectors as indices; and

(b5) creating said predictor based on a database of said rules from said hash table responsive to said compiled programs to predict subsequent run-time behavior of programs compiled by said compiler.

18. A heuristic predicting compiler for predicting the run-time behavior of source programs being compiled by said compiler comprising:

(a) heuristic predicting means for heuristically predicting run-time behavior of source programs, said heuristic predicting means comprising,

(a1) generating means for generating attribute vectors responsive to each of said source programs,

(a2) mapping means for mapping said attribute-vectors generated for each of said source programs to a corresponding profile data of each of said source program to form a rule,

(a3) merging means for merging said rules with the same attribute-vector into a rules list,

(a4) predictor generation means for generating a heuristic predictor responsive to said source programs, wherein said heuristic predictor is created from a hash table of said rules using said attribute-vector as an index;

(b) switching logic means for allowing said compiler to alternate between said predicting means and an alternate means of generating profile data for said program being compiled; and

(c) logic circuit means for conventionally generating profile data for said source program responsive to said predicting means mispredicting said run-time behavior of said source program.

19. The compiler of claim 18, wherein said logic circuit means includes a rule creating means for creating rules responsive to said conventionally compiled source program, and wherein said rules are used in subsequent compilation of said source program by said compiler.

20. The compiler of claim 18, wherein said logic circuit means includes a code modification option means for allowing minor source program changes without having to instrument said source program.

21. A heuristic profile prediction compiler for predicting run-time behavior of source programs being compiled, said compiler comprising:

(a) a heuristic predictor for predicting said run-time behavior of said source program, said heuristic predictor comprising,

(a1) attribute-vectors responsive to static program regions of said source program,

(a2) a rule responsive to a pair of said attribute-vectors and profile data responsive to said source program,

(a3) a database of said rules merged from a variety of source programs with same attribute-vectors, wherein the predictor is based on said database of said rules from a hash table;

(b) a logic switch circuit for allowing said compiler to alternate between said heuristic predicting mode and a conventional compilation mode; and

(c) a conventional profile data generating circuit for conventionally generating profile data of said source program in response to said predictor failing to predict said run-time behavior of said source program.

22. The compiler of claim 21, wherein said conventional profile data generating circuit includes a database of execution counter values of said source program, and wherein said counter values are used as compiler directives in subsequent source program compilations.

23. In a computer system having a compiler for compiling source code, a method for developing and providing a heuristic predicting compiler for predicting run-time behavior of source code being compiled comprising the steps of:

(a) compiling a plurality of source programs;

(b) generating profile data for each said plurality of programs compiled;

(c) generating attribute-vectors for each said programs compiled; and

(d) forming rules responsive to said attribute-vectors generated for each of said compiled programs and said profile data corresponding to each of said compiled programs.

24. The method of claim 23, wherein said plurality of programs includes a plurality of program categories including scientific, non-scientific, integer, and non-integer categories, and wherein a separate database of rules is created responsive to attribute-vectors and profile data from programs in each of said program categories.

25. The method of claim 23, wherein said step (c) includes the steps of:

(c1) determining loop nesting levels of a basic block in each of said compiled programs;

(c2) determining loop depth levels of said basic block in each of said compiled programs;

(c3) determining "if-statements" nesting levels in each of said programs being compiled;

(c4) determining said "if-statement" depth levels in each of said programs being compiled;

(c5) determining the size of a loop body;

(c6) determining the direction of a branch instruction in each of said programs being compiled; and

(c7) determining the contents of each of said programs being compiled.

26. The method of claim 25, wherein upon completing said step (c) each said steps further includes consolidating the data from said steps to generate a static attribute-vector of said program being compiled.

27. The method of claim 23, wherein said step (d) includes a step of mapping said attribute-vectors generated for each of said programs with a corresponding profile data to form a rule comprising an attribute-vector and associating profile data.

28. The method of claim 23, wherein upon completing step (d) further includes a step (e) of creating a database of said rules, wherein said database is incorporated in said compiler to predict said run-time behavior of programs being compiled.

29. The method of claim 28, wherein said step (e) includes a step of concatenating a list of said rules and combining said rules with the same attribute-vector to form a single rule.

30. The method of claim 28, wherein said step (e) further includes a step of creating a predictor responsive to said rules, by creating a hash table of said rules, so that said predictor uses said attribute-vector as an index to said hash table to determine whether said run-time behavior of said compiled program matches said rules.