US5537620A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Redundant load elimination on optimizing compilers
Assignee: International Business Machines Corp
•
Filing: 1994-09-16
•
Granted: 1996-07-16
•
Expires: 2014-09-16
Abstract
Abstract A method for eliminating redundant loads in an optimizing compiler is provided. When a LOAD and memory operation occur in an iterative loop structure having an induction variable, the method determines if redundant load elimination optimization may be performed by performing the steps of: creating a symbolic address for a LOAD operation, where the LOAD operation follows a memory operation, creating a symbolic address for the memory operation which precedes the LOAD, and subtracting the LOAD symbolic address from the memory operation symbolic address to generate a difference. If the difference is a constant which is divisible by the increment of the induction variable, the method eliminates the LOAD instruction for each increment of the loop and includes an instruction to copy the value of the memory operation to a register, and further includes an instruction to move the copied value from the register to the target of the load. An additional feature of the invention includes the step of, if the difference is a constant which is divisible by a multiple of the increment of the induction variable, wherein the multiple is greater than one, including additional instructions to copy the value of the memory operation to a separate register for each iteration during a number of iterations equal to the multiple.
Inventors
- 👤 Mauricio Breternitz, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 01:12
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
156 words
A method in a computer system for performing redundant load elimination optimization for an optimizing compiler, the method comprising the steps of: (a) determining whether a LOAD operation follows a memory operation; (b) testing if the LOAD operation and the memory operation are both functions of a loop induction variable and if the loop induction variable is incremented by an increment, and if so, determining if the LOAD operation and the memory operation are both a function of the same loop induction variable; (c) creating a symbolic expression for both the LOAD operation and the memory operation, if the determination in step (a) is affirmative and the determination in step (b) is affirmative; (d) subtracting the symbolic expression for the LOAD from the symbolic expression for the memory operation, generating a difference; and (e) indicating redundant load elimination optimization may be performed if the difference is a constant divisible by the increment of the induction variable.
Claim 2
Independent Claim
156 words
A method in a computer system for performing redundant load elimination optimization for an optimizing compiler, the method comprising the steps of: (a) determining whether a LOAD operation follows a memory operation; (b) testing if the LOAD operation and the memory operation are both functions of a loop induction variable and if the loop induction variable is incremented by an increment, and if so, determining if the LOAD operation and the memory operation are both a function of the same loop induction variable; (c) creating a symbolic expression for both the LOAD operation and the memory operation, if the determination in step (a) is affirmative and the determination in step (b) is affirmative; (d) subtracting the symbolic expression for the LOAD from the symbolic expression for the memory operation, generating a difference; and (e) indicating redundant load elimination optimization may be performed if the difference is a constant divisible by the increment of the induction variable.
Claim 3
Dependent Claim
28 words
A method according to claim 1, further comprising the step of performing redundant load elimination optimization in response to an indication that redundant load optimization may be performed.
Claim 4
Dependent Claim
61 words
A method according to claim 2, wherein the step of performing redundant load elimination optimization comprises eliminating the LOAD instruction for each increment of the loop and including an instruction in the compiled program to copy the value of the memory operation to a register, if the difference is a constant which is divisible by the increment of the induction variable.
Claim 5
Dependent Claim
14 words
A method according to claim 3, further comprising the step of initializing the register.
Claim 6
Dependent Claim
24 words
A method according to claim 3, further including an instruction to move the copied value from the register to the target of the load.
Claim 7
Dependent Claim
33 words
A method according to claim 3, further comprising the step of including an instruction to move the copied value from the register to the target of any subsequent references to the LOAD value.
Claim 8
Dependent Claim
78 words
A method according to claim 2, wherein the step of performing redundant load elimination optimization comprises including additional instructions to copy the value of the memory operation to a separate register for each iteration of the loop for a multiple number of iterations equal to the multiple, if the difference is a constant which is divisible by the increment of the induction variable, and further wherein the constant is divisible by the increment a multiple number of times.
Claim 9
Dependent Claim
24 words
A method according to claim 7, further including an instruction to move the copied value from the register to the target of the load.
Claim 10
Dependent Claim
33 words
A method according to claim 7, further comprising the step of including an instruction to move the copied value from the register to the target of any subsequent references to the LOAD value.
Claim 11
Dependent Claim
58 words
A method according to claim 2, wherein the step of performing redundant load elimination optimization comprises unrolling the loop a number of times equal to the multiple, if the difference is a constant which is divisible by the increment of the induction variable, and further wherein the constant is divisible by the increment a multiple number of times.
Claim 12
Independent Claim
123 words
A method in a computer system for eliminating redundant loads for an optimizing compiler, wherein a LOAD and memory operation occur in an iterative loop structure having an induction variable, the method comprising the steps of: creating a LOAD symbolic address for a LOAD operation, where the LOAD operation follows a memory operation; creating a memory operation symbolic address for the memory operation which precedes the LOAD; subtracting the LOAD symbolic address from the memory operation symbolic address to generate a difference; eliminating the LOAD instruction for each increment of the loop and including an instruction to copy the value of the memory operation to a register, if the difference is a constant which is divisible by the increment of the induction variable.
Claim 13
Independent Claim
123 words
A method in a computer system for eliminating redundant loads for an optimizing compiler, wherein a LOAD and memory operation occur in an iterative loop structure having an induction variable, the method comprising the steps of: creating a LOAD symbolic address for a LOAD operation, where the LOAD operation follows a memory operation; creating a memory operation symbolic address for the memory operation which precedes the LOAD; subtracting the LOAD symbolic address from the memory operation symbolic address to generate a difference; eliminating the LOAD instruction for each increment of the loop and including an instruction to copy the value of the memory operation to a register, if the difference is a constant which is divisible by the increment of the induction variable.
Claim 14
Dependent Claim
14 words
A method according to claim 11, further comprising the step of initializing the register.
Claim 15
Dependent Claim
83 words
A method according to claim 11, further comprising the step of including additional instructions in the iterative loop structure to copy the value of the memory operation to a separate register for each iteration during a number of iterations equal to a quotient of the constant divided by the multiple of the increment of the induction variable, if the difference is a constant which is divisible by a multiple of the increment of the induction variable, wherein the multiple is greater than one.
Claim 16
Dependent Claim
24 words
A method according to claim 11, further including an instruction to move the copied value from the register to the target of the load.
Claim 17
Dependent Claim
33 words
A method according to claim 11, further comprising the step of including an instruction to move the copied value from the register to the target of any subsequent references to the LOAD value.
Claim 18
Dependent Claim
71 words
A method according to claim 11, further comprising the step of unrolling the loop a number of times equal to a quotient of the constant divided by the multiple of the increment of the induction variable, if the difference is a constant which is divisible by the increment of the induction variable, and further wherein the constant is divisible by the increment to produce a quotient a multiple number of times.
Claim 19
Independent Claim
174 words
A method in a computer system for performing redundant load elimination optimization for an optimizing compiler, the method comprising the steps of: (a) determining whether a LOAD operation follows a memory operation; (b) testing if the LOAD operation and the memory operation are both functions of a loop induction variable and if the loop induction variable is incremented by an increment, and if so, determining if the LOAD operation and the memory operation are both a function of the same loop induction variable; (c) creating a symbolic expression for both the LOAD operation and the memory operation if the determination in step (a) is affirmative and the determination in step (b) is affirmative; (d) subtracting the symbolic expression for the LOAD from the symbolic expression for the memory operation, generating a difference; (e) performing redundant load elimination optimization, if the difference is a constant, by eliminating the LOAD instruction for each increment of the loop and including an instruction in the compiled program to copy the value of the memory operation to a register.
Claim 20
Independent Claim
174 words
A method in a computer system for performing redundant load elimination optimization for an optimizing compiler, the method comprising the steps of: (a) determining whether a LOAD operation follows a memory operation; (b) testing if the LOAD operation and the memory operation are both functions of a loop induction variable and if the loop induction variable is incremented by an increment, and if so, determining if the LOAD operation and the memory operation are both a function of the same loop induction variable; (c) creating a symbolic expression for both the LOAD operation and the memory operation if the determination in step (a) is affirmative and the determination in step (b) is affirmative; (d) subtracting the symbolic expression for the LOAD from the symbolic expression for the memory operation, generating a difference; (e) performing redundant load elimination optimization, if the difference is a constant, by eliminating the LOAD instruction for each increment of the loop and including an instruction in the compiled program to copy the value of the memory operation to a register.
Claim 21
Dependent Claim
14 words
A method according to claim 17, further comprising the step of initializing the register.
Claim 22
Dependent Claim
24 words
A method according to claim 17, further including an instruction to move the copied value from the register to the target of the load.
Claim 23
Dependent Claim
33 words
A method according to claim 17, further comprising the step of including an instruction to move the copied value from the register to the target of any subsequent references to the LOAD value.
Claim 24
Dependent Claim
92 words
A method according to claim 17, wherein the step of performing redundant load elimination optimization comprises including additional instructions to copy the value of the memory operation to a separate register for each iteration of the loop for a multiple number of iterations equal to a quotient of the constant divided by the multiple of the increment of the induction variable, if the difference is a constant which is divisible by the increment of the induction variable, and further wherein the constant is divisible by the increment a multiple number of times.
Claim 25
Dependent Claim
24 words
A method according to claim 21, further including an instruction to move the copied value from the register to the target of the load.
Claim 26
Dependent Claim
33 words
A method according to claim 21, further comprising the step of including an instruction to move the copied value from the register to the target of any subsequent references to the LOAD value.
Claim 27
Dependent Claim
72 words
A method according to claim 17, wherein the step of performing redundant load elimination optimization comprises unrolling the loop a number of times equal to a quotient of the constant divided by the multiple of the increment of the induction variable, if the difference is a constant which is divisible by the increment of the induction variable, and further wherein the constant is divisible by the increment a multiple number of times.
References Cited (Backward Citations)
US4435753A
Cited
US4567574A
Cited
US4656583A
Cited
EP0190622A2
Cited
US4656582A
Cited
US4920477A
Cited
US4953084A
Cited
US4931928A
Cited
US5287510A
Cited
US5333280A
Cited
US5107418A
Cited
EP0476667A2
Cited
US5293631A
Cited
US5442797A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |