United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6894778 Loop Predication for Loop Optimizer in C2
JDK-6894778 : Loop Predication for Loop Optimizer in C2

Details
Type:
Enhancement
Submit Date:
2009-10-23
Status:
Closed
Updated Date:
2011-04-20
Project Name:
JDK
Resolved Date:
2011-04-20
Component:
hotspot
OS:
generic
Sub-Component:
compiler
CPU:
generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
hs18
Fixed Versions:
hs17 (b08)

Related Reports
Backport:
Relates:

Sub Tasks

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).

                                    

Comments
EVALUATION

Don't know why jprt didn't update the evaluation (maybe due to "-id loop_predication"). But here is the hg changeset 
information

Changeset: b2b6a9bf6238
Author:    cfang
Date:      2010-01-12 14:37 -0800
URL:       http://hg.openjdk.java.net/jdk7/hotspot-comp/hotspot/rev/b2b6a9bf6238

6894779: Loop Predication for Loop Optimizer in C2
Summary: Loop predication implementation
Reviewed-by: never, kvn

! src/share/vm/includeDB_compiler2
! src/share/vm/opto/c2_globals.hpp
! src/share/vm/opto/compile.cpp
! src/share/vm/opto/compile.hpp
! src/share/vm/opto/loopTransform.cpp
! src/share/vm/opto/loopnode.cpp
! src/share/vm/opto/loopnode.hpp
! src/share/vm/opto/parse.hpp
! src/share/vm/opto/parse1.cpp
! src/share/vm/opto/parse2.cpp
! src/share/vm/opto/split_if.cpp
! src/share/vm/runtime/deoptimization.cpp
! src/share/vm/runtime/deoptimization.hpp
                                     
2010-01-14



Hardware and Software, Engineered to Work Together