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

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

部分冗長除去法(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(n²)で，PFEはO(n³)となる．

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