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.
Claims9
1-6. (canceled)
A computer-implemented method executed by at least one processor for processing a plurality of instructions in a computer program, the method comprising the steps of:
- analyzing the computer program in a single pass;
- determining 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.
13-18. (canceled)
A computer-implemented method executed by at least one processor for processing a plurality of instructions in a computer program, the method comprising 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.