gcc と clang の出力を数えて読む

目標

gccの-SアセンブリとclangのLLVM IRを、関数単位に切り分けて数えるツールreadasm.pyを作り、それで-O0と-O2(-O1)の違い、すなわちインライン化、定数畳み込み、除算の乗算への変換、末尾再帰のループへの変換、mem2regとφを、数字で確認します。

なぜ重要なのか

最適化が何をしたのかを知らないと、性能問題の前で推測しかできず、-O2でだけ起きるバグの前で、コンパイラーを疑うことになります。出力を直接読めば、どちらも確認できます。採点ツールは、定数や割る数を変えた変形のCを、採点するときに新しくコンパイルするので、自分のツールが規則どおりに読めて初めて通ります。

ルール

어셈블리(gcc -S)   맨 앞이 글자·_·. 인 'name:' 줄이 이름표. '.' 으로 시작하면 안쪽 이름표(.L3 등),
                   아니면 함수의 시작. 들여 쓴 줄 가운데 '.' 으로 시작하지 않는 것이 명령. # 뒤는 주석.
                   명령은 앞뒤 공백을 걷고 명령어와 피연산자 사이 공백을 하나로('movl\t$1, %eax' → 'movl $1, %eax')
functions(asm)     {함수: [명령…]} (이름표·지시어 제외) · count(asm, f) 는 그 수(endbr64 포함)
calls(asm, f)      call·callq 의 대상(나온 순서), '@PLT' 는 뗀다
returns_constant   endbr64 를 뺀 몸체가 [mov(l|q) $값, %eax|%rax ; ret] 이면 그 값, [xor %eax, %eax ; ret] 이면 0, 아니면 None
div_magic(asm, f)  f 안 첫 movabs(q) 의 즉시값을 부호 없는 64비트로 본 '0x' + 16자리 소문자 16진수, 없으면 None
back_edges(asm, f) f 안에서 앞서 나온 안쪽 이름표로 가는 j* 명령의 수
IR(clang -emit-llvm)  'define … @이름(' 부터 맨 앞의 '}' 까지. 이름표 줄('3:')·빈 줄 제외, ';' 뒤는 주석
opcode(명령)       '%5 = add nsw i64 …' → add · 'store …' → store · tail/musttail/notail 은 건너뛴다
opcode_counts      {opcode: 수} · ssa_summary(O0 IR, O1 IR, f) → {"O0": {alloca, load, store, phi}, "O1": {…}}

ステップ

/root/mini/readasm.pyのasm_lines(asm)とfunctions(asm)を埋めます。まず材料を作ってみてください。gcc -O0 -S -fno-asynchronous-unwind-tables /opt/fixtures/mini/real/opt.c -o opt-O0.s(-O2も)。
mnemonic・count・callsを埋めます。-O2でsquareの呼び出しが消えるかどうかが見えます。
returns_constantを埋めます。sum_to・always・neverが-O2で何に畳まれるかを確認します。
div_magicを埋めます。採点ツールは、割る数を変えた変形でも確かめます。
back_edgesを埋めます。factは、-O0ではcall、-O2ではループです。
ir_functions・opcode・opcode_countsを埋めます(clang -O0 -S -emit-llvm …、-O1も)。
ssa_summaryを埋めます。
/root/mini/real_report.jsonに、自分のreadasmで読んだ値を書きます。fib_O0・fib_O2(opt.cのfibの命令数)、fib_mini(モジュール8のコード生成器で作った/opt/fixtures/mini/programs/fib.miniのアセンブリのmini_f_fibの命令数。python3 mini.py asmで)、sum_to_O2、div10_magic、fact_O2_calls(呼び出しの数)、fact_O2_back_edges、fib_O1_phi(-O1のIRのfibのphiの数)です。

参考

コード生成器までのファイル(codegen.py、mini.py)は、ラボを開始するときに置かれています。
objdump -d --no-show-raw-insn opt.oで、焼いたあとの機械語も同じ形で見られます(このラボの採点は、-Sの出力で行います)。
よくある間違いは、ラベル(.L3:)を命令として数える、タブをそのままにして文字列が変わってしまう、マジックナンバーを符号付きの数で書く、すべてのジャンプをループと数える、IRのラベル行を命令として数える、の5つです。
ファイル名がreadasmである理由は、inspectがPythonの標準モジュール名なので、その名前で保存すると標準モジュールが隠れてしまうからです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

アセンブリを関数に切り分ける

行ごとに#以降を取り除き、行頭から始まる「name:」をラベルと見ます。「.」で始まるラベルは今の関数の内側のラベルで、そうでなければ新しい関数の始まりです。インデントされた行のうち「.」で始まらないものだけが命令で、split(None, 1)で空白を1つにまとめます。

命令数と呼び出し

countはfunctionsの結果の長さです(endbr64も命令です)。callsは、最初の単語がcallまたはcallqの命令の対象を集め、「@」以降を取り除きます。-O0と-O2で、sum_squaresの呼び出し一覧を比べてみてください。

定数1つに畳まれた関数

endbr64を除いた本体がちょうど2命令で、2つ目がretのときだけ見ます。最初の命令がmov(l|q) $値, %eax(または%rax)ならその値、xorで%eaxを自分自身と消せば0です。

除算の代わりに乗算: マジックナンバー

関数の命令を先頭から見て、movabs(またはmovabsq) $数, %レジスターを探します。gccは符号付きの10進数で書くので、2 ** 64で割った余りを取って符号なしの数にしてから、'0x%016x'で書きます。

再帰がループになったか

asm_linesで1つの関数の行を順に見ながら、ここまでに出てきた内側のラベルを集めます。jで始まる命令の対象がすでに出てきたラベルなら、後ろへ戻るジャンプです。-O2のfactでは、callが消えて、この数が現れます。

LLVM IRを関数に切り分ける

「define … @名前(」の行で関数を開き、行頭が「}」の行で閉じます。その間の行は、「;」以降を取り除き、空か「3:」のようなラベルなら除きます。opcodeは、「=」があればその後ろの最初の単語、tail・musttail・notailは飛ばします。

スタックの段がφになるのを数える

2つのIRで、それぞれopcode_countsを求めて、alloca・load・store・phiの4つだけを(なければ0で)取り出します。-O0のallocaが-O1で0になり、phiができることが、モジュール7で計算したφの位置の実物です。

gccと自分のコンパイラーを並べて

材料を作り直し(gcc -O0/-O2 -S、clang -O1 -emit-llvm、mini.py asm)、自分のreadasmの関数で8つの値を計算して書きます。数字を手で移さないでください。採点ツールが、同じコンパイラーでもう一度読んで突き合わせます。