コンパイラがあなたを驚かせるとき

 (xania.org)
1 ポイント 投稿者 GN⁺ 2025-12-26 | 1件のコメント | WhatsAppで共有
  • 単純な整数加算関数をコンパイルする際に、GCCとClangの最適化の違いを観察した事例
  • GCCはループ内で2つの数を一度に足す x*2 + 1 形式のループ最適化を実行
  • Clangはループを完全に削除し、v(v - 1)/2 という閉形式の数式による計算に置き換え
  • この変換によってコードは O(n) から O(1) に変わり、数学的な単純化が自動で行われる
  • 20年以上コンパイラを扱ってきた著者ですら驚くほど、コンパイラの知的な最適化レベルを示す事例

GCCのループ最適化

  • 単純な整数加算関数を書いたとき、GCCはループベースの効率的な加算コードを生成
    • ループ内部で lea edx, [rdx+1+rax*2] 命令を使い、2つの数を同時に加算
    • これは x と x+1 を足す演算を x*2 + 1 に変換した形
  • 最適化レベルを -O3 に上げると、**並列加算（vectorization）**によってループをより高速に処理
  • こうした方式は反復文を維持しつつ、演算効率を最大化する伝統的な最適化の形

Clangの数学的最適化

  • 同じコードをClangでコンパイルすると、ループが完全に消える
    • Clangは入力値が正かどうかを確認した後、一連の lea、imul、shr 命令で計算を実行
    • 結果として (v² - v)/2、すなわち 整数和の閉形式の数式へ変換
  • この変換は反復文を削除し、定数時間 O(1) の計算に置き換える
  • 著者はこの結果を「整数和の数学的解法を自力で見つけ出した」と表現

数式の展開過程

  • Clangが生成したアセンブリコードを数学的に逆追跡すると、次のような変換が行われている
    • v + ((v - 1)(v - 2) / 2) - 1
    • これを展開して整理すると (v² - v)/2 に単純化される
  • 最終的に v(v - 1)/2 の形となり、1からvまでの総和の公式と一致
  • この過程は、コンパイラが数学的パターンを認識して最適化した事例として提示される

コンパイラの知的な動作

  • Clangがこの特定の命令シーケンスを使う理由は、オーバーフロー防止と誘導変数追跡の方式によるものだと説明される
  • 正確な内部動作の原因は明確ではないが、Clangの内部最適化ロジックが複合的に作用した結果として言及される
  • 著者はこうした結果を「謙虚さを感じさせ、刺激を与えてくれる経験」と表現

まとめとシリーズ文脈

  • この記事は 「Advent of Compiler Optimisations 2025」 シリーズの24本目の記事
  • コンパイラがコード変換を通じて 数学的単純化と性能向上を達成する過程を探る
  • 著者は「コンパイラは今でも私を驚かせる」と述べ、長年の経験にもかかわらず続く技術的な驚異を強調

関連記事

1件のコメント

 
GN⁺ 2025-12-26
Hacker Newsの意見

  • この機能を実装したコードは ScalarEvolution.cpp と IndVarSimplify.cpp にある

    • 1つのファイルにほぼ 16,000行 のコードが入っているのは驚きであると同時に、少し不安でもある

  • この種の最適化は本当に興味深い
    コンパイラ最適化は大きく2種類に分かれる — データフロー解析 と パターン認識および置換
    前者はたいていのプログラムに有効で、後者はだんだんリターンが減っていくパターンの蓄積作業である
    リンク先の例は賢くて面白いが、実際のところ大きな価値はない。45年間こういうループを書いたことがない
    もちろん、こうしたパターン置換は高水準コードから自動生成されるため、依然として重要ではある
    正直に言えば、自分の optimizer がこういう最適化をできないので少し文句を言っているだけかもしれない

    • 実際には思った以上に価値があるかもしれない。LLVM の SCEV(Scalar Evolution) は主に解析に使われ、数式ループ以外の最適化も可能にしている
    • どの最適化を行ったのかは明確ではない。以前ニッチ向けのコンパイラを作ったとき、自分で書いた最適化よりもコンパイラのほうが賢く処理していて驚いたことを思い出す

  • これは Scalar Evolution(SCEV) と呼ばれる機能で、LLVM ではかなり複雑に実装されている

  • 類似の最適化例として 「Do not optimize away」記事 がある

    • その記事の冒頭の説明は少し間違っている。コードは 0 から N まで足すが N 自体は含まないので、実際には N(N-1)/2 が正しい。数学的には 1 から N までの和は N(N+1)/2 なので、上限を含めないなら N を (N-1) に変える必要がある
    • コンパイラはこれもまだ最適化できるのではないかと思う。定数畳み込み版と非定数版をそれぞれ作って実行時に分岐すれば可能そうだ

  • この最適化の本当にすごい点は 汎用化(generic) されていることだ
    単に「有限整数列の和」というパターンを認識するのではなく、汎用的に適用されている点が印象的だ

  • コンパイラがさらに多くの closed form を追加できるかもしれない。そこまでの価値があるのか気になる
    関連概念として Wilf–Zeilberger pair がある

  • またしても GCC が Clang より遅い 結果に驚いた
    GCC は20年も先行していたのに、それでもなお Clang のほうが速いコードを出すことがある
    以前ビット抽出をしたとき、Clang は2回のシフトで済んだのに、GCC は3回も使っていた

    • GCC と LLVM/Clang の間にはコンパイラ技術の世代差が大きい。GCC も依然として素晴らしいプロジェクトだが、現代的な最適化手法 を適用するには構造的に難しいと聞く
    • 実際の性能は両コンパイラで似たようなものだ。異なる最適化パスを持っているため、状況によって結果が変わる
    • GCC は初期に ライセンス重視の理想主義的設計 をしていたため拡張性が低かった。今はかなり緩和されたが、コード生成器はいまだに複雑だ。一方 Clang は構造が単純で最適化の実装がしやすい。個人的には MSVC や ICC の出力もかなり良いと感じる
    • もしかして bitfield 関連のコードだったのか？ GCC はその部分の最適化が特に弱い

  • 誰かが グラフ彩色問題(graph coloring) を定数に置き換える最適化を試したことがあるのだろうかと気になる

    • グラフ彩色は NP-hard 問題なので O(1) に置き換えるのは難しい。平面グラフなら四色定理が適用されるが、常に同じ答えになるわけではない。ただグラフ理論の話をしたかっただけだ

  • これは実装と仕様の境界を曖昧にする例だ
    私たちは実装を書いているつもりでも、実際には 仕様のプロキシ を書いているようなものだ
    つまり、コンパイラが 命令型機械の幻想 を作り出しているのである

  • 最初は Matt がこうした動作を知らないことに驚いた
    自分も大学時代に LLVM IR をいじっていて、再帰が乗算に単純化 されるのを見て衝撃を受けた
    Matt が知らなかったということは、この最適化が彼の扱わない単純なケースにしか適用されないことを意味するのかもしれない

    • 実際には彼はすでに知っていた。2017年の講演で同じ例に自ら言及していた
      YouTube動画リンク