JDK-8240227 : Loop predicates should be copied to unswitched loops
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 11,12,13,14,15
  • Priority: P2
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2020-02-28
  • Updated: 2022-05-06
  • Resolved: 2020-03-19
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 11 JDK 14 JDK 15
11.0.8-oracleFixed 14.0.2Fixed 15 b16Fixed
Related Reports
Relates :  
JDK-8252696 - Loop unswitching may cause out of bound array load to be executed
Relates :  
JDK-8193130 - Bad graph when unrolled loop bounds conflicts with range checks
Relates :  
JDK-8253644 - C2: assert(skeleton_predicate_has_opaque(iff)) failed: unexpected
Relates :  
JDK-8237859 - C2: Crash when loads float above range check
Relates :  
JDK-8203915 - Induction variable of over-unrolled loop conflicts with range checks
Description
While working on JDK-8237859, we have discovered that control edges from RangeCheck loop predicates (which replaced RangeCheck nodes in the loop) to LoadP nodes are not updated when unswitching a loop and then creating pre/main/post loops for both unswitched versions (see comments in JDK-8237859). As a result, the main loop can be overunrolled and made not entrant but an optimized LoadP which makes an out-of-bounds access is scheduled even before the loop unswitching if.

A closer look at loop unswitching suggests that we need to copy the loop predicates down to both unswitched versions anyways. Otherwise, the pre/main/post code does not find the original loop predicates anymore due to the added loop selection if statement. It could then overunroll the main loop without properly updating the range check predicates. This has not been observed, yet. However, when running the attached test which overunrolls both unswitched loops, we hit the bad AD file assertion below which must be related to the missing loop predicates that need to be copied down to the main loop while creating pre/main/post loops. The same assertion error was reported originally before cloning the predicates down to the main loop while creating pre/main/post loops in JDK-8203915.


Default case invoked for: 
   opcode  = 106, "Con"
o1	Con	=== o0  [[]]  #top

--N: o1	Con	=== o0  [[]]  #top

# To suppress the following error report, specify this argument
# after -XX: or in .hotspotrc:  SuppressErrorAt=/matcher.cpp:1563
#
# A fatal error has been detected by the Java Runtime Environment:
#
#  Internal Error (open/src/hotspot/share/opto/matcher.cpp:1563), pid=4259, tid=4271
#  assert(false) failed: bad AD file
#
# JRE version: Java(TM) SE Runtime Environment (15.0) (slowdebug build 15-internal+0-2019-11-08-0757471.christian...)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (slowdebug 15-internal+0-2019-11-08-0757471.christian..., compiled mode, compressed oops, g1 gc, linux-amd64)
# Problematic frame:
# V  [libjvm.so+0xd99893]  Matcher::Label_Root(Node const*, State*, Node*, Node const*)+0x4d3
#
# Core dump will be written. Default location: Core dumps may be processed with "/usr/share/apport/apport %p %s %c %d %P" (or dumping to /home/christian/jdk/open/core.4259)
#
# An error report file with more information is saved as:
# /home/christian/jdk/open/hs_err_pid4259.log
#
# Compiler replay data is saved as:
# /home/christian/jdk/open/replay_pid4259.log
#
# If you would like to submit a bug report, please visit:
#   https://bugreport.java.com/bugreport/crash.jsp
#
Current thread is 4271
Dumping core ...
Aborted (core dumped)


Reproduce:
java -Xcomp -XX:+TraceLoopOpts -XX:-TieredCompilation -XX:CompileCommand=compileonly,Overunrolling::test5 Overunrolling.java

