Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6894778

Loop Predication for Loop Optimizer in C2

    XMLWordPrintable

    Details

    • Subcomponent:
    • Resolved In Build:
      b08
    • CPU:
      generic
    • OS:
      generic
    • Verification:
      Not verified

      Backports

        Description

        To implement the loop predication optimization for the loop optimizer in the C2 compiler. The idea is to insert a predicate on the entry path to a loop, and raise a uncommon trap if the check of the condition(s) fails. The condition checks are promoted from inside the loop body, and thus the checks inside the loop could be eliminated.

        While the loop predication is more a framework, it could be applied to range check, null check, and array check eliminations, etc. Loop predication has advantage over the existing iteration-splitting based range check elimination, and loop peeling based null check and array check eliminations. First, it does not increase the code size (but the iteration splitting, and loop peeling do increase the code size significantly), so we can apply loop predication to outer loops without the conscern of code size increment. Second, while the iteration spliting based range check elimination leaves range checks in the pre- and post- loops not removed, loop predication does not split the loop, and thus the range checks could be eliminated for the whole loop body.

        Given the following example code regarding range check elimination, the existing iteration splitting based range check could only remove the range checks for col[i] and val[i] in the "main" loop of the innermost. However, when loop predication is applied, all range checks for col[i], val[i] in the innermost loop, as well as row[r+1] and y[r] in the outer loop could be removed in the loops. (Note: the range check for the indirect array reference x[col[i]] could not be removed by both approaches without knowing the value of col[i]; and the range check for row[r] is folded away into the range check for row[r+1])
        for (int r=0; r<M; r++) {
            double sum = 0.0;
            int rowR = row[r];
            int rowRp1 = row[r+1];
            for (int i=rowR; i<rowRp1; i++){
                sum += x[ col[i] ] * val[i];
            }
            y[r] = sum;
        }

        Finally, loop predication could be used as a framework for future aggressive loop optimizations when certain assumption is made (e.g., 99.9...% of the chances that certain case does not occur).

          Attachments

            Issue Links

              Activity

                People

                • Assignee:
                  cfang Changpeng Fang (Inactive)
                  Reporter:
                  cfang Changpeng Fang (Inactive)
                • Votes:
                  0 Vote for this issue
                  Watchers:
                  0 Start watching this issue

                  Dates

                  • Created:
                    Updated:
                    Resolved:
                    Imported:
                    Indexed: