この記事は，言語実装 Advent Calendar 2020の11日目の記事です．前回はDrumatoさんのRust製のパーサコンビネータcombineを覗き見する(v4.4.0)，次回はalgon_320さんのELVM Scratch 3.0 backendです．
この記事では，コンパイラの代表的なコード最適化手法の一つであるLazy Code Motion (LCM)について説明します．何故LCMなのかというと，個人的に好きなアルゴリズムだからです．

概要

LCMは，部分冗長除去(Partial Redundancy Elimination, PRE)と呼ばれるコード最適化手法の一種です．
PRE自体は，Global Optimization by Suppression of Partial Redundancies (E. Morel and C. Renvoise, 1979, Communications of the ACM)の論文で提案されました． LCMはそれを拡張する形で，Lazy Code Motion (J. Knoop, O. Rüthing and B. Steffen, 1992, PLDI)の論文で提案されました．その後，Optimal code motion: theory and practice (J. Knoop, O. Rüthing and B. Steffen, 1994, TOPLAS)で拡張されています．
LCMの特徴として，以下が挙げられます．

任意の構造をもった入力プログラムを扱うことができる．
任意の実行経路に計算を増やすことのない安全なコード移動を行う．
レジスタ圧力を抑えるために，できるだけ遅いプログラム点に式を移動する．

上記の特徴のうち，１の特徴について詳しく書くと長くなってしまうので割愛します．２と３の特徴については，この記事を読んでいただければわかると思います．
以下，コンパイラの構成と最適化 (中田育男, 1999, 朝倉書店)をベースにLCMを解説します．

前提知識

この節では，この記事を読む上での前提知識を説明します．
まず，入力プログラムは関数ごとに，制御フローを節と辺で表した有向グラフである制御フローグラフG(Control Flow Graph, CFG)で表されているとします． Gは，節集合N，辺集合E，開始節s，終了節eを用いてG(N,E,s,e)とよく表されます．開始節sは，先行節を持たず，終了節eは後続節を持たない特別な節です．先行節とは，ある節の親の節集合で，節nの先行節を $pred(n) = \{ m | (m,n) \in E \}$ と表します．同様に，後続節は，ある節の子の節集合で，節nの後続節を $succ(n) = \{ m | (n,m) \in E \}$ と表します．

CFGのイメージとして，下の画像をご覧ください．左のようなmain関数は，右のようなCFGになります．この例でいうと， $pred(1) = \{ \textbf{s} \}$ で， $succ(1) = \{ 2, 3\}$ となります．

f:id:juln:20201207161139p:plain — CFGのイメージ

また，命令 $d=a+b$ に対して，aやbの値を変更する文( $a=1$ や $b=c - d$ など)を変更文といいます．さらに，節Bは基本ブロックを表していて，コンパイラの構成と最適化に則って，以下のように２つに分割することにします．その分け目は，B中の最後の変更文の直後で，分けたものの最初の方を入口部分，後ろの方を出口部分と呼びます．入口部分の最初の計算を入口計算と呼び，出口部分の計算を出口計算と呼びます．コード移動の際に，式を挿入する必要がありますが，そのときの挿入点は，入口計算や出口計算があるときはその直前，入口計算がなく変更文があるときは最初の変更文の直前，どちらもなければその部分の最後とします．

f:id:juln:20201207172239p:plain — 基本ブロックの分割

LCMの詳細

Step 1: 危険辺の除去(Eliminate critical edges)

危険辺(critical edge)とは，２つ以上の後続節をもつ節から２つ以上の先行節をもつ節への辺のことです．
例えば，下図(a)の節２から節３への辺は危険辺です．節３に部分冗長な式があると仮定すると，それをプログラムの前方（図でいうと上の方）に移動させることで部分冗長性を除去したいのですが，節３から節２には式を移動させることはできません．もし，節２に移動させてしまうと，節２の右側の後続節にも影響を及ぼしてしまいます．
このような危険辺は，下図(b)のように，辺上に新しく節を挿入することで除去することができます．

f:id:juln:20201204174654p:plain — Eliminate critical edge

Step 2: 局所的な情報の計算(Compute local information)

このステップでは，各節内で得られる情報を計算します．節B内で得られる情報は，以下の三種類あり，それぞれ条件を満たすときにtrue，満たさないときはfalseの値を取ります．

