RFR: 8332920: C2: Partial Peeling is wrongly applied for CmpU with negative limit

[Tobias Hartmann]

On Mon, 3 Jun 2024 12:39:05 GMT, Christian Hagedorn <chagedorn at openjdk.org> wrote:

> A signed test is wrongly split off an unsigned test during Partial Peeling which results in not entering a loop even though it should. 
> 
> #### Idea of Partial Peeling
> 
> Partial Peeling rotates a loop with the hope to being able to convert the loop into a counted loop later. It is therefore preferable to use signed tests over unsigned tests because counted loops must use a signed loop exit test (i.e. with a `BaseCountedLoopEnd`). 
> 
> #### Partial Peeling with Unsigned Test
> 
> However, if there is only a suitable unsigned test, we can still try to use it for Partial Peeling. The idea is to then split off a signed version of the unsigned test and place it right before the unsigned test which can then be used as a loop exit test and later as `BaseCountedLoopEnd`:
> 
> https://github.com/openjdk/jdk/blob/0ea3bacf48be90d93f9e6c8e6568a0b8c61afb46/src/hotspot/share/opto/loopopts.cpp#L3074-L3080
> 
> #### Requirements for Using an Unsigned Test
> 
> The Signed and Unsigned Loop Exit Test do not need have the same result at runtime. It is sufficient if the Signed Loop Exit Test implies the Unsigned Loop Exit Test:
> - If the Signed Loop Exit Test is false, then the (original) Unsigned Loop Exit Test will make sure to exit the loop if required.
> - If the Signed Loop Exit Test is true, then the (original) Unsigned Loop Exit Test must also be true. Otherwise, we would exit a loop that we should have continued to execute. 
> 
> #### The Requirements Are Currently Broken
> 
> This strong requirement for splitting off a signed test is currently broken as seen in the test cases (for example, `testWhileLTIncr()`): We split off the signed loop exit test `i >= limit`, then partial peel and we get the signed loop exit test `i >= limit` as entry guard to the loop which is wrong:
> 
> https://github.com/openjdk/jdk/blob/0ea3bacf48be90d93f9e6c8e6568a0b8c61afb46/test/hotspot/jtreg/compiler/loopopts/TestPartialPeelAtUnsignedTestsNegativeLimit.java#L159-L178
> 
> #### Why Are the Requirements Broken?
> 
> The reason is that 
> 
> i >=u limit
> 
> can only be converted into the two signed comparisons
> 
> i < 0 || i >= limit
> 
> if `limit` is non-negative (i.e. `limit >= 0`): 
> https://github.com/openjdk/jdk/blob/0ea3bacf48be90d93f9e6c8e6568a0b8c61afb46/src/hotspot/share/opto/loopopts.cpp#L3054-L3061
> 
> This is currently missing and we wrongly use `i < 0` or `i >= limit` as split off signed test.
> 
> #### Fixing the Broken Requirements
> To fix this, I've added a bailout when `limit` could be negative which is the same as checking if the type of ...

Looks great otherwise. Nice test and proof!

src/hotspot/share/opto/loopopts.cpp line 3054:

> 3052:   //   i < 0 || i >= limit
> 3053:   //
> 3054:   // Note that this does not hold for limit < 0:

As we discussed, rephrase this as counterexample.

src/hotspot/share/opto/loopopts.cpp line 3076:

> 3074:   // Loop:
> 3075:   //   <peeled section>
> 3076:   //   Signed Loop Exit Condition i < 0 or i >= limit

Suggestion:

  //   Signed Loop Exit Condition i < 0 (or i >= limit)

src/hotspot/share/opto/loopopts.cpp line 3090:

> 3088:   //      i <   0        // Signed Loop Exit Condition
> 3089:   //      i >u  MAX_INT  // all negative values are greater than MAX_INT when converted to unsigned
> 3090:   //      i >=u limit    // limit <= MAX_INT (trivially) and since limit >= 0 assumption (COND)

As we discussed, an intermediate step in the proof would be good here.

src/hotspot/share/opto/loopopts.cpp line 3099:

> 3097:   // After Partial Peeling, we have the following structure:
> 3098:   //   <cloned peeled section>
> 3099:   //   Signed Loop Exit Condition i < 0 or i >= limit

Suggestion:

  //   Signed Loop Exit Condition i < 0 (or i >= limit)

src/hotspot/share/opto/loopopts.cpp line 3104:

> 3102:   //     <rest of unpeeled section>
> 3103:   //     <peeled section>
> 3104:   //     Signed Loop Exit Condition i < 0 or i >= limit

Suggestion:

  //     Signed Loop Exit Condition i < 0 (or i >= limit)

test/hotspot/jtreg/compiler/loopopts/TestPartialPeelAtUnsignedTestsNegativeLimit.java line 145:

> 143:             // <Peeled Section>
> 144: 
> 145:             // Found as loop head in ciTypeFlow, but both path inside loop -> head not cloned.

Suggestion:

            // Found as loop head in ciTypeFlow, but both paths inside loop -> head not cloned.

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

Marked as reviewed by thartmann (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/19522#pullrequestreview-2098147678
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627150450
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627145726
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627176821
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627144467
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627144737
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627050035