Page History

Loop Optimizations in C2

Loop Identification

ciTypeFlow analysis

Single entry loops

Irreducible loops

Clone loop head

Parse phase

Add regions and phis for loop head

IdealLoop phase

Replace Region with Loop node

Beautify loops: split shared headers and merge multiple entry and back branch paths

Loop Construction

Building side tables for ideal graph

IdealLoopTree structures describe loops tree

Dominators for control graph

Data nodes placement

Initial nodes assignment to loops (build_loop_early)

...

Find best nodes placement (build_loop_late)

Loop Optimizations

Split-if and split-through-phi

Local subgraph transformations to simplify graph

Loop predication

Range checks and NULL checks moved outside loop if possible

Array filling

Pattern match array initialization loop and replace it with call to assembler stub

Vectorization

Replace array initialization, copy and arithmetic with vector operations in unrolled loops

Iteration splitting for inner loops

For each optimization below policy method is called to determine which optimization could be done for this loop

...

Main loop unrolling (with maximum 16 unrolls)

Range Check Elimination

For array accesses range check is generated in compiled code:

...

  If (index * SCALE + Offset < Range) {

Loop Predication

The general idea is to insert a predicate on the entry path to a loop, and raise a uncommon trap if the check of the condition fails. The condition checks are promoted from inside the loop body, and thus the checks inside the loop could be eliminated. Currently, loop predication optimization has been applied to remove array range check and loop invariant checks (such as null checks).

...

Similar to array range check elimination loop predication is used to move a loop invariant check outside the loop directly.

Loop Predication Advantages

Existing optimizations that perform elimination of checks inside the loops are iteration range splitting based. The loop is peeled to form pre-, main- and post-loops. The loop bounds are adjusted in the ways that checks in the main-loop could be safely removed.

...