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

[Vladimir Kozlov]

Looks good to me. Thank you for good explanation of the problem.

Vladimir K

On 3/11/20 5:20 AM, Christian Hagedorn wrote:
> 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