RFR: 8289996: Fix array range check hoisting for some scaled loop iv

[Pengfei Li]

Recently we found some array range checks in loops are not hoisted by
C2's loop predication phase as expected. Below is a typical case.

  for (int i = 0; i < size; i++) {
    b[3 * i] = a[3 * i];
  }

Ideally, C2 can hoist the range check of an array access in loop if the
array index is a linear function of the loop's induction variable (iv).
Say, range check in `arr[exp]` can be hoisted if

  exp = k1 * iv + k2 + inv

where `k1` and `k2` are compile-time constants, and `inv` is an optional
loop invariant. But in above case, C2 igvn does some strength reduction
on the `MulINode` used to compute `3 * i`. It results in the linear index
expression not being recognized. So far we found 2 ideal transformations
that may affect linear expression recognition. They are

- `k * iv` --> `iv << m + iv << n` if k is the sum of 2 pow-of-2 values
- `k * iv` --> `iv << m - iv` if k+1 is a pow-of-2 value

To avoid range check hoisting and further optimizations being broken, we
have tried improving the linear recognition. But after some experiments,
we found complex and recursive pattern match does not always work well.
In this patch we propose to defer these 2 ideal transformations to the
phase of post loop igvn. In other words, these 2 strength reductions can
only be done after all loop optimizations are over.

Tested hotspot::hotspot_all_no_apps, jdk::tier1~3 and langtools::tier1.
We also tested the performance via JMH and see obvious improvement.

Benchmark                        Improvement
RangeCheckHoisting.ivScaled3          +21.2%
RangeCheckHoisting.ivScaled7           +6.6%

-------------

Commit messages:
 - 8289996: Fix array range check hoisting for some scaled loop iv

Changes: https://git.openjdk.org/jdk/pull/9508/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=9508&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8289996
  Stats: 164 lines in 3 files changed: 163 ins; 0 del; 1 mod
  Patch: https://git.openjdk.org/jdk/pull/9508.diff
  Fetch: git fetch https://git.openjdk.org/jdk pull/9508/head:pull/9508

PR: https://git.openjdk.org/jdk/pull/9508