Patent ID: 8087012

Claim:
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.