harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sergey Kuksenko (JIRA)" <j...@apache.org>
Subject [jira] Created: (HARMONY-2170) [drlvm][jit] Suggestion of new Range Check elimination optimization.
Date Mon, 13 Nov 2006 13:03:37 GMT
[drlvm][jit] Suggestion of new Range Check elimination optimization.
--------------------------------------------------------------------

                 Key: HARMONY-2170
                 URL: http://issues.apache.org/jira/browse/HARMONY-2170
             Project: Harmony
          Issue Type: Improvement
          Components: DRLVM
         Environment: All.
            Reporter: Sergey Kuksenko


Currently [drlvm][jit] contains ABCD (range check elimination) algorithm.
ABCD algorithm works pretty well if iterations over an array is perfomed with array.length
access.
However, there are a set of code patterns where ABCD algorithm won't work.
For example, java.util classes ArrayList, Vector, HashMap, etc... very often contains a field
where a real upper bound is stored (and usually this upped bound is less then array.legth).
So, iteration over such arrays usually is performed by the following way:

 for (int i = 0; i < real_length; i++) {
    array[i]....
}

Where "real_length" is a field which contains real upper bound.
Very often it is too expensive or impossible for JIT to determine value range for this field
and in such ways (when cycle limit is value obtained outside method) ABCD range check elimination
can't work.

Suggestion:

In case of cycle like:
int i=0;
while(i < real_length) {
   checkRange(array, i);  // introduce explicit range check operation
   ...array[i]...
   i++;
}

Split this cycle to:

int i=0;
while(i < min(real_length, array.length) ) {
   ...array[i]...         // NO range check here
   i++;
}
while(i<real_length) {
   checkRange(array, i);
   ...array[i]...
   i++;
}

After such splitting range check is useless at the first cycle and may be removed.



-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message