-O2 が何をしたかを読む

一言でいうと

ここまで作った段階、すなわち構文解析、意味解析、中間表現、最適化、レジスター割り当て、コード生成は、gccやclangの中にもそのままあります。その出力(-Sのアセンブリ、-emit-llvmのLLVM IR、objdump -dの機械語)を関数単位に切り分けて数えてみると、最適化が何をしたのか、つまり呼び出しを溶かし込んだのか、ループを定数1つに畳んだのか、除算を乗算に変えたのか、再帰をループに変えたのかが、数字で現れます。

なぜ必要なのか

「-O2でビルドすると速くなる」ことは知っていても、何が速くなったのかを知らないと、性能問題の前で推測しかできません。反対に、「-O2でだけ結果がおかしい」というバグに出会ったとき、コンパイラーを疑う前に確認できることがあります。そのコードが未定義動作に頼っていないか、です。どちらの場合も、答えはコンパイラーが出したものを直接読むことです。このモジュールは、その読む目を、前の9つのモジュールで自分で作ってみたものにつなげます。

どう動くのか

材料の/opt/fixtures/mini/real/opt.cにある関数は、それぞれ1つの変換をねらっています。

関数	-O2が行うこと	アセンブリで見えるもの
`sum_to`	1から100まで足すループを丸ごと計算	`movl $5050, %eax`・`ret`の2行
`sum_squares`	`square`の呼び出しを溶かし込む(インライン化)	`call square`が消える
`div10`	除算(idiv、数十サイクル)を乗算とシフトに	`movabsq $7378697629483820647`・`imulq`・`sarq`
`fact`	末尾再帰をループに	`call fact`が消えて、後ろへ戻るジャンプができる
`always`	`x + 1 > x`を常に真に(符号付きオーバーフローはないと仮定)	`movl $1, %eax`・`ret`
`fib`	再帰を部分的に展開し、レジスターをすべて使う	命令数が-O0の10倍を超えることもある

除算のマジックナンバー。x / 10はx × 0x6666666666666667 ÷ 2^66と同じです(負の数の補正がもう1つ)。0x6666…67は、2^66 / 10を切り上げた数です。乗算は数サイクルで、除算は数十サイクルなので、割る数が定数なら、コンパイラーはほとんど常にこう置き換えます。割る数を変えて再コンパイルすると、マジックナンバーも変わります。そのため、このラボの採点ツールは、変形を作って確かめます。

未定義動作と最適化。always(int x) { return x + 1 > x; }は、xがINT_MAXのときにオーバーフローしますが、Cでは符号付き整数のオーバーフローは未定義動作です。コンパイラーは「そんなことは起こらない」と仮定してかまわないので、式全体を1に畳みます。符号なしのuwrapは、オーバーフローが折り返しとして定義されているので、そうはできず、実際の比較が残ります。ミニがオーバーフローを「折り返す」と定義しておいた理由が、これです。定義しておけば、インタプリター・VM・ネイティブコードが同じ答えを出す必要があり、最適化器は、その答えを変えられません。

LLVM IRとSSA。clang -S -emit-llvmは、LLVMの中間表現を文字で見せてくれます。-O0では、すべてのローカル変数がalloca(スタックの段)1つずつで、使うたびにload、変えるたびにstoreです。モジュール8のコード生成器と同じ方式です。-O1では、その段が消えて(mem2reg・SROA)、2つの道が合流する場所にphiができます。モジュール7で支配境界を使って位置を計算した、まさにそのφです。

-O0: fib              %2 = alloca i64          -O1: fib           %6 = phi i64 [ … ], [ … ]
                      store i64 %0, ptr %3                         (alloca·load·store 없음)
                      %4 = load i64, ptr %3

JITも同じことをします。JVMのJIT(HotSpot C2)とブラウザーのV8は、実行中にこれらの段階を動かします。違いは、入力に実行中に見た事実(この呼び出し位置には、いつもこの型が来る)が加わるだけなので、このモジュールで読む変換、すなわちインライン化、定数畳み込み、ループの変換が、JITのログでもそのまま見えます。

現場での姿

Compiler Explorerとobjdump -dコマンド。性能レビューで「このループがベクトル化されたか」「この関数がインライン化されたか」を確認するいちばん速い方法は、出力を読むことです。objdump -d --no-show-raw-insn 실행파일は、すでに焼いたバイナリでも、同じものを見せてくれます(プレースホルダーは実行ファイル名です)。
-O2でだけ起きるバグ。符号付きオーバーフロー、初期化していない変数、ポインターのエイリアス規則違反は、-O0では偶然合っていて、-O2で間違います。-fwrapv(符号付きオーバーフローを折り返しとして定義)や-fsanitize=undefinedで先に確認します。
ビルドオプションがそのまま契約。配布するバイナリの-Oレベルを変えることは、コードを変えるのと同じ重さで扱う必要があります。同じソースでも、命令数が10倍変わり、未定義動作の結果が変わります。

次のラボですること

readasm.pyに、gccのアセンブリを関数ごとの命令リストに切り分けるパーサー、命令数と呼び出し一覧、定数1つに畳まれた関数の検出、除算のマジックナンバーの取り出し、後ろへ戻るジャンプ(ループの痕跡)の数え上げ、LLVM IRの関数ごとの命令と命令の種類の数え上げ、-O0と-O1のメモリ命令・φの比較を作ります。最後に、opt.cと、モジュール8で自分で作ったコード生成器のfibを並べて数え、レポートに残します。