RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).

The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).

Tested on:
- original bug reproducer
- hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
- hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)

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

Commit messages:
 - Update comments in test case
 - Exclude MachMerge nodes from dominance assertion
 - Remove cloned multi-nodes in call-catch cleanup
 - Document assumptions in live-range splitting
 - Add basic definition dominance assertion
 - Add test case

Changes: https://git.openjdk.java.net/jdk/pull/3303/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=3303&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8263227
  Stats: 102 lines in 4 files changed: 95 ins; 0 del; 7 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3303.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3303/head:pull/3303

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Nils Eliasson-2
On Thu, 1 Apr 2021 10:02:39 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>
> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>
> Tested on:
> - original bug reproducer
> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)

Looks good!

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

Marked as reviewed by neliasso (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
On Tue, 6 Apr 2021 09:42:01 GMT, Nils Eliasson <[hidden email]> wrote:

> Looks good!

Thanks for reviewing, Nils!

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Nils Eliasson-2
In reply to this post by Nils Eliasson-2
On Tue, 6 Apr 2021 09:42:01 GMT, Nils Eliasson <[hidden email]> wrote:

>> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>>
>> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>>
>> Tested on:
>> - original bug reproducer
>> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
>> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)
>
> Looks good!

And thanks for the PDF with the excellent walk through!

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Vladimir Kozlov-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 1 Apr 2021 10:02:39 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>
> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>
> Tested on:
> - original bug reproducer
> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)

src/hotspot/share/opto/lcm.cpp line 1415:

> 1413:       if (dead) {
> 1414:         // Remove projections if n is a dead multi-node.
> 1415:         for (uint k = j + n->outcnt(); sb->get_node(k)->is_Proj(); k--) {

I don't get this logic. The loop is not executed if sb->get_node(j + n->outcnt()) is not Proj node.

src/hotspot/share/opto/lcm.cpp line 1419:

> 1417:                  "dead projection should correspond to current node");
> 1418:           sb->get_node(k)->disconnect_inputs(C);
> 1419:           sb->remove_node(k);

If you remove node here then `j` could be incorrect in `sb->remove_node(j)` at line #1424

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Vladimir Kozlov-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 1 Apr 2021 10:02:39 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>
> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>
> Tested on:
> - original bug reproducer
> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)

Also where is guarantee that all Proj users are in the same block.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
In reply to this post by Vladimir Kozlov-2
On Tue, 6 Apr 2021 17:54:20 GMT, Vladimir Kozlov <[hidden email]> wrote:

>> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>>
>> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>>
>> Tested on:
>> - original bug reproducer
>> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
>> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)
>
> src/hotspot/share/opto/lcm.cpp line 1415:
>
>> 1413:       if (dead) {
>> 1414:         // Remove projections if n is a dead multi-node.
>> 1415:         for (uint k = j + n->outcnt(); sb->get_node(k)->is_Proj(); k--) {
>
> I don't get this logic. The loop is not executed if sb->get_node(j + n->outcnt()) is not Proj node.

Thanks for reviewing, Vladimir! The intention of this loop is to remove all projections of a multi-node `n` before removing `n` itself (if it has been found to be dead). I indeed have to rethink this code as e.g. the loop can be executed if `n` is not a multi-node but `k` ends up pointing to a projection of another node. I will investigate and come back with a new revision.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
In reply to this post by Vladimir Kozlov-2
On Tue, 6 Apr 2021 17:55:35 GMT, Vladimir Kozlov <[hidden email]> wrote:

>> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>>
>> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>>
>> Tested on:
>> - original bug reproducer
>> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
>> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)
>
> src/hotspot/share/opto/lcm.cpp line 1419:
>
>> 1417:                  "dead projection should correspond to current node");
>> 1418:           sb->get_node(k)->disconnect_inputs(C);
>> 1419:           sb->remove_node(k);
>
> If you remove node here then `j` could be incorrect in `sb->remove_node(j)` at line #1424

