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

[Tobias Hartmann]

On Mon, 28 Aug 2023 15:37:53 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> Hi,
>> 
>> This patch adds unsigned bounds and known bits constraints to `TypeInt` and `TypeLong`. This opens more transformation opportunities in an elegant manner as well as helps avoid some ad-hoc rules in Hotspot. The new constraints are applied to identity and value calls of the common nodes (Add, Sub, L/R/URShift, And, Or, Xor, bit counting, Cmp, Bool, ConvI2L/L2I), the detailed ideas for each node will be presented below.
>> 
>> In general, a `TypeInt/Long` represents a set of values `x` that satisfies: `x s>= lo && x s<= hi && x u>= ulo && x u<= uhi && (x & zeros) == 0 && (~x & ones) == 0`. These constraints are not independent, e.g. an int that lies in [0, 3] in signed domain must also lie in [0, 3] in unsigned domain and have all bits but the last 2 being unset. As a result, we must normalize the constraints (tighten the constraints so that they are optimal) before constructing a `TypeInt/Long` instance.
>> 
>> Please kindly review, thanks very much.
>> 
>> Testing
>> 
>> - [x] GHA
>> - [x] Linux x64, tier 1-4
>
> 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

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

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