Jicchoの箱

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

MENU

Reaching Definition

アルゴリズム コンパイラ 最適化

はじめに

この記事は，以前に私がQiitaに投稿した記事である． ふと，はてなブログにも残しておきたいと思ったので，移植する．

最適化とは

コンパイラは、フロントエンドで字句解析、構文解析などをして、バックエンドでCFG(Control Flow Graph、制御フローグラフ)作成、各種最適化、レジスタ割り付け、実行可能コードの出力などの処理を行います。 今回は、そのうちの最適化の話です。最適化とは、簡単に言ってしまえば、より早く、より効率的にプログラムが動作するように、しかも、プログラムの意味を変えずに、プログラムを変形しようということです。今までに、様々な最適化アルゴリズムが考案されています。

Reaching Definition

今回は、タイトルにもあるようにReaching Definitionの話をします。 これは、ある変数の定義がどこまで到達するのかといった情報をデータフローする解析手法です。

概要

例えば、以下のようなプログラムsample.cがあったとします。

void main(int x){
  int a,b,c,d;
  a = 1;
  b = 2;
  if(x < 10){
    a = 5;
  } else {
    b = 3;
    c = a + b;
  }
  d = a + b;
  return;
}

このような場合は、まず、c の値はコンパイル時に判明します。 なぜかというと、c = a + b;の命令には、aについては a = 1; だけ、bについては b = 3; だけの定義が到達するからです。よって、c の値は 1 + 3 だと判明します。 一方、d の値はコンパイル時にはわかりません。 それは、d = a + b; の命令には a,b についての定義が２つ以上到達するからです。 if文のtrue側が実行されたとすると、a = 5; b = 2; が到達し、false側が実行されたとすると、a = 1; b = 3; が到達します。 このように定義がどこにどれくらい到達するのか解析するのがReaching Definitionです。 さらに、上記の c の値のように、定義が一つだけ到達すると分かった時には、そこに値を伝播させることができます。これをConstant propagationと言います。

アルゴリズム

それでは、アルゴリズムの説明に入ります。 まず、CFGの各命令について、以下の表のようにgenとkillの計算をします。

Statement s gen[s] kill[s]
d1 : t ← a⊕b {d1} def(t) - {d1}
d2 : t ← Mem[x] {d2} def(t) - {d2}
d3 : t ← f() {d3} def(t) - {d3}

1行目は、何らかの計算をしてtに代入する場合、2行目はメモリからtに値をロードする場合、3行目は関数f()の返り値をtに代入する場合です。２列目は、命令sがあったとき、gen[s]に追加すべき要素です。ここで、d1やd2というのは、各命令につけた番号です。３列目は、命令sがあったとき、kill[s]に追加すべき要素です。ここで、def(t)とは、変数tを定義する全ての命令を表します。 表中にないようなメモリへのストア命令や条件分岐文などはgenとkillの計算には関与しません。

次に、inとoutの計算をします。ある命令nについてのinとoutは以下の数式で計算します。

in[n] = \cup_{p \in pred[n]}out[p] \\
out[n] = gen[n] \cup (in[n]-kill[n])

ここで、pred[n]はnの先行節を表します。上記の式を、すべての命令についてinとoutの変化がなくなるまで繰り返します。以下に、疑似コードを示します。

foreach n
  in[n] ← {}; 
  out[n] ← {}; 
endfor; 
do 
  foreach n 
    in2[n] ← in[n]; 
    out2[n] ← out[n]; 
    foreach p in pred[n]
      in[n] ← union(in[n],out[p]);
    endfor;
    out[n] ← union(gen[n],in[n]-kill[n]);
  endfor;
while in[n] = in2[n] and out[n] = out2[n] for all n;

inとoutは空集合で初期化します。また、union()関数は引数の和集合を計算する関数です。 これだけだと分かりずらいと思うので、先ほどのsample.cの場合で例を考えてみましょう。

1: a ← 1
2: b ← 2
3: if x < 10 goto L1 else goto L2
4: L1: a ← 5
5: goto L3
6: L2: b ← 3
7: c ← a + b
8: goto L3
9: L3: d ← a + b

