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

The details regarding the transformation in each node:

- `And/Or/Xor`: Previously, ad-hoc rules are used, such that and of a positive is a positive, or of 2 bools is a bool, etc. This is naturally expanded in a generalised manner using the bit information.
- `L/R/URShift`: Since the operations only concern the lowest bits of the shift amount, bit information is a natural generalisation, bounds calculation are mostly the same, and the information of the pushed-in bits can be used.
- `CountLeadingZeros`, `CountTrailingZeros`, `PopCount`: Previously, this can only do constant propagation, otherwise it returns the typed bottom. The type can be greatly sharpened.
- `Add/Sub`: Previously, bounds can only be inferred if there is no overflow occurs, I expand this a little bit so that bounds can also be inferred if the upper and lower bounds overflow in the same manner. Unsigned bounds are added, and bits are calculated manually, this can help in situations such as:

        for (int i = 0; i < max; i += 4) {
            bool b = (i & 3) == 0; // This is constant zero
        }
- `CmpI/L`: Unsigned bounds help us represent `TypeInt::CC_NE`, helps narrow the comparison results when the inputs do not overlap
- `CmpU/UL`: An ad-hoc rule regarding comparing of an `Add/Sub` and a constant was used, this is replaced by the usage of unsigned bounds

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

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