Efficient dead code elimination
AssigneeSun Microsystems, Inc.
InventorsSreekumar R. Nair, Sheldon M. Lobo
Life of this patent
Estimating the term…
Abstract
Disclosed is a method for eliminating dead code from a computer program using an operands graph generated from a flow graph of a computer program. In one embodiment of the present invention, the operands graph is traversed for any unused operands. Upon detection of any,unused operands, the instructions defining the unused operands are removed from execution.
Claims19
A computer implemented method of optimizing a program, comprising:
- detecting an unused operand within an operands graph, said operands graph including a linked list of all operands defined and used within the program;
- removing the instruction defining said unused operand from execution by marking said instruction as dead;
- marking said operand as dead when an operand reference count of an operand within said operands graph is not decremented from an initial value;
- and
- decrementing an operand reference count of each operand from the initial value each time the operand is used by said instruction.
A computer-readable storage medium having stored thereon instructions which, when executed by a processor, configure the processor to perform a method comprising:
- detecting an unused operand within an operands graph, said operands graph including a linked list of all operands defined and used within the program;
- removing the instruction defining said unused operand from execution;
- and
- traversing a linked list of basic blocks and said linked list of operands in said operands graph for one or more unused operands.
A system having processor comprising:
- an operands graph traversal module configured to traverse an operands graph generated from a computer program, said operands graph including a linked list of all operands defined and used within the program;
- a dead operands detection module configured to detect an unused operand using said operands graph, detect an operand within said operands graph having a use-def count of 1, and mark said operand as dead;
- and
- a dead instruction detection module configured to remove an instruction defining said unused operand from execution and mark said instruction as dead in response to said dead operands detection module marking said operand as dead.
A system having processor comprising:
- means for detecting an unused operand within an operands graph, said operands graph including a linked list of all operands defined and used within the program;
- and
- means for removing the instruction defining said unused operand from executions, said means for removing comprising:
- means for marking said instruction as dead, and
- means for adjusting a flow graph such that said instruction is not executed, said flow graph generated from a computer program, said operands graph generated via static single assignment from said flow graph.
Dependencies are inferred from the claim text.