Date: Sun, 26 Jun 2022 14:43:08 +0000 (UTC) Message-ID: <1297188864.3105.1656254588611@4aa150d0af50> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_3104_1303178251.1656254588611" ------=_Part_3104_1303178251.1656254588611 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html RangeCheckElimination

# RangeCheckElimination

#### Iteration = range splitting

=20

For loop-invariant arrays, range checks can usually be eliminated.

= =20

=20

This is carried out by means of iteration range splitting. A middle rang= e of loop index values is computed before the loop is entered. (It is often= the whole sequence of index values, but need not be if loop peeling or unr= olling is happening also.) The loop is cloned three times, with the three c= lones running in succession. The middle loop handles the middle range, and = the pre-loop (resp. post-loop) handles any index values before (resp. after= ) the middle range. The middle range is chosen so that the middle loop (mai= n loop) is as large as possible, but is constrained to values which can be = predicted not to cause array range checks to fail.

=20

Here is a simple case:

=20
Simple Loop
=20
```for (int index =3D Start; index < Limit; index++) {
Array[index] =3D 0;
}
```
=20
=20

The loop is split like this:

=20
Simple Loop, Optimized
=20
```int MidStart =3D Math.max(Start, 0);
int MidLimit =3D Math.min(Limit, Array.length);
int index =3D Start;
for (; index < MidStart; index++) { // PRE-LOOP
Array[index] =3D 0;  // RANGE CHECK
}
for (; index < MidLimit; index++) { // MAIN LOOP
Array[index] =3D 0;  // NO RANGE CHECK
}
for (; index < Limit; index++) {  // POST-LOOP
Array[index] =3D 0;  // RANGE CHECK
}
```
=20
=20

#### When the optimi= zation applies

=20

This typically happens when:

=20
=20
• the array is a loop invariant,
• =20
• on a hot loop,
• =20
• whose index variable has a constant stride,
• =20
• and where the array is indexed by linear functions of the index variabl= e.
• =20
=20
Typical Loop
=20
```for (int index =3D Start; index < Limit; index +=3D STRIDE) {
... Array1[index * SCALE1 + Offset1] ...
... Array2[index * SCALE2 + Offset2] ...
}
```
=20
=20

Capitalized names (`Limit`, `Array1`) must be loop= -invariant, while all-caps names (`STRIDE`, `SCALE1`)= must be compile-time constants. Any number of arrays can be dealt with thi= s way, both for read and write. Other non-matching arrays will not disturb = the optimization, but they will be range-checked continually. The loop need= not be a literal Java `for` statement; the JIT can deal with a = wide range of loop idioms.

=20

The values `MinStart` and `MinLimit` are computed = similarly as above, except that there are more min/max terms, and there may= be divisions if `SCALE` values are not unity.

=20

This pattern is quite general, although it doesn't help with every imagi= nable loop. Pointer-chasing loops, and loops with non-constant strides, don= 't participate in this optimization. Key rules of thumb:

=20
=20
• =20
• Use at most simple linear expressions to index each array.
• =20
=20

A constant value can be a `final static` variable.

=20

A loop-invariant value can be an object field, as long as the compiler c= an prove the field isn't changed by the loop. This will fail if the loop bo= dy is not totally inlined, and the object field cannot be proven non-escapi= ng.

=20

#### Source code

=20
=20
• See logic related to `PhaseIdealLoop::add_constraint` in loopTra= nsform.cpp.
• =20
• The optimization is controlled by the flag RangeCheckElimination.
• = =20
------=_Part_3104_1303178251.1656254588611--