Integrated: JDK-8298118: split-if optimization causes empty loop to temporarily have more than one phi

[Damon Fenacci]

On Mon, 23 Jan 2023 17:41:01 GMT, Damon Fenacci <duke at openjdk.org> wrote:

> ## Issue
> C2 crashes with an assertion failure while running this very simple test:
> 
> static void test(int a) {
>     int I;
>     for (int j = 6; j < 129; ++j) {
>         a >>= 37388;
>         a += 1001;
>     }
>     a >>>= -8;
>     for (i = 0; i < 8; ++i) {
>         iArrFld[i] = I;
>     }
>     for (int j = i; j < 7; ) {
>         x = a;
>     }
> }
> 
> The failing assertion makes sure that only one phi exists when removing empty counted loops (in `IdealLoopTree::do_remove_empty_loop`), i.e. the one of the induction variable.
> 
> https://github.com/openjdk/jdk/blob/836198a4009c4a3f10a76dc8734e4792bb2509ba/src/hotspot/share/opto/loopTransform.cpp#L3623-L3629
> 
> ---
> ## Cause
> The test code produces an empty counted loop with 2 phis: nodes 398 (induction variable) and 495.
> <img width="324" alt="image" src="https://user-images.githubusercontent.com/2198987/214060433-db007bfa-6e64-419c-a144-38031bb33a86.png">
> Phi 495 is dead and should be removed (in fact it is set to be removed in one of the next IGVN iterations but the assert happens before the next iteration).
> 
> We get to this situation from here (while running `PhaseIdealLoop::split_if_with_blocks`):
> <img width="465" alt="image" src="https://user-images.githubusercontent.com/2198987/214054769-dc680a6e-af5d-4e68-8a86-c1a8f20a3405.png">
> _Split-if_ "moves" node 396 before phi 401 (it actually creates new nodes 495 and 496) and additionally one of 495's inputs gets replaced by a constant (singleton).
> <img width="390" alt="image" src="https://user-images.githubusercontent.com/2198987/214062911-717f7b77-29c7-481e-8471-8bee0cbbf02d.png">
> 
> Then dead nodes are removed starting from 396 (396, 401, 395). To avoid killing the new node (495) a use to a temporary node is added during the iterative removal run (the reason for this is explained by @vnkozlov [here](https://github.com/openjdk/jdk/pull/3336#discussion_r610877083)):
> <img width="310" alt="image" src="https://user-images.githubusercontent.com/2198987/214063747-af3a3971-d35f-4998-9170-27c8a4f7cfc4.png">
> 
> So, we end up with this graph:
> <img width="297" alt="image" src="https://user-images.githubusercontent.com/2198987/214076314-0b2a75fb-7207-43bb-9f98-036054007773.png">
> 
> It is worth mentioning that the code envisages the removal of the new node (495) if dead, but only in the next iteration (it gets added to the _worklist_).
> https://github.com/openjdk/jdk/blob/836198a4009c4a3f10a76dc8734e4792bb2509ba/src/hotspot/share/opto/phaseX.cpp#L1493-L1495
> 
> Later on in the same iteration, while running `IdealLoopTree::iteration_split`, the loop body gets "cleaned"
> https://github.com/openjdk/jdk/blob/836198a4009c4a3f10a76dc8734e4792bb2509ba/src/hotspot/share/opto/loopTransform.cpp#L4040-L4041
> So, the dead phi node (495) is removed from `IdealLoopTree::_body` but it still remains linked to the _CountedLoop_ node (397).
> The body is now empty and is therefore scheduled to be removed in `IdealLoopTree::do_remove_empty_loop` but the assert checking for the number of phis attached to the _CountedLoop_ node (397) finds 2 phis and breaks.
> 
> ---
> ## Further consideration
> The situation that caused this assert to fail is very specific (split-if, counted loop, empty body...) but we can't rule out that another constellation won't produce the same issue.
> 
> ---
> ## Possible solutions
> I can think of three possible fixes for this issue:
> 
> **1.** relaxing the check for the assert so that only phis with no uses are taken into account (the one currently implemented with this PR)
> **2.** removing the dead phi node right after replacing
> https://github.com/openjdk/jdk/blob/836198a4009c4a3f10a76dc8734e4792bb2509ba/src/hotspot/share/opto/loopopts.cpp#L1139-L1141
> 
> // Remove possibly dead phi node immediately
> if (phi != NULL && phi->outcnt() == 0) {
>   _igvn.remove_dead_node(phi);
> }
> 
> **3.** removing the dead phi node when removing it from the loop body in `IdealLoopTree::DCE_loop_body`
> 
> void IdealLoopTree::DCE_loop_body() {
>   for (uint i = 0; i < _body.size(); i++) {
>     Node *node = _body.at(i);
>     if (node->outcnt() == 0) {
>       _body.map(i, _body.pop());
>       _phase->_igvn.remove_dead_node(node);
>       i--; // Ensure we revisit the updated index.
>     }
>   }
> }
> 
> 
> **...what do you think?**

This pull request has now been integrated.

Changeset: 4b0e656b
Author:    Damon Fenacci <damon.fenacci at oracle.com>
Committer: Tobias Hartmann <thartmann at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/4b0e656bb6a823f50507039df7855183ab98cd83
Stats:     59 lines in 2 files changed: 57 ins; 0 del; 2 mod

8298118: split-if optimization causes empty loop to temporarily have more than one phi

Reviewed-by: roland, thartmann, kvn

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

PR: https://git.openjdk.org/jdk/pull/12148