mem2regを解説してみる

# はじめに

この記事は，まだmem2regのことを[ふんわりとしか理解していない](https://github.com/maekawatoshiki/cilk/blob/master/src/ir/mem2reg.rs)人が書いています．間違いの指摘などお待ちしております．
また，この記事内では解説にLLVM-IRの前提知識を必要とします．(``alloca``, ``load``, ``store``, use-def chain などが何なのかわかっていればOK.)

# mem2reg とは

**mem2reg**はLLVMのPassの一つで，可能な限りメモリアクセスをレジスタアクセスへと変換します．
LLVMのPassとは言いますが，単にメモリアクセスをレジスタアクセスへと変換する機構のことだと思っていただければOKです．

# mem2reg は大まかに何をするのか

ここからの解説は，主に[このあたりのコード](https://llvm.org/doxygen/PromoteMemoryToRegister_8cpp_source.html)に沿って進めていきます．

1. レジスタへと昇格できる alloca を集める.
    - どんなalloca? → ``load``, ``store``からのみアクセスされていて，アドレスの取得などに利用されていない.
    - 以降の``store``, ``load``はこれらのallocaを対象としたものとする

2. 簡単な場合を先に処理しておく
    - 一回しか``store``されていない場合
        - その``store src, dst``以降の``load dst``をすべて``src``で置き換えるだけ
    - 一つのBasic Block内でのみ``store``, ``load``されている場合
        - そのBasic Block内の``store``, ``load``を実行順に歩いていって，``load dst``ならその一つ前の``store src, dst``の``src``に置き換えるだけ

3. それぞれの``alloca``について，``store``されるBasic Block (以降 def block)，``load``されるBasic Block (以降 using block)を求め，これらを使い入口生存(live in)しているBasic Block(以降 livein block)を計算する
4. def blockの支配辺境に``phi``を挿入する．この時もlivein blockを使う．
5. プログラムの入口からBasic Blockを歩いていって，後続ブロックをたどりながらプログラムの出口にたどりつくまでに次のことを繰り返す．同じブロックをたどらないように注意．
    - ``store src, dst``にたどり着いたら，``src``を記録
    - ``load dst``にたどり着いたら，その参照(use)を記録された値と置き換え
    - ``phi``にたどり着いたら，記録された値をincoming nodeとして追加する． そして``phi``を記録 (これら``phi``への操作は同じブロックをたどって行うことがある)

6. 完成 (多分)

# ちょっと詳しく解説

上の章の 3. と 4. と 5. について詳しく見ていきます．

## 3. について

### 入口生存

あるブロックの入口で変数が生存していること．
def blockとusing blockを求めてあるので，using blockから前任ブロックをたどっていってdef blockにたどり着くまでのすべてのブロックがlivein blockとなる．

## 4. について

### 支配・支配木

> プログラムの入口からブロックB2に達するどの路も必ずブロックB1を通るとき，ブロックB1はブロックB2を**支配する(dominate)**という．ブロックBは自分自身を支配することになっている．
また，支配関係は反射的かつ推移的であり，木の形で書くことができることが知られている．この木では，親のブロックが子孫のブロックを支配する．この木を**支配木(dominator tree)**という．[^1]

画像で表すと次のようになる．

![Untitled Diagram-6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/69622/1163a159-67d6-60d4-df3a-a1f723dd42d9.png)

### 支配辺境

> ブロックiの支配辺境（dominance frontier）とは，制御フローグラフ上で，初めてiの支配関係から「はずれた」ブロックjのことである．[^1]

画像で表すと次のようになる．ブロックの右下に示したのが支配辺境．先ほどの画像の制御フローグラフを参考にしてください．

![Untitled Diagram-5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/69622/81e5c6a6-58e3-2fad-dff2-a7bfff493cb8.png)

支配辺境を求めるアルゴリズムにはいくつかありますが，LLVMは線形時間で解けるものを使っているようです[^2]．


### phi の挿入位置

phi を挿入するブロックは，あるdef blockの支配辺境であることが知られています[^1]．
とりあえず支配辺境の先頭に incoming node を持たない phi を挿入しておきましょう．

## 5. について

次のようなプログラムを考えます．

![Untitled Diagram-7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/69622/be8917af-f96a-ef69-20bf-18fba2e03565.png)

``4.``までの処理でphiが挿入されているので次のようになります．

![Untitled Diagram.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/69622/544e1cd3-1b52-8b55-98b6-04ca4035900e.png)

プログラムの先頭からBasic Blockを歩いていきます．以下の点に注意しながらGIFを見てみてください．

> - ``store src, dst``にたどり着いたら，``src``を記録
- ``load dst``にたどり着いたら，その参照(use)を記録された値と置き換え
- ``phi``にたどり着いたらincoming nodeとして記録された値を追加する. ``phi``を記録

![ezgif.com-gif-maker.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/69622/1edeb636-3815-972b-c2ce-6a33471352a9.gif)

(TODO: GIF内で, loadの参照を置き換えるのではなく, load自体を置き換えてしまっている. 近いうちに直します...)

ここまで来たら，あとは ``alloca``, ``store`` を削除してやれば完成です．(まあ途中で削除してもいいんですけどね)

# 最後に

この記事で紹介した手法で生成されるSSAはpruned SSAと呼ばれているようです．ほかにもSemi-pruned SSAなどがあり，まだあまりよく理解できていないので今後調べていきたい．

[^1]: [静的単一代入形式を用いた最適化（導入編）](https://www.jstage.jst.go.jp/article/jssst/25/1/25_1_1_19/_article/-char/ja/)  とってもわかりやすい．
[^2]: [A linear time algorithm for placing φ-nodes](https://dl.acm.org/doi/10.1145/199448.199464). 実際に[コード](https://llvm.org/doxygen/GenericIteratedDominanceFrontier_8h_source.html#l00131)を読むとわかりやすい．