何もコンパイルされないマスク：HotSpot の JIT はどのようにビットを推論することを学んだか

開発者が (x << 2) & -4 と入力した場合、最適化コンパイラはそれを単なるシフト演算子 x << 2 にコンパイルすべきです。ビット単位の AND は消えるはずです。なぜでしょうか？ x = 1011 0111 という 8 ビットの数値があり、私の式が (x << 2) & -4 のようになっていると想像してください。 x 1011 0111 (元の x) ---------------------- x << 2 1101 1100 (x を左シフト、下位 2 ビットは常に 0) & -4 1111 1100 (-4 は 2 の補数表現。マスクは下位 2 ビットのみをクリアする) ---------------------- 結果 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 の倍数」と言うことはできません。その知識はビットに宿っており、範囲だけではそれを表現できません。 Known Bits の登場 修正点：範囲に加えて、各個別のビットについて何を知っているかを追跡します。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、または未知の 3 つの状態のいずれかにあります。 x << 2 の型は次のようになります。ドットは未知を表します。 ビット: 31 ... 2 1 0 x: . ... . . . . . . (x は完全に未知) x << 2: . ... . . . . . 0 0 (下位 2 ビット：既知のゼロ！) したがって、x << 2 は zeros = 0b11 を持ち、それ以外は未知です。コンパイラは今、その数値が 4 の倍数であることを知っています。このデータ構造は HotSpot だけのものではありません。LLVM の KnownBits は C2 の表現に最も近いものです（同じ Zero & One == 0 の不変条件を持つ Zero と One のビットマスク）。GCC は、条件付き定数伝播パスでマスクとして同じものを追跡します（値と不確実性マスク）。それは同じアイデアです。整数の安価で非関係的な、ビットごとの抽象化です。HotSpot は JDK 26 で基盤 (JDK-8315066、Quan Anh Mai と Emanuel Peter による) を取得し、(x << 2) & -4 を削除する実際の部分は JDK 27 で取り込まれました。豆知識：Quan Anh Mai は merykitty で、彼女の魔法の SWAR 行パーサーを 1BRC の際に分解しました。 INFONon-relational: この抽象化は各ビットを個別に追跡し、ビット間の関係を記録することはありません（「ビット 3 は常にビット 5 と等しい」など）。その独立性が、それを安価にしている理由です。ビットごとの定数ブックキーピングです。 互いを洗練する 2 つのビュー これで、同じ数値に対して 2 つの異なる説明が並置されることになります。範囲と既知のビットのセットです。それぞれが他方が知らないことを知っており、互いに教え合うことができます。 ビットは下位 2 ビットがゼロであることを知っています。範囲はそれを使用します。もし範囲が現在 [5, 41] と言っている場合、5、6、7、および 41 はすべて下位ビットがゼロではなく、発生しえないため、範囲は [8, 40] に絞り込まれます。これは、その中の 4 の倍数に最も近い値です。 範囲は値が [0, 200] の内側にあることを知っています。ビットはそれを使用します。0 から 200 までのすべての数値は、上位 24 ビットがゼロです。したがって、それらは未知のビットではなく、既知のゼロであり、ビットはそれを記録します。 この「2 つの抽象化を組み合わせて、互いに洗練させる」パターンは、コンパイラ文献では名前（還元積）があり、範囲とビットが合意するまで調整し続ける関数は、還元演算子と呼ばれます。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 は各部分を「単純区間」と呼びます。その境界は符号を共有しているため、符号付きおよび符号なし比較はそれに同意します。単純区間は、有効な符号付き範囲であり、有効な符号なし範囲でもあり、符号境界をまたぐことはないため、共有プレフィックストリックは常に安全です。 還元は 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 の両方で同一である上位ビットは、その間のすべての値で同一です（これはバイナリカウントの仕組みです：