Patent US5790867A successfully refreshed from Google Patents.
US5790867A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiler with extended redundant copy elimination
Assignee: International Business Machines Corp
•
Filing: 1996-01-02
•
Granted: 1998-08-04
•
Expires: 2016-01-02
Abstract
Abstract A compiler and method of compiling provide extended redundant copy elimination by eliminating copy statements having provably equivalent data items when it is determined that the defined operand of a copy statement has both a non-uniquely reachable use, and an additional, uniquely reachable use that is also a copy statement.
Inventors
- 👤 William J. Schmidt
- 👤 Robert R. Roediger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 17:32
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
77 words
A method of removing redundant copy statements during compilation of a computer procedure, each copy statement including a defined operand and a used operand, the method comprising the steps of: (a) determining if the defined operand of a first copy statement in the computer procedure has a non-uniquely reachable use, and an additional, uniquely reachable use in a second copy statement in the computer procedure; and (b) removing any copy statement having equivalent defined and used operands.
Claim 2
Independent Claim
77 words
A method of removing redundant copy statements during compilation of a computer procedure, each copy statement including a defined operand and a used operand, the method comprising the steps of: (a) determining if the defined operand of a first copy statement in the computer procedure has a non-uniquely reachable use, and an additional, uniquely reachable use in a second copy statement in the computer procedure; and (b) removing any copy statement having equivalent defined and used operands.
Claim 3
Dependent Claim
74 words
The method of claim 1, further comprising the steps of: (a) determining if every reachable use of the defined operand of the first copy statement is a uniquely reachable use; and (b) if every reachable use of the defined operand of the first copy statement is a uniquely reachable use, replacing the used operand in each uniquely reachable use with the used operand in the first copy statement and removing the first copy statement.
Claim 4
Dependent Claim
52 words
The method of claim 1, wherein the step of removing any copy statement having equivalent defined and used operands comprises the steps of: (a) determining if the defined operand in the second copy statement is equivalent to the used operand in the first copy statement; and (b) removing the second copy statement.
Claim 5
Dependent Claim
58 words
The method of claim 1, further comprising the step of repeating step (a) of claim 1 for every copy statement in the computer procedure to identify if the defined operand of any copy statement in the computer procedure that has a non-uniquely reachable use also has a uniquely reachable use in another copy statement in the computer procedure.
Claim 6
Dependent Claim
76 words
The method of claim 4, wherein the step of removing any copy statement having equivalent defined and used operands comprises the step of, after identifying that the defined operand of a copy statement in the computer procedure that has a non-uniquely reachable use also has a uniquely reachable use in another copy statement in the computer procedure, performing dataflow analysis on the computer procedure to identify any copy statements having provably equivalent defined and used operands.
Claim 7
Dependent Claim
119 words
The method of claim 5, wherein the step of removing any copy statement having equivalent defined and used operands further includes the steps of: (a) prior to performing dataflow analysis, building one or more equivalence classes, each equivalence class including a set of potentially equivalent operands that are operands in at least one common copy statement in the computer procedure; and (b) after performing dataflow analysis, determining from the equivalence classes the equivalent operands at each copy statement in the computer procedure that has not been removed prior to performing dataflow analysis; and wherein the step of performing dataflow analysis includes the step of modifying the equivalence classes to reflect which data items are equivalent at which copy statements.
Claim 8
Dependent Claim
104 words
The method of claim 6, wherein the step of repeating step (a) of claim 1 for every copy statement in the computer procedure includes the step of building an equivalence candidate set including the defined operands of any copy statements which are uniquely reachable uses of the defined operand of another copy statement in the computer procedure that itself has a non-uniquely reachable use, and wherein the performing dataflow analysis step further includes the steps of: (a) aborting dataflow analysis if the equivalence candidate set is empty; and (b) discarding any equivalence classes not having at least one operand in the equivalence candidate set.
Claim 9
Dependent Claim
43 words
The method of claim 1, further comprising the step of, if the first copy statement has a non-uniquely reachable use in a second statement, propagating the first copy statement to any local reachable uses of the defined operand of the first copy statement.
Claim 10
Dependent Claim
14 words
The method of claim 1, wherein the computer procedure is in an intermediate representation.
Claim 11
Independent Claim
176 words
A method of compiling a computer procedure, the method comprising the steps of: (a) optimizing the computer procedure to form an optimized representation, the computer procedure including at least one copy statement, the copy statement including a defined operand and a used operand, the optimizing step including the steps of: (1) determining if every reachable use of a defined operand of a first copy statement in the computer procedure is a uniquely reachable use; (2) if step (a)(1) is true, replacing the used operand in each uniquely reachable use with, the used operand in the first copy statement and removing the first copy statement; (3) if step (a)(1) is not true, determining if the defined operand has a uniquely reachable use in a second copy statement in the computer procedure; (4) if step (a)(3) is true, determining if the defined and used operands of any copy statement are equivalent; and (5) removing any copy statement having equivalent defined and used operands; and (b) generating an object code representation of the computer procedure from the optimized representation.
Claim 12
Independent Claim
176 words
A method of compiling a computer procedure, the method comprising the steps of: (a) optimizing the computer procedure to form an optimized representation, the computer procedure including at least one copy statement, the copy statement including a defined operand and a used operand, the optimizing step including the steps of: (1) determining if every reachable use of a defined operand of a first copy statement in the computer procedure is a uniquely reachable use; (2) if step (a)(1) is true, replacing the used operand in each uniquely reachable use with, the used operand in the first copy statement and removing the first copy statement; (3) if step (a)(1) is not true, determining if the defined operand has a uniquely reachable use in a second copy statement in the computer procedure; (4) if step (a)(3) is true, determining if the defined and used operands of any copy statement are equivalent; and (5) removing any copy statement having equivalent defined and used operands; and (b) generating an object code representation of the computer procedure from the optimized representation.
Claim 13
Dependent Claim
28 words
The method of claim 10, further comprising the step of, prior to the optimizing step, generating an intermediate representation from a source code representation of the computer procedure.
Claim 14
Dependent Claim
87 words
The method of claim 10, wherein step (a)(4) of claim 10 includes the step of determining if the defined operand in the second copy statement is equivalent to the used operand in the first copy statement; wherein step (a)(5) of claim 10 includes the step of removing the second copy statement; and wherein the optimizing step further includes the step of repeating steps (a)(1)-(a)(5) for each copy statement in the computer procedure; whereby steps (a)(4) and (a)(5) are performed for each copy statement identified in step (a)(3).
Claim 15
Dependent Claim
117 words
The method of claim 10, further comprising the step of repeating steps (a)(1)-(a)(3) of claim 10 for every copy statement in the computer procedure to identify if the defined operand of any copy statement in the computer procedure has a uniquely reachable use in another copy statement in the computer procedure, and wherein step (a)(4) comprises the step of, after repeating steps (a)(1)-(a)(3) for every copy statement in the computer procedure to identify that the defined operand of a copy statement in the computer procedure has a uniquely reachable use in another copy statement in the computer procedure, performing dataflow analysis on the computer procedure to identify any copy statements having provably equivalent defined and used operands.
Claim 16
Dependent Claim
121 words
A computer system for compiling a computer procedure into a machine-readable representation, the computer procedure including at least one copy statement which includes a defined operand and a used operand, the computer system comprising: (a) an optimizer that optimizes the computer procedure into an optimized representation, the optimizer including a redundant copy statement eliminating module that (1) identifies if a first copy statement in the computer procedure has a uniquely reachable use to a second copy statement and an additional, non-uniquely reachable use to another statement, and (2) if so, removes any redundant copy statements which have equivalent defined and used operands; and (b) a machine-readable code generator that generates a machine-readable representation of the computer procedure from the optimized representation.
Claim 17
Dependent Claim
121 words
A computer system for compiling a computer procedure into a machine-readable representation, the computer procedure including at least one copy statement which includes a defined operand and a used operand, the computer system comprising: (a) an optimizer that optimizes the computer procedure into an optimized representation, the optimizer including a redundant copy statement eliminating module that (1) identifies if a first copy statement in the computer procedure has a uniquely reachable use to a second copy statement and an additional, non-uniquely reachable use to another statement, and (2) if so, removes any redundant copy statements which have equivalent defined and used operands; and (b) a machine-readable code generator that generates a machine-readable representation of the computer procedure from the optimized representation.
Claim 18
Dependent Claim
38 words
The computer system of claim 14, further comprising a front end module that generates an intermediate representation from a source code representation of the computer procedure, wherein the optimizer operates on the intermediate representation of the computer procedure.
Claim 19
Dependent Claim
41 words
The computer system of claim 14, wherein the redundant copy eliminating module determines if the defined operand in the second copy statement is equivalent to the used operand in the first copy statement, and if so, removes the second copy statement.
Claim 20
Dependent Claim
69 words
The computer system of claim 16, wherein the redundant copy eliminating module identifies if the defined operand of any copy statement in the computer procedure has a uniquely reachable use in another copy statement in the computer procedure, and wherein the redundant copy eliminating module includes a dataflow analyzer that performs dataflow analysis on the computer procedure to identify any copy statements having provably equivalent defined and used operands.
Claim 21
Dependent Claim
117 words
A program storage device readable by a computer system, the program storage device tangibly embodying a program of instructions executable by the computer system to optimize a computer procedure by eliminating redundant copy statements during compilation of the computer procedure, the computer procedure having at least one copy statement which includes a defined operand and a used operand, the program comprising: (a) an identifier that identifies if a first copy statement: in the intermediate representation has a uniquely reachable use to a second copy statement and an additional, non-uniquely reachable use to another statement; and (b) a redundant copy eliminator, responsive to the identifier, that removes any redundant copy statements which have equivalent defined and used operands.
Claim 22
Dependent Claim
117 words
A program storage device readable by a computer system, the program storage device tangibly embodying a program of instructions executable by the computer system to optimize a computer procedure by eliminating redundant copy statements during compilation of the computer procedure, the computer procedure having at least one copy statement which includes a defined operand and a used operand, the program comprising: (a) an identifier that identifies if a first copy statement: in the intermediate representation has a uniquely reachable use to a second copy statement and an additional, non-uniquely reachable use to another statement; and (b) a redundant copy eliminator, responsive to the identifier, that removes any redundant copy statements which have equivalent defined and used operands.
Claim 23
Dependent Claim
42 words
The program storage device of claim 18, wherein the identifier determines if the defined operand in the second copy statement is equivalent to the used operand in the first copy statement, and wherein the redundant copy eliminator removes the second copy statement.
Claim 24
Dependent Claim
68 words
The program storage device of claim 18, wherein the identifier identifies if the defined operand of any copy statement in the computer procedure that has a non-uniquely reachable use also has a uniquely reachable use in another copy statement in the computer procedure, and wherein the redundant copy eliminator performs dataflow analysis on the computer procedure to identify any copy statements having provably equivalent defined and used operands.
Claim 25
Independent Claim
132 words
A method of transferring a program product to a computer system, the method comprising the steps of: (a) establishing a connection with the computer system; and (b) transmitting the program product to the computer system, the program product being executable by the computer system to optimize a computer procedure by eliminating redundant copy statements during compilation of the computer procedure, the computer procedure having at least one copy statement which includes a defined operand and a used operand, the program product executing the steps of: (1) determining if the defined operand of a first copy statement in the computer procedure has a non-uniquely reachable use, and an additional, uniquely reachable use in a second copy statement in the computer procedure; and (2) removing any copy statement having equivalent defined and used operands.
Claim 26
Independent Claim
132 words
A method of transferring a program product to a computer system, the method comprising the steps of: (a) establishing a connection with the computer system; and (b) transmitting the program product to the computer system, the program product being executable by the computer system to optimize a computer procedure by eliminating redundant copy statements during compilation of the computer procedure, the computer procedure having at least one copy statement which includes a defined operand and a used operand, the program product executing the steps of: (1) determining if the defined operand of a first copy statement in the computer procedure has a non-uniquely reachable use, and an additional, uniquely reachable use in a second copy statement in the computer procedure; and (2) removing any copy statement having equivalent defined and used operands.
References Cited (Backward Citations)
US4656583A
Cited
JPS6325733A
Cited
US4843545A
Cited
JPS63261430A
Cited
US5230050A
Cited
US5293630A
Cited
US5598560A
Cited
US5293631A
Cited
US5515535A
Cited
US5274818A
Cited
US5659754A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-03 | 2002-02-02 | 2002-08-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-03 | 2006-02-02 | 2006-08-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-03 | 2010-02-02 | 2010-08-04 | $7700.00 | Window Closed / Lapsed |