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

[John R Rose]

On Tue, 25 Jan 2022 12:29:57 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 two additional commits since the last revision:
> 
>  - fixes
>  - John's patch

src/hotspot/share/opto/loopTransform.cpp line 2543:

> 2541: //------------------------------is_scaled_iv---------------------------------
> 2542: // Return true if exp is a constant times the given induction var (of type bt).
> 2543: // The multiplication must be done in full precision (exactly of type bt).

Now that the short-scale detection is factored up here, the comment should change also.
I've also tweaked the pseudocode grammar to be (I think) more correct.

 // The multiplication is either done in full precision (exactly of type bt),
 // or else bt is T_LONG but iv is scaled using 32-bit arithmetic followed by a ConvI2L.
 // This grammar of cases is recognized, where X is I|L according to bt:
 //    SIV[iv] = VIV[iv] | (CastXX SIV[iv])
 //            | (MulX VIV[iv] ConX) | (MulX ConX VIV[iv])
 //            | (LShiftX VIV[iv] ConI)
 //            | (ConvI2L SIV[iv])  -- a "short-scale" can occur here; note recursion
 //            | (SubX 0 SIV[iv])  -- same as MulX(iv, -scale); note recursion
 // On success, the constant scale value is stored back to ret_scale.
 // The value (*p_short_scale) reports if such a ConvI2L conversion was present.

src/hotspot/share/opto/loopTransform.cpp line 2558:

> 2556:     if (p_scale != NULL) {
> 2557:       *p_scale = 1;
> 2558:     }

(Should set short_scale to false on this path.)

src/hotspot/share/opto/loopTransform.cpp line 2620:

> 2618:       }
> 2619:       if (p_short_scale != NULL) {
> 2620:         // (ConvI2L (MulI iv K)) can be 64-bit linear if iv is kept small enough...

Since short-scale is already set by the recursive call to `is_scaled_iv`, it should not be overwritten here.  Suggest using `|=` instead of `=` to assign the value, since you can only get a short-scale from one place, but it might come from either the recursive call or the current call.

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

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