Method and apparatus for hierarchical restructuring of computer code
AssigneeMotorola, Inc.
InventorsMauricio Breternitz, Jr., Roger A. Smith
Life of this patent
Estimating the term…
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.
Claims51
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.
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.