US6117185A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Skip list data storage during compilation
Assignee: International Business Machines Corp
•
Filing: 1997-09-24
•
Granted: 2000-09-12
•
Expires: 2017-09-24
Abstract
Abstract A compiler and method of compiling provide enhanced performance by utilizing a skip list data structure to store various properties of a program at points of interest in the procedure, for example, the properties of the statements in each block in the control flow graph. A special procedure is used to initialize the skip list, prior to performing data flow analysis, to ensure that the skip list structure is not used in an inefficient manner as a result of initialization. Furthermore, special procedures are used to simultaneously scan and compare two skip lists as part of solving dataflow equations.
Inventors
- 👤 William Jon Schmidt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 01:46
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
205 words
A method of storing dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, in a linked list of data storage nodes, and using said linked list in dataflow analysis, the method comprising identifying a new dataflow analysis property by evaluation of instructions and expressions of said computer procedure, and generating a new data storage node for said new dataflow analysis property to be associated with the computer procedure by: allocating said new data storage node, the new data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order.
Claim 2
Independent Claim
205 words
A method of storing dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, in a linked list of data storage nodes, and using said linked list in dataflow analysis, the method comprising identifying a new dataflow analysis property by evaluation of instructions and expressions of said computer procedure, and generating a new data storage node for said new dataflow analysis property to be associated with the computer procedure by: allocating said new data storage node, the new data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order.
Claim 3
Dependent Claim
68 words
The method of claim 1 adapted to preparing a linked list including data storage nodes of either a first smaller size or a second larger size, wherein data storage nodes of the second larger size include a second pointer storage space for storing a pointer identifying a location of an other data storage node, wherein the allocating step further comprises selecting a size for the data storage node.
Claim 4
Dependent Claim
16 words
The method of claim 2 wherein the size for the data storage node is randomly selected.
Claim 5
Dependent Claim
51 words
The method of claim 1 wherein the pointer stored into the first pointer storage space identifies a location of a data storage node storing an existing dataflow analysis property associated with the computer procedure that is next subsequent to the new dataflow analysis property in the predetermined dataflow analysis property order.
Claim 6
Dependent Claim
59 words
The method of claim 2 wherein the pointer stored into the first pointer storage space identifies a location of a subsequent data storage node of the first smaller size that is storing an existing dataflow analysis property associated with the computer procedure that is next subsequent to the new dataflow analysis property in the predetermined dataflow analysis property order.
Claim 7
Dependent Claim
82 words
The method of claim 5 wherein the pointer stored into the second pointer storage space identifies a location of a subsequent data storage node of the second larger size that is storing an existing dataflow analysis property associated with the computer procedure that, as compared to all existing properties associated with the computer procedure that are stored in data storage nodes of the second larger size, is next subsequent to the new dataflow analysis property in the predetermined dataflow analysis property order.
Claim 8
Dependent Claim
24 words
The method of claim 1 further comprising deleting a data storage node for a dataflow analysis property to be disassociated with the computer procedure.
Claim 9
Dependent Claim
182 words
A computer-readable media, said media storing a dataflow analysis program and a linked list of data storage nodes storing dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, wherein said dataflow analysis program, when executed, identifies dataflow analysis properties by evaluation of instructions and expressions of said computer procedure, and the linked list comprises: a plurality of data storage nodes, each data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; the data storage space of each node storing an identifier of a first dataflow analysis property for which the node was allocated; and the first pointer storage space of each data storage node storing a pointer identifying a location of an other data storage node, the other data storage node storing a second dataflow analysis property associated with the computer procedure that is subsequent to the first dataflow analysis property in a predetermined dataflow analysis property order.
Claim 10
Dependent Claim
182 words
A computer-readable media, said media storing a dataflow analysis program and a linked list of data storage nodes storing dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, wherein said dataflow analysis program, when executed, identifies dataflow analysis properties by evaluation of instructions and expressions of said computer procedure, and the linked list comprises: a plurality of data storage nodes, each data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; the data storage space of each node storing an identifier of a first dataflow analysis property for which the node was allocated; and the first pointer storage space of each data storage node storing a pointer identifying a location of an other data storage node, the other data storage node storing a second dataflow analysis property associated with the computer procedure that is subsequent to the first dataflow analysis property in a predetermined dataflow analysis property order.
Claim 11
Dependent Claim
52 words
The media of claim 8 wherein said linked list comprises data storage nodes of either a first smaller size or a second larger size, wherein data storage nodes of the second larger size include a second pointer storage space for storing a pointer identifying a location of an other data storage node.
Claim 12
Dependent Claim
18 words
The media of claim 9 wherein the sizes of individual nodes in said linked list are randomly determined.
Claim 13
Dependent Claim
37 words
The media of claim 9 wherein the pointer stored into the second pointer storage space of a node of the second larger size, identifies a location of a subsequent data storage node of the second larger size.
Claim 14
Dependent Claim
224 words
A computer system for compiling a computer procedure into a machine-readable representation, the computer system comprising: (a) an optimizer that optimizes the computer procedure into an optimized representation, the optimizer storing dataflow analysis properties relating to effects of instructions and expressions associated with the computer procedure, in a linked list of data storage nodes, a new data storage node for a new dataflow analysis property to be associated with the computer procedure being generated by: allocating said new data storage node, the new data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order; and (b) a machine-readable code generator that generates a machine-readable representation of the computer procedure from the optimized representation.
Claim 15
Dependent Claim
224 words
A computer system for compiling a computer procedure into a machine-readable representation, the computer system comprising: (a) an optimizer that optimizes the computer procedure into an optimized representation, the optimizer storing dataflow analysis properties relating to effects of instructions and expressions associated with the computer procedure, in a linked list of data storage nodes, a new data storage node for a new dataflow analysis property to be associated with the computer procedure being generated by: allocating said new data storage node, the new data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order; and (b) a machine-readable code generator that generates a machine-readable representation of the computer procedure from the optimized representation.
Claim 16
Dependent Claim
193 words
A program product, comprising: (a) a program configured to store dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, in a linked list of data storage nodes, and generate a new data storage node for a new dataflow analysis property to be associated with the computer procedure by: allocating said new data storage node, the ass data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order; and (b) a signal bearing media bearing the program.
Claim 17
Dependent Claim
193 words
A program product, comprising: (a) a program configured to store dataflow analysis properties relating to effects of instructions and expressions associated with a computer procedure, in a linked list of data storage nodes, and generate a new data storage node for a new dataflow analysis property to be associated with the computer procedure by: allocating said new data storage node, the ass data storage node including a data storage space for storing an identifier of a dataflow analysis property and at least a first pointer storage space for storing a pointer identifying a location of an other data storage node; storing into the data storage space of the new data storage node, an identifier of the new dataflow analysis property for which the new node was allocated; and storing into the first pointer storage space of the new data storage node, a pointer identifying a location of an other data storage node, the other data storage node storing an existing dataflow analysis property associated with the computer procedure that is subsequent to the new dataflow analysis property in a predetermined dataflow analysis property order; and (b) a signal bearing media bearing the program.
Claim 18
Dependent Claim
16 words
The program product of claim 13, wherein the signal bearing media is a transmission type media.
Claim 19
Dependent Claim
15 words
The program product of claim 13, wherein the signal bearing media is a recordable media.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-12 | 2004-03-13 | 2004-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-12 | 2008-03-13 | 2008-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-12 | 2012-03-13 | 2012-09-12 | $7700.00 | Window Closed / Lapsed |