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

[Emanuel Peter]

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 ...

More to come later

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

> 3050:   //   limit >= 0   (COND)
> 3051:   // then the unsigned loop exit condition is equivalent to the signed loop exit condition
> 3052:   //   i < 0 || i >= limit

Could we come up with an alternative equation if `limit < 0`? And maybe even a combined condition? Not sure if that is helpful, but I'd like to think about it. Could also be a follow-up RFE.

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

> 3066:   }
> 3067: 
> 3068:   // For stride < 0, we split off the signed loop exit condition

Suggestion:

  // For stride < 0, we insert off the signed loop exit condition

Why do you say "split", we are inserting this extra check, right? Or is the idea that the "rotation" puts this new condition as the last check, hence the exit check in the loop body? Being a big more explicit could help here.

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

> 3085:   //   "Signed Loop Exit Test" implies "Unsigned Loop Exit Test"
> 3086:   // This is trivially given:
> 3087:   // - Stride < 0:

Suggestion:

  // - stride < 0:

Stylistic decision, leave this to your

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

There is not litterally an `OR` here, right? It's a bit confusing.

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

PR Review: https://git.openjdk.org/jdk/pull/19522#pullrequestreview-2098213690
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627105115
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627116743
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627112350
PR Review Comment: https://git.openjdk.org/jdk/pull/19522#discussion_r1627118565