Loop Invariant Method Expression Hoisting

摘要

A system, method and computer-readable medium are disclosed for improving the performance of a compiler. A set of source code instructions are processed to generate a plurality of source code instruction subsets, each of which is respectively associated with a mathematical operator. The source code subsets are then reordered to “hoist,” or place, a source code instruction subset associated with a product operator before a source code instruction subset associated with a summation operator. The plurality of source code instruction subsets are iteratively reordered until no source code instruction subset associated with a summation operator precedes a source code instruction subset associated with a product operator. A compiler is then used to compile the resulting reordered plurality of source code instruction subsets into a set of optimized object code instructions.

主权项

1. A computer-implementable method for improving the performance of a compiler, comprising:
identifying, in source code, an expression that is included in a nested loop, the expression including at least one term that is dependent on at least one iterator variable of the nested loop; generating a sum-of-products representation of the expression, the sum-of-products representation including a summation of groups of multiplied terms in the expression; for each multiplied term in the sum-of-products representation,
sorting terms in the multiplied term based on iterator variables of the nested loop; andmodifying the sum-of-products representation to insert partial; expressions in place of the terms that depend on the same iterator variables; modifying the source code so that partial expressions in the sum-of-products representation are moved from an inner loop of the nested loop to an outer loop of the nested loop when the partial expressions do not depend on an iterator variable of the inner loop; and compiling the source code to produce object code.