Method and apparatus for hierarchical restructuring of computer code

• US 6,381,739 B1
• Filed: 05/15/1996
• Issued: 04/30/2002
• Est. Priority Date: 05/15/1996
• Status: Expired due to Fees

• Current Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Smith, Roger A., Breternitz, Mauricio Jr.
• Primary Examiner(s): Millin, Vincent
• Assistant Examiner(s): Nguyen, Cuong H.
• Application Number:
  US08/647,862
• Time in Patent Office: 2,176 Days
• Field of Search: 395/705-706, 395/707-709, 395/800.25, 395/377, 395/800.36, 395/183.14, 395/580, 395/800.26, 395/800.27, 395/183.22, 395/583, 345/441, 717/8, 714/37, 714/38
• US Class Current: 714/37
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A compiler (142) constructs (FIGS. 14-32) a Reduced Flowgraph (RFG) from computer source code (144). The RFG is used to instrument (FIG. 36) code (142). An object module is created (146) and executed (148). Resulting path frequency counts are written to a counts file (154). A compiler (158) uses the source code (144) and the generated counts to identify runtime correlations between successive path edges and Superedges. An object module (159) is generated containing reordered (156) code generated to optimize performance based on the runtime correlations. If cloning is enabled (152), high frequency path edges are cloned (154) or duplicated to minimize cross edge branching.

Claims

1. A computer-implemented method for hierarchical restructuring of computer code using runtime statistics, said method comprising:

a) building a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions corresponding to execution flow of a computer program, wherein building comprises;

replacing an SESE region of the CFG with an edge, wherein the edge describes a structure of the SESE region;

b) creating a first executable, which comprises;

1) inserting a plurality of instrumentation instructions into the computer program utilizing the hierarchical representation;

c) executing the first executable, wherein;

one or more of the plurality of instrumentation instructions generates path correlation counts during execution of the first executable;

d) creating a second executable, which comprises;

1) reordering computer code utilizing the path correlation counts.

2. The method in claim 1 wherein step (d) further comprises:

2) cloning segments of computer code.

3. The method in claim 1 wherein within substep (1) of step (d):

the reordering utilizes a second hierarchical representation of the Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions.

4. The method in claim 1 wherein the hierarchical representation is additionally in terms of Single Entry/Zero Exit (SEZE) regions.

5. The method in claim 1 which further comprises:

e) reading into a memory the computer program as source code stored on secondary storage media.

6. The method in claim 1 which further comprises:

e) reading into a memory the computer program as object code stored on secondary storage media.

7. The method in claim 1 wherein step (d) further comprises:

2) storing the second executable on secondary storage.

8. An external storage media containing the second executable created by the method claimed in claim 1 encoded in machine readable form.

9. The method in claim 1, wherein at least one of the path correlation counts corresponds to at least two execution paths of the computer program.

10. The method in claim 9, wherein the at least two execution paths are nonadjacent execution paths.

11. The method in claim 4, wherein building further comprises replacing an SESE/SEZE chain of the CFG with a second edge, wherein the second edge describes a structure of the SESE/SEZE chain.

12. The method in claim 1, wherein the CFG may not be a strongly connected flowgraph.

13. The method in claim 1, wherein the CFG includes at least one 1-reducible edge.

14. The method in claim 1, wherein the hierarchical representation includes both nesting properties and full control flow information of the CFG.

15. A software sequencer stored via computer readable media, said computer readable media comprising:

a first plurality of computer instructions for building a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions corresponding to execution flow of a computer program, wherein the first plurality of computer instructions comprises;

a second plurality of computer instructions for replacing an SESE region of the CFG with an edge, wherein the edge describes a structure of the SESE region;

a third plurality of computer instructions for creating a first executable, which comprises inserting a plurality of instrumentation instructions into the computer program utilizing the hierarchical representation;

a fourth plurality of computer instructions for executing the first executable, wherein one or more of the plurality of instrumentation instructions generates path correlation counts during execution of the first executable; and

a fifth plurality of computer instructions for creating a second executable, which comprises reordering computer code utilizing the path correlation counts.

16. The software sequencer of claim 15, wherein each of the plurality of computer instructions includes object code.

17. A computer-implemented method for instrumenting computer code, said method comprising:

a) utilizing a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) and Single Entry/Zero Exit (SEZE) regions corresponding to execution flow of a computer program to identify a location in the computer program at which to insert instrumentation as an identified location, wherein at least one edge of the hierarchical representation replaces an SESE region of the CFG and the hierarchical representation includes nesting properties and full control flow information of the CFG; and

b) inserting one or more instrumentation instructions at the identified location in the computer program.

18. The method in claim 17 which further comprises:

c) building the hierarchical representation of the Control Flow Graph (CFG).

19. The method in claim 17 wherein:

the hierarchical representation is a Reduced FlowGraph (RFG).

20. The method in claim 17 which further comprises:

