Eliminating maximum/minimum operations in loop bounds

Abstract

A technique is provided 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.

1. A method for eliminating maximum and minimum expressions within loop bounds, the method comprising:
 identifying an unmodified loop in a code; 
 determining whether the unmodified loop in the code meets conditions to be identified as a candidate for loop versioning, wherein meeting the conditions for the unmodified loop comprises: 
 determining that an upper loop bound and a lower loop bound of the unmodified loop contain maximum and minimum expressions;
 determining that operands in the maximum and minimum expressions are loop-invariant in the unmodified loop, the operands being loop-invariant relative to an outermost loop of a nested loop if the unmodified loop is the nested loop; 
 determining that a code size of the unmodified loop does not exceed a predetermined size; and 
 determining that a total number of instructions within the unmodified loop is greater than a predetermined constant; 
 
 determining a profitability of loop versioning the unmodified loop based on a plurality of factors for the unmodified loop in response to the conditions being met, wherein determining the profitability using the plurality of factors comprise:
 examining a performance gain of a fast version of the unmodified loop versus the unmodified loop; 
 examining a probability of executing the fast version of the unmodified loop at runtime; and 
 examining 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 of the unmodified loop; 
 checking whether a loop iteration value is simplified into a non-zero constant; 
 examining branches within the unmodified loop for branch folding opportunities; and 
 performing loop versioning on the unmodified loop to generate a versioned loop; 
 wherein examining the probability of executing the fast version of the unmodified loop at runtime is predicted utilizing only static analysis, in response to the pair of lower loop bound and upper loop bound values resulting in the constant number from the maximum and minimum expressions of the unmodified loop and in response to the loop iteration value being simplified into the non-zero constant. 
 
     
     
       2. The method of  claim 1 , wherein the unmodified loop is a plurality of unmodified 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. 
 
     
     
       3. A computer program product, tangibly embodied on a non-transitory 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 an unmodified loop in a code; 
 determining whether the unmodified loop in the code meets conditions to be identified as a candidate for loop versioning, wherein meeting the conditions for the unmodified loop comprises:
 determining that an upper loop bound and a lower loop bound of the unmodified loop contain maximum and minimum expressions; 
 determining that operands in the maximum and minimum expressions are loop-invariant in the unmodified loop, the operands being loop-invariant relative to an outermost loop of a nested loop if the unmodified loop is the nested loop; 
 determining that a code size of the unmodified loop does not exceed a predetermined size; and 
 determining that a total number of instructions within the unmodified loop are greater than a predetermined constant; 
 
 determining a profitability of loop versioning the unmodified loop based on a plurality of factors for the unmodified loop in response to the conditions being met, wherein determining the profitability using the plurality of factors comprise:
 examining a performance gain of a fast version of the unmodified loop versus the unmodified loop; 
 examining a probability of executing the fast version of the unmodified loop at runtime; and 
 examining 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 of the unmodified loop;
 checking whether a loop iteration value is simplified into a non-zero constant; 
 examining branches within the unmodified loop for branch folding opportunities; and 
 performing loop versioning on the unmodified loop to generate a versioned loop; 
 wherein examining the probability of executing the fast version of the unmodified loop at runtime is predicted utilizing only static analysis, in response to the pair of lower loop bound and upper loop bound values resulting in the constant number from the maximum and minimum expressions of the unmodified loop and in response to the loop iteration value being simplified into the non-zero constant. 
 
 
     
     
       4. The computer program product of  claim 3 , wherein the unmodified 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.