Eliminate Maximum Operation in Loop Bounds with Loop Versioning
First Claim
1. A method for eliminating maximum and minimum expressions within loop bounds, the method comprising:
- identifying a loop in a code;
determining whether the loop in the code meets conditions, wherein the conditions comprise;
an upper loop bound and a lower loop bound of the loop to contain maximum and minimum expressions;
operands in the maximum and minimum expressions to be loop-invariant, the operands being loop-invariant relative to an outermost loop of a nested loop if the loop is a nested loop;
a code size of the loop not to exceed a predetermined size; and
a total number of instructions within the loop to be greater than a predetermined constant;
determining a profitability of loop versioning based on a plurality of factors for the loop if the conditions are met, wherein the plurality of factors comprise;
a performance gain of a fast version of the loop;
a probability of executing the fast version of the loop at runtime; and
an overhead for performing loop versioning;
identifying a pair of lower loop bound and upper loop bound values that result in a constant number from the maximum and minimum expressions;
checking whether a loop iteration value is simplified into a non-zero constant;
examining branches within the loop for branch folding opportunities; and
performing loop versioning on the loop to generate a versioned loop.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and computer program product for eliminating maximum and minimum expressions within loop bounds are provided. A loop in a code is identified. The loop is determined to meet conditions, which require an upper loop bound and a lower loop bound to contain maximum and minimum expressions, loop-invariant operands, a predetermined size for a code size, and a total number of instructions to be greater than a predetermined constant. A profitability of loop versioning is determined based on a performance gain of a fast version of the loop, a probability of executing the fast version of the loop at runtime, and an overhead for performing loop versioning. A pair of lower loop bound and upper loop bound values resulting in a constant number is identified. A loop iteration value is checked to be a non-zero constant. Branches are identified, and loop versioning is performed to generate a versioned loop.
-
Citations
4 Claims
-
1. A method for eliminating maximum and minimum expressions within loop bounds, the method comprising:
-
identifying a loop in a code; determining whether the loop in the code meets conditions, wherein the conditions comprise; an upper loop bound and a lower loop bound of the loop to contain maximum and minimum expressions; operands in the maximum and minimum expressions to be loop-invariant, the operands being loop-invariant relative to an outermost loop of a nested loop if the loop is a nested loop; a code size of the loop not to exceed a predetermined size; and a total number of instructions within the loop to be greater than a predetermined constant; determining a profitability of loop versioning based on a plurality of factors for the loop if the conditions are met, wherein the plurality of factors comprise; a performance gain of a fast version of the loop; a probability of executing the fast version of the loop at runtime; and an overhead for performing loop versioning; identifying a pair of lower loop bound and upper loop bound values that result in a constant number from the maximum and minimum expressions; checking whether a loop iteration value is simplified into a non-zero constant; examining branches within the loop for branch folding opportunities; and performing loop versioning on the loop to generate a versioned loop. - View Dependent Claims (2)
-
-
3. A computer program product, tangibly embodied on a computer readable medium, for eliminating maximum and minimum expressions within loop bounds, the computer program product including instructions for causing a computer to execute a method, comprising:
-
identifying a loop in a code; determining whether the loop in the code meets conditions, wherein the conditions comprise; an upper loop bound and a lower loop bound of the loop to contain maximum and minimum expressions; operands in the maximum and minimum expressions to be loop-invariant, the operands being loop-invariant relative to an outermost loop of a nested loop if the loop is a nested loop; a code size of the loop not to exceed a predeternined size; and a total number of instructions within the loop to be greater than a predetermined constant; determining a profitability of loop versioning based on a plurality of factors for the loop if the conditions are met, wherein the plurality of factors comprise; a performance gain of a fast version of the loop; a probability of executing the fast version of the loop at runtime; and an overhead for performing loop versioning; identifying a pair of lower loop bound and upper loop bound values that result in a constant number from the maximum and minimum expressions; checking whether a loop iteration value is simplified into a non-zero constant; examining branches within the loop for branch folding opportunities; and performing loop versioning on the loop to generate a versioned loop.
-
-
4. The computer program product of claim 4, wherein the loop is a plurality of loops and performing loop versioning generates a plurality of versioned loops;
-
wherein combinations of the plurality of versioned loops are generated until the code reaches a predetermined limit; and wherein the plurality of versioned loops are sorted based on execution frequency information.
-
Specification