命令選択 — 複数の命令を1つに畳む

今日のゴール

「アドレスを計算してから読む」という2命令を、RV64 が持つ offset(base) 形式のロード1命令に畳み込む。 fixed17 を通したまま、静的・動的の両方で命令数を減らす。

この回の位置づけ

項目	内容
必須の前提	コマ15（完成した `final/mycc.py`）、O1（測定基盤。`golden.py` が `measure.py` と `O1_measure/bench/` を使う）
推奨の前提	—
改変しない	`mycc.py`、`scaffold/`、`optcc.py`
編集する	`isel.py`
完了条件	`check.py` の全 Step が PASS になり、`golden.py` が `fixed17` 全通と静的・動的の命令数削減を報告する
コマ数	2
備考	最適化発展シリーズの第3回。O2・O4・O5 とは独立している。索引の一覧表では2コマぶんとしているが、O4・O6 と違って資料に明示の区切りは置いていない

optcc.py --passes isel が、isel.py をパスとして差し込む。

いまのコンパイラは何を出しているか

変数 s を読むたびに、コンパイラは2命令を出している。

  addi a0, s0, -24      # s のアドレスを計算して
  lw   a0, 0(a0)        # そのアドレスから読む

コマ3 以来の「codegen_lval でアドレスを作り、ld/lw で読む」という 2段構えの設計から、まっすぐ出てきた形である。素直だが、無駄がある。

RV64 のロード命令は、もともと offset(base) という形を持っている。

  lw   a0, -24(s0)      # 1命令で同じこと

addi が要らない。変数を読むたびに1命令減るので、効きが大きい。

命令選択とは

いま行ったのは、「この計算にはこの命令が使える」という対応づけである。これを命令選択（instruction selection）という。

「s0 から -24 の位置にある 4バイトを読む」という仕事
    → 素朴な割り当て: addi + lw    (2命令)
    → うまい割り当て: lw            (1命令)

同じ仕事に対して機械語の命令の選び方が複数あり、その中から良いものを選ぶ。 CPU が持つアドレッシングモードや複合命令を活かすほど命令数が減る。

この回で扱う3つの置き換えは次のとおり。

前	後	効くところ
`addi rD, rS, N` + `load rD, 0(rD)`	`load rD, N(rS)`	変数を読むたび
`addi rD, rS, N` + `store rV, 0(rD)`	`store rV, N(rS)`	変数へ書くとき
`li rC, 2ᵏ` + `mul rD, rX, rC`	`slli rD, rX, k`	ポインタ添字 `p[i]` の要素サイズ倍

3番目は、コマ9（ポインタ演算）で作った、p[i] のアドレス計算で添字に要素サイズを掛ける処理である。 int なら4倍なので、掛け算ではなく2ビット左シフトで済む。掛け算は加算やシフトより数倍遅い命令なので、これも意味がある。

畳んでよいか — 消えるレジスタに注意

1番目の置き換えは必ず安全である。畳む前も後も、rD には読み出した値が入る。

しかし2番目・3番目は違う。

  addi a1, s0, -16
  sw   a0, 0(a1)        # → sw a0, -16(s0) に畳むと、a1 に何も入らなくなる

a1 を後で誰かが読むなら、畳んではいけない。実際、畳んではいけない例がすぐ見つかる。

  addi sp, sp, -8       # スタックを確保して
  sd   a0, 0(sp)        # そこへ積む

この形は addi rD, rS, N + store rV, 0(rD) にぴったり当てはまる。しかし畳んで sd a0, -8(sp) にすると、sp が動かなくなる。積んだつもりの値は、次の push で上書きされて消える。

重要

パターンが一致することと、置き換えてよいことは別である。「その後でそのレジスタが使われるか」を確かめてから畳む。

そこで is_dead_after(lines, pos, reg) を作る。 pos の後ろを1行ずつ見て、

見つけたもの	判定
`reg` を読む命令	まだ使われている → 畳めない
`reg` に書く命令	読まれる前に上書きされた → 畳んでよい
ラベル・分岐・`call`	ここで基本ブロックが終わる → 判断できない（安全側で畳まない）