NComp(B): Bに入口計算がある．(初期値: false)
XComp(B): Bに出口計算がある．(初期値: false)
Transp(B): Bに変更文がない．(初期値: true)

それぞれの値は，以下のアルゴリズムで計算することができます．このアルゴリズムは，Building an Optimizing Compiler (R. Morgan, 1998, Digital Press)から引用し，少しアレンジしています．

 procedure Compute_Local(BasicBlock B)
  bool killed = false;
  bool available = false;
  bool anticipated = false;
  foreach Inst within B in execution order  do
    if Inst == Inst_orig then
      if !killed and !anticipated then
         anticipated = true;
         NComp(B) = true;
      endif;
      available = true;
    endif;

    if destination(Inst) within source(Inst_orig) then
      killed = true;
      available = false;
    endif;
  endfor;

  if available and killed then 
    XComp(B) = true;
  endif;
  
  if killed then
    Transp(B) = false;
  endif;
endprocedure Compute_Local;

以下，この記事では次のようなCFGを例に用います．

f:id:juln:20201211122539p:plain — LCMを適用する例

また，この記事では，冗長除去のターゲットとする式をa+bとし，a+bを右辺に持つ命令（d=a+bなど）はすべて同じ一時変数tを用いて，t=a+bとd=tに分解されているとします．このようにしておくと後から楽です．
なので，この例では，上記のアルゴリズム中のInst_origはt=a+bを，source(Inst_orig)は「{a,b}という集合」を表します．また，destination(Inst)は，命令Instの左辺を指します．例えば，Instがx=y+zという命令であるとき，destination(Inst)はxを表します．

上記のアルゴリズムは，基本ブロックBを引数に取り，B内の命令を上から順に見ていって，その命令が「t=a+bであるかどうか」と「式a+bに対する変更文かどうか」という処理をしています．その後，変更文が見つかる前にt=a+bを見つけたらNComp(B)をtrueに，変更文はあったが式がavailableであったらXCompをtrueに，変更文があったらTranspをfalseにしています．
上記の例のCFGでいうと，

NComp = {7, 11, 12}
XComp = {2}
!Transp = {2, 5}

となります．(ここで，三行目は，Transpがfalseの節を書いているので注意してください．)

Step 3: 下安全性の計算(Compute Down-safety)

各節内の情報を計算し終わったら，次は下安全性を計算します．
まず，下安全性って何でしょうか？式expに対する下安全性の定義は以下のようになっています．

プログラム点pでexpが下安全である $\Leftrightarrow$ pから $\textbf{e}$ までの全ての実行経路中にexpが存在し，かつ，その間にexpの変更文が存在しない．

つまり，式expに関して下安全なところでは，式expの計算結果は必ず同じ値になるということです．なので，ある下安全な点から別の下安全な点に式を移動させても（その２点間の全ての節が下安全である必要がある），プログラムの意味は変えることはありません．この「プログラムの意味を変えない」という意味で「安全」なのです． LCMを含むPREでは，そうやって式を移動できることに着目し，上手く式を移動することで，冗長性を除去することを試みます．
ここで，節Bの下安全性に関する述語を２つ，以下のように定義します．

NdSafe(B): Bの入口挿入点で下安全である．(初期値: true)
XdSafe(B): Bの出口挿入点で下安全である．(初期値: true)

そして，これらは次のデータフロー方程式を用いて計算することができます．

f:id:juln:20201211154245p:plain — dataflow equations for down-safety

このデータフロー方程式は，コンパイラバックエンド処理データフロー解析 : Reaching Definitionで説明したように，これ以上計算しても，全ての節のNdSafeとXdSafeが変化しなくなるまで繰り返して計算します．また，一つ一つ節を訪れながら計算していきますが，トポロジカルオーダーで訪問すると，効率よく計算できます．
先ほどの例のCFGで下安全性を計算すると，次のようになります．ここで，黒い逆三角がその場所で下安全であることを示しています．NdSafeとXdSafeを満たす節は，それぞれ次のようになっています．

NdSafe = {6, 7, 9, 10, 11, 12}
XdSafe = {2, 5, 6, 9, 10, 11}

f:id:juln:20201211130742p:plain — compute down-safety

Step 3: 上安全性の計算(Compute Up-safety)

下安全があれば，上安全もあります．下安全性と同様に，式expに対する上安全性の定義は以下のようになっています．