`k` should always be greater than `j`, as `sb->get_node(k)` is a projection of `sb->get_node(j)`. Shouldn't this make the removal safe?

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
In reply to this post by Vladimir Kozlov-2
On Tue, 6 Apr 2021 17:58:36 GMT, Vladimir Kozlov <[hidden email]> wrote:

> Also where is guarantee that all Proj users are in the same block.

Isn't this guaranteed by `PhaseCFG::schedule_node_into_block()`?

https://github.com/openjdk/jdk/blob/ec599da68cac6349e7f28b508d8038c18a4e7347/src/hotspot/share/opto/gcm.cpp#L48-L72

I will run some tests with extra assertions in `PhaseCFG::verify()` to double-check.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 8 Apr 2021 10:46:10 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> src/hotspot/share/opto/lcm.cpp line 1415:
>>
>>> 1413:       if (dead) {
>>> 1414:         // Remove projections if n is a dead multi-node.
>>> 1415:         for (uint k = j + n->outcnt(); sb->get_node(k)->is_Proj(); k--) {
>>
>> I don't get this logic. The loop is not executed if sb->get_node(j + n->outcnt()) is not Proj node.
>
> Thanks for reviewing, Vladimir! The intention of this loop is to remove all projections of a multi-node `n` before removing `n` itself (if it has been found to be dead). I indeed have to rethink this code as e.g. the loop can be executed if `n` is not a multi-node but `k` ends up pointing to a projection of another node. I will investigate and come back with a new revision.

On second thought, at the loop entry, the only users of `n` are (unused) projections or else `n` wouldn't be dead. Assuming these projections are scheduled right after `n`, the code should be OK. In any case, I will submit a (hopefully) clearer revision.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Vladimir Kozlov-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 8 Apr 2021 11:04:00 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> Also where is guarantee that all Proj users are in the same block.
>
>> Also where is guarantee that all Proj users are in the same block.
>
> Isn't this guaranteed by `PhaseCFG::schedule_node_into_block()`?
>
> https://github.com/openjdk/jdk/blob/ec599da68cac6349e7f28b508d8038c18a4e7347/src/hotspot/share/opto/gcm.cpp#L48-L72
>
> I will run some tests with extra assertions in `PhaseCFG::verify()` to double-check.

> > Also where is guarantee that all Proj users are in the same block.
>
> Isn't this guaranteed by `PhaseCFG::schedule_node_into_block()`?
>
>
> I will run some tests with extra assertions in `PhaseCFG::verify()` to double-check.

Okay.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Vladimir Kozlov-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 8 Apr 2021 13:49:56 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> Thanks for reviewing, Vladimir! The intention of this loop is to remove all projections of a multi-node `n` before removing `n` itself (if it has been found to be dead). I indeed have to rethink this code as e.g. the loop can be executed if `n` is not a multi-node but `k` ends up pointing to a projection of another node. I will investigate and come back with a new revision.
>
> On second thought, at the loop entry, the only users of `n` are (unused) projections or else `n` wouldn't be dead. Assuming these projections are scheduled right after `n`, the code should be OK. In any case, I will submit a (hopefully) clearer revision.

You are right that users will follow `n` but I am not sure that no other nodes were inserted in between users.
I would prefer to see loop code like this:
  for (uint k = new_cnt; k > j; k-- ) {
    Node* user = sb->get_node(k);
    if (user->is_Proj() && user->in(0) == n) {
Or may be record user's indexes into a local array for users in previous loop at lines #1406-1412 and iterate of that loop.
I also noticed wrong code stile in `for()` statements near your change. Please, fix them too.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Vladimir Kozlov-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 8 Apr 2021 10:54:31 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> src/hotspot/share/opto/lcm.cpp line 1419:
>>
>>> 1417:                  "dead projection should correspond to current node");
>>> 1418:           sb->get_node(k)->disconnect_inputs(C);
>>> 1419:           sb->remove_node(k);
>>
>> If you remove node here then `j` could be incorrect in `sb->remove_node(j)` at line #1424
>
> `k` should always be greater than `j`, as `sb->get_node(k)` is a projection of `sb->get_node(j)`. Shouldn't this make the removal safe?

Yes, you are right - users should follow.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block [v2]

Roberto Castañeda Lozano-2
In reply to this post by Roberto Castañeda Lozano-2
> This change eliminates dead multi-nodes created by call-catch cleanup after GCM. Eliminating all dead code created by call-catch cleanup avoids potential issues when splitting the live range of call result values, see the analysis in the [bug report](https://bugs.openjdk.java.net/browse/JDK-8263227) for details. This solution is the least invasive of the three alternatives proposed in the bug report (the other two are constraining global code motion and extending live-range splitting).
>
> The change also extends the control-flow graph verification pass to catch similar live-range splitting issues earlier (with `+VerifyRegisterAllocator`).
>
> Tested on:
> - original bug reproducer
> - hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
> - hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator` and `+StressGCM` (5 repetitions)

Roberto Castañeda Lozano has updated the pull request incrementally with four additional commits since the last revision:

 - Complete projection assertions with basic checks
 - Enforce code style in surrounding 'for' statements
 - Simplify loop that removes dead projections, rename and comment for clarity
 - Assert that projections are stuck to their parents

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/3303/files
  - new: https://git.openjdk.java.net/jdk/pull/3303/files/a4973ba0..808451de

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=3303&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=3303&range=00-01

  Stats: 26 lines in 2 files changed: 13 ins; 1 del; 12 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3303.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3303/head:pull/3303

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block [v2]

Roberto Castañeda Lozano-2
In reply to this post by Vladimir Kozlov-2
On Thu, 8 Apr 2021 18:20:13 GMT, Vladimir Kozlov <[hidden email]> wrote:

> I am not sure that no other nodes were inserted in between users.

Isn't this enforced by local scheduling? From `PhaseCFG::select()`:

https://github.com/openjdk/jdk/blob/b1ebf82269fa85bed859ffafacd59ed000f22bd0/src/hotspot/share/opto/lcm.cpp#L477-L478

https://github.com/openjdk/jdk/blob/b1ebf82269fa85bed859ffafacd59ed000f22bd0/src/hotspot/share/opto/lcm.cpp#L516-L523

`PhaseCFG::call_catch_cleanup()` runs right after local scheduling, and it doesn't reorder the cloned instructions before reaching the dead code elimination loop, so I don't see any place where other nodes might be inserted in between projections of the same node. I checked this with an assertion in `PhaseCFG::verify()` (commits 8d96589 and 808451d), and the following tests run without assertion failures:

- hs-tier1-5 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`
- hs-tier6-9 (linux-x64) with `+VerifyRegisterAllocator`
- hs-tier1-3 (windows-x64, linux-x64, linux-aarch64, and macosx-x64) with `+VerifyRegisterAllocator`, `+StressGCM`, and `+StressLCM` (5 repetitions)

Based on above analysis, code comments in `lcm.cpp`, and test results, I suggest to treat the fact that projections are scheduled next to their parent nodes as an invariant, and exploit the invariant as in this (updated) change -- but I am fine with the more defensive alternative you propose if you still prefer that.

> I also noticed wrong code stile in for() statements near your change. Please, fix them too.

Done.

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

PR: https://git.openjdk.java.net/jdk/pull/3303
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8263227: C2: inconsistent spilling due to dead nodes in exception block

Roberto Castañeda Lozano-2
In reply to this post by Vladimir Kozlov-2
On Thu, 8 Apr 2021 17:53:08 GMT, Vladimir Kozlov <[hidden email]> wrote:

> > > Also where is guarantee that all Proj users are in the same block.
> >
> >
> > Isn't this guaranteed by `PhaseCFG::schedule_node_into_block()`?
> > I will run some tests with extra assertions in `PhaseCFG::verify()` to double-check.
>
> Okay.

Done, see results in the related discussion (https://github.com/openjdk/jdk/pull/3303#discussion_r611430316).

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

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