JDK-6894778 : Loop Predication for Loop Optimizer in C2
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: hs18
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2009-10-23
  • Updated: 2013-11-01
  • Resolved: 2011-04-20
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6 Other
6u21Fixed hs17Fixed
Related Reports
Relates :  
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
14-01-2010