まぁ、こんな感じに書けると思います。次に、gen、kill、in、outを計算すると以下のようになります。

n gen[n] kill[n] in[n] out[n]
1 1 4 1
2 2 6 1 1,2
3 1,2 1,2
4 4 1 1,2 2,4
5 2,4 2,4
6 6 2 1,2 1,6
7 7 1,6 1,6,7
8 1,6,7 1,6,7
9 9 1,2,4,6,7 1,2,4,6,7,9

表中の数字は、各命令の数字に対応しています。 ここで注目すべきなのは、n = 7 のときの in です。in[7] = {1,6}なので、１番と６番の定義が到達しているということです。つまり、7: c ← a + bは7: c ← 1 + 3と置き換えられるということになります。 さらに、定数畳み込み(Constant folding)を適用させれば、7: c ← 4となります。 一方、n = 9 のときに注目すると、９番の命令には定数伝播できないことがわかります。見てわかるように、in[9]には、aについての定義である1と4があり、bについての定義である2と6もありますね。これでは、コンパイル時にどちらの定義を選択すれば良いのかコンパイラは知ることができず、最適化できないということになります。

参考記事

Common Sub-expression Elimination
Dead Code Elimination
CFG，トポロジカルソート，Bit Vector，ワークリストアルゴリズム
Lazy Code Motion

Lazy Code Motion

コンパイラ 最適化 アルゴリズム Advent Calendar

この記事は，言語実装 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の特徴として，以下が挙げられます．

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

上記の特徴のうち，１の特徴について詳しく書くと長くなってしまうので割愛します． ２と３の特徴については，この記事を読んでいただければわかると思います．
以下，コンパイラの構成と最適化 (中田育男, 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の計算が終わったら，その結果を用いてプログラム変形をします．プログラム変形の基本方針としては，次のようになります．

  1. NCompを満たす節のt=a+bを削除
  2. NLatestを満たす節の最初にt=a+bを挿入
  3. 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)の手法のように，コードの複写を伴う手法を用いる必要があります． それらの手法は，冗長性を除去できるメリットがある反面，ちゃんとデメリットもあります． コード最適化はまだまだ奥が深いです．

終わりに

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

コンパイラのコード最適化や解析手法の論文のサーベイ

論文 サーベイ コンパイラ 最適化

この記事では，自分が最適化コンパイラの研究をする上で読んできた論文をまとめていこうと思う． まとめることで，自分のためにもなるだろうし，読んだ人のためにもなれたら嬉しい． 以下，随時更新．

