RFR: 8320909: C2: Adapt IGVN's enqueuing logic to match idealization of AndNode with LShift operand

[Marc Chevalier]

On Wed, 23 Apr 2025 09:49:40 GMT, Marc Chevalier <mchevalier at openjdk.org> wrote:

>> The JBS issues has 3 reproducers. Two of them don't reproduce anymore. Let's enumerate:
>> 
>> - Test, TestSimple:
>>   Disappeared with:
>>   [JDK-8319372: C2 compilation fails with "Bad immediate dominator info"](https://bugs.openjdk.org/browse/JDK-8319372) in #16844
>>   which actually fixed it by removing the handling of the problematic pattern in `CastIINode::Value`.
>>   Reverting this fix makes the issue reappear.
>> - Reduced2: I fix here
>> - Test3, Reduced3:
>>   Disappeared with:
>>   [JDK-8347459: C2: missing transformation for chain of shifts/multiplications by constants](https://bugs.openjdk.org/browse/JDK-8347459) in #23728
>>   which just shadowed it. The bug is essentially the same as Reduced2 otherwise. I also fix these here (even with reverted JDK-8347459)
>> 
>> The issue comes from the fact that `And[IL]Node::Value` has a special handling when
>> an operand is a left-shift: in the expression
>> 
>> lhs & (X << s)
>> 
>> if `lhs` fits in less than `s` bits, the result is sure to be 0. This special handling
>> also tolerate a `ConvI2LNode` between the `AndLNode` and `LShiftINode`. In this case,
>> updating the Shift node during IGVN won't enqueue directly the And node, but only the
>> Conv node. If this conv node cannot be improved, the And node is not enqueued, and its
>> type is not as good as it could be.
>> 
>> Such a case is illustrated on the following figures from Reduced2. Node `239 Phi` is a phi with a
>> dead branch, so the node is about to be eleminated. On the second figure, we can see
>> `152 LShiftI` taking its place. The node `243 ConvI2L` is enqueued, but no change happens
>> during its idealization, so the node `244 AndL` is not enqueued, while it could receive an update.
>> 
>> 
>> <img src="https://github.com/user-attachments/assets/a68b27d0-b3cc-4850-b20e-0cff17047ed8" width="400">
>> <img src="https://github.com/user-attachments/assets/d98731e8-d85c-413d-a77e-059787b01884" width="400">
>> 
>> The fix is pretty direct: we recognize this pattern and we enqueue the And node during IGVN
>> to make sure it has a chance to be refined.
>> 
>> The case of Reduced3 is mostly the same, with a twist: the special handling of And nodes
>> also can see through casts. See the next figure with a `CastIINode` between the `AndINode` and
>> the `LShiftINode`. The fix has to take that into account.
>> 
>> <img src="https://github.com/user-attachments/assets/ae3d5a01-a0d6-4346-944c-4ba46af64ee2" width="400">
>> 
>> 
>> Overall, the situation can be of the form:
>> 
>> LShift -> C...
>
> I've added the other (not-anymore-)reproducer, tried to make clear where it comes from but where it was fixed. I've renamed the issue, added flag-free runs (because actually no flags are really needed for these). I think the PR is ready for more review.

> @marc-chevalier FYI: https://github.com/openjdk/jdk/pull/17508 this could be an alternative solution, at least once we fully follow that road. It tracks the "known bits", which would give you the "modulo information".

Yes, exactly! A bitwise domain is exactly what we could use here. It'd give limited modulo/range information, but with bitwise operations, we care about bits. Godspeed to that! It's nice.

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

PR Comment: https://git.openjdk.org/jdk/pull/24792#issuecomment-2823956171