Date: Fri, 29 Mar 2024 06:53:53 +0000 (UTC) Message-ID: <1005461238.1285.1711695233343@34fc92c9345b> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1284_1318884933.1711695233343" ------=_Part_1284_1318884933.1711695233343 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
For loop-invariant arrays, range checks can usually be eliminated.
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.
Here is a simple case:
for (int index =3D Start; index < Limit; index++) { Array[index] =3D 0; }
The loop is split like this:
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 }
This typically happens when:
for (int index =3D Start; index < Limit; index +=3D STRIDE) { ... Array1[index * SCALE1 + Offset1] ... ... Array2[index * SCALE2 + Offset2] ... }
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.
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.
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:
A constant value can be a final static
variable.
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.
PhaseIdealLoop::add_constraint
in loopTra=
nsform.cpp.