部分冗長除去法(Partial Redundancy Elimination, PRE)

  1. Global Optimization by Suppression of Partial Redundancies (E. Morel and C. Renvoise, 1979, Communications of the ACM)
    PREが最初に提案された論文．式を前方に移動させることで，冗長性を除去する．ループ不変式のループ外移動も行うことができる．この手法では，式はできるだけ前方のプログラム点(earliest)に移動するので，レジスタ圧力(register pressure)が高まる．後に，この手法を改善した多くの手法が考案されている．

  2. The Value Flow Graph: A Program Representation for Optimal Program Transformations (B. Steffen, J. Knoop and O. Rüthing, 1990, ESOP)
    Value Flow Graph上で，データの流れを解析し，各プログラム点におけるHerbrand equivalenceを見つける手法．このアルゴリズムは任意のCFG上で動作し，字面は一致しないが，値は同じである式も検出できる．質問伝播のところで紹介しているGlobal Value Numbers and Redundant Computationsに対抗している．

  3. 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．１の手法を改善した手法．式をできるだけ後方のプログラム点に移動させることで，レジスタ圧力の増加を抑える．一般的に使われているPREである．まず最初に，データフロー方程式を用いて，下安全(down-safe)なプログラム点のうち最も早いプログラム点(earliest)を求める．次に，そのプログラム点から計算を遅らせることのできるプログラム点(Delay)を求める．最後に，これ以上遅らせることができない最も遅いプログラム点(Latest)を求め，そこに式を挿入する．データフロー方程式を解く際に，ワークリストアルゴリズムやビットベクトルを用いれば，高速に計算できる．しかし，LCMは字面が一致する式の冗長性しか解析できない．PREとコピー伝播を複数回適用することで，副次的効果(Second Order Effect)を反映させることができるが，コストが高い．さらに，データフロー方程式はループの繰返しを跨いだ冗長性を解析することができない．

  4. Effective Partial Redundancy Elimination(P. Briggs and K. D. Cooper, 1994, PLDI)

  5. Global Code Motion Global Value Numbering(C. Click, 1995, PLDI)

  6. Partial redundancy elimination driven by a cost-benefit analysis (R. N. Horspool and H. C. Ho, 1997, Israel Conference on Computer Systems and Software Engineering)
    エッジプロファイルを取り実行経路ごとの実行頻度を考慮して投機的なコード移動(speculative code motion)を行うPRE(Speculative PRE)を提案している．これによって，保守的なコード移動しか行わないLCMでは除去できない冗長性を除去でき，実行効率が改善する場合がある．論文内では，ベンチマークなどで効果を示していないが，是非とも見たかった．

  7. A new algorithm for partial redundancy elimination based on SSA form (F. Chow, S. Chan, R. Kennedy, S. Liu, R. Lo and P. Tu, 1997, PLDI),
    Partial redundancy elimination in SSA form (R. Kennedy, S. Chan, S. Liu, R. Lo, P. Tu and F. Chow, 1999, TOPLAS)
    静的単一代入形式(SSA Form)を使ったPREであるSSAPREを提案している論文．式の値を保持する変数に対するFactored Redundancy Graph (FRG)を作成し，FRG上でPREを行う．FRGは疎なグラフなので，解析コストが低く，PREが速く動作する．

  8. Path Profile Guided Partial Redundancy Elimination Using Speculation (R. Gupta, D. A. Berson and J. Z. Fang, 1998, ICCL)
    ４の手法と同様にCost-Benefit AnalysisとSpeculative PREを行うが，CFGのうちループとそうでない部分とで分けて考えている．また，Cost-Benefit Analysisに基づいたデータフロー方程式も提案している．この手法によって，ベンチマークプログラムがどれくらい速くなったという記述がなかったのが残念．

  9. Complete Removal of Redundant Expressions (R. Bodík, R. Gupta and M. L. Soffa, 1998, PLDI)
    コードサイズを増大させてしまう代わりに，式の冗長性を完全に除去する手法．LCMなどのPREは安全なコード移動しかしないので，除去することができない冗長性が存在する．その冗長性を除去するためには，投機的なコード移動が必要になる．投機的なコード移動は，プログラムの実行効率を低減させないように，通常はプロファイルを取って行うが，その分解析コストがかかる．一方で，この手法は投機的な式の挿入を，コードを複写することで，下安全な挿入にして行い，冗長性を除去する．しかし，何でもかんでも複写してしまうとコードサイズが増えすぎてしまうので，実用上はプログラムの一部にのみ適用することが想定されている．また，コードの複写は，CFGを既約(irreducible)にする可能性がある．コード最適化の中には，可約(reducible)なCFGにしか動作しないものも結構あるので，適用の際には注意が必要．

  10. Sparse code motion (O. Rüthing, J. Knoop and B. Steffen, 2000, POPL)
    略してSCM．LCMを拡張して疎な挿入点を見つける手法．まず式の最適な挿入点をLCMによって求めたあと，そこからさらに前のプログラム点に式を移動させることで，式の出現数を最小にするというコード移動を行う．レジスタ圧力は高まるが，コードサイズを小さくできる．down-safe，up-safe，earliestの述語を利用して，CFGを２部グラフに変換し，その２部グラフのマッチングを求めたりしている．かなりグラフ理論よりの内容．証明が載っているが正直難しい．

  11. E-path_PRE: partial redundancy elimination made easy(D. M. Dhamdhere, 2002, ACM SIGPLAN Notices, Vol. 37, No. 8, pp. 53-65)

  12. Optimal and Efficient Speculation-Based Partial Redundancy Elimination (Q. Cai and J. Xue, 2003 CGO),
    A lifetime optimal algorithm for speculative PRE (J. Xue and Q. Cai, 2006, TACO)
    プロファイル情報に基づいて投機的なPREを行うMCPREという手法を提案している．CFGに対して最大流問題を適用し，最小カット問題を解くことで，実行頻度が一番小さい経路を探している．TACO版の方では，一時変数の生存期間が短くなるように拡張している．

  13. Value-Based Partial Redundancy Elimination (T. VanDrunen and A. L. Hosking, 2004, CC)
    SSA形式上でGVNとPREを行うGVN-PREを提案している．字句形式が異なる式を，同じ値に写像し，その部分冗長性も除去することができる．コピー伝播を適用することなく，PREの副次的効果を反映させることができる．しかし，GVN-PREはPREとデータフロー方程式が異なるので，PREと同じ結果を得るためには，複数回の適用が必要である．

  14. An SSA-based algorithm for optimal speculative code motion under an execution profile(Zhou et al., 2011, PLDI)

