何もコンパイルされないマスク:HotSpot の JIT はどのようにビットを推論することを学んだか
The mask that compiles to nothing: how HotSpots JIT learned to reason about bits (questdb.com)
要約
最適化コンパイラは、(x << 2) & -4 のような式を、ビット単位の AND が不要であることを認識し、単なるシフト演算子 x << 2 にコンパイルできます。これは、JVM の HotSpot JIT コンパイラが、数値の範囲だけでなく、個々のビットの状態(ゼロか、イチか、不明か)も追跡する「Known Bits」という抽象化機能によって実現されています。この機能により、コンパイラはビットレベルの制約を理解し、不要な演算を削除できるようになりました。
全文翻訳
何もコンパイルされないマスク:HotSpotのJITはビットをどのように推論するようになったか
開発者が (x << 2) & -4 と入力した場合、最適化コンパイラはそれを単なるシフト演算 x << 2 にコンパイルするはずです。ビット単位の AND は消えるべきです。なぜでしょうか? 8ビットの数値 x = 1011 0111 があり、私の式が (x << 2) & -4; のようになっていると想像してください。
x 1011 0111 (元のx)---------------------- x << 2 1101 1100 (シフト後のx、下位2ビットは常に0) & -4 1111 1100 (-4を2の補数で表したもの -> マスクは下位2ビットのみをクリアする)---------------------- result 1101 1100 (x << 2と同じ、ビット単位のANDは効果がない)
しかし、C2コンパイラはこれを実際にはどのように行うのでしょうか? この最適化は、複数の変更セットにわたって構築された一般的な抽象化に依存しています。この記事は、それを理解し説明しようとする私の試みです。
JITコンパイラは数値について実際に何を知っているのか?
C2がメソッドをコンパイルしているとき、特定の変数内の値について何を知っているのでしょうか?
答えは「可能な値のセット」です。コンパイラは通常、x の正確な実行時値を把握できません(それが変数のポイントです)が、x が制約されていることを証明できることがよくあります。その制約が十分にタイトであると証明できれば、コードを書き換えることができます。古典的な例は、コンパイラが配列インデックスが常に [0, length) の範囲内にあると証明した場合、境界チェックを削除することです。定数畳み込み、デッドコード削除、その他の最適化は、多くの場合「可能な値のセットが小さすぎて処理できると証明する」ことに帰着します。
C2は、この「可能な値のセット」を型として格納します。Javaの int や long の型を想像しないでください。むしろ、範囲を保持する、はるかにリッチな内部型です。HotSpotのほとんどの期間、整数型は本質的に次のようになっていました。
[lo, hi] // 値は、この符号付き範囲内(両端を含む)にある
したがって、x & 0xFF の型は [0, 255] となり、コンパイラはそれを使用できました。この符号付き範囲はシンプルで有用ですが、目的には弱すぎます。
x << 2 を考えてみましょう。x が任意の値を取りうる場合、x << 2 の範囲は何でしょうか? まあ…ほとんど何でもありえます。左シフトはオーバーフローしたり、ラップアラウンドしたり、巨大な正の値や巨大な負の値を生み出したりする可能性があります。結果をカバーする最もタイトな符号付き区間は [Integer.MIN_VALUE, 2147483644] です。これは巨大な範囲で、int の全範囲にわずかに満たない程度であり、コンパイラにはほとんど何も有用な情報を提供しません。
しかし、x << 2 について非常に具体的なことがわかっています。x が何であっても、下位2ビットは常にゼロです! 範囲ではこれを表現できません。[lo, hi] は「値が小さい」と言うことはできますが、「値が偶数である」とか、ましてや「値が4の倍数である」と言うことはできません。その知識はビットに宿っており、範囲だけではそれを表現できません。
既知ビットの導入
解決策:範囲に加えて、各個々のビットについて何を知っているかを追跡します。32ビット整数について、型と一緒に2つの追加の32ビットマスクが移動すると想像してください。
zeros: 位置i の1は「ビットi は確実に 0」を意味します。ones: 位置i の1は「ビットi は確実に 1」を意味します。
未知のビットは両方のマスクで 0 です。ビットが両方になることはないので、不変条件 zeros & ones == 0 は常に満たされなければなりません。C2では、これは 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 は、与えられた数値 v がマスクによって許可されているかどうかをチェックするだけです。マスクは実際に発生しうる値を決して除外してはならず、C2のテストと内部チェックはこれを使用して、それらが除外されていないことを検証します。
各ビットは、既知の0、既知の1、または未知のいずれかの状態になります。x << 2 の型は次のようになります(. は未知を表します)。
bit: 31 2 1 0x: . . . . . . . . . . . . . . . . . . .
(x は完全に未知)
x << 2: . . . . . . . . . . . . . . . . . 0 0
(下位2ビット: 確実にゼロ!)
したがって、x << 2 は zeros = 0b11 を持ち、それ以外はすべて未知です。コンパイラは今や、その数値が4の倍数であることを知っています。
このデータ構造はHotSpotに固有のものではありません。LLVMの KnownBits はC2の表現に最も近いものです(同じ Zero & One == 0 の不変条件を持つ Zero と One のビットマスク)。GCCは、その条件付き定数伝播パスで mask として同じものを追跡しています(値と不確実性マスク)。それは同じアイデアです。安価で、非関係的な、ビットごとの整数の抽象化です。HotSpotはJDK 26で基盤(Quan Anh MaiとEmanuel Peterによる)を取得し、(x << 2) & -4 を実際に削除する部分はJDK 27に組み込まれました。面白い事実:Quan Anh Maiはmerykittyであり、1BRCの際に彼の魔法のようなSWARラインパーサーを分解しました。
非関係的: この抽象化は各ビットを個別に追跡し、ビット間の関係を記録することはありません(「ビット3は常にビット5と等しい」など)。その独立性が、それを安価にしています。ビットごとの定数ブックキーピングです。
互いに洗練し合う2つのビュー
これで、同じ数値に対して2つの異なる説明が並置されることになります。範囲と既知ビットのセットです。それぞれが他方が知らないことを知っており、互いに教え合うことができます。
- ビットは下位2ビットがゼロであることを知っています。範囲はそれを使用します。もし範囲が現在
[5, 41]と言っている場合、5、6、7、41 はすべて非ゼロの下位ビットを持ち、発生しないため、範囲は[8, 40]にタイト化されます。これは、その内部にある最も近い4の倍数です。 - 範囲は値が
[0, 200]にあることを知っています。ビットはそれを使用します。0から200までのすべての数値は、上位24ビットがゼロです。したがって、それらは未知のビットではなく、既知のゼロであり、ビットはそれを記録します。
この「2つの抽象化を組み合わせて互いに洗練させる」パターンは、コンパイラ文献に名前があります(縮約積(reduced product))。範囲とビットが合意するまで調整し続ける関数は還元演算子と呼ばれます。C2では、それは非常に実用的な名前 canonicalize_constraints() を持つ関数であり、新しい整数型が作成されるたびに実行されます。それはこの機能全体の心臓部です。
正規化のダンス
では、どのようにして範囲とビットを合意させるのでしょうか? どちらも新しいことを追加できなくなるまで、互いに調整させ続けます。まず1つの明確化:C2の整数型は実際には3つの制約を保持しており、値は32ビットパターンがすべてパスした場合にのみ型に属します。type.hpp の定義から直接抜粋します。
v >= _lo && v <= _hi && // 符号付き範囲
juint(v) >= _ulo && juint(v) <= _uhi && // 同じビットを符号なしで比較
_bits.is_satisfied_by(v) // 既知ビット
なぜ符号なし範囲も必要なのでしょうか? C2は符号なし比較を推論する必要があるからです。この投稿の冒頭にあった境界チェックを思い出してください。HotSpotはそれを単一の符号なし比較 index u< length にコンパイルします。そのような比較が常に真か常に偽かを判断することは、符号付き範囲ではなく、符号なし範囲の問題です。符号付き範囲と符号なし範囲を交差させると、1つまたは2つの互いに素な部分が得られ、それぞれに符号が両方とも負であるか、両方とも非負である境界があります。たとえば、符号付き [-5, 5] と符号なし [2, UINT_MAX] は [-5, -1] と [2, 5] に交差します。負の値は、それらのビットパターンが UINT_MAX のすぐ下にある巨大な符号なし数として読み取られるため、符号なしチェックに合格しますが、0 と 1 は失敗します。C2は、これらの各部分を「単純区間(simple interval)」と呼びます。その境界は符号を共有しているため、符号付きおよび符号なし比較はそれらに同意します。単純区間は同時に有効な符号付き範囲であり、有効な符号なし範囲でもあり、符号境界をまたがないため、ステップ1の共有プレフィックストリックは常に安全です。正規化は一度に1つの単純区間に対して機能します。外側のcanonicalize_constraints()は分割を行い、結果をマージします。
// 2つの単純区間は、2つの別々の結果にタイト化できます
auto neg_type = canonicalize_constraints_simple({U(srange._lo), urange._hi}, _bits);
auto pos_type = canonicalize_constraints_simple({urange._lo, U(srange._hi)}, _bits);
各単純区間が両方のビューからの境界をどのように混合しているかに注意してください。負の部分は符号付きの下限から符号なしの上限まで実行され、非負の部分は符号なしの下限から符号付きの上限まで実行されます。ループは次のとおりです。
-
ビットが区間から学習する。 現在の単純区間
[ulo, uhi]を取ります。uloとuhiの両方で同一である上位ビットは、その間のすべての値で同一です(これはバイナリカウントの仕組みです。上位桁は、2のべき乗の境界を越えるまで変化しません)。それらのビットは既知になります。 -
区間がビットから学習する。 現在の
uloを取ります。既知ビットに違反する場合(たとえば、ビットが下位2ビットをゼロにするように要求しているのにuloが0b...101の場合)、uloは実際には可能な値ではないため、ビットを満たすulo以上の最小値に引き上げます。同様のことをuhiにも行って引き下げます。 -
ステップ1に戻り、タイト化された区間がさらに既知ビットを明らかにするかどうかを確認します。完全なパスが何も変更しなくなるまで繰り返します。
それがcanonicalize_constraints_simpleのループです。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<U>(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<U>(canonicalized_bits._present, canonicalized_bounds._result, canonicalized_bits._result);
}
}
これは終了するのでしょうか? はい。別の完全なラウンドをトリガーする各反復は、少なくとも1つの以前は未知だったビットを既知のビットに変えなければならず、ループが終了する直前に最終的な境界のみのタイト化が行われる可能性があります。最大で64ビットがあることを考えると、収束はワード幅によって制限されます。
ANDを消滅させる方法を教える
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.zerosSHL by k: 両方のマスクをkだけシフトし、zerosに(1<<k)-1をORする // 空いた下位kビットは確実にゼロ、まさにx<<2の事実
転移関数: 入力についてわかっていることを出力についてわかっていることに変換する単一操作のルール。上記の AND と SHL のルールは転移関数です。オペランドの既知ビットを入力し、結果の既知ビットを取得します。実際のコードはほとんど変わりません。ANDルール(infer_and_impl):
U<CTP> zeros = st1._bits._zeros | st2._bits._zeros;
U<CTP> ones = st1._bits._ones & st2._bits._ones;
左シフト(infer_lshift)、ここで pattern = (1 << k) - 1 は文字通り「空いた下位ビットはゼロ」という事実です。
U<CTP> pattern = (U<CTP>(1) << masked_shift) - U<CTP>(1);
U<CTP> known_one_bits = t1->_bits._ones << masked_shift;
U<CTP> known_zero_bits = (t1->_bits._zeros << masked_shift) | pattern;
他のコンパイラも同様のテクニックを使用していることを学びました。ここで見たANDとシフトのルールは、LLVMでは KnownBits::operator& と KnownBits::shl として、GCCでは bit_value_binop として実装されています。
Quan Anh Maiは、JDK-8367341でC2の AND、OR、XOR ノードの Value にこれを持ち込みました。同じパッチは、ANDのすぐ隣に OR と XOR のルールを追加します(問題はAnd / Orとだけタイトルされていますが、XOR の双対も一緒に運ばれます)。Ashay Raneは、この投稿全体を開始したJDK-8278857で左シフトのルールを作成しました。
既知ビットがグラフを流れるようになると、実際の最適化、つまりマスクの削除は、ほぼ1行のコードになります。x & y が y になるのはいつでしょうか? ANDが y が設定する可能性のあるビットをクリアできない場合です。既知ビットの用語では、y が1になる可能性があるすべての位置で、x が確実に1である必要があります。C2の実際のコード、AndINode::Identity のコードは次のとおりです。これは、マスクを最終的に削除したJDK-8380475の変更(Ashay Raneによる)です。まずC2の2つの用語:in(1) と in(2) は AND ノードの2つのオペランドであり、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();
// x & y == x <=> (~y.ones & ~x.zeros) == 0
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);
}
2つの既知ビットの if 文は鏡像です。最初のものは x & y を y に折りたたみ、2番目のものは x に折りたたみます。(x << 2) & -4 の場合、最初にトリガーされるのは2番目の条件です。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 を表すノードに設定され、2番目の引数 (in(2)) は -4 を表します。
x = x << 2: zeros = ...0011 -> ~zeros = ...1100 (x が設定する可能性のあるビット: 下位2つを除くすべて)
y = -4: ones = ...1100 -> ~ones = ...0011 (y がクリアする可能性のあるビット: 下位2つ)
(~y.ones & ~x.zeros) == (...0011 & ...1100) == 0
-4 は下位2ビットのみをクリアする可能性があり、x << 2 はそれらの2ビットが確実にゼロであるため、ANDは何も変更せず、C2は in(1)、つまり x << 2 を返します。& -4 ノードはグラフから削除されます。マシンコードにはシフトのみが含まれ、and 命令はまったく発行されません。
この仕組みの効果を実際に見てみましょう。ここにシンプルな、ほとんど素朴なテストプログラムがあります。2つの1行メソッドと、それらを十分に呼び出してC2コンパイルをトリガーするループです。
public class ShiftMask {
// 冗長: (x << 2) は既に下位2ビットがゼロであり、-4 == 0xFFFFFFFC は
// それらの2ビットのみをクリアします。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にそれらの2つのメソッドの逆アセンブリを印刷させます(これにはJDKのライブラリパスにhsdisが必要です)。
javac ShiftMask.javajava -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='print,ShiftMask::kept' \
-XX:PrintAssemblyOptions=intel ShiftMask
以下のリストの環境:AMD Ryzen 9 9950X、Ubuntu 26.04、Linux 7.0.0。JDK 24の出力は標準のCorretto 24.0.2です。JDK 27の出力はopenjdk/jdkのローカルビルドで0c209afdです。
compileonlyフィルターは、ホットなmainループをインタープリタのままにするため、OSRコンパイルにはなりません。以下に読むのは、通常の、呼び出しによってトリガーされるメソッド本体です。JDK 24では、この作業がマージされる前は、冗長なマスクが発行されていました。
; JDK 24:
; static int redundant(int x) { return (x << 2) & -4; }
...
shl esi,0x2 ; esi = x << 2
mov eax,esi
and eax,0xfffffffc ; & -4, no-opだが、古いC2は透過できない
...
ret
JDK 27ビルドでは、冗長なandは削除されており、このx86-64ビルドではC2はシフトを単一のlea命令に折りたたんでいます。
; JDK 27:
; static int redundant(int x) { return (x << 2) & -4; }
...
lea eax,[rsi*4+0x0] ; eax = x << 2 (ANDは削除)
...
ret
lea eax,[rsi*4+0x0] は、単一のアドレス指定操作で x * 4、つまり x << 2 を計算します。どこにもand命令はありません。
理解を検証するための実験をしましょう。マスクを-4から-8に変更します。これによりビット2もクリアされますが、これはC2がゼロであると証明できないため、同じJDK 27ビルドでもand命令が再び発行されるコードに含まれます。
; JDK 27:
; static int kept(int x) { return (x << 2) & -8; }
...
shl esi,0x2 ; esi = x << 2
mov eax,esi
and eax,0xfffffff8 ; マスクは残る: -8 は1になりうるビットをクリアする
...
ret
redundant と kept メソッドは、同じバイトコード(ishl、次にiand、次にireturn)から始まりますが、マスク定数のみが異なります。既知ビット分析が、そのビルドが最初のiandをドロップし、2番目を保持する理由です。
これをどうやってテストするのか?
canonicalize_constraints とすべてのビットルールが、2^64個のすべての可能なlong値に対して実際に正しいことをどのように証明できるでしょうか?
この変更には、小さなintn_t<N>型(任意の小さな幅の整数)が付属しています。正規化は、4ビット型(4ビットでは16値、範囲とマスクのすべての組み合わせ)に対して網羅的にテストされます。私はこれを有用なトリックとして読みました。整数幅を縮小して網羅的テストが安価になるまで縮小し、その宇宙のすべての状態をテストします。操作の転移関数は、網羅的な小幅テストとランダムな広幅テストの組み合わせを使用します。
コア部分(test_rangeinference.cpp)は次のとおりです。小さな宇宙全体を6つのネストされたループで実行し、すべての可能な (lo, hi, ulo, uhi, zeros, ones) タプルを canonicalize_constraints に渡します。
for (int lo = S::min; lo <= S::max; lo++) {
for (int hi = lo; hi <= S::max; hi++) {
for (int ulo = U::min; ulo <= U::max; ulo++) {
for (int uhi = ulo; uhi <= U::max; uhi++) {
for (int zeros = U::min; zeros <= U::max; zeros++) {
for (int ones = U::min; ones <= U::max; ones++) {
TypeIntPrototype<S, U> t{{S(lo), S(hi)}, {U(ulo), U(uhi)}, {U(zeros), U(ones)}};
auto new_t = t.canonicalize_constraints();
// ...その後、new_tがtと全く同じ値を含むことをアサートします。vごと
S と U は intn_t<N> / uintn_t<N> であり、テスト は N = 1, 2, 3, 4 に対してすべてを実行します。
私が気にする理由、そしておそらくあなたが気にするべき理由
私はコンパイラエンジニアではなく、そのふりもしません。私はただ、コンパイラコンピュータがどのように機能するかを学ぶのが好きで、このような最適化を追いかけるのは楽しいです。また、新しい概念を理解するためにLLMを使用します。これらの探求中に、私はLLMを個人的なチューターとして使用します。理解できるまで質問します。もしあなたが実際のコンパイラエンジニアで、私の説明に誤りを見つけたら、教えてください! 喜んで修正します。
実際、これはすでに起こりました。この投稿の以前のバージョンでは、単純区間を「符号なしのもの」と説明していましたが、Redditユーザーのcal-cheeseが私を訂正してくれました。それは符号付き範囲と符号なし範囲の交差部分です。上記の説明は修正されたものです。ありがとうございます!
この素晴らしい探求に私を導いてくれたQuan Anh Mai、Emanuel Peter、そしてAshay Raneに感謝します!