Jicchoの箱

情報系大学院生の備忘録.コンピュータサイエンス,特にコンパイラの話が多め.

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

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

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

  3. 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では除去できない冗長性を除去でき,実行効率が改善する場合がある.論文内では,ベンチマークなどで効果を示していないが,是非とも見たかった.

  4. 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が速く動作する.

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

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

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

  8. 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版の方では,一時変数の生存期間が短くなるように拡張している.

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

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

  2. Partial Dead Code Elimination Using Slicing Transformations (R. Bodík and R. Gupta, 1997, PLDI)

  3. Path Profile Guided Partial Dead Code Elimination Using Predication (R. Gupta, D. A. Berson and J. Z. Fang, 1997, PACT)

  4. 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)

スカラ置換(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と投機的なコード移動を組み合わせたレジスタ促進を提案している論文.保守的な投機的移動とプロファイル駆動の投機的移動の2種類を提案している.

  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)

  2. 質問伝播に基づく投機的部分冗長除去 (滝本宗宏, 2009, 情報処理学会論文誌 プログラミング)

  3. Demand-driven Partial Dead Code Elimination (M. Takimoto, 2012, IPSJ Transactions on Programming)

  4. Effective Demand-driven Partial Redundancy Elimination (Y. Sumikawa and M. Takimoto, 2013, IPSJ Transactions on Programming)

  5. 質問伝播に基づく大域ロード命令集約 (澄川靖信, 滝本宗宏, 2013, 第54回プログラミング・シンポジウム)

  6. 要求駆動型スカラ置換 (澄川靖信, 小島量, 滝本宗宏, 2015, コンピュータソフトウェア, Vol.32, No.2, pp.93-113)

解析系

  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. 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)という木構造で表される.アルゴリズムも簡潔で,線形時間で動作する.素晴らしい.

参考書籍

  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など色々扱っている.

各学会の締め切りなどのまとめ

この記事は,各学会の開催時期や締め切りをまとめた備忘録記事である.

国内学会

  1. 情報処理学会 プログラミング研究会 PRO
    開催時期は,6,7,10,1,3月.それぞれ約2ヶ月前に発表申し込みを行い,約一ヶ月前に論文を投稿する.投稿論文は発表会後にアクセプトされれば,情報処理学会論文誌 プログラミングに掲載される.論文投稿をしないで,発表だけ行うということもできる.英語論文で投稿しアクセプトされるか,日本語論文をアクセプト後に英語論文にすることで,Journal of Information Processing (JIP)に掲載できる.JIPはオープンアクセスで,dblpにも載る.

  2. 日本ソフトウェア科学会 大会
    開催時期は,8月下旬〜9月上旬.登壇発表申し込み締め切りは7月で,講演論文やポスターの締め切りは8月.参加したことないので,次は参加したい.

  3. プログラミングおよびプログラミング言語ワークショップ PPL
    開催時期は3月上旬.カテゴリ1(国内外未発表論文)の発表申し込みは12月下旬,論文提出は1月上旬.カテゴリ2(国外既発表論文)の発表申し込みは1月下旬.カテゴリ3(ポスターなど)の発表申し込みは2月上旬.例年,合宿形式で温泉に行く.ポスターセッションは,お酒がOKなのでわいわいと盛り上がる.

  4. プログラミング・シンポジウム
    開催時期は1月上旬.発表申し込み締め切りが11月で,論文の提出締め切りがその3週間後くらい.これも例年,合宿形式で温泉に行く.

国際学会

とりあえず,列挙する.

  1. Programming Language Design and Implementation, PLDI
    開催時期は6月.提出時期は11月下旬.

  2. Principles of Programming Languages, POPL
    開催時期は1月.提出時期は7月.

  3. Parallel Architectures and Compilation Techniques, PACT
    開催時期は10月.提出時期は4月.

  4. Code Generation and Optimization, CGO
    開催時期は2月.提出時期は8月.

  5. Compiler Construction, CC
    開催時期は2月.提出時期は11月.CGOの併設カンファレンス.

  6. Asian Symposium on Programming Languages and Systems, APLAS
    開催時期は12月.提出時期は6月.

  7. ECOOP
    開催時期は7月.提出時期は1月.

  8. Languages and Compilers for Parallel Computing, LCPC
    開催時期は10月.提出時期は7月.