部分無用コード除去 (Partial Dead Code Elimination, PDE)

  1. Partial Dead Code Elimination (J. Knoop, O. Rüthing and B. Steffen, 1994, PLDI)
    部分的に死んでいるコードを除去できるPartial Dead Code Elimination (PDE)を提案している論文．LCMと同じようにデータフロー方程式を用いて，死んでいる文とより後方に移動できる文を特定し，プログラムを変形する．文を後方に移動(sinking)→DCEという変形をすることで，副次的効果が多く得られる．最初は後方への移動ってどうやるんだろと思ったけど，LCMと同じようにDelayabilityを計算していて，なるほどと思った．Partial Faint Code Elimination (PFE)も提案している．これは，片方の文をDCEすれば，もう片方の式もDCEできるようになる副次的効果を，両方の文をfaint codeとして同時に考慮することで同時に除去できるようなfirst order effectを得られるようにしたもの．計算量は，bit-vectorアルゴリズムを使えば，PDEはO(n2)で，PFEはO(n3)となる．

  2. The Revival Transformation(L. Feigen et al., 1994, POPL)

  3. Partial Dead Code Elimination Using Slicing Transformations (R. Bodík and R. Gupta, 1997, PLDI)
    １の手法のように式の後方への移動を考えるのではなく，CFGをいくつかの領域に分割するプログラムスライシングと呼ばれる手法を使ってPDEを実現している．１の手法は式を後方に移動できないときにはPDEできないが，この手法はそのような場合でもPDEできる．代入文が生きている領域を表すために，Predicate Flow Graph (PFG)というグラフを定義している．この手法の計算コストは，プログラムサイズに対して指数関数的に増加する．

  4. Path Profile Guided Partial Dead Code Elimination Using Predication (R. Gupta, D. A. Berson and J. Z. Fang, 1997, PACT)
    CFG上のある経路がどのくらいの頻度で実行されるのかというプロファイル情報を元に，PDEを行う手法．実行頻度が高いところのdead codeを除去するために，実行頻度がより低いところに式を挿入する．これによって，安全性の観点から１の手法ではできなかったsinkingをできるようになるので，よりPDEできるようになる．PREのところで紹介しているPath Profile Guided Partial Redundancy Elimination Using Speculationの手法とノリは同じ．

  5. Region-Based Partial Dead Code Elimination on Predicated Code (Q. Cai, L. Gao and J. Xue, 2004, CC),
    Partial Dead Code Elimination on Predicated Code Regions (J. Xue, Q. Cai and L. Gao, 2006, Software-Practice and Experience)
    CFGをPredicate Partition Graph (PPG)というグラフに変換し，PPG上のSingle Entry Multiple Exit (SEME) region内でPDEを行う．実験結果では，結構良い結果が出ている．PPGの方の論文をよく読めていないので，それを読んでから戻って読みたい．

