なぜ (x << 2) & -4 のAND演算は消えるべきなのか

8ビットの数値 x = 10110111 を例に考えます。（出典）

  • x を2ビット左シフトすると 11011100（下位2ビットは必ず0になる）
  • これを -4（2の補数表現で下位2ビットだけをクリアするマスク）とAND演算しても、結果は変わらず 11011100

つまり & -4 という演算は、シフト演算の性質上もともと何もしていないことになります。

最適化コンパイラであれば、(x << 2) & -4 を単なる x << 2 にまで簡約できてしかるべきだ。

「範囲」だけでは「常に偶数」を表現できない

HotSpotのC2コンパイラは、ある変数が取りうる値の集合を「型」として内部管理しています。従来この型は [最小値, 最大値] という符号付き範囲だけで表現されていました。

手法 x << 2 の情報 最適化への活用
範囲 [lo, hi] のみ ほぼint型全域（[Integer.MIN_VALUE, 2147483644]） ほとんど活用できない
Known Bits併用 下位2ビットが確実に0 & -4 のようなマスク演算を除去できる

x が取りうる値が全く分からない場合、x << 2 の範囲はオーバーフローや符号反転を考慮するとint型のほぼ全域に広がってしまい、コンパイラにとってほとんど役に立ちません。

「known-0・known-1・不明」を追跡する仕組み

そこでC2は、範囲情報に加えて32ビットの数値それぞれについて「確実に0（zeros）」「確実に1（ones）」を示す2つのビットマスクを併せ持つようになりました。

template <class U>
class KnownBits {
  U _zeros;
  U _ones;
  bool is_satisfied_by(U v) const {
    return (v & _zeros) == U(0) && (v & _ones) == _ones;
  }
};

x << 2 の場合、下位2ビットは zeros に立ち、それ以外は不明のままです。これにより、コンパイラは「この数値は4の倍数である」ことを把握でき、& -4 のようなマスク演算を安全に削除できるようになります。

この仕組みはHotSpot固有のものではなく、LLVMの KnownBits（同じzero/oneビットマスクと zeros & ones == 0 という不変条件を持つ）が最も近い実装だとされ、GCCも同様の情報を追跡しているといいます。

普段Python・TypeScriptを中心に書いている身としては、ここまで低レベルな最適化に触れる機会は多くありません。ただ、自分が日常的に使っているV8やCPythonのような処理系の内部でも、似たような「値についての知識」を積み上げる仕組みが動いているのだろうと想像すると、普段意識しない部分への解像度が少し上がる感覚があります。