[15] RFR(M): 8240227: Loop predicates should be copied to unswitched loops

[Christian Hagedorn]

Hi

Please review the following patch:
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.

Thank you!

Best regards,
Christian


[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
[5] https://bugs.openjdk.java.net/browse/JDK-8236722