c) reading into a memory the computer program as source code stored on secondary storage media.

21. The method in claim 17 which further comprises:

c) reading into a memory the computer program as object code stored on secondary storage media.

22. The method in claim 17 which further comprises:

c) creating an executable that includes the one or more instrumentation instructions; and

d) storing the executable on secondary storage.

23. The method in claim 22 which further comprises:

e) executing the executable, wherein;

one or more of the instrumentation instructions generates a set of path correlation counts during execution of the executable; and

f) storing the set of path correlation counts to secondary storage.

24. The method in claim 23 which further comprises:

f) creating a second executable, which comprises;

l) reordering computer code utilizing the set of path correlation counts.

29. The method in claim 21 which further comprises:

b) reading one or more path correlation counts stored on secondary storage media.

25. A computer-implemented method for laying out computer code for improved data processor execution, said method comprising:

a) utilizing a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions corresponding to execution flow of a computer program to determine code layout for the computer program, and wherein at least one edge of the hierarchical representation replaces an SESE region of the CFG and the hierarchical representation includes nesting properties and fill control flow information of the CFG.

26. The method in claim 25 wherein the hierarchical representation is additionally in terms of Single Entry/ZeroExit (SEZE) regions.

27. The method in claim 25 which further comprises:

b) building the hierarchical representation of the Control Flow Graph (CFG).

28. The method in claim 25 wherein:

the hierarchical representation is a Reduced FlowGraph (RFG).

30. The method in claim 25 wherein within step (a):

one or more path correlation counts are utilized to reorder code.

31. The method in claim 25 which further comprises:

b) creating a computer program executable based on code layout in step (a); and

c) writing the computer program executable to Secondary Storage.

32. An external storage medium containing the computer program executable created using the method claimed in claim 31 encoded in machine readable format.

33. A computer-implemented method for cloning computer code for improved data processor execution, said method comprising:

a) utilizing a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions corresponding to execution flow of a computer program to identify a segment of code in the computer program to clone, wherein at least one edge of the hierarchical representation replaces an SESE region of the CFG and the hierarchical representation includes nesting properties and full control flow information of the CFG; and

b) cloning the segment of code identified in step (a) by duplicating the segment of code.

34. The method in claim 33 wherein:

the hierarchical representation is a Reduced FlowGraph (RFG).

35. The method in claim 33 which further comprises:

c) building the hierarchical representation of the Control Flow Graph (CFG) utilized in step (a).

36. The method in claim 33 wherein the hierarchical representation is additionally in terms of Single Entry/Zero Exit (SEZE) regions.

37. The method in claim 33 which further comprises:

b) creating an computer program executable that includes the segment of code cloned in step (b); and

c) writing the computer program executable to secondary storage.

38. The method in claim 33 which further comprises:

b) reading one or more path correlation counts stored on secondary storage media.

39. An external storage medium containing the computer program executable created using the method claimed in claim 37 encoded in machine readable format.

40. The method in claim 38 wherein within step (a):

one or more path correlation counts are utilized to identify the segment of code to clone.

41. A computer-implemented method for analyzing a control flowgraph, said method comprising:

partitioning the flowgraph into Single Entry/Single Exit (SESE) regions; and

representing the flowgraph using a hierarchical structure, wherein each of said SESE regions in the flowgraph is replaced with an edge which describes a structure of each of said SESE regions.

42. The method of claim 41, wherein said partitioning is further characterized by transforming the flowgraph into canonical SESE regions.

43. The method of claim 41, wherein said partitioning further comprises partitioning the flowgraph into Single Entry/Zero Exit (SEZE) regions.

44. The method of claim 41, wherein said partitioning the flowgraph further includes node splitting.

45. The method of claim 41, wherein said representing the flowgraph further includes node splitting.

46. The method of claim 41, wherein said flowgraph is a strongly connected flowgraph.

47. The method of claim 41, wherein said flowgraph is a not strongly connected flowgraph.

48. The method in claim 41, wherein the control flowgraph may not be a strongly connected flowgraph.

49. The method in claim 41, wherein the control flowgraph includes at least one 1-reducible edge.

50. A computer-implemented method for hierarchical restructuring of computer code using runtime statistics, said method comprising:

a) building a hierarchical representation of a Control Flow Graph (CFG) in terms of Single Entry/Single Exit (SESE) regions corresponding to execution flow of a computer program;

b) creating a first executable, which comprises;

1) inserting a plurality of instrumentation instructions into the computer program utilizing the hierarchical representation;

c) executing the first executable, wherein;

one or more of the plurality of instrumentation instructions generates path correlation counts during execution of the first executable, wherein at least one of the path correlation counts corresponds to at least two execution paths of the computer program;

d) creating a second executable, which comprises;

1) reordering computer code utilizing the path correlation counts.

51. The method in claim 50, wherein the at least two execution paths are nonadjacent execution paths.