The mask that compiles to nothing: how HotSpots JIT learned to reason about bits

The mask that compiles to nothing: how HotSpot's JIT learned to reason about bits

When a developer types (x & mask) where the mask only clears the lowest 2 bits, the result is 1101 1100 (same as x).

class KnownBits {
  static_assert(U(-1) > U(0), "bit info should be unsigned");
public:
  U _zeros;
  U _ones;

  bool is_satisfied_by(U v) const {
    return (v & _zeros) == U(0) && (v & _ones) == _ones;
  }
};

is_satisfied_by just checks whether a given number v is allowed by the masks. The masks must never rule out a value that can actually occur, and C2's tests and internal checks use this to verify they don't. Every bit is now in one of three states: known-0, known-1, or unknown.

Here's the type of x:

_lo && v = _ulo && juint(v)
(canonicalized_bounds._present, canonicalized_bounds._result, canonicalized_bits._result);
}
canonicalized_bits = adjust_bits_from_unsigned_bounds(canonicalized_bits._result, canonicalized_bounds._result);
if (!canonicalized_bits._progress || canonicalized_bits.empty()) {
  return SimpleCanonicalResult(canonicalized_bits._present, canonicalized_bounds._result, canonicalized_bits._result);
}

Does this terminate?

Yes. Each iteration that triggers another full round must turn at least one previously-unknown bit into a known bit, and a final bounds-only tightening may happen just before the loop exits. Given there are at most 64 bits, convergence is bounded by the word width.

Teaching AND to disappear

We also have to teach C2 to compute known bits through operations: every participating operation needs a rule for "given the known bits of my inputs, what are the known bits of my output?" These rules are simple and mechanical:

• AND: out.ones = a.ones & b.ones (a bit is 1 only if it's 1 in BOTH)
  out.zeros = a.zeros | b.zeros (a bit is 0 if it's 0 in EITHER)
• OR: out.ones = a.ones | b.ones
out.zeros = a.zeros & b.zeros
• SHL by k: shift both masks left by k, and OR (1 << k) - 1 into zeros

zeros = st1._bits._zeros | st2._bits._zeros;
U ones = st1._bits._ones & st2._bits._ones;

And the left shift (infer_lshift), where pattern = (1 << k) - 1:

pattern = (U(1) << k) - 1;
U known_one_bits = t1->_bits._ones << k;
U known_zero_bits = (t1->_bits._zeros << k) | pattern;

if (in(1) == in(2)) { return in(1); }
const TypeInt* t1 = phase->type(in(1))->is_int();
const TypeInt* t2 = phase->type(in(2))->is_int();
if ((~t1->_bits._ones & ~t2->_bits._zeros) == 0) {
  // All bits that might be 0 in in1 are known to be 0 in in2
  return in(2);
}
if ((~t2->_bits._ones & ~t1->_bits._zeros) == 0) {
  // All bits that might be 0 in in2 are known to be 0 in in1
  return in(1);
}
return MulNode::Identity(phase);

The two known-bits ifs are mirror images: the first collapses x & y to y, the second to x. For (x & y):

(~y.ones & ~x.zeros) == 0

Let's have a look at a concrete example: (x & -4).

• x: ~zeros = ...1100 (bits x might have set: all but the low two)
• y = -4: ones = ...1100 → ~ones = ...0011 (bits y might clear: the low two)
• (~y.ones & ~x.zeros) == (...0011 & ...1100) == 0

-4 can only clear the low two bits, and x type (an integer of arbitrary tiny width).

Canonicalization is checked exhaustively

Through 4-bit types (at 4 bits that's 16 values, every combination of ranges and masks, by brute force). I read it as a useful trick: shrink the integer width until exhaustive testing becomes cheap, then test every state in that universe. The operation transfer functions use a mix of exhaustive tiny-width tests and random wider ones.

Here's the core (test_rangeinference.cpp): six nested loops over the whole tiny universe, feeding every possible (lo, hi, ulo, uhi, zeros, ones) tuple through canonicalize_constraints:

for (int lo = S::min; lo <= S::max; lo++) {
  // ... nested loops ...
  t{{S(lo), S(hi)}, {U(ulo), U(uhi)}, {U(zeros), U(ones)}};
  auto new_t = t.canonicalize_constraints();
  // ...then assert new_t contains exactly the same values as t, for every v
}

S and U are intn_t / uintn_t, and the test runs the whole thing for N = 1, 2, 3, 4.

Why I care, and maybe why you should

I'm not a compiler engineer, and I won't pretend to be. I just enjoy learning how compilers and computers work, and chasing an optimization like this is fun. I also use LLMs to help me understand concepts that are new to me. During these explorations I use LLM as a personal tutor: I ask questions until I understand what is going on.

If you are an actual compiler engineer and spot an error in my explanation, please let me know! I will be happy to correct it. In fact, this already happened: an earlier version of this post described the simple interval as "the unsigned one", and Reddit user cal-cheese corrected me: it is a piece of the intersection of the signed and unsigned ranges. The explanation above is the fixed one. Thank you!

Thanks to Quan Anh Mai, Emanuel Peter, and Ashay Rane, whose work sent me down this wonderful rabbit hole!