US 7,444,626 B2Granted

Apparatus and method for linear dead store elimination

AssigneeInternational Business Machines Corporation

InventorsRonald Ian McIntosh, Mark Peter Mendell

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus and method for removing stores to local variables that are not aliased by other variables or to variables which have already been removed by previous optimizations prior to performing dead store elimination optimization are provided. With the method and apparatus, instructions that include a memory reference to a local variable that is not modified by other instructions are identified. For these instructions, an identifier of the variable referenced is maintained in a data structure along with the location of the store instruction in the procedure (for a store instruction) or a load indicator (for a load instruction). The data structure is then traversed to see if there are any store instructions referencing a variable that does not have a corresponding load instruction referencing the same variable. Such store instructions are eliminated prior to performing traditional dead store elimination.

Claims18

Dependent claims

A method, in a data processing system, for optimizing instructions, comprising:

receiving a set of instructions;
performing linear dead store elimination on each instruction in the set of instructions to form partially optimized instructions, wherein the linear dead store elimination comprises:
determining, for an instruction including a memory reference to a local variable, that the instruction is a dead store instruction with regard to the local variable;
and
writing a linear dead store elimination data structure entry into a linear dead store elimination data structure for the dead store instruction;
traversing the linear dead store elimination data structure to identify linear dead store elimination data structure entries corresponding to store instructions that do not have matching linear dead store elimination data structure entries corresponding to load instructions;
and
removing the instructions from the set of instructions that have linear dead store elimination data structure entries corresponding to store instructions that do not have matching linear dead store elimination data structure entries corresponding to load instructions;
and
providing the partially optimized instructions to a conventional dead store elimination engine for performing traditional dead store elimination operations on the partially optimized instructions to generate optimized instructions.

7 more elements

A computer program product in a recordable-type medium for optimizing instructions, comprising:

first instructions for receiving a set of instructions;
second instructions for performing linear dead store elimination on each instruction in the set of instructions to form partially optimized instructions, wherein the second instructions for performing the linear dead store elimination comprises:
third instructions for determining, for an instruction including a memory reference to a local variable, that the instruction is a dead store instruction with regard to the local variable;
and
fourth instructions for writing a linear dead store elimination data structure entry into a linear dead store elimination data structure for the dead store instruction;
fifth instructions for traversing the linear dead store elimination data structure to identify linear dead store elimination data structure entries corresponding to store instructions that do not have matching linear dead store elimination data structure entries corresponding to load instructions;
and
sixth instructions for removing the instructions from the set of instructions that have linear dead store elimination data structure entries corresponding to store instructions that do not have matching linear dead store elimination data structure entries corresponding to load instructions;
and
seventh instructions for providing the partially optimized instructions to a conventional dead store elimination engine for performing traditional dead store elimination operations on the partially optimized instructions to generate optimized instructions.

7 more elements

Dependencies are inferred from the claim text.