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

[Christian Hagedorn]

Thank you Nils for your review!

Best regards,
Christian

On 12.03.20 16:16, Nils Eliasson wrote:
> Hi Christian,
> 
> I like the comprehensive tests you added.
> 
> Reviewed!
> 
> // Nils
> 
> On 2020-03-11 13:20, 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