RFR: 8299959: C2: CmpU::Value must filter overflow computation against local sub computation

[Emanuel Peter]

On Tue, 17 Jan 2023 22:47:26 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>> During CCP, the overflow computation can be wider than the `sub` computation, thus we must filter them together.
>> 
>> **Example**
>> 
>> CmpI(AddI(in11 ,in12), in2)
>> in1 = AddI
>> 
>> type(int1):  int:-17..-5:www
>> type(int11): int:<=-4:www
>> type(int12): int:-1
>> type(int2):  int:>=0
>> 
>> If we call `CmpU::Value` now, we go into the overflow computation.
>> Addin `-1` to the range `int:<=-4:www` we get two ranges: `int:<=-5:www` and `int:max`.
>> Unsigned-comparing these to `int:>=0`, we get `GT` for `int:<=-5:www` (negative numbers become very large unsigned numbers), and `GE` for `int:max`. Together that is `GE == bool == 0..1`
>> 
>> During CCP, we now have a type-update (widening) for `int11` to `int`. The logic in `CmpU::Value` does not go into the overflow computation, since `type(in11) == t11 == TypeInt::INT`. Instead, we now just do the `sub` computation based on `in1` and `in2`. 
>> There we have t1 > t2 (unsigned comparison, so negative values become very large positive values), so we get a `GT == int:1`, which is narrower than `GE == 0..1`
>> 
>> CCP detects that the type narrowed instead of widened, we get an assert: `failed: Not monotonic`.
>> 
>> **Discussion of Solution**
>> 
>> We cannot assume that the types of `in1` and those of `in11` and `in12` are in sync when we are in `CmpU::Value`. During IGVN generally the inputs of inputs are narrower (narrower type may not have propagated to AddI yet), during CCP they are wider (widening may not yet have propagated to AddI yet).
>> 
>> We can assume that the overflow computation and the `sub` computation are individually `monotonic`. Currently, the combination is not monotonic, as the example shows. We can ensure that the combination is monotonic by `filtering` them against each other (taking the intersection / narrowest type possible).
>> We only need to do this filtering if we actually do the overflow computation - else we have already checked that `in11` or `in12` do not have types that would lead to a narrower result than `sub`, and so taking the result of `sub` is sufficient.
>
> Looks reasonable.

Thanks for the reviews @vnkozlov @rwestrel @chhagedorn !

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

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