RFR: 8367341: C2: apply KnownBits and unsigned bounds to And / Or operations [v2]

[Quan Anh Mai]

On Mon, 13 Oct 2025 13:15:38 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Emanuel's reviews
>
> @merykitty Thank you very much for working on this, very exciting. And it seems that the actual logic is now simpler than all the custom logic before!
> 
> However, we need to make sure that all cases that you are not deleting are indeed covered.
> 1. `OrINode::add_ring`
> 
>   if ( r0 == TypeInt::BOOL ) {
>     if ( r1 == TypeInt::ONE) {
>       return TypeInt::ONE;
>     } else if ( r1 == TypeInt::BOOL ) {
>       return TypeInt::BOOL;
>     }
>   } else if ( r0 == TypeInt::ONE ) {
>     if ( r1 == TypeInt::BOOL ) {
>       return TypeInt::ONE;
>     }
>   }
> 
> That seems to be covered by KnownBits.
> 
> 2. `OrINode::add_ring`
> 
>   if (r0 == TypeInt::MINUS_1 || r1 == TypeInt::MINUS_1) {
>     return TypeInt::MINUS_1;
>   }
> 
> Seems also ok, handled by the KnownBits.
> 
> 3. `OrINode::add_ring`
> 
>   // If either input is not a constant, just return all integers.
>   if( !r0->is_con() || !r1->is_con() )
>     return TypeInt::INT;        // Any integer, but still no symbols.
> 
>   // Otherwise just OR them bits.
>   return TypeInt::make( r0->get_con() | r1->get_con() );
> 
> Constants would also be handeld by KnownBits.
> 
> 4. `xor_upper_bound_for_ranges`
> I think also this should be handled by doing KnownBits first, and then inferring the signed/unsigned bounds, right?
> 
> 5. `and_value`
> Does not look so trivial. Maybe you can go over it step by step, and leave some GitHub code comments?

@eme64 Thanks for your review, I believe I have addressed all of your suggestions.

> However, we need to make sure that all cases that you are not deleting are indeed covered.

For this, from the testing POV, all the current idealization tests pass.

>From the theoretical POV, let me present it below:

For `Xor`:

    return round_up_power_of_2(U(hi_0 | hi_1) + 1) - 1; // This should be trivially covered by `KnownBits`, since it tries to deal with the highest bits that are known to be 0 in both inputs

For `Or`:

    // If both args are bool, can figure out better types
    if ( r0 == TypeInt::BOOL ) {
      if ( r1 == TypeInt::ONE) {
        return TypeInt::ONE; // Trivial, since all bits except the lowest is 0 in both inputs, and the lowest bit is 1 in the second input
      } else if ( r1 == TypeInt::BOOL ) {
        return TypeInt::BOOL; // Trivial, since all bits except the lowest is 0 in both inputs
      }
    } else if ( r0 == TypeInt::ONE ) {
      if ( r1 == TypeInt::BOOL ) {
        return TypeInt::ONE; // Same as above
      }
    }

    if (r0 == TypeInt::MINUS_1 || r1 == TypeInt::MINUS_1) {
      return TypeInt::MINUS_1; // Trivial, since all bits is 1 in 1 of the inputs
    }

    // If either input is not a constant, just return all integers.
    if( !r0->is_con() || !r1->is_con() )
      return TypeInt::INT;        // Any integer, but still no symbols.

    // Otherwise just OR them bits.
    return TypeInt::make( r0->get_con() | r1->get_con() ); // Constant folding is trivial

For `And`:

    // If both types are constants, we can calculate a constant result.
    if (r0->is_con() && r1->is_con()) {
      return IntegerType::make(r0->get_con() & r1->get_con()); // Constant folding is trivial
    }

    // If both ranges are positive, the result will range from 0 up to the hi value of the smaller range. The minimum
    // of the two constrains the upper bound because any higher value in the other range will see all zeroes, so it will be masked out.
    if (r0->_lo >= 0 && r1->_lo >= 0) {
      return IntegerType::make(0, MIN2(r0->_hi, r1->_hi), widen); // In this case, both have a single simple interval, and the max of the result (which is the same as the unsigned max) is not larger than the min of either input.
    }

    // If only one range is positive, the result will range from 0 up to that range's maximum value.
    // For the operation 'x & C' where C is a positive constant, the result will be in the range [0..C]. With that observation,
    // we can say that for any integer c such that 0 <= c <= C will also be in the range [0..C]. Therefore, 'x & [c..C]'
    // where c >= 0 will be in the range [0..C].
    if (r0->_lo >= 0) {
      return IntegerType::make(0, r0->_hi, widen); // r0 will have a single simple interval, and the result will be the union of 2 sets both of which have the max being not larger than r0->_hi
    }

    if (r1->_lo >= 0) {
      return IntegerType::make(0, r1->_hi, widen); // Same as above
    }

    // At this point, all positive ranges will have already been handled, so the only remaining cases will be negative ranges
    // and constants.

    assert(r0->_lo < 0 && r1->_lo < 0, "positive ranges should already be handled!");

    // As two's complement means that both numbers will start with leading 1s, the lower bound of both ranges will contain
    // the common leading 1s of both minimum values. In order to count them with count_leading_zeros, the bits are inverted.
    NativeType sel_val = ~MIN2(r0->_lo, r1->_lo);

    NativeType min; // This takes into consideration that the result is negative iff both the inputs are negative, then uses the lower bound to infer the leading 1s in that case
    if (sel_val == 0) {
      // Since count_leading_zeros is undefined at 0, we short-circuit the condition where both ranges have a minimum of -1.
      min = -1;
    } else {
      // To get the number of bits to shift, we count the leading 0-bits and then subtract one, as the sign bit is already set.
      int shift_bits = count_leading_zeros(sel_val) - 1;
      min = std::numeric_limits<NativeType>::min() >> shift_bits;
    }

    NativeType max;
    if (r0->_hi < 0 && r1->_hi < 0) {
      // If both ranges are negative, then the same optimization as both positive ranges will apply, and the smaller hi
      // value will mask off any bits set by higher values.
      max = MIN2(r0->_hi, r1->_hi); // Both ranges are negative, then similar to when r0->_lo >= 0 && r1->_lo >= 0
    } else {
      // In the case of ranges that cross zero, negative values can cause the higher order bits to be set, so the maximum
      // positive value can be as high as the larger hi value.
      max = MAX2(r0->_hi, r1->_hi); // Consider the union of the results when inferring from 4 combinations of simple intervals of the inputs. If both simple intervals are in the negative range, the result is negative. Otherwise, the result will be not larger than the upper bound of the simple interval in the non-negative range.
    }

    return IntegerType::make(min, max, widen);

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

PR Comment: https://git.openjdk.org/jdk/pull/27618#issuecomment-3405411175