CFG,トポロジカルソート,Bit Vector,ワークリストアルゴリズム

はじめに

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

Control Flow Graph(CFG)

CFGとは、基本ブロック(basic block)をノードとするグラフのこと。 まず、基本ブロックとは何かというところから説明したいと思います。

基本ブロック(basic block)

ある命令 n が唯一の先行節 p を持ち、また p の唯一の後続節が n であるとき、p と n の gen、kill、in、out を合わせて考えることができ、p と n を一つのノードにまとめることができます。 これが、基本ブロックの根底にある考え方です。基本ブロックは、次の定義を満たします。

  1. 基本ブロック内の最初の命令は、ラベル付きである。
  2. 基本ブロック内の最後の命令は、無条件ジャンプ、または条件付きジャンプである。
  3. 基本ブロック内のその他の命令は、ラベル付き、無条件ジャンプ、条件付きジャンプのどれでもない。

つまり、基本ブロックの途中では、どこかに分岐することもなく、どこかから合流することもないということです。また、この定義より、基本ブロック内の最初と最後の命令以外は、常に唯一の先行節と唯一の後続節を持ちます。よって、基本ブロックを1単位として、gen、kill、in、out の計算をすることができます。 簡単な場合として、命令 n が唯一の先行節 p を持ち、p の唯一の後続節が n であるときを考えてみます。 f:id:juln:20210113145522j:plain

上の図みたいなのを想像してください。 外側の赤い枠が、p と n を合わせてできた基本ブロックだとします。その基本ブロックの in と out を、in[pn]、out[pn] とします。すると、見てわかるように、in[pn] は in[p] と等しく、同様に、out[pn] は out[n] と等しくなります。また、p と n はお互いが唯一の先行節、後続節の関係なので、out[p] と in[n] も等しくなります。 ここで、Reaching Definitionのデータフロー方程式を考えてみましょう。out[n]は以下のように書けます。

out[n] = gen[n] \cup (in[n] - kill[n])

in[n] = out[p] より、

out[n] = gen[n] \cup ((gen[p] \cup (in[p] - kill[p])) - kill[n])

これを少し整理してみると、

out[n] = (gen[n] \cup (gen[p] - kill[n])) \cup (in[p] - (kill[p] \cup kill[n]))

このように書けます。 これはつまり、この p と n を合わせてできた基本ブロックの gen[pn] と kill[pn] が次のように書けることを意味しています。

gen[pn] = gen[n] \cup (gen[p] - kill[n]) 
kill[pn] = kill[p] \cup kill[n]

よって、out[n] = out[pn]、in[p] = in[pn] なので、次の式が得られます。

out[pn] = gen[pn] \cup (in[pn] - kill[pn])

この out[pn] が、 p と n を合わせてできた基本ブロックの out の値です。これで一つの命令単位でなく、一つの基本ブロック単位で in と out を計算することができます。 このようにして、基本ブロック単位でデータフロー方程式を解くことで、より高速に解を得ることができます。

基本ブロックのトポロジカルソート

トポロジカルソートとは、グラフ理論におけるノードの順序付け方法の一つです。 これをCFGに対して適用すると、あるノードが実行されるとき、そのノードのすべての先行節が実行されているように、ノードを順序付けすることができます。 例えば、次のようなCFGがあったとします。 f:id:juln:20210113145839j:plain

各ブロックの左側の黒い数字は、このCFG内のそのブロックの固有の番号(basic block id)です。このCFGにトポロジカルソートを適用させると、ブロックを辿る順序は、各ブロックの右側の赤い数字の順番になります。上の図を見ると、あるブロックに到達したときには、そのブロックの全ての先行節がすでに訪問されている状態になっていることがわかると思います。 トポロジカルソートを求めるアルゴリズムは色々あるらしいですが、ここでは深さ優先探索(depth first search)を用いた方法を紹介します。

function DFS(n):
  if visited[n] = false
    visited[n] ← true;
    foreach s in succ[n]
      DFS(s);
    endfor;
    topo_sorted[N] ← n;
    N ← N - 1;
  endif;
