US5978588A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for profile-based code placement using a minimum cut set of the control flow graph
Assignee: Oracle America Inc
•
Filing: 1997-06-30
•
Granted: 1999-11-02
•
Expires: 2017-06-30
Abstract
Abstract A method and apparatus placing blocks of object code by a compiler. The code placement is done optimally, using a "cut set technique" that uses the "max-flow/min-cut" principle. A preferred embodiment of the present invention divides a source program into blocks and generates a control flow graph (cfg) and a data flow graph (dfg) for the blocks. The compiler then identifies the strongly connected components (sccs) of the dfg and recursively breaks down the cycles in each scc to yield a plurality of directed acyclic graphs (dfg-dag's). The compiler then finds the "minimum cut set" in the cfg corresponding to each dfg-dag and moves the code into blocks in accordance with the minimum cut sets. Lastly, the compiler generates object code for the blocks.
Inventors
- 👤 David R. Wallace
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 22:56
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
92 words
A method of compiling a source program into an object program and of optimally placing code blocks of the source program, the steps performed by a data processing system, of: receiving the source program; dividing the source program into source program blocks; determining a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; finding a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and moving computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 2
Independent Claim
92 words
A method of compiling a source program into an object program and of optimally placing code blocks of the source program, the steps performed by a data processing system, of: receiving the source program; dividing the source program into source program blocks; determining a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; finding a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and moving computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 3
Dependent Claim
163 words
A computer program product including: a computer usable medium having computer readable code embodied therein for causing compilation of a source program into an object program and of optimally placing code blocks of the source program, the computer program product comprising: computer readable program code devices configured to cause a computer to effect receiving the source program; computer readable program code devices configured to cause a computer to effect dividing the source program into source program blocks; computer readable program code devices configured to cause a computer to effect determining a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; computer readable program code devices configured to cause a computer to effect finding a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and computer readable program code devices configured to cause a computer to effect moving computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 4
Dependent Claim
163 words
A computer program product including: a computer usable medium having computer readable code embodied therein for causing compilation of a source program into an object program and of optimally placing code blocks of the source program, the computer program product comprising: computer readable program code devices configured to cause a computer to effect receiving the source program; computer readable program code devices configured to cause a computer to effect dividing the source program into source program blocks; computer readable program code devices configured to cause a computer to effect determining a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; computer readable program code devices configured to cause a computer to effect finding a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and computer readable program code devices configured to cause a computer to effect moving computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 5
Dependent Claim
132 words
A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause said processor to compile a source program into an object program, optimally placing code blocks of the source program, by performing the steps of: executing a computer program to receive the source program; executing the computer program to divide the source program into source program blocks; executing the computer program to determine a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; executing the computer program to find a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and executing the computer program to move computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 6
Dependent Claim
132 words
A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause said processor to compile a source program into an object program, optimally placing code blocks of the source program, by performing the steps of: executing a computer program to receive the source program; executing the computer program to divide the source program into source program blocks; executing the computer program to determine a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; executing the computer program to find a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and executing the computer program to move computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 7
Independent Claim
104 words
An apparatus that compiles a source program into an object program and that optimally places code blocks of the source program, comprising: a portion configured to receive the source program; a portion configured to divide the source program into source program blocks; a portion configured to determine a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; a portion configured to find a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and a portion configured to move computer instructions between the source code blocks in accordance with the minimum cut set.
Claim 8
Independent Claim
104 words
An apparatus that compiles a source program into an object program and that optimally places code blocks of the source program, comprising: a portion configured to receive the source program; a portion configured to divide the source program into source program blocks; a portion configured to determine a control flow graph, a data flow graph, and a plurality of dfg-dag's for the source program; a portion configured to find a minimum cut set in a control flow graph generated in accordance with the dfg-dag's; and a portion configured to move computer instructions between the source code blocks in accordance with the minimum cut set.
References Cited (Backward Citations)
US5555201A
Cited
US5666296A
Cited
US5557761A
Cited
US5850552A
Cited
US5787287A
Cited
US5894576A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |