RFR: 8299546: C2: MulLNode::mul_ring() wrongly returns bottom type due to casting errors with large numbers [v2]

[Christian Hagedorn]

On Tue, 10 Jan 2023 14:27:39 GMT, Christian Hagedorn <chagedorn at openjdk.org> wrote:

>> The current logic in `MulLNode::mul_ring()` casts all `jlong` values of the involved type ranges of a multiplication to `double` in order to catch overflows when multiplying the two type ranges. This works fine for values in the `jlong` range that are not larger than 2<sup>53</sup> or lower than -2<sup>53</sup>. For numbers outside that range, we could experience precision errors because these numbers cannot be represented precisely due to the nature of how doubles are represented with a 52 bit mantissa. For example, the number 2<sup>53</sup> and 2<sup>53</sup> + 1 both have the same `double` representation of 2<sup>53</sup>.
>> 
>> In `MulLNode::mul_ring()`, we could do a multiplication with a `lo` or `hi` value of a type that is larger than  2<sup>53</sup> (or smaller than -2<sup>53</sup>). In this case, we might get a different result compared to doing the same multiplication with `jlong` values (even though there is no overflow/underflow). As a result, we return `TypeLong::LONG` (bottom type) and missed an optimization opportunity (e.g. folding an `If` when using the `MulL` node in the condition etc.).
>> 
>> This was caught by the new verification code added to CCP in [JDK-8257197](https://bugs.openjdk.org/browse/JDK-8257197) which checks that after CCP, we should not get a different type anymore when calling `Value()` on a node. In the found fuzzer testcase, we run into the precision problem described above for a `MulL` node and set the type to bottom during CCP (even though there was no actual overflow). Since the type is bottom, we do not re-add the node to the CCP worklist because the premise is that types only go from top to bottom during CCP. Afterwards, an input type of the `MulL` node is updated again in such a way that the previously imprecise `double` multiplication in `mul_ring()` is now exact (by coincidence). We then hit the "missed optimization opportunity" assert added by JDK-8257197.
>> 
>> To fix this problem, I suggest to switch from a `jlong` - > `double` multiplication overflow check to an overflow check without casting. I've used the idea that `x = a * b` is the same as `b = x / a` (for `a != 0` and `!(a = -1 && b = MIN_VALUE)`)  which is also applied in `Math.multiplyExact()`: https://github.com/openjdk/jdk/blob/66db0bb6a15310e4e60ff1e33d40e03c52c4eca8/src/java.base/share/classes/java/lang/Math.java#L1022-L1036
>> 
>> The code of `MulLNode::mul_ring()` is almost identical to `MulINode::mul_ring()`. I've refactored that into a template class in order to share the code and simplified the overflow checking by using `MIN/MAX4` instead of using nested `if/else` statements.
>> 
>> Thanks,
>> Christian
>
> Christian Hagedorn has updated the pull request incrementally with one additional commit since the last revision:
> 
>   review

That would indeed make things easier and faster. We would probably also need such a portable solution to provide 128-bit integers for all architectures with a struct that stores the lo and high part. Would be great to get these in at some point, so I'd suggest to file an RFE for it.

For this bug here, I'm not sure if we should wait until the 128-bit integer support makes it in. I think it is okay to spend some more cycles (compared to using 128-bit integers) during the compilation when using @merykitty's proposal with a high multiplication for now. We could still come back to this code again and update it with 128-bit integers later. What do you think?

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

PR: https://git.openjdk.org/jdk/pull/11907