endfunction;

procedure Topological_Sort:
  N ← the number of nodes
  foreach n : 0 to N
    visited[n] ← false;
  endfor;
  DFS(entry_node);
endprocedure

Topological_Sort手続きが終わったときに、topo_sorted配列に格納されているのがトポロジカルソートされたブロックの順序です。 Reaching DefinitionやAvailable expressionsなどは、先行節のoutの情報を用いてinを計算するforward analysisなので、全ての先行節がすでに訪問され、outが計算されていれば、効率よくデータフロー解析を行うことができます。なので、forward analysisでは、このトポロジカルソートした順序でブロックを訪問します。 また、Liveness analysisなどのbackward analysisは、逆に後続節のinの情報を用いてoutを計算するので、トポロジカルソートの逆順でブロックを辿る必要があります。逆トポロジカルソートは、上記のアルゴリズムで、entry_nodeではなくexit_nodeからDFSを適用し、DFS関数内で後続節の代わりに先行節へのエッジを辿ることで得られます。

Bit Vector

データフロー解析では、フローされているデータは何らかの集合です。それは、一つの命令だったり、変数だったりしますが、そのような有限集合は、Bit Vectorで表すことができます。 Bit Vectorで表すと何がうれしいかというと、集合のAND演算やOR演算を高速に処理することができるようになります。

Reaching Definitionでの例を考えてみます。

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
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

このような例を考えてみたとき、例えば、9番のノードの in は、5と8番のノードの out の和集合で表されます。これをBit Vectorで表してみると、

1 2 4 6 7
out[5] 0 1 1 0 0
out[8] 1 0 0 1 1
in[9] 1 1 1 1 1

このようになります。out[5]は2と4番の命令に対してビットが立っていることを表し、同様にout[8]は1と6と7番の命令に対してビットが立っていることを表しています。

in[9] = out[5] \cup out[8]

であるので、上の表を見ても分かるように、ビットのOR演算をした結果が、in[9]に格納されます。 逆に、積集合を計算したいときは、ビットのAND演算をすれば良いのです。 このように集合をビット演算で計算できるので、より高速にデータフロー解析をすることができるようになります。

ワークリストアルゴリズム

これは、データフロー方程式を再計算しなければならないところだけ、再計算するというアルゴリズムです。例えば、Reaching Definitionのアルゴリズムはこのように書けるのでした。

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集合が変更されると、また全ての命令についてループを回し、再計算していました。これだと、再計算する必要のないところまで再計算していて、非効率です。そこで、再計算されるべきところだけワークリストに保存して、再計算するというのがこのアルゴリズムです。 Reaching Definitionのワークリストアルゴリズムは、以下のように書くことができます。

worklist ← set of all nodes;
while worklist ≠ empty
  pop n from worklist;
  old_out ← out[n];
  foreach p in pred[n]
      in ← union(in,out[p]);
  endfor;
  out[n] ← union(gen[n],in-kill[n]);
  if old_out ≠ out[n]
    foreach s in succ[n]
      if s ∉ worklist
        push s into worklist;
      endif;
    endfor;
  endif;
endwhile;

ループのないCFGならトポロジカルソート順に基本ブロックを訪問すれば、全ブロックの計算は2回で済みますが、ほとんどのプログラムはループを含んでいます。ループがあると、全ブロックの再計算が何回も行われることもあり、非効率的です。しかし、このワークリストアルゴリズムでは、再計算はループの中だけに留まるので、より効率的にデータフロー方程式の解を得ることができます。

参考記事

Reaching Definition
Common Sub-expression Elimination
Dead Code Elimination

Lazy Code Motion

Dead Code Elimination(無用コード除去, DCE)

はじめに

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

Liveness analysis

そのまま日本語に訳すと、生存解析。ある変数の定義がプログラムのどこで使われるのか解析する手法です。 これによって、無用コード除去(Dead Code Elimination, DCE)ができるようになります。

概要

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

void main(int v){
  int a,b,x;
  a = 1;
  b = 2;

  if(v < a){
    x = a + b;
  } else {
    a = 10;
    b = 5;
  }
  a = 100;
  x = a * b;
  b = 20;
}