スカラ置換(Scalar Replacement)

  1. Improving register allocation for subscripted variables (D. Callahan, S. Carr and K. Kennedy, 1990, PLDI)
    スカラ置換が提案された論文．配列参照の依存関係を解析し，ループの繰返しに跨って値を再利用するために一時変数を導入し，次の繰返しの時に再利用することで，配列参照をレジスタ参照に置き換える．しかし，この手法は，一つの基本ブロックからなる最内ループの配列参照に対する冗長性しか解析できない．

  2. Scalar replacement in the presence of conditional control flow (S. Carr and K. Kennedy, 1994, Software: Practice and Experience)
    1の手法をPREを用いて拡張することで，スカラ置換が条件分岐を考慮することができるようにした手法．Carr-Kennedyアルゴリズムと呼ばれ，一般的なスカラ置換である．データフロー方程式が使われているので，分かりやすい．しかし，アルゴリズムのステップ数が多く，煩雑である．また，多重ループには対応していない．後に，多くの改善手法が提案されている．

  3. Increasing the Applicability of Scalar Replacement (B. So and M. Hall, 2004, CC)
    2の手法を多重ループ向けに拡張した手法．これも中々に難しい印象がある．

  4. Extending the Applicability of Scalar Replacement to Multiple Induction Variables (N. Baradaran, P. C. Diniz and J. Park, 2004, LCPC)
    2の手法を二つ以上の誘導変数でもスカラ置換できるように拡張した手法．これはまだあまり読めてない．

  5. Inter-Iteration Scalar Replacement in the Presence of Conditional Control-Flow (M. Budiu and S. C. Goldstein, 2004)
    2の手法を，実行時にメモリアクセスが最適になるようにコードを挿入するように拡張した手法．投機的な移動はしないので，プログラムの意味を変更することはない．実験結果を見ると確かに実行時にメモリアクセスが減ってはいるが，分岐命令はすごい増えてるんじゃ...？実行速度は遅くなったものもあるが，ほとんどのものは速くなっているらしい．ほんとかな？

  6. Redundancy Elimination Revisited (K. Cooper, J. Eckhardt and K. Kennedy, 2008, PACT)
    2の手法とGVNを組み合わせたEnhanced Scalar Replacementを提案した論文．字面は異なるが同じメモリ番地を参照する配列参照の冗長性を除去できる．しかし，可約なループにしか対応していない．

  7. Inter-iteration Scalar Replacement Using Array SSA Form (R. Surendran, R. Barik, J. Zhao and V. Sarkar, 2014, CC)
    array SSA形式を用いてスカラ置換を行う手法．最内ループから入れ子レベルごとに，配列参照の冗長性の解析を行い，その都度，入力プログラム上でプログラム変形を行う．プログラム変形を行う度にarray SSAを再構築する必要があるので，解析コストが高そう．

レジスタ促進(Register Promotion)

  1. A Practical Data Flow Framework for Array Reference Analysis and its Use in Optimizations (E. Duesterwald, R. Gupta and M. L. Soffa, 1993, PLDI)
    ループ中で，データ依存している式の依存距離(dependence distance)をデータフローする手法を提案している論文．データフロー解析っぽいが，ループの抽出が必要なので，入力プログラムの構造に大きく依存する．

  2. Register promotion in C programs (J. Lu and K. D. Cooper, 1997, PLDI)
    ポインタ解析を用いることで，メモリ参照をレジスタ参照に変更するレジスタ促進を提案している論文．メモリ参照をループ外に移動させたりして，レジスタ参照を多くしている．

  3. Register Promotion by Sparse Partial Redundancy Elimination of Loads and Stores (R. Lo, F. Chow, R. Kennedy, S. Liu and P. Tu, 1998, PLDI)
    SSAPREと投機的なコード移動を組み合わせたレジスタ促進を提案している論文．保守的な投機的移動とプロファイル駆動の投機的移動の２種類を提案している．

  4. Load-reuse analysis: design and evaluation (R. Bodík, R. Gupta and M. L. Soffa, 1999, PLDI)
    PREとGVNを組み合わせることで，字面が異なる式の冗長性と字面が異なるが同じメモリ番地を参照する命令を検出する手法を提案している論文．Value Name Graph (VNG)というグラフを作り，そのグラフ上で値番号に対するデータフロー方程式を解くことで，式の冗長性を除去している．