3行目が保守的なのがポイントである。ラベルの先は別の経路から来るかもしれないので、この単純な前向き走査では分からない。

補足

ここが O2・O5 につながる。 「ブロックを越えて、このレジスタが後で使われるか」を正しく知るには、フローグラフの上で生存変数解析を行う必要がある。それが O2（フローグラフ）と O5（生存解析）の主題である。

ただし、正確にすれば畳める場所が増える、とは限らない。実際に数えてみると、is_dead_after が「ブロック境界なので判断できない」と答えた回数は bench と fixed17 の全22本を通して 0回である。正確な生存解析を持ち込んでも、この3つの畳み込みが増える箇所は1つも無い。いまのコード生成が出す形では、たまたま「同じブロックの中で完結する」ものしか無いからである。

解析を正確にすることと、最適化が効くことは別 —— この数え上げは O6 の「正確な解析は畳み込みを増やすか」で行う。

実装

Step	実装対象	内容
1	`fold_load`	安全な畳み込み。まずこれだけで効果が出る
2	`is_dead_after`	「この後で使われないか」の判定
3	`fold_store` / `fold_mul_to_shift`	Step 2 を使って安全に畳む
4	`run`	変化がなくなるまで繰り返す（B1 と同じ）

reads_reg / writes_reg（命令がどのレジスタを読み書きするか）と正規表現はスケルトンで用意してある。

python3 ../optcc.py --passes isel ../O1_measure/bench/matmul.c | grep -c slli
python3 ../optcc.py --passes '' ../O1_measure/bench/matmul.c | grep -c "addi a0, s0"

テスト

python3 check.py     # 各置き換えの単体テスト(未実装は SKIP)
python3 golden.py    # fixed17 + ベンチマーク + 静的/動的の削減

check.py には「push の並びを畳まないこと」を確かめる項目がある。安全判定が働いていないと、ここで落ちる。

測ってみると

教員の実装では次のようになる。「前」は O1 の全構成の基準表の 素 列、「後」は +isel 列である。この回はその差分を作る。

ベンチマーク    静的:前   後   削減    動的:前      後   削減
bubble           340   301   11%     24023   20566   14%
fib_rec           77    73    5%     73993   69061    6%
loop_sum          70    65    7%      7840    7038   10%
matmul           453   411    9%     27958   24606   11%
strops           243   225    7%     77108   69066   10%
合計            1183  1075    9%    210922  190337    9%

合計だけを見ると静的9%減・動的9%減で同程度に見えるが、ベンチマークごとに見るとループが主体の bubble・loop_sum・matmul・strops はどれも動的削減が静的削減を上回る（bubble は静的11%に対し動的14%）。ループの中にある命令を消せているので、ループが支配的なベンチマークほど動的の効きが大きい。再帰呼び出しが主体でループが小さい fib_rec だけは静的5%・動的6%とどちらも小さいままである。 O1 で作った物差しが、ここで意味を持つ。

発展課題

B1 と組み合わせる: optcc.py --passes isel と B1 のピープホールを両方かけるとどうなるか。順番を変えると結果は変わるか
addi の畳み込み: li rC, N + add rD, rX, rC → addi rD, rX, N （N が12ビットに収まるとき）を追加する
除算のシフト化: li rC, 2ᵏ + div rD, rX, rC は srai にできるか。 負数のときに答えが変わるので注意（S2 で見た「0方向への切り捨て」）
非隣接の畳み込み: 代入 x = 式; では、アドレス計算と store の間に式の計算が入るので隣り合っていない。これを畳むには何が必要か
どの置き換えがいちばん効いたか: 3つを1つずつ無効にして測り、寄与を比べる

補足

コラム: 本物の命令選択は木の上で行う。 教科書（タイガーブック9章）の命令選択は、中間表現の木に対して「この形の部分木は、この1命令で実現できる」というタイルを敷き詰める（maximal munch や動的計画法）。今回は生成済みのアセンブリに対するパターン置換で同じ効果を出しているが、木の上で行えば「アドレス計算そのものを最初から作らない」ことができ、 is_dead_after のような後追いの安全確認も要らなくなる。中間表現を導入する動機の1つが、ここにある。

この資料の原稿を見る