Strength reduction compiler optimizations for operations with unknown strides
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 operations that have an unknown stride 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 operations with unknown strides. 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 an operation in the computer program that has an unknown stride at compile-time could be improved by substituting at least one alternative instruction for at least one original instruction in the operation;
- and
- when the operation in the computer program that has an unknown stride at compile-time 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:
- (A) generating a control flow graph of the computer program, the control flow graph comprising a plurality of basic blocks;
- (B) generating a dominator tree that represents which basic blocks in the control flow graph dominate other basic blocks in the control flow graph;
- (C) 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;
- (D) selecting a root candidate from the candidate table;
- (E) processing the candidate table of instructions to generate an increment table for the selected root candidate and related candidates in the candidate table;
- (F) computing cost of each increment in the increment table;
- (G) for each selected increment in the increment table, when the cost for the selected increment indicates the selected increment is profitable, performing the steps of:
- inserting an initializer instruction for a temporary variable;
- substituting at least one alternative instruction that references the temporary variable 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 insertion of the initializer instruction for the temporary variable and the replacement of the at least one original instruction with the at least one alternative instruction;
- (H) repeating steps (D), (E), (F) and (G) until all root candidates in the candidate table have been processed.
Dependencies are inferred from the claim text.