RFR: 8251535: Partial peeling at unsigned test adds incorrect loop exit check

[Christian Hagedorn]

On Thu, 15 Oct 2020 12:42:53 GMT, Tobias Hartmann <thartmann at openjdk.org> wrote:

> C2's `PhaseIdealLoop::partial_peel` searches for loop exit tests on the induction variable as cut point for partial
> peeling. If no suitable signed test is found and `PartialPeelAtUnsignedTests` is enabled (default), unsigned `i <u
> limit` checks are used. Since the exit condition `!(i <u limit)` can be split into `i < 0 || i >= limit`,
> `PhaseIdealLoop::insert_cmpi_loop_exit` either clones the lower or upper bound check and inserts it as cut point before
> the unsigned test. For example:
>   loop:
>     i += 1000;
>     if (i <u 10_000) {
>         goto loop;
>     }
>     goto exit;
>   exit:
>     return i;
> 
> Is converted to:
> 
>   loop:
>     i += 1000;
>     if (!(i < 10_000)) {   <-- Loop exit test as cut point for partial peeling
>         goto exit;
>     }
>     if (i <u 10_000) {
>         goto loop;
>     }
>     goto exit;
>   exit:
>     return i;
>     
> Now the problem is that if the unsigned check is inverted, i.e. we exit if the check **passes**, the newly inserted
> test is incorrect:
>     
>   loop:
>     i += 1000;
>     if (i <u 10_000) {
>         goto exit;
>     }
>     goto loop;
>   exit:
>     return i;
> 
> Is converted to:
> 
>   loop:
>     i += 1000;
>     if (i < 10_000) {   <-- This exit condition is wrong! For example, we should not exit for i = -1.
>         goto exit;
>     }
>     if (i <u 10_000) {
>         goto exit;
>     }
>     goto loop;
>   exit:
>     return i;
> 
> This leads to incorrect results because the loop is left too early.
> 
> The fix is to simply bail out when the loop exit condition is `i <u limit` => `i >= 0 && i < limit` because it can't be
> split into a single signed exit check.
> Thanks,
> Tobias

Nice explanation! Looks reasonable to me.

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

Marked as reviewed by chagedorn (Reviewer).

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