Patent US6002879A successfully refreshed from Google Patents.
US6002879A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for performing common subexpression elimination on a rack-N static single assignment language
Assignee: Micron Technology Inc
•
Filing: 1997-04-01
•
Granted: 1999-12-14
•
Expires: 2017-04-01
Abstract
Abstract Briefly, in one embodiment, the invention is a method for eliminating common subexpressions in an initial SSA intermediate language representation of at least a portion of a computer program. The method includes (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the initial intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and (d) renaming the unambiguous common subexpression.
Inventors
- 👤 Jim J. Radigan
- 👤 Vishesh M. Parikh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 14:26
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
81 words
A method for eliminating common subexpressions in an initial SSA intermediate language representation of at least a portion of a computer program, the method comprising: (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the initial intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and d) renaming the unambiguous common subexpression.
Claim 2
Independent Claim
81 words
A method for eliminating common subexpressions in an initial SSA intermediate language representation of at least a portion of a computer program, the method comprising: (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the initial intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and d) renaming the unambiguous common subexpression.
Claim 3
Dependent Claim
14 words
The method of claim 1, wherein phi-nodes are inserted in the absence of ambiguity.
Claim 4
Dependent Claim
13 words
The method of claim 1, wherein phi-nodes are inserted for each global variable.
Claim 5
Dependent Claim
58 words
The method of claim 1, wherein the act of renaming the definition and the subsequent use comprises: (1) performing a depth-first ordered traversal of a list of terminal nodes including the unambiguous definition and the subsequent use; (2) renaming the unambiguous definition when encountered during the traversal; and (3) renaming the subsequent use when encountered during the traversal.
Claim 6
Dependent Claim
56 words
The method of claim 1, wherein the act of renaming the definition and the subsequent use thereof comprises: (1) searching for a statement node containing the unambiguous definition reaching a statement node including the unambiguous use of the definition; (2) renaming the definition as a compiler temporary; and (3) renaming the use to the compiler temporary.
Claim 7
Dependent Claim
36 words
The method of claim 1, wherein renaming the unambiguous common expression comprises: (1) performing a depth-first ordered traversal of a list of interior nodes; and (2) renaming the unambiguous common subexpression when encountered during the traversal.
Claim 8
Dependent Claim
29 words
The method of claim 1, wherein renaming subexpressions comprises: (1) searching for expression nodes including an unambiguous common subexpression; and (2) renaming the common subexpression as a compiler temporary.
Claim 9
Dependent Claim
20 words
The method of claim 1, wherein acts (b) and (c) are performed in separate passes through the intermediate language representation.
Claim 10
Dependent Claim
25 words
The method of claim 1, wherein the method is iterated until the SSA intermediate language representation accommodates each definition in the initial intermediate language representation.
Claim 11
Dependent Claim
20 words
The method of claim 1, further comprising: (a) translating as SSA intermediate language resulting from acts (b)-(c) into object code.
Claim 12
Independent Claim
87 words
A method for eliminating common subexpressions while compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) creating an intermediate language of the portion of the source code; (b) inserting a phi-node in the intermediate language for an unambiguous definition used in an unambiguous subexpression reaching a join point; (c) renaming the unambiguous definition and any subsequent use of the definition; (d) renaming the unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 13
Independent Claim
87 words
A method for eliminating common subexpressions while compiling at least a portion of a computer program into machine readable object code, the method comprising: (a) creating an intermediate language of the portion of the source code; (b) inserting a phi-node in the intermediate language for an unambiguous definition used in an unambiguous subexpression reaching a join point; (c) renaming the unambiguous definition and any subsequent use of the definition; (d) renaming the unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 14
Dependent Claim
24 words
The method of claim 11, wherein creating an intermediate language includes scanning the source code, creating a statement node, and creating an expression node.
Claim 15
Dependent Claim
22 words
The method of claim 12, wherein the intermediate language representation includes a plurality of statement nodes and a plurality of expression nodes.
Claim 16
Dependent Claim
14 words
The method of claim 11, wherein phi-nodes are inserted in the absence of ambiguity.
Claim 17
Dependent Claim
13 words
The method of claim 11, wherein phi-nodes are inserted for each global variable.
Claim 18
Dependent Claim
62 words
The method of claim 11, wherein the act of renaming definitions and subsequent uses thereof comprises: (1) performing a depth-first ordered traversal of a list of terminal nodes; (2) renaming the unambiguous definition when encountered while traversing the list of terminal nodes; and (3) renaming the use reached by the renamed, unambiguous definition when encountered while traversing the list of terminal nodes.
Claim 19
Dependent Claim
54 words
The method of claim 11, wherein the act of renaming the definition and the subsequent use comprises: (1) searching for statement nodes containing the unambiguous definition reaching a statement node including an unambiguous use of the definition; (2) renaming the definition as a compiler temporary; and (3) renaming the use to the compiler temporary.
Claim 20
Dependent Claim
39 words
The method of claim 11, wherein renaming unambiguous common subexpression comprises: (1) performing a depth-first ordered traversal of a list of interior nodes; and (2) renaming the unambiguous common subexpression when encountered while traversing the list of interior nodes.
Claim 21
Dependent Claim
29 words
The method of claim 11, wherein renaming subexpressions comprises: (1) searching for expression nodes including the unambiguous common subexpression; and (2) renaming the common subexpression as a compiler temporary.
Claim 22
Dependent Claim
15 words
The method of claim 11, wherein acts (b) and (c) are performed in separate passes.
Claim 23
Dependent Claim
35 words
The method of claim 11, wherein acts (a), (b), and (c) are iterated until the SSA intermediate language representation accommodates each definition in the initial intermediate language representation and any subsequent use of the definition.
Claim 24
Dependent Claim
17 words
The method of claim 11, further comprising: (f) translating the resultant SSA intermediate language into object code.
Claim 25
Independent Claim
214 words
A method for eliminating common subexpressions while compiling at least a portion of source code into machine readable object code, the method comprising: (a) creating an initial intermediate language, including: (1) scanning the source code; (2) creating statement nodes; (3) creating expression nodes; (4) constructing an expression tree for each expression node; (5) initializing a list of interior nodes for each expression tree; and (6) initializing a list of terminal nodes for each expression tree; (b) inserting a phi-node in the initial intermediate language for each unambiguous global variable and each unambiguous subexpression in the initial intermediate language; (c) renaming each unambiguous definition and any subsequent use of the definition, the renaming including: (1) searching for statement nodes containing an unambiguous definition that reaches a statement node containing an unambiguous use of the definition by performing a depth-first ordered traversal of a list of terminal nodes; (2) renaming each unambiguous definition in the list of terminal nodes encountered while traversing the list of terminal nodes to a compiler temporary; and (3) renaming uses reached by a renamed, unambiguous definition in the list of terminal nodes while traversing the list of terminal nodes to the compiler temporary; (d) renaming each unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 26
Independent Claim
214 words
A method for eliminating common subexpressions while compiling at least a portion of source code into machine readable object code, the method comprising: (a) creating an initial intermediate language, including: (1) scanning the source code; (2) creating statement nodes; (3) creating expression nodes; (4) constructing an expression tree for each expression node; (5) initializing a list of interior nodes for each expression tree; and (6) initializing a list of terminal nodes for each expression tree; (b) inserting a phi-node in the initial intermediate language for each unambiguous global variable and each unambiguous subexpression in the initial intermediate language; (c) renaming each unambiguous definition and any subsequent use of the definition, the renaming including: (1) searching for statement nodes containing an unambiguous definition that reaches a statement node containing an unambiguous use of the definition by performing a depth-first ordered traversal of a list of terminal nodes; (2) renaming each unambiguous definition in the list of terminal nodes encountered while traversing the list of terminal nodes to a compiler temporary; and (3) renaming uses reached by a renamed, unambiguous definition in the list of terminal nodes while traversing the list of terminal nodes to the compiler temporary; (d) renaming each unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 27
Dependent Claim
98 words
A program storage device readable by a general purpose computer, the program storage device being encoded with statements implementing a method for eliminating common subexpressions in a SSA intermediate language representation of at least a portion of a computer program, the method comprising: (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and (d) renaming the unambiguous common subexpression.
Claim 28
Dependent Claim
98 words
A program storage device readable by a general purpose computer, the program storage device being encoded with statements implementing a method for eliminating common subexpressions in a SSA intermediate language representation of at least a portion of a computer program, the method comprising: (a) inserting a phi-node for an unambiguous definition used in an unambiguous subexpression reaching a join point in the intermediate language subsequent to the join point; (b) inserting a phi-node for the unambiguous common subexpression; (c) renaming the unambiguous definition and a subsequent use reached by the definition; and (d) renaming the unambiguous common subexpression.
Claim 29
Dependent Claim
14 words
The device of claim 24, wherein phi-nodes are inserted in the absence of ambiguity.
Claim 30
Dependent Claim
13 words
The device of claim 24, wherein phi-nodes are inserted for each global variable.
Claim 31
Dependent Claim
66 words
The device of claim 24, wherein the act of renaming the definition and the subsequent use comprises: (1) performing a depth-first ordered traversal of a list of terminal nodes including the unambiguous definition and the subsequent use; (2) renaming the unambiguous definition when encountered while traversing the list of terminal nodes; and (3) renaming the subsequent use when encountered while traversing the list of terminal nodes.
Claim 32
Dependent Claim
55 words
The device of claim 24, wherein the acts of renaming the definition and the subsequent use comprises: (1) searching for a statement node containing the unambiguous definition reaching a statement node including the unambiguous use of the definition; (2) renaming the definition as a compiler temporary; and (3) renaming the use to the compiler temporary.
Claim 33
Dependent Claim
43 words
The device of claim 24, wherein the act of renaming the unambiguous common expression comprises: (1) performing a depth-first ordered traversal of a list of interior nodes; and (2) renaming the unambiguous common subexpression when encountered while traversing the list of interior nodes.
Claim 34
Dependent Claim
32 words
The device of claim 24, wherein the acts of renaming subexpressions comprises: (1) searching for expression nodes including an unambiguous common subexpression; and (2) renaming the common subexpression as a compiler temporary.
Claim 35
Dependent Claim
20 words
The device of claim 24, wherein acts (b) and (c) are performed in separate passes through the intermediate languages representation.
Claim 36
Dependent Claim
25 words
The device of claim 24, wherein the method is iterated until the SSA intermediate language representation accommodates each definition in the initial intermediate language representation.
Claim 37
Dependent Claim
17 words
The device of claim 24, further comprising: (a) translating an SSA intermediate language resulting for acts (b)-(c).
Claim 38
Dependent Claim
100 words
A program storage device readable by a general purpose computer, the program storage device being encoded with statements implementing a method for eliminating common subexpressions while compiling at least a portion of a computer program, the method comprising: (a) creating an intermediate language of the portion of the computer program; (b) inserting a phi-node in the intermediate language an unambiguous definition used in an unambiguous subexpression reaching a join point; (c) renaming the unambiguous definition and any subsequent use of the definition; (d) renaming the unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 39
Dependent Claim
100 words
A program storage device readable by a general purpose computer, the program storage device being encoded with statements implementing a method for eliminating common subexpressions while compiling at least a portion of a computer program, the method comprising: (a) creating an intermediate language of the portion of the computer program; (b) inserting a phi-node in the intermediate language an unambiguous definition used in an unambiguous subexpression reaching a join point; (c) renaming the unambiguous definition and any subsequent use of the definition; (d) renaming the unambiguous common subexpression.; and (e) translating the resultant SSA intermediate language representation into object code.
Claim 40
Dependent Claim
24 words
The device of claim 34, wherein creating an intermediate language includes scanning the source code, creating a statement node, and creating an expression node.
Claim 41
Dependent Claim
22 words
The device of claim 34, wherein the intermediate language representation includes a plurality of statement nodes and a plurality of expression nodes.
Claim 42
Dependent Claim
14 words
The device of claim 34, wherein phi-nodes are inserted in the absence of ambiguity.
Claim 43
Dependent Claim
17 words
The device of claim 34, wherein the act of inserting phi-nodes is performed for each global variable.
Claim 44
Dependent Claim
63 words
The device of claim 34, wherein the act of renaming the definition and the subsequent use comprises: (1) performing a depth-first ordered traversal of a list of terminal nodes; (2) renaming the unambiguous definition when encountered while traversing the list of terminal nodes; and (3) renaming the use reached by the renamed, unambiguous definition when encountered while traversing the list of terminal nodes.
Claim 45
Dependent Claim
55 words
The device of claim 34, wherein the act of renaming the definition and the subsequent use comprises: (1) searching for a statement node containing the unambiguous definition reaching a statement node including the unambiguous use of the definition; (2) renaming the definition as a compiler temporary; and (3) renaming the use to the compiler temporary.
Claim 46
Dependent Claim
34 words
The device of claim 34, wherein renaming the unambiguous common subexpression comprises: (1) performing a depth-first ordered traversal of a list of interior; (2) renaming the unambiguous common subexpression when encountered during the traversal.
Claim 47
Dependent Claim
29 words
The device of claim 34, wherein renaming subexpressions comprises: (1) searching for expression nodes including an unambiguous common subexpression; and (2) renaming the common subexpression as a compiler temporary.
Claim 48
Dependent Claim
20 words
The device of claim 34, wherein acts (b) and (c) are performed in separate passes through the intermediate language representation.
Claim 49
Dependent Claim
31 words
The device of claim 34, wherein the method iterated until the SSA intermediate language representation accommodates each definition in the initial intermediate language representation and any subsequent use of the definition.
Claim 50
Dependent Claim
20 words
The device of claim 34, further comprising: (f) translating an SSA intermediate language resulting from acts (b)-(c) into object code.
References Cited (Backward Citations)
US5287510A
Cited
US5327561A
Cited
US5448737A
Cited
US5475842A
Cited
US5584027A
Cited
US5659754A
Cited
US5768596A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-13 | 2003-06-14 | 2003-12-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-13 | 2007-06-14 | 2007-12-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-13 | 2011-06-14 | 2011-12-14 | $7700.00 | Window Closed / Lapsed |