Strength reduction compiler optimizations for operations with unknown strides

摘要

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.

主权项

1. 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 by a compiler performing the steps of:
constructing a control flow graph of the instructions in the computer program;building a dominator tree corresponding to the control flow graph that indicates which blocks in the control flow graph dominate other blocks in the control flow graph;determining an order of analyzing the instructions in the control flow graph in the single pass based on the dominator tree;constructing a candidate table of instructions in the computer program in an order determined by the dominator tree;generating at least one increment table by processing the candidate table;computing cost of each increment in the increment table; anddetermining whether a selected increment in the increment table is profitable based on the computed cost; determining by the compiler 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, the compiler substituting the at least one alternative instruction for the at least one original instruction.