The Mask That Compiles to Nothing: How HotSpot's JIT Learned to Reason About Bits

When a programmer writes the expression (x << 2) & -4, an intelligent optimizing compiler should recognize that the bitwise AND is redundant and simply compile it as x << 2.

The Logic of the Redundant Mask

To understand why, consider an 8-bit integer $x = 10110111_2$.

The bitwise AND has no effect because the shift already guaranteed the bits the mask intended to clear were already zero. But how does the C2 compiler actually prove this?

---

The Limitation of Signed Ranges

C2 optimizes code by proving constraints on variables. For instance, if the compiler can prove an array index falls within $[0, \text{length})$, it can $\text{~~delete the bounds check~~}$ entirely.

Historically, HotSpot tracked integer types using a signed range: $\text{Type} = [lo, hi]$

While useful for simple bounds, this abstraction is too blunt for bitwise operations. Consider a left shift: shifting can cause overflows and wrap-arounds, resulting in a massive range. The tightest signed interval for a shifted int might be: $[Integer.MIN\_VALUE, 2147483644]$

This range is nearly the entire 32-bit space, providing the compiler with almost no actionable information. It can tell you if a number is "small," but it cannot tell you if a number is even or a multiple of four. That information exists in the bits, not the range.

---

Introducing KnownBits

To solve this, HotSpot introduced a way to track individual bit states. Instead of just a range, the compiler now tracks two 32-bit masks:

1. zeros: A bit is $1$ if that position is definitely 0.
2. ones: A bit is $1$ if that position is definitely 1.

If a bit is $0$ in both masks, its value is unknown. Because a bit cannot be both $0$ and $1$ simultaneously, the following invariant must always hold: zeros & ones == 0

Implementation Detail

In rangeinference.hpp, this is implemented as a lightweight template:

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; 
    } 
};

The is_satisfied_by method simply verifies if a value $v$ conforms to the known bit constraints.

Note: This approach is "non-relational." It tracks bits independently and does not record relationships (e.g., it cannot track "bit 3 is always equal to bit 5"). This independence is what keeps the bookkeeping computationally cheap.

Industry Context

This technique isn't unique to HotSpot; it's a common compiler pattern:

• LLVM: Uses a nearly identical KnownBits representation.
• GCC: Employs a similar "value plus uncertainty mask" in its conditional constant-propagation pass.

---

The Synergy: A Reduced Product

HotSpot now maintains two parallel descriptions of a number: the Range and the KnownBits. These two abstractions refine each other through a process known in compiler theory as a reduced product.

How they collaborate:

• Bits $\rightarrow$ Range: If the KnownBits mask indicates the low two bits are zero (meaning the value is a multiple of 4), a range of $[5, 41]$ can be tightened to $[8, 40]$.
• Range $\rightarrow$ Bits: If the range is $[0, 200]$, the compiler knows the top 24 bits must be zero, allowing it to update the zeros mask.

This reconciliation happens in a function called canonicalize_constraints(), which runs whenever a new integer type is generated.

---

The Canonicalization Dance

To reach a stable state, the compiler performs the following steps:

• Check if the signed range implies any new KnownBits.
• Check if the KnownBits imply a tighter signed range.
• Check if the unsigned range implies any new KnownBits.
• Repeat until no further refinements are possible (reaching a fixed point).

In type.hpp, a value $v$ is only considered part of a type if it satisfies three distinct constraints:

1. Signed Range: $v \ge \text{\_lo}$ and $v \le \text{\_hi}$
2. Unsigned Range: $\text{juint}(v) \ge \text{\_ulo}$ and $\text{juint}(v) \le \text{\_uhi}$
3. Known Bits: $\text{\_bits.is\_satisfied\_by}(v)$

The inclusion of an unsigned range allows HotSpot to compile these checks into a single, efficient unsigned comparison.

Timeline & Credits

• JDK 26: Foundations laid by Quan Anh Mai (known as merykitty) and Emanuel Peter (JDK-8315066).
• JDK 27: Implementation of the logic that actually deletes redundant masks like (x << 2) & -4.