Strength reduction compiler optimizations for conditional operations
AssigneeInternational Business Machines Corporation
InventorWilliam J. Schmidt
Life of this patent
Estimating the term…
Abstract
An optimizing compiler includes a strength reduction mechanism that optimizes a computer program that includes conditional operations by analyzing the instructions in the computer program in a single pass, determining whether instruction substitution is profitable for original instructions in the code, and performing instruction substitution for one or more original instructions for which instruction substitution is deemed profitable, including conditional operations. The substituted instructions result in strength reduction in the computer program.
Claims13
An apparatus comprising:
- at least one processor;
- a memory coupled to the at least one processor;
- a computer program residing in the memory, the computer program including a plurality of instructions;
- and
- an optimizing compiler residing in the memory and executed by the at least one processor, the optimizing compiler including a strength reduction mechanism that analyzes the computer program in a single pass, determines whether a conditional operation in the computer program could be improved by substituting at least one alternative instruction for at least one original instruction in the operation, and when the conditional operation in the computer program could be improved, substituting the at least one alternative instruction for the at least one original instruction.
An article of manufacture comprising software stored on a non-transitory computer readable storage medium, the software comprising:
- a strength reduction mechanism that analyzes in a single pass a computer program that has a plurality of instructions, determines whether a conditional operation in the computer program could be improved by substituting at least one alternative instruction for at least one original instruction in the conditional operation, and when the conditional operation in the computer program could be improved, substituting the at least one alternative instruction for the at least one original instruction.
The article of manufacture of claim 18 wherein the strength reduction mechanism further analyzes the computer program in the single pass by constructing a candidate table of instructions in the computer program in an order determined by the dominator tree, computing cost of each candidate in the candidate table, and determining whether a selected candidate in the candidate table is profitable based on the computed cost.
An apparatus comprising:
- at least one processor;
- a memory coupled to the at least one processor;
- a computer program residing in the memory, the computer program including a plurality of instructions;
- and
- an optimizing compiler residing in the memory and executed by the at least one processor, the optimizing compiler performing the steps of:
- generating a control flow graph of the computer program, the control flow graph comprising a plurality of basic blocks;
- generating a dominator tree that represents which basic blocks in the control flow graph dominate other basic blocks in the control flow graph;
- processing the instructions in the control flow graph in an order determined by the dominator tree to generate a candidate table of instructions with corresponding data;
- computing cost of each candidate in the candidate table;
- for each selected candidate in the candidate table, when the cost for the selected candidate indicates the selected candidate is profitable, performing the steps of:
- substituting at least one alternative instruction for at least one original instruction in the computer program;
- and
- removing at least one unneeded instruction from the computer program, wherein an instruction is unneeded due to the replacement of the at least one original instruction with the at least one alternative instruction.
Dependencies are inferred from the claim text.