質問伝播(Question Propagation)

  1. Global Value Numbers and Redundant Computations (B. K. Rosen, M. N. Wegman and F. K. Zadeck, 1988, POPL)
    質問伝播(Question Propagation)と呼ばれる手法を提案した論文．SSA形式上で後ろ向きにクエリを伝播していくことで，冗長性を検査し，除去する手法．副次的効果を上手く反映できる．しかし，この手法は既約なCFGにしか適用できない．

  2. 質問伝播に基づく投機的部分冗長除去 (滝本宗宏, 2009, 情報処理学会論文誌 プログラミング)
    1の手法を任意のCFG上で動作するPREに拡張した手法．ループ不変式を投機的にループ外に巻き上げることによって，実行効率の向上を目指している．

  3. Demand-driven Partial Dead Code Elimination (M. Takimoto, 2012, IPSJ Transactions on Programming)
    質問伝播を用いてPDEを実現している論文．データフロー解析と比べて，質問伝播は速く動作することが実験結果でよく示されている．

  4. Effective Demand-driven Partial Redundancy Elimination (Y. Sumikawa and M. Takimoto, 2013, IPSJ Transactions on Programming)
    2の手法にSSAGVNを追加することで，字面が一致していなくても値の等価性を検査できるように拡張した手法．

  5. 質問伝播に基づく大域ロード命令集約 (澄川靖信, 滝本宗宏, 2013, 第54回プログラミング･シンポジウム)
    大域ロード命令集約（Global Load Instruction Aggregation, GLIA）を質問伝播で実現している．データフロー解析と比べてかなり速く解析できている．ただし，実行効率は変わらない．

  6. 要求駆動型スカラ置換 (澄川靖信, 小島量, 滝本宗宏, 2015, コンピュータソフトウェア, Vol.32, No.2, pp.93-113)
    4の手法をスカラ置換向けに拡張した手法．最初はよくできていると思ったが，アルゴリズムに間違いがあると思う．ある条件を満たした時に投機的に式を挿入するのだが，その条件が緩すぎて投機的な挿入が多くなってしまっている．下安全性のチェック方法を見直す必要がありそうだ．

演算子強度低減(Strength Reduction)

  1. A composite hoisting-strength reduction transformation for global program optimization part I (S. M. Joshi and D. M. Dhamdhere, 1982, International Journal of Computer Mathematics)
    A composite hoisting-strength reduction transformation for global program optimization part II (S. M. Joshi and D. M. Dhamdhere, 1982, International Journal of Computer Mathematics)
    演算子強度低減を大域的最適化として確立させた論文．PREの最初のアルゴリズム(Global Optimization by Suppression of Partial Redundancies)を元に作っているので，delayabilityは考えられていない．

  2. Efficient Code Motion and an Adaption to Strength Reduction (B. Steffen, J. Knoop and O. Rüthing, 1991, TAPSOFT)
    部分冗長除去のところで紹介しているThe Value Flow Graph: A Program Representation for Optimal Program Transformationsを演算子強度低減に応用している論文．

  3. Lazy Strength Reduction (J. Knoop, O. Rüthing and B. Steffen, 1993, Journal of Programming Languages)
    部分冗長除去のところで紹介しているLazy Code Motionを演算子強度低減に応用している論文．LCMと同様にLatestなプログラム点に式を挿入するので，レジスタプレッシャの増大を抑える．演算子強度低減用の述語を定義し，updateするための式(h = h+80みたいな式)の挿入点を決めている．あとはLCMと同じような議論なので，LCMを理解している人は読みやすい．

  4. Strength Reduction via SSAPRE (R. Kennedy et al., 1998, CC)
    タイトル通りSSAPREを演算子強度低減に応用した手法．

  5. Operator Strength Reduction (K. D. Cooper, L. T. Simpson and C. A. Vick, 2001, TOPLAS)
    SSA形式上で演算子強度低減：OSRを行う手法．F. E. Allen(Program Flow Analysis: Theory and Applications)のアルゴリズムを改良したらしい．sparse conditional constant propagationやlazy code motion，global reassociationを先に適用して，そのあとにOSRをやる．

  6. Strength Reduction of Integer Division and Modulo Operations (J. Sheldon, W. Lee, B. Greenwald and S. Amarasinghe, 2001, LCPC)
    タイトル通り，整数の割り算や剰余演算に対して演算子強度低減を行う．実験結果を見ると中々速くなっている．

