US5950009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for profile-based reordering of program portions in a computer program
Assignee: International Business Machines Corp
•
Filing: 1997-03-10
•
Granted: 1999-09-07
•
Expires: 2017-03-10
Abstract
Abstract An apparatus and several methods provide for a more optimized computer program that will have a faster execution time than was possible using the prior art reordering technique that adds to a trace until it finds no more predecessors or successors to add. The apparatus and methods disclosed herein use a variety of methods to reorder the program portions in a more intelligent manner that will improve its run-time performance. Each of these methods involves constructing traces in the control flow graph of the computer program. In a first embodiment, a basic block is only added to a trace if it is not negligible within predetermined limits. This negligibility test results in traces that are not extended for infrequently executed basic blocks. In a second embodiment, a basic block is only added to a trace if it is a perfect partner with the last basic block added to the trace. The concept of a "perfect partner" helps to match basic blocks together in a trace that have the greatest affinity for each other. In a third embodiment, a basic block is only added to a trace if it satisfies "should follow" flags and predetermined negligibility criteria. The "should follow" flags and negligibility criteria provide a complex criteria for adding basic blocks to a trace, criteria that create more efficient code in some specific circumstances.
Inventors
- 👤 Vita Bortnikov
- 👤 Bilha Mendelson
- 👤 Mark Novick
- 👤 William Jon Schmidt
- 👤 Inbal Shavit-Lottem
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 23:22
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
198 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a computer program residing in the memory comprising a plurality of portions joined by a plurality of program paths; profile data residing in the memory representing the execution frequency of at least one of the plurality of program paths within the computer program; a reordering mechanism residing in the memory and executed by the at least one processor for determining an order for the plurality of portions of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along the plurality of program paths through at least one of the plurality of portions, the reordering mechanism placing the at least one portion in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists.
Claim 2
Independent Claim
198 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a computer program residing in the memory comprising a plurality of portions joined by a plurality of program paths; profile data residing in the memory representing the execution frequency of at least one of the plurality of program paths within the computer program; a reordering mechanism residing in the memory and executed by the at least one processor for determining an order for the plurality of portions of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along the plurality of program paths through at least one of the plurality of portions, the reordering mechanism placing the at least one portion in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists.
Claim 3
Dependent Claim
52 words
The apparatus of claim 1 wherein the reordering mechanism orders the plurality of traces, the reordering mechanism determining the order for the plurality of portions of the computer program from the order of creation of the plurality of traces and the order of the plurality of portions within the plurality of traces.
Claim 4
Dependent Claim
20 words
The apparatus of claim 1 wherein each of the plurality of portions of the computer program comprises a basic block.
Claim 5
Independent Claim
175 words
A method for improving execution speed of a computer program on a computer apparatus by reordering a plurality of program portions in a computer program, the method comprising the step of: constructing a plurality of traces, each trace comprising at least one of the plurality of portions, the step of constructing each trace comprising the steps of: adding a portion to the trace in an order determined by: (1) profile data; and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists; ordering the plurality of traces according to their order of creation; and reordering the plurality of portions of the computer program from the order of the plurality of traces and the order of the plurality of portions within the plurality of traces.
Claim 6
Independent Claim
175 words
A method for improving execution speed of a computer program on a computer apparatus by reordering a plurality of program portions in a computer program, the method comprising the step of: constructing a plurality of traces, each trace comprising at least one of the plurality of portions, the step of constructing each trace comprising the steps of: adding a portion to the trace in an order determined by: (1) profile data; and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists; ordering the plurality of traces according to their order of creation; and reordering the plurality of portions of the computer program from the order of the plurality of traces and the order of the plurality of portions within the plurality of traces.
Claim 7
Dependent Claim
42 words
The method of claim 4 wherein the at least one reordering method comprises the steps of adding predecessor and successor portions to the trace if they are negligible within predetermined limits compared to at least one of the portions in the trace.
Claim 8
Dependent Claim
39 words
The method of claim 4 wherein the at least one reordering method comprises not adding a candidate portion to the trace unless the candidate portion is a perfect partner with at least one of the portions in the trace.
Claim 9
Dependent Claim
66 words
The method of claim 4 wherein the at least one reordering method comprises not adding an unreordered successor portion to the trace if the unreordered successor portion should follow a portion of the computer program that is different than a portion of the computer program in the trace that identifies the unreordered successor portion as a candidate for reordering and that precedes the unreordered successor portion.
Claim 10
Dependent Claim
47 words
The method of claim 7 wherein the unreordered successor portion should follow a portion of the computer program that is different than the portion of the computer program in the trace if the unreordered successor portion is not negligible within predetermined limits compared to the different portion.
Claim 11
Dependent Claim
79 words
The method of claim 4 wherein the at least one reordering method comprises not adding an unreordered successor portion to the trace if the portion of the computer program in the trace that identifies the unreordered successor portion as a candidate for reordering and that precedes the unreordered successor portion has a different portion that should follow the portion in the trace, and the different portion is not negligible within predetermined limits compared to the portion in the trace.
Claim 12
Dependent Claim
54 words
The method of claim 4 wherein the at least one reordering method does not add an unreordered predecessor portion to the trace if the portion in the trace that identifies the unreordered predecessor as a candidate for reordering and that succeeds the unreordered predecessor portion should follow a different portion of the computer program.
Claim 13
Dependent Claim
31 words
The method of claim 10 wherein the different portion should follow the unreordered predecessor portion if the unreordered successor portion is not negligible within predetermined limits compared to the different portion.
Claim 14
Dependent Claim
68 words
The method of claim 4 wherein the at least one reordering method does not add an unreordered predecessor portion to the trace if a portion different from the portion in the trace that identifies the unreordered predecessor as a candidate for reordering and that succeeds the unreordered predecessor portion should follow the unreordered predecessor portion and is not negligible within predetermined limits compared to the unreordered predecessor portion.
Claim 15
Dependent Claim
161 words
A program product comprising: (A) an optimizer, the optimizer reordering a plurality of program portions in a computer program according to profile data, the optimizer comprising: a reordering mechanism for determining an order for the plurality of portions of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along a plurality of program paths through at least one of the plurality of portions, the reordering mechanism placing the at least one portion in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists; and (B) signal bearing media bearing the optimizer.
Claim 16
Dependent Claim
161 words
A program product comprising: (A) an optimizer, the optimizer reordering a plurality of program portions in a computer program according to profile data, the optimizer comprising: a reordering mechanism for determining an order for the plurality of portions of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along a plurality of program paths through at least one of the plurality of portions, the reordering mechanism placing the at least one portion in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor portion to the at least one portion in the trace when at least one predecessor portion exists, and that does not necessarily add to the trace any successor portion to the at least one portion in the trace when at least one successor portion exists; and (B) signal bearing media bearing the optimizer.
Claim 17
Dependent Claim
14 words
The program product of claim 13 wherein the signal bearing media comprises recordable media.
Claim 18
Dependent Claim
14 words
The program product of claim 13 wherein the signal bearing media comprises transmission media.
Claim 19
Dependent Claim
21 words
The program product of claim 13 wherein each of the plurality of portions of the computer program comprises a basic block.
Claim 20
Independent Claim
260 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a computer program residing in the memory comprising a plurality of basic blocks joined by a plurality of program paths; profile data residing in the memory representing the execution frequency of at least one of the plurality of program paths within the computer program; a reordering mechanism residing in the memory and executed by the at least one processor for determining an order for the plurality of basic blocks of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along the plurality of program paths through at least one of the plurality of basic blocks, the reordering mechanism placing the at least one basic block in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor basic block to the at least one basic block in the trace when at least one predecessor basic block exists, and that does not necessarily add to the trace any successor basic block to the at least one basic block in the trace when at least one successor basic block exists; the reordering mechanism ordering the plurality of traces according to their order of creation; the reordering mechanism determining the order for the plurality of basic blocks of the computer program from the order of the plurality of traces and the order of the plurality of basic blocks within the plurality of traces.
Claim 21
Independent Claim
260 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a computer program residing in the memory comprising a plurality of basic blocks joined by a plurality of program paths; profile data residing in the memory representing the execution frequency of at least one of the plurality of program paths within the computer program; a reordering mechanism residing in the memory and executed by the at least one processor for determining an order for the plurality of basic blocks of the computer program by constructing a plurality of traces, each trace comprising a possible execution path along the plurality of program paths through at least one of the plurality of basic blocks, the reordering mechanism placing the at least one basic block in the trace in an order determined by (1) the profile data and (2) at least one reordering method that does not necessarily add to the trace any predecessor basic block to the at least one basic block in the trace when at least one predecessor basic block exists, and that does not necessarily add to the trace any successor basic block to the at least one basic block in the trace when at least one successor basic block exists; the reordering mechanism ordering the plurality of traces according to their order of creation; the reordering mechanism determining the order for the plurality of basic blocks of the computer program from the order of the plurality of traces and the order of the plurality of basic blocks within the plurality of traces.
Claim 22
Independent Claim
181 words
A method for improving execution speed of a computer program on a computer apparatus by reordering a plurality of basic blocks in a computer program, the method comprising the step of: constructing a plurality of traces, each trace comprising at least one of the plurality of basic blocks, the step of constructing each trace comprising the steps of: (A) adding a basic block to the trace in an order determined by: (1) profile data; and (2) at least one reordering method that does not necessarily add to the trace any predecessor basic block to the basic block in the trace when at least one predecessor basic block exists, and that does not necessarily add to the trace any successor basic block to the basic block in the trace when at least one successor basic block exists; (B) ordering the plurality of traces according to their order of creation; (C) reordering the plurality of basic blocks of the computer program from the order of the plurality of traces and the order of the plurality of basic blocks within the plurality of traces.
Claim 23
Independent Claim
181 words
A method for improving execution speed of a computer program on a computer apparatus by reordering a plurality of basic blocks in a computer program, the method comprising the step of: constructing a plurality of traces, each trace comprising at least one of the plurality of basic blocks, the step of constructing each trace comprising the steps of: (A) adding a basic block to the trace in an order determined by: (1) profile data; and (2) at least one reordering method that does not necessarily add to the trace any predecessor basic block to the basic block in the trace when at least one predecessor basic block exists, and that does not necessarily add to the trace any successor basic block to the basic block in the trace when at least one successor basic block exists; (B) ordering the plurality of traces according to their order of creation; (C) reordering the plurality of basic blocks of the computer program from the order of the plurality of traces and the order of the plurality of basic blocks within the plurality of traces.
Claim 24
Dependent Claim
44 words
The method of claim 18 wherein the at least one reordering method comprises the steps of adding predecessor and successor basic blocks to the trace if they are negligible within predetermined limits compared to at least one of the basic blocks in the trace.
Claim 25
Dependent Claim
42 words
The method of claim 18 wherein the at least one reordering method comprises not adding a candidate basic block to the trace unless the candidate basic block is a perfect partner with at least one of the basic blocks in the trace.
Claim 26
Dependent Claim
72 words
The method of claim 18 wherein the at least one reordering method comprises not adding an unreordered successor basic block to the trace if the unreordered successor basic block should follow a basic block of the computer program that is different than a basic block of the computer program in the trace that identifies the unreordered successor basic block as a candidate for reordering and that precedes the unreordered successor basic block.
Claim 27
Dependent Claim
48 words
The method of claim 21 wherein the unreordered successor basic block should follow a basic block of the computer program that is different than the basic block in the trace if the unreordered successor basic block is not negligible within predetermined limits compared to the different basic block.
Claim 28
Dependent Claim
79 words
The method of claim 18 wherein the at least one reordering method comprises not adding an unreordered successor portion to the trace if the portion of the computer program in the trace that identifies the unreordered successor portion as a candidate for reordering and that precedes the unreordered successor portion has a different portion that should follow the portion in the trace, and the different portion is not negligible within predetermined limits compared to the portion in the trace.
Claim 29
Dependent Claim
60 words
The method of claim 18 wherein the at least one reordering method does not add an unreordered predecessor basic block to the trace if the basic block in the trace that identifies the unreordered predecessor basic block as a candidate for reordering and that succeeds the unreordered predecessor basic block should follow a different basic block of the computer program.
Claim 30
Dependent Claim
35 words
The method of claim 24 wherein the different basic block should follow the unreordered predecessor basic block if the unreordered successor basic block is not negligible within predetermined limits compared to the different basic block.
Claim 31
Dependent Claim
68 words
The method of claim 18 wherein the at least one reordering method does not add an unreordered predecessor portion to the trace if a portion different from the portion in the trace that identifies the unreordered predecessor as a candidate for reordering and that succeeds the unreordered predecessor portion should follow the unreordered predecessor portion and is not negligible within predetermined limits compared to the unreordered predecessor portion.
References Cited (Backward Citations)
US5021945A
Cited
US4847755A
Cited
US5517628A
Cited
US4947315A
Cited
US5179703A
Cited
US5014185A
Cited
US4914590A
Cited
US5428782A
Cited
US5555417A
Cited
US5465258A
Cited
US5428793A
Cited
US5412799A
Cited
US5212794A
Cited
US5355487A
Cited
US5333304A
Cited
US5335344A
Cited
US5535329A
Cited
US5193180A
Cited
US5450586A
Cited
US5265254A
Cited
US5606698A
Cited
US5522036A
Cited
US5485616A
Cited
US5539907A
Cited
US5689712A
Cited
US5797013A
Cited
US5787284A
Cited
US5797012A
Cited
US5812854A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-06 | 2003-03-08 | 2003-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-06 | 2007-03-08 | 2007-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-06 | 2011-03-08 | 2011-09-07 | $7700.00 | Window Closed / Lapsed |