编译为无的掩码：HotSpot的JIT如何学会推理位

# 编译后消失的掩码：HotSpot 的 JIT 是如何学会推理比特位的 Source: https://questdb.com/blog/jvm-jit-known-bits/ 当开发者写出 `\(x << 2\) & -4` 这样的表达式时，优化编译器应将其编译为单纯的移位操作 `x << 2`：按位与 `AND` 应该消失。为什么？假设我们有一个 8 位数 `x = 1011 0111`，表达式为 `(x << 2) & -4`： ``` x 1011 0111 (原始 x) ---------------------- x << 2 1101 1100 (左移后，最低 2 位始终为 0) & -4 1111 1100 (-4 的补码表示，掩码只清除最低 2 位) ---------------------- result 1101 1100 (与 x << 2 相同，按位与没有效果) ``` 但 C2 编译器实际上是如何做到这一点的？该优化依赖于一个通用的抽象，跨越多个变更集构建而成。本文是我尝试理解并解释它的过程。 ## JIT 到底*知道*你的数字的哪些信息？ https://questdb.com/blog/jvm-jit-known-bits/#what-does-the-jit-actually-,[object-object],-about-your-numbers? 当 C2 编译一个方法时，它对某个变量中的值了解多少？答案是“一组可能的值”。编译器通常无法知道 `x` 在运行时的确切值（这正是变量的意义所在），但它往往能证明 `x` 是*受限*的。如果能证明约束足够严格，它就能重写代码。一个经典的例子：如果编译器证明数组索引始终在 `[0, length)` 范围内，它会删除[边界检查](https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/parse2.cpp#L157-L179)。常量折叠、死分支消除以及其他优化通常归结为“证明可能值的集合足够小，从而可以采取行动”。 C2 将此“可能值的集合”存储为一个*类型*。别想象 Java 的 `int` 或 `long` 类型，而是一个更丰富的[内部类型](https://github.com/openjdk/jdk/blob/6c7fe6fd2045f13fce28139e8e6c5c1a9f6fa7d3/src/hotspot/share/opto/type.hpp#L632)，它携带一个*范围*。在 HotSpot 的大部分生命周期中，整数类型本质上就是： ``` [lo, hi] // 该值处于该有符号范围的某个位置（包含边界） ``` 因此 `x & 0xFF` 的类型将是 `[0, 255]`，编译器可以利用这一点。这个有符号范围简单且有用，但对于我们的目的来说太弱了。考虑 `x << 2`。如果 `x` 可以是任何值，那么 `x << 2` 的范围是什么？嗯……几乎任何值。左移可能会溢出、回绕，产生巨大的正数和负数。覆盖结果的最紧有符号区间是 `[Integer.MIN_VALUE, 2147483644]`。这是一个巨大的范围，几乎覆盖了整个 `int` 范围，编译器几乎得不到任何有用的信息。 但我们对 `x << 2` 有非常具体的信息：无论 `x` 是什么，最低两位始终为零！范围无法表达这一点。`[lo, hi]` 可以说“该值很小”，但它不能说“该值是偶数”，更不用说“该值是 4 的倍数”。这种知识存在于*比特位*中，仅凭范围无法表达。 ## 引入已知比特位 https://questdb.com/blog/jvm-jit-known-bits/#enter-known-bits 解决办法：在范围的基础上，同时追踪我们对每个比特位所了解的信息。对于一个 32 位整数，想象两个额外的 32 位掩码伴随类型： - `zeros`：第 *i* 位为 `1` 表示“第 *i* 位*一定为 0*” - `ones`：第 *i* 位为 `1` 表示“第 *i* 位*一定为 1*” 未知的比特位在两个掩码中都是 `0`。一个位不能同时为两者，因此必须始终满足不变式 `zeros & ones == 0`。在 C2 中，这是 `rangeinference.hpp` 中的十几行代码（https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.hpp#L46-L81）： ``` template <typename 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` 仅检查给定数字 `v` 是否被掩码允许。掩码绝不能排除实际可能出现的值，C2 的测试和内部检查会用此来验证它们不会。现在每个比特位处于三种状态之一：**已知-0**、**已知-1** 或 **未知**。下面是 `x << 2` 的类型，用 `.` 表示未知： ``` bit: 31 ... 2 1 0 x: . . . . . . . . . . . . . . . . . . . (x 完全未知) x << 2: . . . . . . . . . . . . . . . . . 0 0 (低两位：已知为零！) ``` 因此 `x << 2` 的 `zeros = 0b11`，其余全部未知。现在编译器*知道*这个数是 4 的倍数。 这种数据结构并非 HotSpot 独有。LLVM 的 `KnownBits`（https://github.com/llvm/llvm-project/blob/c9ae1305b08161a626a9c7267350bd36b01f2393/llvm/include/llvm/Support/KnownBits.h#L23-L26）与 C2 的表示最为接近（一个 `Zero` 位掩码和一个 `One` 位掩码，具有相同的 `Zero & One == 0` 不变式）；GCC 在其[条件常量传播传递](https://github.com/gcc-mirror/gcc/blob/f7cde200320e0800e4fcc5cea399e9faef50f8d4/gcc/tree-ssa-ccp.cc#L169-L182)中以 `mask` 的形式追踪相同的信息（一个值加上一个不确定性掩码）。这都是同样的思路：对整数进行廉价、非关系、逐位的抽象。 HotSpot 在 JDK 26 中获得了基础（JDK-8315066，由 Quan Anh Mai 和 Emanuel Peter 提交），而实际删除 `(x << 2) & -4` 的部分则落在 JDK 27 中。有趣的事实：Quan Anh Mai 就是 *merykitty*，我们在 1BRC（https://www.morling.dev/blog/one-billion-row-challenge/）期间分析过其[神奇 SWAR 行解析器](https://questdb.com/blog/1brc-merykittys-magic-swar/)。 **非关系型**：该抽象独立追踪每个比特位，从不记录比特位*之间*的关系（没有“位 3 总是等于位 5”）。这种独立性使其廉价：每个比特位的记账是恒定的。 ## 相互精化的两种视图 https://questdb.com/blog/jvm-jit-known-bits/#two-views-that-refine-each-other 现在我们并排拥有同一个数的两种不同描述：一个**范围**和一组**已知比特位**。每一种都知道对方不知道的事情，并且它们可以相互*教导*： - 比特位知道低两位为零。范围利用这一点：如果当前范围为 `[5, 41]`，那么 5、6、7 和 41 的低位均非零，不可能出现，因此范围收紧到 `[8, 40]`（其中最接近的 4 的倍数）。 - 范围知道该值在 `[0, 200]` 内。比特位利用这一点：0 到 200 之间的每个数的高 24 位都为零，因此这些并非未知位；它们实际上已知为零，比特位会记录下来。 这种“组合两种抽象并让它们相互精化”的模式在编译器文献中有一个名字（**归约积(reduced product)** (https://arxiv.org/abs/1309.5146)），而让范围与比特位协调一致直到它们达成一致的函数称为*归约算子*。在 C2 中，它是一个名字非常接地气的函数 `canonicalize_constraints()`，每次创建新的整数类型时都会运行。这是整个特性的核心。 ## 规范化之舞 https://questdb.com/blog/jvm-jit-known-bits/#the-canonicalization-dance 那么如何让范围和比特位达成一致呢？让它们轮流精化对方，直到彼此都无法提供新信息为止。先澄清一点：C2 同时维护有符号区间和无符号区间，这里的归约操作在*无符号*区间上运行，即“简单区间” `[ulo, uhi]`，它从不跨越符号边界，因此步骤 1 中的共享前缀技巧总是安全的。下面的辅助函数在一个这样的简单区间上操作；外部的 `canonicalize_constraints()` 在有符号和无符号视图跨越边界时进行拆分和重组。 循环： 1. **比特位从区间学习。** 取当前无符号区间 `[ulo, uhi]`。在 `ulo` 和 `uhi` 中*相同*的高位比特，对于介于它们之间的每个值也都是相同的（这就是二进制计数的原理：在跨越 2 的幂边界之前，前导数字不会改变）。这些比特位现在成为已知的。 2. **区间从比特位学习。** 取当前 `ulo`。如果它违反了已知比特位（例如比特位要求低两位为零，但 `ulo` 是 `0b...101`），那么 `ulo` 实际上不是一个可能的值，因此将其提升为 ≥ `ulo` 且满足比特位的*最小*值。对 `uhi` 做镜像操作，将其拉低。 3. **返回步骤 1**，看看更紧的区间是否揭示更多已知比特位。重复直到完整的一轮不改变任何东西。 这就是完整的循环，直接来自 `canonicalize_constraints_simple` (https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.cpp#L530-L553)：`adjust_unsigned_bounds_from_bits` 是步骤 2，`adjust_bits_from_unsigned_bounds` 是步骤 1，而退出条件是 `_progress` 变为 false： ``` while (true) { canonicalized_bounds = adjust_unsigned_bounds_from_bits(canonicalized_bounds._result, canonicalized_bits._result); if (!canonicalized_bounds._progress || canonicalized_bounds.empty()) { return SimpleCanonicalResult(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); } } ``` 这样会终止吗？是的。每次触发另一轮完整迭代必须将至少一个先前未知的比特位转变为已知比特位，而最后一轮仅收紧边界可能在循环退出前发生。鉴于最多有 [64 位](https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.cpp#L523-L529)，收敛由字宽界定。 ## 教会 AND 消失 https://questdb.com/blog/jvm-jit-known-bits/#teaching-and-to-disappear 我们还需要教会 C2 如何通过操作计算已知比特位：每个参与的操作都需要一个规则，用于“给定输入的已知比特位，输出的已知比特位是什么？”这些规则简单且机械： ``` AND: out.ones = a.ones & b.ones // 一个位为 1 仅当它在两者中都为 1 out.zeros = a.zeros | b.zeros // 一个位为 0 如果它在任意一个中为 0 OR: out.ones = a.ones | b.ones out.zeros = a.zeros & b.zeros SHL by k: 将两个掩码左移 k 位，然后将 (1<<k)-1 或入 zeros 的低 k 位 （左移腾出的低位始终为零） ``` 你可以从 C2 代码中看到这些规则。[AND 规则](https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.hpp#L364-L372)非常简洁（我将 `U` 设为 `uint64_t` 以匹配 64 位、仅含两行的代码）： ``` U zeros = st1._bits._zeros | st2._bits._zeros; U ones = st1._bits._ones & st2._bits._ones; ``` 而左移规则（`infer_lshift` (https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.hpp#L424-L451)）中，`pattern = (1<<k)-1` 字面表达“腾出的低位为零”这一事实： ``` U pattern = (U(1) << masked_shift) - U(1); U known_one_bits = t1->_bits._ones << masked_shift; U known_zero_bits = (t1->_bits._zeros << masked_shift) | pattern; ``` 我了解到其他编译器也使用类似的技术。我们刚才看到的 AND 和移位规则在 LLVM 中对应 `KnownBits::operator&` (https://github.com/llvm/llvm-project/blob/c9ae1305b08161a626a9c7267350bd36b01f2393/llvm/include/llvm/Support/KnownBits.h#L593-L596) 和 `KnownBits::shl` (https://github.com/llvm/llvm-project/blob/c9ae1305b08161a626a9c7267350bd36b01f2393/llvm/lib/Support/KnownBits.cpp#L410-L492)，在 GCC 中对应 `bit_value_binop` (https://github.com/gcc-mirror/gcc/blob/f7cde200320e0800e4fcc5cea399e9faef50f8d4/gcc/tree-ssa-ccp.cc#L1522-L1536)。Quan Anh Mai 在 [JDK-8367341](https://bugs.openjdk.org/browse/JDK-8367341) 中将此引入 C2 的 `AND`、`OR` 和 `XOR` 节点的 `Value` 中；同一补丁还添加了 [OR 规则](https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.hpp#L391-L404) 和 [XOR 规则](https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/rangeinference.hpp#L406-L417)，紧挨着 AND（XOR 的对偶规则也一并加入，尽管该 issue 只标注为 *And / Or*）。Ashay Rane 在 [JDK-8278857](https://bugs.openjdk.org/browse/JDK-8278857) 中实现了左移规则，这正是本文的起点。 随着已知比特位在图中流动，实际的优化——删除掩码——几乎变成了一行代码。什么时候 `x & y` 就是 `y`？当 AND 不可能清除 `y` 可能设置的任何位时。用已知比特位的术语来说：在每个 `y` *可能*为 1 的位置，`x`*必须*为 1。下面是 C2 中的真实代码，`AndINode::Identity` (https://github.com/openjdk/jdk/blob/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/hotspot/share/opto/mulnode.cpp#L679-L700)，这是 [JDK-8380475](https://bugs.openjdk.org/browse/JDK-8380475) 的更改（由 Ashay Rane 完成），最终删除了掩码。先说明两个 C2 术语：`in(1)` 和 `in(2)` 是 `AND` 节点的两个操作数，`Identity` 是每个节点用于回答“我是否冗余？”的钩子。返回其中一个输入告诉编译器删除这个 `AND`，并将所有使用它的节点重新连接到那个输入： ``` Node* AndINode::Identity(PhaseGVN* phase) { // x & x => x 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) { // in1 中可能为 0 的所有位，在 in2 中已知为 0 return in(2); } if ((~t2->_bits._ones & ~t1->_bits._zeros) == 0) { // in2 中可能为 0 的所有位，在 in1 中已知为 0 return in(1); } return MulNode::Identity(phase); } ``` 两个已知比特位的 `if` 是镜像的：第一个将 `x & y` 化简为 `y`，第二个化简为 `x`。对于 `(x << 2) & -4`，触发的是第二个：`x & y == x` 恰好当 `y` 可能清除的每一位在 `x` 中已经确定为零时成立。用已知比特位的术语，`~y.ones` 是 `y` 可能清除的位集合（任何非已知-1 的位），`~x.zeros` 是 `x` 可能设置的位集合（任何非已知-0 的位），两者均在 32 位字段内；当这两个集合不重叠时，恒等式成立： ``` x & y == x <=> (~y.ones & ~x.zeros) == 0 ``` 让我们看一个具体例子：`(x << 2) & -4` `AndINode` 的第一个参数（`in(1)`）设置为表示 `x = x << 2` 的节点，第二个参数（`in(2)`）表示 `-4`。 ``` x = x << 2: zeros = ...0011 -> ~zeros = ...1100 (x 可能设置的位：除低两位外所有) y = -4: ones = ...1100 -> ~ones = ...0011 (y 可能清除的位：低两位) (~y.ones & ~x.zeros) == (...0011 & ...1100) == 0 ``` `-4` 只能清除低两位，而 `x << 2` 的这两位确定为零，因此 AND 没有任何改变，C2 返回 `in(1)`，即 `x << 2`。`& -4` 节点从图中删除。机器代码仅包含移位操作，`and` 指令完全不产生。 让我们看看这个机制的实际效果。下面是一个简单的——几乎天真的——测试程序：两个单行方法和一个循环，循环调用它们足够多次以触发 C2 编译： ``` public class ShiftMask { // 冗余：(x << 2) 的低两位已经为零，而 -4 == 0xFFFFFFFC // 正好清除这两位。C2 应该删除 AND。 static int redundant(int x) { return (x << 2) & -4; } // 非冗余：-8 == 0xFFFFFFF8 也清除位 2，而 C2 无法证明该位为零。 static int kept(int x) { return (x << 2) & -8; } public static void main(String[] args) { long s = 0; for (int i = 0; i < 400_000; i++) { s += redundant(i); s += kept(i); } System.out.println(s); } } ``` 编译它，然后让 C2 打印这两个方法的反汇编（这需要在 JDK 的库路径上有 [hsdis](https://github.com/openjdk/jdk/tree/0c209afd4f9f669490ef6e07ac582fbc0a6cb649/src/utils/hsdis)）： ``` javac ShiftMask.java java -XX:+UnlockDiagnosticVMOptions -XX:-TieredCompilation \ -XX:CompileCommand='compileonly,ShiftMask::redundant' \ -XX:CompileCommand='compileonly,ShiftMask::kept' \ -XX:CompileCommand='dontinline,ShiftMask::redundant' \ -XX:CompileCommand='dontinline,ShiftMask::kept' \ -XX:CompileCommand='print,ShiftMask::redundant' \ -XX:CompileCommand='