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

When a developer types (x << 2) & -4, an optimizing compiler should compile it to just the shift, x << 2: the bitwise AND should disappear. Why? Imagine we have an 8-bit number x = 1011 0111 and my expression looks like (x << 2) & -4; x 1011 0111 (the original x)---------------------- x << 2 1101 1100 (x after lshift, the 2 lowest bits are always 0s) & -4 1111 1100 (-4 in two's complement -> the mask only clears lowest 2 bits)---------------------- result 1101 1100 (same as x << 2, the bitwise AND has no effect) But how does the C2 compiler actually do this? The optimization relies on a general abstraction, built over multiple changesets. This post is my attempt to understand it and explain it. What does the JIT actually know about your numbers? When C2 is compiling a method, what does it know about the value in a given variable? The answer is "a set of possible values." The compiler usually can't know the exact runtime value of x (that's the whole point of a variable), but it can often prove that x is constrained. If it can prove the constraint is tight enough, it can rewrite the code. A classic example: if the compiler proves an array index is always in [0, length), it deletes the bounds check. Constant folding, dead branch elimination, and other optimizations often come down to "prove the set of possible values is small enough to act on." C2 stores this "set of possible values" as a type. Don't imagine a Java types int or long, but a much richer internal type that carries a range. For most of HotSpot's life, an integer type was essentially: [lo, hi] // the value is somewhere in this signed range, inclusive So the type of x & 0xFF would be [0, 255], and the compiler could use that. This signed range is simple and useful, but it is too weak for our purpose.

Consider x << 2. What's the range of x << 2 if x can be anything? Well... almost anything. Shifting left can overflow, wrap around, produce huge positives and huge negatives. The tightest signed interval covering the result is [Integer.MIN_VALUE, 2147483644]. It is a huge range, just shy of the full int range, and it gives the compiler almost nothing useful. But we know something very specific about x << 2: No matter what x is the bottom two bits are always zero! A range can't express that. [lo, hi] can say "the value is small" but it can't say "the value is even," let alone "the value is a multiple of four." That knowledge lives in the bits, and the range alone cannot express it. Enter known bits The fix: alongside the range, also track what we know about each individual bit. For a 32-bit integer, imagine two extra 32-bit masks travelling with the type:

zeros: a 1 in position i means "bit i is definitely 0" ones: a 1 in position i means "bit i is definitely 1"

A bit that's unknown is 0 in both masks. A bit can't be both, so the invariant zeros & ones == 0 must always hold. In C2 it's a dozen lines of rangeinference.hpp: template <class U>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.

Each one knows things the other doesn't, and they can teach each other:

The bits know the low two bits are zero. The range uses that: if it currently says [5, 41], then 5, 6, 7, and 41 all have nonzero low bits and can't occur, so the range tightens to [8, 40], the nearest multiples of four inside it. The range knows the value is in [0, 200]. The bits use that: every number from 0 to 200 has its top 24 bits zero, so those aren't unknown bits at all; they're known-zero, and the bits record it.

This "combine two abstractions and let them refine each other" pattern has a name in the compiler literature (a reduced product), and the function that makes the range and the bits reconcile until they agree is called the reduction operator. In C2 it's a function with the very down-to-earth name canonicalize_constraints(), and it runs every time a new integer type is created. It's the heart of the whole feature. The canonicalization dance So how do you get the range and the bits to agree? You let them take turns refining each other until neither has anything new to add. One clarification first: C2's integer type actually carries three constraints, and a value belongs to the type only if the same 32-bit pattern passes all of them. Straight from the definition in type.hpp: v >= _lo && v <= _hi && // the signed rangejuint(v) >= _ulo && juint(v) <= _uhi && // the same bits, compared unsigned_bits.is_satisfied_by(v) // the known bits Why an unsigned range too? Because C2 has to reason about unsigned comparisons. Remember the bounds check from the beginning of this post? HotSpot compiles it into a single unsigned comparison, index u< length, and deciding whether such a comparison is always true or always false is a question about unsigned ranges, not signed ones. Intersecting the signed and the unsigned range produces one or two disjoint pieces, each with bounds that are either both negative or both non-negative.

For example, the signed [-5, 5] and the unsigned [2, UINT_MAX] intersect to [-5, -1] and [2, 5]: the negative values pass the unsigned check because their bit patterns read as huge unsigned numbers just below UINT_MAX, while 0 and 1 fail it. C2 calls each such piece a "simple interval". Because its bounds share a sign, signed and unsigned comparisons agree on it: a simple interval is a valid signed range and a valid unsigned range at the same time, and it never straddles the sign boundary, so the shared-prefix trick in step 1 is always safe. The reduction works on one simple interval at a time; the outer canonicalize_constraints() does the splitting and merges the results back: // The 2 simple intervals can be tightened into 2 separate resultsauto neg_type = canonicalize_constraints_simple({U(srange._lo), urange._hi}, _bits);auto pos_type = canonicalize_constraints_simple({urange._lo, U(srange._hi)}, _bits); Note how each simple interval mixes bounds from both views: the negative piece runs from the signed low bound to the unsigned high bound, and the non-negative piece from the unsigned low bound to the signed high bound. The loop:

Bits learn from the interval. Take the current simple interval [ulo, uhi]. The high bits that are identical in both ulo and uhi are identical for every value in between (that's just how binary counting works: the leading digits don't change until you cross a power-of-two boundary). Those bits are now known.

Interval learns from the bits. Take the current ulo. If it violates the known bits (say the bits demand the low two are zero but ulo is 0b...101), then ulo isn't actually a possible value, so bump it up to the smallest value ≥ ulo that satisfies the bits. Do the mirror thing to pull uhi down.

Go back to step 1 and see if the tighter interval reveals more known bits.