Please download the dossier by clicking on the dossier button x
×

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
First Claim
Patent Images

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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×