このような場合は、if文のfalse側の a = 10; で格納された a の値は使われないです。また、最後の b = 20; の b の値もその後使われません。 そのような使われない値はレジスタに保存しておくのも無駄であるので、命令を削除してしまおうというのがDead Code Eliminationです。

アルゴリズム

それでは、アルゴリズムの説明に入ります。 genとkillの計算表は以下のようになってます。

Statement s gen[s] kill[s]
t ← a ⊕ b {a, b} {t}
t ← Mem[a] {a} {t}
Mem[a] ← b {b} {}
if a < b goto L1 else goto L2 {a, b} {}
f(a,b) {a, b} {}
t ← f(a,b) {a, b} {t}

これは、それぞれ以下のような場合です。

1行目:何らかの計算をして、tに代入する場合。 2行目:aの場所のメモリの値を、tにロードする場合。 3行目:aの場所のメモリに、bの値をストアする場合。 4行目:何らかの条件を判定して、指定した場所へジャンプする条件分岐。 5行目:関数f()を、引数 a と b で呼び出す場合。 6行目:関数f()を引数 a と b で呼び出し、その返り値をtに代入する場合。

次に、inとoutの計算式を示します。

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

ここで、succ[n]はnの後続節を表します。このLiveness analysisは、Reaching DefinitionやAvailable expressionsと違い、プログラムの実行順とは逆順でデータフロー解析をしていきます。この逆順の解析をbackward dataflow analysisと言います。 上記の式を、すべての命令についてinとoutの変化がなくなるまで繰り返します。以下に、疑似コードを示します。

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

まず、inとoutは空集合で初期化します。そのあと、データフロー方程式に沿って各inとoutを計算していきます。ここで、気を付けなければならないのが、バックワード解析では、outの方から計算します。また、union関数は引数の和集合を計算する関数です。 では、先のsample.cで例を考えてみましょう。

1: a ← 1
2: b ← 2
3: if v < a goto L1 else goto L2
4: L1: x ← a + b
5 goto L3
6: L2: a ← 10
7: b ← 5
8: goto L3
9: L3: a ← 100
10: x ← a * b
11: b ← 20

次に、gen、kill、in、outを計算すると以下のようになります。

n gen[n] kill[n] in[n] out[n]
1 {a} {v} {a, v}
2 {b} {a, v} {a, b, v}
3 {a, v} {a, b, v} {a, b}
4 {a, b} {x} {a, b} {b}
5 {b} {b}
6 {a}
7 {b} {b}
8 {b} {b}
9 {a} {b} {a, b}
10 {a, b} {x} {a, b}
11 {b}

バックワード解析なので、11番のノードのoutから計算していきます。 ここで、注目すべきなのは、6番のノードのoutです。6番のノードでは、a ← 10 という操作をしていますが、out[6]に a がないので、その値は今後使われないということがわかります。同様に、11番のノードにも注目してみると、out[11]には b が含まれないので、この b の値は今後使われないということがわかります。 使われないなら無駄なので削除してしまいましょうということで、sample.cをDCEしてみると以下のようになります。

