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

[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%

Pengfei Li has updated the pull request incrementally with one additional commit since the last revision:

  Address comment from merykitty

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

Changes:
  - all: https://git.openjdk.org/jdk/pull/9508/files
  - new: https://git.openjdk.org/jdk/pull/9508/files/f65be1c8..8a3c704a

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=9508&range=01
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=9508&range=00-01

  Stats: 14 lines in 1 file changed: 9 ins; 2 del; 3 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