Method for optimizing a loop in a computer program by speculatively removing loads from within the loop

• US 6,151,704 A
• Filed: 04/01/1997
• Issued: 11/21/2000
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Radigan, Jim J.
• Primary Examiner(s): Banankhah, Majid A.
• Assistant Examiner(s): CALDWELL, PATRICIA G
• Application Number:
  US08/829,980
• Time in Patent Office: 1,330 Days
• Field of Search: 395/705-709, 395/680-685, 712/216, 717/5-9
• US Class Current: 717/159
• CPC Class Codes: G06F 8/443 Optimisation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.