プログラム点pでexpが上安全である $\Leftrightarrow$ $\textbf{s}$ からpまでの全ての実行経路中にexpが存在し，かつ，その間にexpの変更文が存在しない．

上安全性は下安全性の考え方を逆にしただけです．上安全性は，上安全な点ではプログラムの前方で既に計算した値がそのまま使えるということを表しています．なので，上安全な点に式を挿入してしまうと，それは冗長となってしまうので，そういうコード移動はしないようにします．余談ですが，共通部分式除去(Common Sub-expression Elimination, CSE)は，この上安全性を計算することで，共通部分式を見つけているとの見方もできます．
ここで，下安全性と同様に，節Bの上安全性に関する述語を２つ，以下のように定義します．

NuSafe(B): Bの入口挿入点で上安全である．(初期値: true)
XuSafe(B): Bの出口挿入点で上安全である．(初期値: true)

これらも同じように，次のデータフロー方程式を用いて計算することができます．下安全性の計算と同じように，全ての節のNuSafeとXuSafeが変化しなくなるまで繰り返し計算します．

f:id:juln:20201211154504p:plain — dataflow equations for up-safety

例のCFGで計算すると，次のようになります．ここで，黒い三角がその場所で上安全であることを示しています．NuSafeとXuSafeを満たす節は，それぞれ次のようになっています．

NuSafe = {6, 8, 13}
XuSafe = {2, 6, 7, 8, 11, 12, 13}

f:id:juln:20201211132436p:plain — compute up-safety

Step 4: 最早点の計算(Compute Earliest)

次に，最早点(earliest)を計算します．Earliestとは，下安全性を満たし，かつ，できるだけ開始節 $\textbf{s}$ に近い場所のことを言います．
節BのEarliestに関する述語を２つ，以下のように定義します．

NEarliest(B): Bの入口挿入点で下安全である，かつ，Bのいずれかの先行節は安全でない．(初期値: false)
XEarliest(B): Bの出口挿入点で下安全である，かつ，Bの入口挿入点は安全ではない．(初期値: false)

Earliestは，次の式で計算できます．この式は，繰り返して計算する必要はありません．

f:id:juln:20201211154614p:plain — dataflow equations for earliest

例のCFGで，Earliestを計算すると，以下のようになります．黒い四角がある場所が，Earliestを満たします．NEarliestとXEarliestを満たす節は，それぞれ次のようになっています．

NEarliest = {9}
XEarliest = {2, 5}

f:id:juln:20201211134347p:plain — compute earliest

このEarliestで示すプログラム点に式を挿入しても，式の冗長性を安全に除去することができます．最初に紹介したGlobal Optimization by Suppression of Partial Redundanciesの論文では，このEarliestで示す点に式を挿入するPREです．
ここで，冗長除去のために使っている一時変数 t は，レジスタに割り付けられることが前提となっています．あまり式を前に移動させすぎると，レジスタが足りなくなって，スピルが発生してしまい，プログラムの実行速度が遅くなってしまう問題があります．これをレジスタ圧力が増大するといいます．
そこで，このEarliestのプログラム点から，もっと式を遅らせることができる(CFGでいうと，もっと下の方で計算する)プログラム点を計算できれば，レジスタ圧力を抑えることができると考えて編み出されたのが，このLCMです．

Step 5: 式を遅らせることができる点の計算(Compute Delayed)

ということで，Earliestのプログラム点から，もっと式を遅らせることができるプログラム点Delayedを計算します．お決まりのように，節BのDelayedに関する述語を２つ，以下のように定義します．

NDelayed(B): Bの入口挿入点まで計算を遅らせることができる．(初期値: true)
XDelayed(B): Bの出口挿入点まで計算を遅らせることができる．(初期値: true)

これらは，次のデータフロー方程式を用いて計算することができます．これも下安全性の計算と同じように，全ての節のNDelayedとXDelayedが変化しなくなるまで繰り返し計算します．

f:id:juln:20201211160021p:plain — dataflow equations for delayed

例のCFGで，Delayedを計算すると，以下のようになります．黒い丸がある場所が，Delayedを満たします．NDelayedとXDelayedを満たす節は，それぞれ次のようになっています．

NDelayed = {9, 10, 11}
XDelayed = {2, 5, 9, 10}

f:id:juln:20201211140408p:plain — compute delayed

