RFR: 8331717: C2: Crash with SIGFPE Because Loop Predication Wrongly Hoists Division Requiring Zero Check [v2]

[Christian Hagedorn]

On Thu, 12 Dec 2024 08:48:14 GMT, Theo Weidmann <tweidmann at openjdk.org> wrote:

>> Fixes a bug in loop predication where not strictly invariant tests involving divisions or modulo are pulled out of the loop.
>> 
>> The bug can be seen in this code:
>> 
>> 
>> public class Reduced {
>>     static int iArr[] = new int[100];
>> 
>>     public static void main(String[] strArr) {
>>         for (int i = 0; i < 10000; i++) {
>>             test();
>>         }
>>     }
>> 
>>     static void test() {
>>         int i1 = 0;
>> 
>>         for (int i4 : iArr) {
>>             i4 = i1;
>>             try {
>>                 iArr[0] = 1 / i4;
>>                 i4 = iArr[2 / i4]; // Source of the crash
>>             } catch (ArithmeticException a_e) {
>>             }
>>         }
>>     }
>> }
>> 
>> 
>> The crucial element is the division `2 / i4`. Since it is used to access an array, it is the input to a range check. See node 230:
>> <img width="699" alt="Screenshot 2024-12-11 at 15 14 47" src="https://github.com/user-attachments/assets/0b2ed978-7135-4a7e-bd10-25c0ffe7a9bb" />
>> 
>> Loop predication will try to pull this range check together with its input, the division, before the `for` loop. Due to a bug in Invariance::compute_invariance loop predication is allowed to do so, which results in the division being pulled out without its non-zero check. 322 is a clone of 230 placed before the loop head without any zero check for the divisor:
>> 
>> <img width="798" alt="Screenshot 2024-12-11 at 15 11 48" src="https://github.com/user-attachments/assets/9d4911cc-9967-4b7a-9969-98e01a55cd0d" />
>> 
>> 
>> More specifically, this bug occurs because 230's zero check (174 If) is not its direct control. Between the zero check and the division is another unrelated check (293 RangeCheck), which can be hoisted:
>> 
>> <img width="825" alt="Screenshot 2024-12-12 at 09 14 37" src="https://github.com/user-attachments/assets/bd572556-1d30-41d5-b74c-22b673963dc2" />
>> 
>> Due to the way the Invariance class works, a check that can be hoisted will be marked as invariant. Then, to determine if any given node is invariant, Invariance::compute_invariance checks if all its inputs are invariant:
>> 
>> https://github.com/openjdk/jdk/blob/ceb4366ebf02f64165acc4a23195e9e3a7398a5c/src/hotspot/share/opto/loopPredicate.cpp#L456-L475
>> 
>> Therefore, when recursively traversing the inputs for 230 Div, the hoisted, unrelated check 293 RangeCheck is hit before the zero check. As that check has been hoisted before already, it is marked invariant and `all_inputs_invariant` will be set to true. (All other inputs are...
>
> Theo Weidmann has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Combine test files

You're welcome :-) 

> Then the division is anchored in the loop because the zero check of invar2 is in the loop

Unfortunately, this is already the case before this fix. We can only hoist the zero check out of the loop but not the division itself - it ends up at the next control node which is the `LoopNode` if it was the first check. Thus, we propose to have a closer look at that separately - there is definitely room for improvement:

> Even when going with Option 1 or 2, we could still allow rewiring of divisions to a dominating check if we can prove that this is a zero check that covers the division to be rewired (e.g. same divisor and comparison excludes zero etc.) - and maybe that's all we need (discussed this idea with @eme64). Could be investigated with/against Option 3.

I think that aligns with your suggestion here:

> One find suggestion, though, what do you think about overriding DivINode::depends_only_on_test and checking if the control node is a pattern that does exclude 0 from the value range of the divisor. This will do the job as the control of 230 DivI is an unrelated RangeCheck, making depends_only_on_test return false and the division stays in the loop while for the aforementioned case the control is the zero check and the division can be hoisted out of the loop.

Not exactly sure what you mean with the `CastNode`. Are you thinking in a more general sense to handle `CastNodes`, unrelated to divisions? It indeed generally is a problem for any kind of pinned data node that loses connection to its check. For `CastNodes`, we also pin them for array accesses with `pin_array_access_node()` - not only load nodes. There might be more problems with `CastNodes` where we need to do this more careful pinning as for array accesses. One would need to further investigate.

Nevertheless, with this fix, I don't think we make the current situation worse: We cannot hoist divisions out of the loop and Theo's patch just fixes an edge case, where we wrongly hoisted a division out of a loop. My guess is that disallowing that edge case does not affect performance much.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/22666#issuecomment-2556980947