ループ最適化(Loop Optimization)

  1. Collective Loop Fusion for Array Contraction(G. R. Gao et al., 1993, LCPC)

  2. Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution(K. Kennedy and K. S. McKinley, 1994, LCPC)

  3. Improving Data Locality with Loop Transformations(K. S. McKinley, S. Carr and C. Tseng, 1996, TOPLAS)

  4. A Parametrized Loop Fusion Algorithm for Improving Parallelism and Cache Locality(S. K. Singhai and K. S. McKinley, 1997, The Computer Journal)

  5. A Model for Fusion and Code Motion in an Automatic Parallelizing Compiler(U. Bondhugula et al., 2010, PACT)

手続き間最適化(Inter-procedural Optimization)

  1. Function merging by sequence alignment(R. C. O. Rocha et al., 2019, CGO)

  2. Effective function merging in the SSA form(R. C. O. Rocha et al., 2020, PLDI)

解析系

  1. Dependence graphs and compiler optimizations (D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure and M. Wolfe, 1981, POPL)
    ある式がどの式にデータ依存しているかを表す依存グラフ(Dependence Graph)を提案している論文．Loop Fusionなどのループに対する最適化も提案している．

  2. The program dependence graph and its use in optimization (J. Ferrante, K. J. Ottenstein and J. D. Warren, 1987, TOPLAS)
    データ依存と制御依存を両方表すProgram Dependence Graph (PDG)を提案している論文．PDG上で効率よく行える最適化の紹介もされている．

  3. Efficiently computing static single assignment form and the control dependence graph(R. Cytron et al., 1991, TOPLAS)

  4. How to Analyze Large Programs Efficiently and Informatively(D. M. Dhamdhere, B. K. Rosen and F. K. Zadeck, 1992, PLDI)

  5. The Program Structure Tree: Computing Control Regions in Linear Time (R. Johnson, D. Pearson and K. Pingali, 1994, PLDI)
    Single Entry Single Exit (SESE) regionを求めるための効率的なアルゴリズムを提案している論文．それぞれのSESE regionは，Program Structure Tree (PST)という木構造で表される．アルゴリズムも簡潔で，CFGの辺の数をEとすると，O(E)で動作する．素晴らしい．

  6. A Generalized Theory of Bit Vector Data Flow Analysis(U. P. Khedker and D. M. Dhamdhere, 1994, TOPLAS)

  7. A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis(E. Duesterwald, R. Gupta and M. L. Soffa, 1997, TOPLAS)

参考書籍

  1. コンパイラ 原理・技法・ツール (A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman)
    通称，ドラゴンブック．名著．理論的な内容が多め．

  2. 最新コンパイラ構成技法 (A. W. Appel)
    通称，タイガーブック．名著．関数型言語を使ってTiger言語を作るというストーリーになっていて，ドラゴンブックよりは実装の話が多い．

  3. コンパイラの構成と最適化 (中田育男)
    中田先生の本．結構広い範囲を扱っていて良い．

  4. Optimizing Compilers for Modern Architectures (R. Allen, K. Kennedy)
    依存解析に基づいた最適化やループ最適化などを扱っている本．良書だと思う．

  5. Building an Optimizing Compiler (R. Morgan)
    基本的な最適化のアルゴリズムが載っていて，かなり使える本．読みやすいので，おすすめ．ただ，有名だけど複雑なアルゴリズムは載っていなかったりするのが残念．

  6. Advanced Compiler Design and Implementation (S. S. Muchnick)
    かなり広い範囲を扱っているので，他の本に載ってないこともこの本には載っていることも多い．辞書的に使ってもいいかも．

  7. Principles of Program Analysis (F. Nielson, H. R. Nielson, C. Hankin)
    Nielson-Nielsonの本．タイトルの通り，プログラムの解析手法についての本．Data Flow Analysis, Constraint Based Analysis, Abstract Interpretationなど色々扱っている．