C2: assert(found) failed: memory-writing node is not placed in its original loop or an ancestor of it

FAILURE:

The attached program Store.java triggers an assertion failure when compiled by C2 as follows:

$ java -Xcomp -XX:-TieredCompilation -XX:CompileOnly=Store Store.java
(...)
# Internal Error (../../src/hotspot/share/opto/block.cpp:1241), pid=73942, tid=73955
# assert(found) failed: memory-writing node is not placed in its original loop or an ancestor of it
(...)

ANALYSIS:

The assertion is triggered within an OSR compilation that enters right before
the innermost loop in Store.java. The "memory-writing" node referred to in the
assertion failure is a store corresponding to "out = 42" ("94 storeImmI" in the
attached CFG store-actual.pdf). GCM moves the store from a loop preheader P
(B19) into its corresponding loop L ({B20, B21, B22, B23, B25, B26}) since both
P and L have the same estimated execution frequency. The reason L has the same
estimated frequency as P is that L exits (to B27) when the "break" is *not*
taken, which has 100% probability as "cond" is always false. Note that, due to
the special CFG shape in OSR compilations and to loop optimizations (strip
mining and "pre-main-post" splitting), L does not naturally correspond to a
single source-level loop in Store.java.

The attached store-expected.pdf shows a slight variation of the CFG (with
different estimated frequencies) where the "94 storeImmI" store is placed in B19
as expected.

The assertion failure is well-founded, as the movement of "94 storeImmI" into
B20 (header of L) violates the invariant that memory values do not interfere
after scheduling [1]. However, in this case the violation does not lead to C2
generating wrong code. Refining the assertion to capture only cases that lead to
wrong code generation would likely require a more sophisticated analysis
involving value and liveness analysis for memory values.

An enhancement is proposed in JDK-8258894 to avoid the interference violation in
the general case, after which the assertion should always hold.

[1] More specifically, in the program point after "94 storeImmI"
(store-actual.pdf), the memory values defined by both "94 storeImmI" and "96
Phi" are live and thus interfere. In contrast, in store-expected.pdf, the memory
value defined by "96 Phi" dies when it is used by "94 storeImmI".

ORIGINAL REPORT FROM FUZZER TEST:

The attached fuzzer test fails with the following assertion introduced in JDK-8255763:

To reproduce:
java -Xcomp -Xbatch -XX:-TieredCompilation -XX:CompileOnly=Test Test.java

#
# A fatal error has been detected by the Java Runtime Environment:
#
# Internal Error (/opt/mach5/mesos/work_dir/slaves/983c483a-6907-44e0-ad29-98c7183575e2-S14607/frameworks/1735e8a2-a1db-478c-8104-60c8b0af87dd-0196/executors/0fdf7e75-5e08-44a9-915d-9a12af821c8b/runs/b7ec209c-74e8-4daf-8366-5f29cccf9200/workspace/open/src/hotspot/share/opto/block.cpp:1241), pid=14717, tid=14731
# assert(found) failed: memory-writing node is not placed in its original loop or an ancestor of it
#
# JRE version: Java(TM) SE Runtime Environment (16.0+30) (fastdebug build 16-ea+30-2130)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (fastdebug 16-ea+30-2130, compiled mode, sharing, compressed oops, g1 gc, linux-amd64)
# Problematic frame:
# V [libjvm.so+0x6b7d36] PhaseCFG::verify() const+0x6c6
...........
Command Line: -Xmx1G -Xcomp -Xbatch -XX:-TieredCompilation -XX:CompileOnly=Test -XX:CompileCommand=quiet Test
...........
Current thread (0x00007ffb00495ac0): JavaThread "C2 CompilerThread0" daemon [_thread_in_native, id=14731, stack(0x00007ffae23fc000,0x00007ffae24fd000)]


Current CompileTask:
C2: 11947 7 % b Test::mainTest @ 172 (614 bytes)

Stack: [0x00007ffae23fc000,0x00007ffae24fd000], sp=0x00007ffae24f8320, free space=1008k
Native frames: (J=compiled Java code, A=aot compiled Java code, j=interpreted, Vv=VM code, C=native code)
V [libjvm.so+0x6b7d36] PhaseCFG::verify() const+0x6c6
V [libjvm.so+0xa0ea44] Compile::Code_Gen()+0x2c4
V [libjvm.so+0xa19ad7] Compile::Compile(ciEnv*, ciMethod*, int, bool, bool, bool, bool, DirectiveSet*)+0x1917
V [libjvm.so+0x849d8c] C2Compiler::compile_method(ciEnv*, ciMethod*, int, bool, DirectiveSet*)+0x1dc
V [libjvm.so+0xa29808] CompileBroker::invoke_compiler_on_method(CompileTask*)+0xe88
V [libjvm.so+0xa2a458] CompileBroker::compiler_thread_loop()+0x5a8
V [libjvm.so+0x18bb296] JavaThread::thread_main_inner()+0x256
V [libjvm.so+0x18c1c10] Thread::call_run()+0x100
V [libjvm.so+0x15a3d06] thread_native_entry(Thread*)+0x116