Delayedが示すプログラム点を見てみると，{6, 7}節で形成しているループ中には遅らせることができないことがわかります．これによって，ループ不変式のループ外移動をすることができるんですね．

Step 6: 最遅点の計算(Compute Latest)

最後に，遅らせることができる点の中で，最も遅い点Latestを計算します．
節BのLatestに関する述語を２つ，以下のように定義します．

NLatest(B): Bの入口挿入点まで計算を遅らせることができるが，これ以上は遅らせることができない．(初期値: false)
XLatest(B): Bの出口挿入点まで計算を遅らせることができるが，Bの後続節には遅らせることができない．(初期値: false)

これらは，次のデータフロー方程式を用いて計算することができます．この式は，繰り返して計算する必要はありません．

f:id:juln:20201211160114p:plain — dataflow equations for latest

例で，Latestを計算すると，次のようになります．星マークがある場所が，Latestを満たします．NLatestとXLatestを満たす節は，それぞれ次のようになっています．

NLatest = {11}
XLatest = {2, 5, 10}

f:id:juln:20201211141937p:plain — compute latest

Latestが示すプログラム点を見てみると，Earliestのときより，計算が遅くなっているところがあるのがわかります(節9 $\rightarrow$ 節10, 11)．この例のCFGは小さいので，そこまで差がありませんが，大きなプログラムになると無視できないほどの差があることがあります．レジスタ圧力はLCMを使ってできるだけ抑えてあげましょう．

Step 7: プログラム変形(Program transformation)

Latestの計算が終わったら，その結果を用いてプログラム変形をします．プログラム変形の基本方針としては，次のようになります．

NCompを満たす節のt=a+bを削除
NLatestを満たす節の最初にt=a+bを挿入
XLatestを満たし，XCompでない節の最後にt=a+bを挿入

以下のアルゴリズムでプログラム変形をすることができます．このアルゴリズムは，Building an Optimizing Compiler (R. Morgan, 1998, Digital Press)から引用しています．

procedure transform(ControlFlowGraph G)
  foreach n in G do
    if NComp(n) then 
      delete the first instruction "t=a+b" from n
    endif;

    if NLatest(n) do
      insert "t=a+b" into the first of n
    endif;

    if XLatest(n) and !XComp(n) do
      insert "t=a+b" into at the end of n
    endif;
  endfor;
endprocedure transfrom;

このアルゴリズムによって，例にLCMを適用すると，次のようなCFGが得られます．赤くハイライトした命令が，LCMによって挿入された命令です．
LCM前後を見比べてみると，節６，７のループ中のループ不変式が節５に移動していて，節１１と１２のところの部分冗長性が除去されています．

f:id:juln:20201211143107p:plain — before and after applying LCM

しかし，これを見てわかるように，LCMは全ての部分冗長性を除去できるわけではありません．例えば，( $\textbf{s}$ , 1, 2, 4, 9, 10, 12, 13, $\textbf{e}$ )の実行経路における冗長性は，除去できていませんね．
LCMは，下安全性を満たす節にだけ式を挿入するので，任意の実行経路に新しく計算を導入することはありません．例えば，節３にt=a+bを挿入することで，節11と12の式を全冗長にして削除することができますが，LCMはこれを行いません．なぜなら，( $\textbf{s}$ , 1, 3, 4, 5, ...)の実行経路に，本来行われなかった計算を新しく挿入してしまうことになるからです．
このような，任意の実行経路に新しく計算を導入するコード移動を投機的なコード移動といいます． LCMで除去できない冗長性を除去するためには，LCMのような安全なコード移動ではなく，投機的なコード移動や，Complete Removal of Redundant Expressions (R. Bodík, R. Gupta and M. L. Soffa, 1998, PLDI)の手法のように，コードの複写を伴う手法を用いる必要があります．それらの手法は，冗長性を除去できるメリットがある反面，ちゃんとデメリットもあります．コード最適化はまだまだ奥が深いです．

終わりに

いかがだったでしょうか．少しはコードモーションの世界が垣間見えたでしょうか．コード最適化ってこんな感じなんだ～と感覚的には掴めたでしょうか．
もっとコンパイラの沼に，そして，コード最適化の沼に落ちてしまう人が増えることを願っています．

Jicchoの箱

コンピュータサイエンス，特にコンパイラの話が多め．

Lazy Code Motion

概要