US6151704A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for optimizing a loop in a computer program by speculatively removing loads from within the loop
Assignee: Intel Corp
•
Filing: 1997-04-01
•
Granted: 2000-11-21
•
Expires: 2017-04-01
Abstract
Abstract A method for optimizing a loop in a computer program. The loop contains at least a first statement that uses a variable. The method includes inserting a second statement that loads the variable. The second statement is inserted prior to the loop. The method also includes inserting a third statement that (i) checks whether the variable has been written to at any point between the second statement and the third statement and if and only if the variable has been written to, then loading the variable.
Inventors
- 👤 Jim J. Radigan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 14:38
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
116 words
A method of optimizing a loop in a computer program, the method comprising: (a) inserting an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop; (b) inserting a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement; and (ii) if the variable has been written to, define the temp with a current value of the variable; and (c) replacing a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 2
Independent Claim
116 words
A method of optimizing a loop in a computer program, the method comprising: (a) inserting an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop; (b) inserting a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement; and (ii) if the variable has been written to, define the temp with a current value of the variable; and (c) replacing a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 3
Dependent Claim
26 words
The method of claim 1, wherein the act of inserting the advance load statement includes inserting the advance load statement into a rank-0 SSA intermediate language.
Claim 4
Dependent Claim
32 words
The method of claim 1, wherein the act of inserting the advance load statement includes inserting the advance load statement into a rank-n SSA intermediate language, where n is greater than 0.
Claim 5
Dependent Claim
33 words
The method of claim 1, wherein the act of replacing the statement includes replacing a statement that occurs at a point after a prior statement in the loop that includes an ambiguous definition.
Claim 6
Dependent Claim
32 words
The method of claim 1, where in the act of inserting a load check statement includes inserting a load check statement that includes an operand that point s to a handler routine.
Claim 7
Independent Claim
235 words
A method of optimizing a loop in a computer program, the loop containing a first statement that uses a rank-1 variable, the rank-1 variable containing a use of a rank-0 variable, the method comprising: inserting a first advance load statement that defines a first temp with the value of the rank-0 variable, the first advance load statement being inserted outside of the loop; inserting a second advance load statement that defines a second temp with the value of rank-1 variable, the second advance load statement being inserted outside of the loop; inserting a first load check statement, the first load check statement configured to check whether the rank-0 variable has been written to at any point between the first advance load statement and the first load check statements and if the rank-0 variable has been written to, then redefine the first temp with a current value of the rank-0 variable and redefines said second temp with a current value of the rank-1 variable; inserting a second load check statement, the second load check statement configured to check whether the rank-1 variable has been written to at any point between the second advance load statement and the second load check statement and if the rank-1 variable has been written to, redefine the second temp with a current value of the rank-1 variable; and replacing the first statement with a second statement that uses the second temp.
Claim 8
Independent Claim
235 words
A method of optimizing a loop in a computer program, the loop containing a first statement that uses a rank-1 variable, the rank-1 variable containing a use of a rank-0 variable, the method comprising: inserting a first advance load statement that defines a first temp with the value of the rank-0 variable, the first advance load statement being inserted outside of the loop; inserting a second advance load statement that defines a second temp with the value of rank-1 variable, the second advance load statement being inserted outside of the loop; inserting a first load check statement, the first load check statement configured to check whether the rank-0 variable has been written to at any point between the first advance load statement and the first load check statements and if the rank-0 variable has been written to, then redefine the first temp with a current value of the rank-0 variable and redefines said second temp with a current value of the rank-1 variable; inserting a second load check statement, the second load check statement configured to check whether the rank-1 variable has been written to at any point between the second advance load statement and the second load check statement and if the rank-1 variable has been written to, redefine the second temp with a current value of the rank-1 variable; and replacing the first statement with a second statement that uses the second temp.
Claim 9
Dependent Claim
28 words
The method of claim 6, wherein the act of inserting the first advance load statement includes inserting the first advance load statement into a rank-1 SSA intermediate language.
Claim 10
Dependent Claim
28 words
The method of claim 6, wherein the act of inserting the second advance load statement includes inserting the second advance load statement into a rank-2 SSA intermediate language.
Claim 11
Dependent Claim
136 words
A computer readable medium, said computer readable medium containing a set of instructions for compiling a program loop in a computer program, which when executed by a computer processor, cause the processor to: (a) insert an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop; (b) insert a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement, and (ii) if the variable has been written to, define the temp with a current value of the variable; and (c) replace a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 12
Dependent Claim
136 words
A computer readable medium, said computer readable medium containing a set of instructions for compiling a program loop in a computer program, which when executed by a computer processor, cause the processor to: (a) insert an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop; (b) insert a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement, and (ii) if the variable has been written to, define the temp with a current value of the variable; and (c) replace a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 13
Dependent Claim
28 words
The computer readable medium of claim 9, wherein the sequences of instructions further cause the processor to insert the advance load statement into a rank-0 SSA intermediate language.
Claim 14
Dependent Claim
34 words
The computer readable medium of claim 9, wherein the sequences of instructions further cause the processor to insert the advance load statement into a rank-n SSA intermediate language, wherein n is greater than 0.
Claim 15
Dependent Claim
37 words
The computer readable medium of claim 9, wherein the sequences of instructions further cause the processor to replace a statement that occurs at a point after a prior statement in a loop that includes an ambiguous definition.
Claim 16
Dependent Claim
32 words
The computer readable medium of claim 9, wherein the sequences of instructions further cause the processor to insert a load check statement that includes an operand that points to a handler routine.
Claim 17
Dependent Claim
143 words
A computer system for optimizing a loop in a computer program comprising: a processor; and one or more storage devices, the storage devices having stored thereon sequences of instruction that when executed by the processor, cause the processor to, (a) insert an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop, (b) insert a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement, and (ii) if the variable has been written to, then define the temp with a current value of the variable, and (c) replace a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 18
Dependent Claim
143 words
A computer system for optimizing a loop in a computer program comprising: a processor; and one or more storage devices, the storage devices having stored thereon sequences of instruction that when executed by the processor, cause the processor to, (a) insert an advance load statement that defines a temp with the value of a variable, the advance loading statement being inserted outside the loop, (b) insert a load check statement in the loop, the load check statement configured to (i) check whether the variable has been written to at any point between the advance load statement and the load check statement, and (ii) if the variable has been written to, then define the temp with a current value of the variable, and (c) replace a statement that occurs in the loop and that uses the variable with a statement that uses the temp.
Claim 19
Dependent Claim
35 words
The computer system of claim 14, wherein the sequences of instructions stored on the one or more storage devices further cause the processor to insert the advance load statement into a rank-0 SSA intermediate language.
Claim 20
Dependent Claim
41 words
The computer system of claim 14, wherein the sequences of instructions stored on the one or more storage devices further cause the processor to insert the advance load statement into a rank-n SSA intermediate language, wherein n is greater than 0.
Claim 21
Dependent Claim
44 words
The computer system of claim 14, wherein the sequences of instructions stored on the one or more storage devices further cause the processor to replace a statement that occurs at a point after a prior statement in a loop that includes an ambiguous definition.
Claim 22
Dependent Claim
39 words
The computer system of claim 14, wherein the sequences of instructions stored on the one or more storage devices further cause the processor to insert a load check statement that includes an operand that points to a handler routine.
References Cited (Backward Citations)
US4435753A
Cited
US4567574A
Cited
US4656583A
Cited
US4656582A
Cited
US4710872A
Cited
US4782444A
Cited
US4821181A
Cited
US4773007A
Cited
US4833606A
Cited
US4802091A
Cited
US4965724A
Cited
US4885684A
Cited
US5202995A
Cited
US5287510A
Cited
US5526499A
Cited
US5293631A
Cited
US5448737A
Cited
US5724536A
Cited
US5966539A
Cited
US5802337A
Cited
US5778210A
Cited
US5862384A
Cited
US6026240A
Cited
US5854933A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-21 | 2004-05-22 | 2004-11-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-21 | 2008-05-22 | 2008-11-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-21 | 2012-05-22 | 2012-11-21 | $7700.00 | Window Closed / Lapsed |