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

[Quan Anh Mai]

On Sun, 27 Aug 2023 12:26:22 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-3
> - [ ] Linux x64, tier 4

Regarding duality, I don't really understand the concept of duality used in the type system, from the usage of `dual` in `join(x, y) = dual(meet(dual(x), dual(y)))`, I kind of understand that the dual of a type is the complement of that type, but I don't see why do we need to represent it using the same representation. Furthermore, having an invalid type instance seems to be dangerous. This concept is only used to calculate the join of 2 types, so I use a `_dual` field to indicate whether we are calculating the union or the intersection of 2 sets, and `make` of invalid types (e.g. intersection of 2 nonoverlap types, or `make` with contradicting constraints) will result in `Type::TOP`. I'm not sure there is any other component relying on the old behaviour.

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

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