void main(int v){
  int a,b,x;
  a = 1;
  b = 2;

  if(v < a){
    x = a + b;
  } else {
    b = 5;
  }
  a = 100;
  x = a * b;

sample2.cでは、無駄な命令が省かれて最適化されました。

DCEの注意点

sample.cは簡単なプログラムだったので、この値は使われない ⇒ よし、消してしまおう! というようにできたのですが、いつでもこのようにできるとは限りません。 DCEで考慮しなければならない場合は、例外処理を発生させる可能性のある命令がある場合です。 普通の計算でもオーバーフローすると例外が発生する場合がありますし、0除算も例外が発生する場合がありますね。 そういった命令を安易に削除してしまうと、プログラムの意味が変わってしまう場合があります。最適化は、プログラムの意味を変えない範囲で行われるべきであるので、こういった場合は注意が必要です。

参考記事

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

Common Sub-expression Elimination(共通部分式削除,CSE)

はじめに

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

Available expressions

日本語に訳すと、利用可能な式。つまり、プログラム中のあるポイントで利用可能である式があるかどうか解析する手法です。 Available expressionsを解析することによって、Common Sub-expression Elimination(共通部分式削除、CSE)ができるようになります。

概要

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

void main(int a, int b){
  int x,y,z;

  x = a + b;
  if(a < 5){
    y = a + b;
  } else {
    a = 10;
    x = a - b;
  }
  z = a + b;
  return;
}

このような場合は、見てわかるように、a + b の値が2回計算されてしまっていて無駄です。 if文のtrue側のy = a + b; の命令を実行するときには、すでに a + b の値を一回計算していて、しかもその値をそのまま使えるので、使ってしまったほうが計算回数が少なくすみます。 しかし、if文を抜けたあとの z = a + b; では、以前に計算した a + b の値は利用することができません。これは、if文のfalse側で、a の値を変更しているからです。 Available expressionsでは、一時変数 t1,t2 を導入して、次のように変形します。

void main(int a, int b){
  int x,y,z;
  int t1,t2;

  t1 = a + b;
  x = t1;
  if(a < 5){
    t1 = a + b;
    y = t1;
  } else {
    a = 10;
    t2 = a - b;
    x = t2;
  }
  t1 = a + b;
  z = t1;
  return;
}

t1はa + bについての一時変数で、t2はa - bについての一時変数です。 Available expressionsでは、まず最初に、

d ← a + b

という計算があったら、a + b用の一時変数tを導入し、

t ← a + b \\
d ← t

という変換をします。このように変換しておけば、データフロー解析後にa + b の値が使えるとわかったら、t ← a + b の命令を消せばいいだけなので、後々楽です。

アルゴリズム

それでは、アルゴリズムの説明に入ります。 Reaching Definitionと同じように、以下の表のようにgenとkillの計算をします。

Statement s gen[s] kill[s]
t ← a ⊕ b {a ⊕ b} - kill[s] expressions containing t
t ← Mem[a] {Mem[a]} - kill[s] expressions containing t
Mem[a] ← b {} expressions of the form Mem[x]
f(a,b) {} expressions of the form Mem[x]
t ← f(a,b) {} expressions containing t and expressions of the form Mem[x]

これは、それぞれ以下のような意味です。

1行目:何らかの計算をして、tに代入する場合。 2行目:aの場所のメモリの値を、tにロードする場合。 3行目:aの場所のメモリに、bの値をストアする場合。 4行目:関数f()を呼び出す場合。 5行目:関数f()を呼び出し、その返り値をtに代入する場合。

kill[s]にある、expressions containing t とは、t を含む式のことです。つまり、t の値は変更されたので、t をオペランドに持つような式(t + x など)は利用可能でないからkillするということです。 また、expressions of the form Mem[x]とは、Mem[x]の式(任意の x の値について)をキルするということです。メモリアクセスについては、プログラムのどの場所で、メモリのどの位置にアクセスするかといったことを正確に解析するのが難しいです。なので、メモリに値をストアする可能性がある場合は、Mem[x]形式の式はすべてキルします。 また、表中にないような条件分岐文などは、genとkillの計算には関与しません。

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

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

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

in[entry_node] ← {};
out[entry_node] ← {all expressions};
foreach n
  if n is not entry_node then
    in[n] ← {all expressions};
    out[n] ← {all expressions};
  endif;
endfor;

do
  foreach n 
    in2[n] ← in[n];
    out2[n] ← out[n];
    foreach p in pred[n]
      in[n] ← intersection(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()関数は引数の和集合を計算する関数で、intersection()関数は引数の積集合を計算する関数です。 では、先ほどのsample2.cの場合で、例を考えてみます。

1: t1 ← a + b
1*: x ← t1
2: if a < 5 goto L1 else goto L2
3: L1: t1 ← a + b
3*: y ← t1
4: goto L3
5: L2: a ← 10
6: t2 ← a - b
6*: x ← t2
7: goto L3
8: L3: t1 ← a + b
8*: z ← t1

一時変数を導入してみると、このように書けると思います。 次に、gen、kill、in、outを計算すると以下のようになります。

n gen[n] kill[n] in[n] out[n]
1 {a + b} {a + b}
2 {a + b} {a + b}
3 {a + b} {a + b} {a + b}
4 {a + b} {a + b}
5 {a + b, a - b} {a + b}
6 {a - b} {a - b}
7 {a - b} {a - b}
8 {a + b} {a + b}

a + b を計算している1,3,8番のノードでは、{a + b}をgen[n]に加えています。また、a - b を計算している6番のノードでは、{a - b}をgen[n]に加えています。 5番のノードではaの値を変更しているので、a + b と a - b はキルされます。 8番のノードには、4番のノードから{a + b}が、7番のノードから{a - b}がデータフローされてきますが、それらの積集合を取ると空集合となるので、8番のノードのin[n]は空集合です。

ここで、3番のノードのinに注目してみると、a + b があります。つまり、3番のノードの入口でa + b が利用可能であるので、3番のノードは消去することができます。この操作のことをCommon Sub-expression Elimination(共通部分式削除、CSE)と言います。 つまり、sample2.cをCSEすると、以下のようになります。

void main(int a, int b){
  int x,y,z;
  int t1,t2;

  t1 = a + b;
  x = t1;
  if(a < 5){
    y = t1;
  } else {
    a = 10;
    t2 = a - b;
    x = t2;
  }
  t1 = a + b;
  z = t1;
  return;
}

上記のsample3.cを見るとわかるように、無駄な計算が省かれ最適化されました。

参考記事

Reaching Definition
Dead Code Elimination
CFG,トポロジカルソート,Bit Vector,ワークリストアルゴリズム
Lazy Code Motion

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 についての定義が2つ以上到達するからです。 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に代入する場合です。2列目は、命令sがあったとき、gen[s]に追加すべき要素です。ここで、d1やd2というのは、各命令につけた番号です。3列目は、命令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}なので、1番と6番の定義が到達しているということです。つまり、7: c ← a + b7: c ← 1 + 3と置き換えられるということになります。 さらに、定数畳み込み(Constant folding)を適用させれば、7: c ← 4となります。 一方、n = 9 のときに注目すると、9番の命令には定数伝播できないことがわかります。見てわかるように、in[9]には、aについての定義である1と4があり、bについての定義である2と6もありますね。これでは、コンパイル時にどちらの定義を選択すれば良いのかコンパイラは知ることができず、最適化できないということになります。

参考記事

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

2020年の振り返りと2021年の抱負

2020年の振り返り

2020年の年始は,まだM2でJIP用に論文を英訳していた.
2019年にPROに投稿,発表した日本語論文を,指導教員の勧めもあって,JIPに載せようということになったのだった.
日本語なんて世界ではせいぜい1億人とちょっとぐらいの人数しか読めないのに対し,英語ならその何倍もの人に読んでもらえる可能性がある.

2月は,修論審査会と修論提出に追われ,3月に修士(理学)の学位を取得した.
この頃にはすでに外出自粛になっていて,せっかくだしどこか行きたかったが,家で論文を読んでいた.

4月からは緊急事態宣言が発令され,本格的に外出自粛,大学にも5月の終わりまで行かなかった.
その分,ゆっくりと家でサーベイできたが,自分はどうも家だと気が抜けてしまう質なので,大学に行けてたらもっと研究が捗っていたのでは...,と今更ながらに思う.

6月~8月は,論文のために提案手法の実装をしていた.
これは大学でやっていたが,先生と相談しつつ2回ほど実装し直したので,3か月もかかってしまった.

9月は実装した手法の効果を確認するために実験をした.
これは個人的に一番嫌な作業である.
ベンチマークのプログラムを一つずつ最適化し,結果を見て,バグがあったら直して,何故か最初から動かないプログラムがあったり...
そもそも効果を確認できるプログラムはほとんどない.
しかもこれ全部一人でやる.
実際やってみると,気の遠くなるような作業なのだ.

10月は実験をやりつつ,CC2021に投稿するために,論文を書いていた.
今思えば,8月くらいから論文を書き始めていればもっとスムーズに書けたと思う.
先生と何回もやりとりして,修正を重ね,11月にCC2021に投稿した.
そして,12月23日,REJECTという最高にイカしたちょっと早めのクリスマスプレゼントをもらって,2020年は終わった.

2021年の抱負

CC2021ではrejectされてしまったが,先生にECOOP2021に出してみてはどうかと勧められた.
ECOOPは,元々オブジェクト指向プログラミングを扱っていたらしいが,最近では割と広い範囲をカバーしているとのことで,以前にProgram Committeeをされたことがある知り合いの先生に聞いたら,コンパイラのコード最適化もカバーしているとのこと.
締め切りが近いが,CC2021に出した論文に少し付け足して出そうと思っているので,もうすでにほとんどできている.
ECOOPに通れば,博士号を取るための最低論文数の要件を満たせる.(まぁ,最低論文数だと博士論文書けそうにないけども)

ということで,2021年の目標は以下!

  • ECOOPに通して,国際会議Proceedings1本
  • 3月に修了して就職する後輩の関連研究を論文化(投稿先はまだ決めていない)
  • 今頭の中にあるアイデアECOOP論文に足して,TACOに投稿
  • 運動する
  • 2020年から続けてきた英語学習(listeningとspeaking)を引き続き継続

とりあえず5個挙げたけど,もっとチャレンジングなこともしたい.
対戦よろしくお願いいたします.

Lazy Code Motion

この記事は,言語実装 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. レジスタ圧力を抑えるために,できるだけ遅いプログラム点に式を移動する.

上記の特徴のうち,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=1b=c - dなど)を変更文といいます. さらに,節Bは基本ブロックを表していて,コンパイラの構成と最適化に則って,以下のように2つに分割することにします. その分け目は,B中の最後の変更文の直後で,分けたものの最初の方を入口部分,後ろの方を出口部分と呼びます. 入口部分の最初の計算を入口計算と呼び,出口部分の計算を出口計算と呼びます. コード移動の際に,式を挿入する必要がありますが,そのときの挿入点は,入口計算や出口計算があるときはその直前,入口計算がなく変更文があるときは最初の変更文の直前,どちらもなければその部分の最後とします.

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

