RFR: 8278296: Generalize long range check transformation [v5]

[John R Rose]

On Wed, 26 Jan 2022 16:04:06 GMT, Roland Westrelin <roland at openjdk.org> wrote:

>> 8259609 (C2: optimize long range checks in long counted loops) only
>> covered the case of a counted loop with a positive stride and a range
>> check with a positive scale. This change generalizes the long range
>> check transformation to all 4 combinations of stride and scale signs.
>> 
>> The stride > 0, scale > 0 case (covered 8259609) was tweaked so it now
>> uses Qmax computed as the inclusive limit of j*K+Q. That helps in
>> generalizing the formulas to other cases.
>> 
>> The addition of PhaseIdealLoop::is_scaled_iv_plus_extra_offset() was
>> required for the case of negative scale in an int loop. The range
>> check then has the shape:
>> 
>> (CmpUL (AddL (ConvI2L (SubI ConI (LshiftI (Phi
>> 
>> with ConI, the zero constant.
>> 
>> This change also addresses this comment from John:
>> 
>> https://github.com/openjdk/jdk/pull/6576#discussion_r765343664
>> 
>> as part of 8276116 (C2: optimize long range checks in int counted loops)
>
> Roland Westrelin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   review

Attached is another bunch of documentation changes, explaining what's going on in great detail.  I think I'm done, actually.  I did this in concert with an executable test harness, to catch logic errors.

[roland-review-0301-patch.txt](https://github.com/openjdk/jdk/files/8165295/roland-review-0301-patch.txt)

In the transform code, I changed the names of some of the variables and some of the order of operations, to correspond better to the documentation (or so I hope; please check).

I made an algorithmic change, replacing an overflowing `Q_max+1` by simply `max_jlong` rather than `R`, since `max_jlong` is a simple rematerializable constant but `R` might need spilling.  I validated this change in my test harness; any value between R and `max_jlong` inclusive will work as `H_clamp`.

Near the conditional moves I made comments suggesting alternative flow-free idioms.  But I can't think of any good reason not to use the conditional moves, even on platforms (like old PPC) which implement them as control flow.  Feel free to toss those comments, though I enjoyed coming up with them.

For the record, I did a series of experiments to validate the subtle logic of this transformation.  Here is the code:
<http://cr.openjdk.java.net/~jrose/jvm/ClampedRangeCheckSimulation.zip>

Attached is another bunch of documentation changes, explaining what's going on in great detail.  I think I'm done, actually.  I did this in concert with an executable test harness, to catch logic errors.

[roland-review-0301-patch.txt](https://github.com/openjdk/jdk/files/8165295/roland-review-0301-patch.txt)

In the transform code, I changed the names of some of the variables and some of the order of operations, to correspond better to the documentation (or so I hope; please check).

I made an algorithmic change, replacing an overflowing `Q_max+1` by simply `max_jlong` rather than `R`, since `max_jlong` is a simple rematerializable constant but `R` might need spilling.  I validated this change in my test harness; any value between R and `max_jlong` inclusive will work as `H_clamp`.

Near the conditional moves I made comments suggesting alternative flow-free idioms.  But I can't think of any good reason not to use the conditional moves, even on platforms (like old PPC) which implement them as control flow.  Feel free to toss those comments, though I enjoyed coming up with them.

For the record, I did a series of experiments to validate the subtle logic of this transformation.  Here is the code:
<http://cr.openjdk.java.net/~jrose/jvm/ClampedRangeCheckSimulation.zip>

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

PR: https://git.openjdk.java.net/jdk/pull/6989