RFR: 8350896: Integer/Long.compress gets wrong type from CompressBitsNode::Value [v15]

[Jatin Bhateja]

On Wed, 16 Jul 2025 10:43:34 GMT, Jatin Bhateja <duke at openjdk.org> wrote:

>> Hi All,
>> 
>> This bugfix patch fixes incorrect value computation for Integer/Long. compress APIs.
>> 
>> Problems occur with a constant input and variable mask where the input's value is equal to the lower bound of the mask value., In this case, an erroneous value range estimation results in a constant value. Existing value routine first attempts to constant fold the compression operation if both input and compression mask are constant values; otherwise, it attempts to constrain the value range of result based on the upper and lower bounds of mask type.
>> 
>> New IR test covers the issue reported in the bug report along with a case for value range based logic pruning.
>> 
>> Kindly review and share your feedback.
>> 
>> Best Regards,
>> Jatin
>
> Jatin Bhateja has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Refine lower bound computation

Quick note on C2 Integral types
-  Integral types now encapsulate 3 lattice structures perf TypeInt/Long, namely signed, unsigned and knownbits.
-   All three lattice values are in sync post-canonicalization.
-   Lattice is a partial order relation, i.e., reflexive, transitive but anti-symmetric.
-   An integral lattice contains two special values: a TOP (no value, no assumption can be drawn by the compiler)
    and BOTTOM (all possible values in the value range)
-   Verification ensures that the lattice is symmetrical around the centerline, i.e., a semi-lattice.
-    For a symmetrical lattice, only one operation i.e., meet/join is sufficient for value resolution; other operations can be computed by taking the dual of the first one using de-Morgan's law.
        _join = Dual (meet (dual(type1), dual(type2))_
-    In theory, meet b/w two lattice points takes us to the greatest lower bound in the Hesse diagram,
while join b/w two lattice points takes us to the lowest upper bound. Also, TOP represents the entire value range of the lattice, while BOTTOM represents no value, but C2 follows an inverted lattice convention.
Inverted integral lattice hasse diagram

                   TOP (no value)
                   /  |  |  \
                  MIN …….. MAX
                   \  |  |  /
                   BOTTOM (all possible values)

-   Thus, a MEET of two lattice points takes us to the greatest upper bound of the lattice structure; in this case, it's the union of two lattice points i.e., we pick the minimum of the lower bounds and max of the upper bounds of participating lattice points. JOIN takes us to the lowest upper-bound lattice points of the inverted lattice structure. in this case, it will be an intersection of lattice points, which constrains the value range i.e., we pick the max of the lower bounds and the minimum of the upper bounds of the two participating integral lattice points.
- 
    e.g., if TypeInt t1 = {lo:10, hi:100} and TypeInt t2 = {lo:1, hi:20}, then

   t1.meet.(t2) = lowest upper bound.
    = { lo = min(t1.lo, t2.lo}, hi = max(t1.hi , t2.hi}}
    = { lo = min(10, 1), hi = max(100, 20)}
    = { lo = 1, hi = 100}

    t1.join(t2) = dual (meet (dual(t1), dual(t2))
    where dual = {lo : hi} => {hi : lo}
    = dual (meet (dual {lo : 10, hi : 100}, dual {lo : 1, hi : 20}})
    = dual (meet ({lo: 100, hi : 10}}, {lo:20: , hi:1})
    = dual (min(t1.lo, t2.lo}, max(t1.hi, t2.hi})
    = dual (min(100, 20), max(10, 1))
    = dual (lo:20, hi:10}
    = (lo : 10, hi : 20)


Additional identities :-
•	TOP meet VAL = VAL since we cannot move to any other greatest lower bound when one of the inputs is TOP (unknown value), to move to the greatest lower bound both the inputs must be known values.
•	BOTTOM meet VAL = BOTTOM

Now, some quick notes on CCP
•	Optimistic data flow analysis using ROPT walk on the ideal graph.
•	Each lattice begins with a TOP value, and analysis progressively adds elements to the lattice. Analysis expects to expand the value range with each data flow iteration, thereby monotonically increasing the lattice set.
After each value transformation, type verification checks that the new value is greater than the old value in the lattice, in other words new value should dominate the old value in the hasse diagram of the lattice. Thus, tnew->meet(told) gives us the lowest upper bound of two lattice points, i.e., tnew should be a superset of told. CCP is an optimistic iterative data flow analysis which traverses the ideal graph in RPOT order and reaches a fixed point once value transforms as no side-effects on the graph.

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

PR Comment: https://git.openjdk.org/jdk/pull/23947#issuecomment-3078010698