LCMの詳細

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

危険辺(critical edge)とは,2つ以上の後続節をもつ節から2つ以上の先行節をもつ節への辺のことです.
例えば,下図(a)の節2から節3への辺は危険辺です.節3に部分冗長な式があると仮定すると,それをプログラムの前方(図でいうと上の方)に移動させることで部分冗長性を除去したいのですが,節3から節2には式を移動させることはできません.もし,節2に移動させてしまうと,節2の右側の後続節にも影響を及ぼしてしまいます.
このような危険辺は,下図(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+bd=tに分解されているとします.このようにしておくと後から楽です.
なので,この例では,上記のアルゴリズム中のInst_origt=a+bを,source(Inst_orig)は「{a,b}という集合」を表します.また,destination(Inst)は,命令Instの左辺を指します. 例えば,Instx=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の計算結果は必ず同じ値になるということです. なので,ある下安全な点から別の下安全な点に式を移動させても(その2点間の全ての節が下安全である必要がある),プログラムの意味は変えることはありません.この「プログラムの意味を変えない」という意味で「安全」なのです. LCMを含むPREでは,そうやって式を移動できることに着目し,上手く式を移動することで,冗長性を除去することを試みます.
ここで,節Bの下安全性に関する述語を2つ,以下のように定義します.

  • 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の上安全性に関する述語を2つ,以下のように定義します.

  • 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に関する述語を2つ,以下のように定義します.

  • 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に関する述語を2つ,以下のように定義します.

  • 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に関する述語を2つ,以下のように定義します.

  • 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前後を見比べてみると,節6,7のループ中のループ不変式が節5に移動していて,節11と12のところの部分冗長性が除去されています.

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

しかし,これを見てわかるように,LCMは全ての部分冗長性を除去できるわけではありません. 例えば,( \textbf{s}, 1, 2, 4, 9, 10, 12, 13,  \textbf{e})の実行経路における冗長性は,除去できていませんね.
LCMは,下安全性を満たす節にだけ式を挿入するので,任意の実行経路に新しく計算を導入することはありません. 例えば,節3に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)の手法のように,コードの複写を伴う手法を用いる必要があります. それらの手法は,冗長性を除去できるメリットがある反面,ちゃんとデメリットもあります. コード最適化はまだまだ奥が深いです.

終わりに

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