RFR: 8366815: C2: Delay Mod/Div by constant transformation

[Emanuel Peter]

On Fri, 24 Oct 2025 07:23:02 GMT, Hannes Greule <hgreule at openjdk.org> wrote:

>> @iwanowww I'm not quite following your suggestions / questions.
>> 
>>> It seems the root cause is a divergence in functionality in GVN between different representations of Div/Mod nodes.
>> 
>>> How hard would it be to align the implementation and improve GVN handling for other representations, so the same type is constructed irrespective of the IR shape?
>> 
>> Do you consider the "expanded" versions of Div/Mod as a "different representation of Div/Mod"?
>> If yes: we could pattern match for such "expanded" versions of Div/Mod, but it would be quite complex: you would have to parse through patterns like displayed [up here](https://github.com/openjdk/jdk/pull/27886#issuecomment-3436423466). Do you think that is a good idea? I already mentioned the idea [up here](https://github.com/openjdk/jdk/pull/27886#issuecomment-3435782079), but did not think it was desirable due to the complexity.
>> 
>>> Alternatively, as part of the expansion, new representation can be wrapped in CastII/CastLL with the narrower type of original Div/Mod node.
>> 
>> How does this "wrapping" help? After parsing, the CastII at the bottom of the "expanded" Div would just have the whole int range. How would the type of the CastII ever be improved, without pattern matching the "expanded" Div?
>
>> It seems the root cause is a divergence in functionality in GVN between different representations of Div/Mod nodes.
>> 
>> How hard would it be to align the implementation and improve GVN handling for other representations, so the same type is constructed irrespective of the IR shape?
> 
> For Div, we can have either the magic multiply/shift variant, or shifting for powers of 2. Each of these can have slightly different shapes depending on e.g., the sign of the divisor, the sign of the dividend, and the sign of the magic constant.
> For DivL, we also use MulHi if supported and a different sequence of instructions otherwise.
> 
> For Mod, we either do what we do for Div, multiply again and subtract to get the remainder; or we just directly use And, or we do the Mersenne number optimization (related: https://bugs.openjdk.org/browse/JDK-8370135) which unrolls the same few operations multiple times.
> 
> Generally, there also isn't one guaranteed result node (like e.g., Sub) where we could place code that recognizes these patterns and provides better results, so I don't think this is feasible (for Div it *might* be doable, at least I only found that off-by-one overapproximation that could be dealt with in Sub).
> 
>> Alternatively, as part of the expansion, new representation can be wrapped in CastII/CastLL with the narrower type of original Div/Mod node.
> 
> I thought about that a bit as well and I think it has the same downside as the current approach: As soon as we don't use the Div/Mod node anymore, making the inputs more precise doesn't help anymore. We still have the Cast node, but that node doesn't know how to recalculate/improve its own type.
> (Additionally, but less of a problem, a Cast node would require optimizations checking their inputs for Div/Mod nodes to uncast).
> 
> Basically, this comes back to what e-graphs do better: remember multiple alternative constructs for the same semantic operation. Without considering whether that's realistic, if a Cast node would keep the original operation alive somehow (but that operation isn't further optimized itself, I guess), then the Cast node could recalculate its type depending on multiple variants and choose the more specific result even at later stages of optimization.
> 
> That said, I'm not in the position if using Cast nodes is more idiomatic, and I'm open to rework the PR to use Cast nodes if you want.

@SirYwell We were probably typing at the same time ;)

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

PR Comment: https://git.openjdk.org/jdk/pull/27886#issuecomment-3441588487