Bug ID: JDK-8304042 C2 SuperWord: schedule must remove packs with cyclic dependencies

Versions (Unresolved/Resolved/Fixed)

The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.

JDK 21
21 b17Fixed

I have found a Test.java, where we have independency on pair and pack level.
The nodes in a pack are all mutually independent (none have a path to any other of them).
But: the packs have cyclic dependencies between them.
When this is SuperWord-vectorized, it leads to wrong results, operations are reordered that should not be reordered.

Regression Test.java
./java -XX:CompileCommand=compileonly,Test::test -Xbatch -XX:+TraceSuperWord -XX:+TraceNewVectors Test.java

I found this during the work of JDK-8298935. The bugs are related, but not the same. JDK-8298935 did not properly verify that the packs were independent.
But independence on pack level is not sufficient, there can still be cyclic dependencies between the packs. This bug here reveals this.

It seems that we missed out on this, even though the SuperWord paper mentions that one has to be careful about cyclic dependencies between the (independent) packs.

See
https://groups.csail.mit.edu/cag/slp/SLP-PLDI-2000.pdf
(3.7 Scheduling)

See also my explanations in the PR of JDK-8298935:
https://github.com/openjdk/jdk/pull/12350#issuecomment-1465860465

Changeset: 83a924a1 Author: Emanuel Peter <epeter@openjdk.org> Date: 2023-04-05 04:52:11 +0000 URL: https://git.openjdk.org/jdk/commit/83a924a1008853dee2ead8f6c3a82f9e3abc6125
05-04-2023
A pull request was submitted for review. URL: https://git.openjdk.org/jdk/pull/13078 Date: 2023-03-17 14:34:26 +0000
23-03-2023
I found a bit more complicated case, where we even hit an assert: ./java -XX:-TieredCompilation -Xbatch --add-modules java.base --add-exports java.base/jdk.internal.misc=ALL-UNNAMED -XX:CompileCommand=compileonly,Test3::test -XX:CompileCommand=printcompilation,Test3::* -XX:LoopUnrollLimit=250 -XX:LoopMaxUnroll=5 Test3.java # Internal Error (/home/emanuel/Documents/fork6-jdk/open/src/hotspot/share/opto/loopnode.cpp:5384), pid=1933953, tid=1933966 # assert(!is_visited) failed: visit only once in PhaseIdealLoop::build_loop_early In the attached picture, we can see that the IR now has cyclic dependency of data/memory nodes, but no phi node is in that cycle. This leads to an unschedulable graph. Hence the assert. I suspect that we expected to traverse a DAG, but then visited a node twice, hence we found a cycle where we did not expect it. The reason is still the same bug: we schedule packs that have cyclic dependencies. We now see that cyclic dependency trigger this "visit only once" assert.
17-03-2023
I found a test that reproduces on 17, and maybe much earlier. See Test2.java java -XX:-TieredCompilation -Xbatch --add-modules java.base --add-exports java.base/jdk.internal.misc=ALL-UNNAMED Test2.java
16-03-2023
Great, Test2.java also reproduces with JDK 11u.
16-03-2023
Quickly checked and the Test.java reproducer first triggers the issue after JDK-8304042 in JDK 18 which is probably just because the test relies on the conversions supported with that change. Older JDK versions should be affected as well.
13-03-2023
ILW = Same as JDK-8298935 = P3
13-03-2023

Relates :	JDK-8304720 - SuperWord::schedule should rebuild C2-graph from SuperWord dependency-graph
Relates :	JDK-8298935 - fix independence bug in create_pack logic in SuperWord::find_adjacent_refs
Relates :	JDK-8275317 - AArch64: Support some type conversion vectorization in SLP