RFR: 8315066: Add unsigned bounds and known bits to TypeInt/Long [v2]

[Quan Anh Mai]

On Wed, 20 Sep 2023 12:58:44 GMT, Tobias Hartmann <thartmann at openjdk.org> wrote:

>> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   typo
>
> Impressive work, Quan Anh! I did some quick correctness testing and it all looks good. This will take a while to review though. I think @rose00 should have a look as well.
> 
> Some quick initial observations/questions:
> - Would it be possible (and make sense) to split this PR and add support for unsigned bounds and zero/one bits separately to ease reviewing?
> - Regarding duality, it seems hacky to introduce a field to keep track of the "position" in the type lattice. As I understand, the purpose of dual types is so that we only have to implement the meet operation for each type and can compute the join by executing meet in the dual half and dual'ing the result. We should be consistent here and not special case TypeInt/Long.
> - Does this solve [JDK-8311597](https://bugs.openjdk.org/browse/JDK-8311597)?
> - To what extent does this implement John's prototype from [JDK-8001436](https://bugs.openjdk.org/browse/JDK-8001436)?
> 
> Thanks,
> Tobias

@TobiHartmann Thanks a lot for taking a look at this patch. Regarding your questions:

- I don't think splitting these 2 would ease reviewing. Since individual changes are small and mostly contained in various `Value` methods, splitting unsigned bounds and known bits would likely to result in the need to review the same thing twice.
- Maybe I miss some important context, but IIUC, the current implementation is more hacky. Since a value set and its dual set are fundamentally different concepts, what is currently done is that we find a common representation space for both of them and a binary operation on that space such that both the `meet` operation on the value set and the `join` operation on the dual set map to that binary operation when we map the 2 sets onto the representation space. In a more detailed explanation, the value set of is the set of `x` such that `lo <= x && x <= hi`, the dual set is the set of `x` such that `x > hi || x < lo`, the representation space is `(x, y)` and the mapping for the 2 sets are `(lo, hi) -> (lo, hi)` and `(lo, hi) -> (hi, lo)`, respectively. Incidentally, the binary operation popping up is `(min(x1, x2), max(y1, y2))`. This binary operation, unfortunately, is ad-hoc and may not be trivial for more complex sets.
- Yes the sign of the result is determined by its sign bit so this patch does solve that issue.
- I think the patch fully covers John's prototype since the prototype does not concern with unsigned bounds as well as the interaction between signed bounds and known bits. The bit calculation of add and sub is really impressive, though.

Thanks a lot,
Quan Anh

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

PR Comment: https://git.openjdk.org/jdk/pull/15440#issuecomment-1729317450