The attached test was adapted from compiler/loopopts/TestOverunrolling::test5 by adding an additional if statement to trigger loop unswitching.
Comments
Fix request (11u) -- will label after testing completed. I would like to downport this for parity with 11.0.8-oracle. Applies clean.
14-04-2020
Fix Request (JDK 14.0.2) This patch fixes a crash in C2 and is required for backporting JDK-8237859. The fix is medium risk and applies cleanly to JDK 14.0.2. In addition to CI testing through all tiers in JDK 15 and 11u, additional testing will be executed in JDK 14.0.2 before pushing.
08-04-2020
URL: https://hg.openjdk.java.net/jdk/jdk/rev/76058080c621 User: chagedorn Date: 2020-03-19 09:15:24 +0000
19-03-2020
https://bugs.openjdk.java.net/browse/JDK-8240227 http://cr.openjdk.java.net/~chagedorn/8240227/webrev.00/ This is the same problem as for JDK-8203915 [1] but now with additional loop unswitching which was not handled in the fix for JDK-8203915. Background: The original idea of inserting skeleton predicates [2] for range check predicates involving the loop induction variable was to copy those concrete predicates down to the main loop when creating pre/main/post loops. When unrolling the loop later, the limit check predicate for the induction variable is updated to become stronger and cover all accesses of the unrolled loop body. If a predicate for the main loop later turns out to always fail due to type information, then the main loop can be completely removed. If we did not do that (which exactly happens in the test case since we do not copy the range check predicates to the unswitched loops which are therefore not found when creating pre/main/post loops for the slow and fast loop) then the C2 matcher can hit the bad AD file assert when over-unrolling the main loop. In the test case some data paths die because CastII nodes for an array load are replaced by TOP. This happens after Opaque1 nodes are removed and the type information about the maximum number of iterations for the pre-loop propagate to the induction variable of the main loop. IGVN concludes that the induction variable is out-of-bounds for some CastII nodes which are then replaced by TOP. As a result, the graph contains vectorized results with a TOP memory input which cannot be handled by the matcher. [3] shows the IR before doing the first IGVN iteration where major_progress() is false (Opaque1 nodes can be removed). The 719 Opaque1 is removed and the type information of 1063 MinI [int:0..13] propagates to the induction variable of the pre-loop 701 Phi [int:5..13] (loop starts with j = 5, at most 8 iterations of the pre-loop) which then propagates over 716 CastII [int:6..14] -> 1665 Phi [int:6..max-31] (32 iterations after unrolling) -> 1537 AddI [int:30..max-7] (adds 24) which is then compared with 1027 CastII [int:5..7] (iArr[i]). [int:5..7] does not contain [int:30..max-7] and therefore 1027 CastII is replaced with TOP. The main loop is dead but is not removed since there is no range check predicate for the main loop that would notice that some loads are always out-of-bounds due to the type information. The fix for JDK-8203915 avoids that (for loops without unswitching) by adding range check predicates for the main loop which are then updated while unrolling and later allow the main loop to be removed. The only thing missing is that the created range check predicates for a loop to be unswitched are not cloned to both unswitched loop versions. Therefore, the changes for [1] cannot be applied since it does not find any predicates when creating pre/main/post loops for the slow and fast loop. This fix addresses that and clones all range check predicates that have at least one control edge to a data node which is part of the loop to be unswitched. All control edges to data nodes which are part of either the slow or fast loop are updated to the new cloned predicates accordingly. All old range predicates of the original loop to be unswitched that do not have any control edges to data nodes can be removed. This patch is also a prerequisite for the fix of JDK-8237859 [4]. I included some renaming for predicate related code that should make the difference between the various predicate types and how they are used clearer (skeleton, concrete, empty, updated...). I also included many more unswitch tests (PartialPeelingUnswitch.java) that I originally wrote as part of an RFE in progress [5] but also helped with testing this fix. [1] https://bugs.openjdk.java.net/browse/JDK-8203915 [2] https://bugs.openjdk.java.net/browse/JDK-8193130 [3] https://bugs.openjdk.java.net/secure/attachment/87257/IR_before_IGVN_major_progress_false.png [4] https://bugs.openjdk.java.net/browse/JDK-8237859
11-03-2020
A fix is currently being tested which clones a range check predicate down to both unswitched loop versions if it has control edges to data nodes that are specific to one of the unswitched loops (part of the original, unswitched loop and therefore cloned to the slow loop while the original node belongs to the fast loop). It also rewires the control inputs to the original predicates to the corresponding cloned version. A range check predicate is not cloned if it has only control edges to data nodes that are not part of the (original, unswitched) loop anymore. Range check predicates without any control edges to data nodes (like a range check for the loop condition variable) are cloned. This fix is needed to further test the fix for JDK-8237859 on top of it. http://cr.openjdk.java.net/~chagedorn/8240227/webrev.00/
06-03-2020
Seems unrelated to JDK-8238812, as the attached fuzzer test of that bug does not apply any loop unswitching.
02-03-2020
ILW = Crash during compilation, reproducible with simple test, disable loop unswitching = HMM = P2
28-02-2020