Eliminate Maximum Operation in Loop Bounds with Loop Versioning

• US 20090055815A1
• Filed: 08/21/2007
• Published: 02/26/2009
• Est. Priority Date: 08/21/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chan, Edwin
• Granted Patent: US 8,087,012 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

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.

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.

2. The method of claim 1, 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.

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.