Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
149 words
A method operable within an optimizing compiler for generating basis items and kill sets for use during subsequent global common subexpression elimination and code motion prodecures, wherein a basis item is an operand which has not been previously defined in a selected instruction block, a basic block, and wherein a kill set is the set of non-basis items which depend on a selected basis item, a non-basis item being an operand which has been previously defined in the basic block, characterized by creating a tuple (v) for each computation which is to be converted to a machine instruction by the compiler, creating a first table having an entry for all the tuples in the program being compiled, assigning a symbolic register to each tuple created, and creating a second table of said assigned symbolic registers addressable by register designation containing the tuple to which that symbolic register is assigned.
Claim 2
Independent Claim
149 words
A method operable within an optimizing compiler for generating basis items and kill sets for use during subsequent global common subexpression elimination and code motion prodecures, wherein a basis item is an operand which has not been previously defined in a selected instruction block, a basic block, and wherein a kill set is the set of non-basis items which depend on a selected basis item, a non-basis item being an operand which has been previously defined in the basic block, characterized by creating a tuple (v) for each computation which is to be converted to a machine instruction by the compiler, creating a first table having an entry for all the tuples in the program being compiled, assigning a symbolic register to each tuple created, and creating a second table of said assigned symbolic registers addressable by register designation containing the tuple to which that symbolic register is assigned.
Claim 3
Dependent Claim
99 words
A method according to claim 1 further comprising: for every basis item in a tuple being entered in the first table adding to the kill set for that basis item, a symbolic register uniquely assigned to that tuple, for every non-basis item in the tuple being entered into the first table, adding the uniquely assigned symbolic register for that tuple to the kill sets for all the basis items in whose kill sets that non-basis item appears and designating the symbolic register assigned to the tuple in the table to the result of the computation of the non-basis element.
Claim 4
Dependent Claim
198 words
A method according to claim 1 or 2 further comprising: evalutaing the program and deriving a list of basis items contained therein, creating a tuple (v) for each computation which is to be converted to a machine instruction by the computer, creating a hash table having an entry for every potential tuple in the program being compiled, as each triple is generated by the compiler performing the following steps: 1) computing a hash address for the tuple 2) determining if an entry already exists for that tuple, 3) if an entry exists in the hash tuble, having a symbolic register designation r, returning r to the system controls 4) if no entry exists in the hash table for that tuple, assigning a unique symbolic register r to that tuple and storing same at the specific address in the hash table 5) determining how many operands are in the tuple and processing each as follows: 6) for each operand, if it is in the basis list storing the symbolic register designation r in that operands kill set 7) if the operand is not in the basis list storing the symbolic register designation in every kill set containing that operand.
Claim 5
Independent Claim
56 words
A method according to claims 1, 2 or 3 for selecting basis itmes without analyzing the program by putting the following items into a basis list: all user variables, and all descriptors of user variables, pointers to run-time stacks and heaps in which data objects are allocated, pointers to object code, destinguished compiler generated temporary results.