maekawatoshiki/compiler-optimizations.md Secret

## compiler-optimizations.md

      
    Raw
  

              compiler-optimizations.md
            
          
    もくじ


コンパイラ最適化とは何か
コンパイラ最適化の代表例（概略）

これさえ実装すれば良い：8つの最適化


コンパイラ最適化に適した、プログラムの形式

SSA (Static Single Assignment) form
なぜ SSA はコンパイラ最適化に適しているか
SSAが実世界で使われている例: LLVM IR
SSAが実世界で使われている例: Cranelift IR


コンパイラ最適化の具体的な実装方法

普通のプログラム→SSA 変換
8つの最適化 ...


コンパイラ最適化とは何か

コンパイラ最適化とはなんでしょうか。私のよく読む本（コンパイラの構成と最適化, p.243）では以下のように定義されています。（以降、この本で「目的プログラムの最適化」と呼んでいるものを、この文章では「コンパイラ最適化」と呼びます。）

目的プログラム（目的コードとも言う）の最適化（optimization）とは、効率のよい目的プログラムとすることである。

また、以下のように続きます。

一般には最もよい目的コードを作り出すことは不可能であり、「よりよい」コードとする努力をするだけである。
「適化」といったほうがよいかもしれないが、昔からコンパイラに関しては「最適化」という言葉が使われているので、ここでもそれを使うことにする。

おそらく、この定義が一般的な認識と大きくずれていることはないと思います。
要するに、コンパイラがプログラムをなんらかの方法で変換し、その結果、プログラムは（なんらかの指標において）より効率の良いものとなるのです。
（上の引用で述べられている通り、「最も良い」プログラムに変換することはできません。もしそのようなことが可能ならば、停止性問題を解いてしまうことになるからです。）
この文章では、コンパイラ最適化について、理論と実装の両方について説明を試みます。誤字や特に知りたい内容などがあれば教えてください。
コンパイラ最適化の代表例

世の中には非常に多くの最適化手法が存在しています。もちろん、それらは実際にコンパイラに実装されているわけで、例えば LLVM には約100個の最適化手法が実装されています（Analysis + Transform passes の数, ターゲット依存のものも数えればもっと多いでしょう, ref. https://llvm.org/docs/Passes.html ）。
様々な最適化を適用すれば、その分より良いプログラムが生成されやすくなるでしょう。（実際は、最適化手法を適用する順番でプログラムが変わったりするので一概には言えないのですが...）
しかし、むやみにいろいろな最適化手法を実装してもあまり効率的ではありません。
そのため、ここではこれさえ実装すれば十分な性能が出せるだろうと言える8つの最適化に注目します。これ以外の最適化も後々紹介する予定です。（実際は、ひとつの最適化を実装するために、また他の手法を知らないといけない、ということがよく起きますからね。）
なお、ここで紹介する最適化はこちらのスライド (p.19)で紹介されています。参考として、最適化手法のカタログも目を通すと良いでしょう。
さて、さっそくですが、以下がその最適化の一覧です。（私が適当に並び替えたので、スライドでの並び順とは異なります。下のほうがより実装が難しいかなぁと思いますが結構適当です。）

Constant Fold
DCE
Peephole
Inline
Unroll
CSE
Code Motion
Vectorize

名前を並べられてもよくわからないと思うので、一つづつ内容を確認していきましょう。
Constant Fold

これは耳にしたことのある方も多いのではないでしょうか。日本語だと定数畳み込みと呼ばれている最適化です。
内容はとてもシンプルで、コンパイル時に計算できる部分は計算しておこうというものです。
具体的には以下のような変形を行います。
# Constant Fold 前
x = 1 * 60 * 60 * 24
# Constant Fold 後
x = 86400
また、コンパイル時に処理できれば良いので、例えば文字列同士の演算にも適用できます。（C言語だとあまり関係ないですが。）
# Constant Fold 前
s = "hello " + "world"
# Constant Fold 後
s = "hello world"
ただ、浮動小数点数を畳み込んでも良いのかは言語仕様によります。コンパイル時と実行時で丸めモードが異なったり、演算の順番によって結果が変わってくる（結合法則が成り立たない）ことがあるからです。
実際に実装するときは、とりあえず整数値の畳み込みを実装すれば良いでしょう。
参考: LLVMでの実装
余談: Constant Propagation と Sparse Conditional Constant Propagation

定数伝播 (Constant Propagation) や 疎な条件分岐を考慮した定数伝播 (Sparse Conditional Constant Propagation, 長いので以下 SCCP) を用いると、より多くのコードを定数へと畳み込むことができます。
定数伝播とは、（変数などの持つ）値が（ある範囲では）変化しないことを利用して、より多くのコードを定数畳み込みの対象とするものです。
例えば以下のような変形を行います。
# Constant Propagation 前
x = 42
y = x + 1 # x が変数だから、Constant Fold できない...
# Constant Propagation 後
x = 42
y = 42 + 1 # y への代入時には、x の値は 42 から変化していない。だから x を 42 で置き換えられる。
           # Constant Fold できるようになった! 
定数伝播では、変数（上の例だと x）の値がどう変化しているか（変化していないか）が重要になってきます。このような情報を解析するためには、データフロー解析（Wikipedia, うまくまとまっているQiitaの記事）の実装が必要です。こちらについても後述予定です。
また、SCCP はプログラム中の条件分岐に注目することで、より多くのコードを定数畳み込みの対象とします。
例えば以下のような変形を行います。
# SCCP 前
x = 42
y = 0
if (x == 42) {
    y = 1
} else {
    y = 2
}
z = y + 1
# SCCP 後
x = 42
y = 0
# この時点で x == 42 だから、if では y = 1 が実行される。
y = 1 # 下の if はごっそり削除
# if (x == 42) {
#     y = 1
# } else {
#     y = 2
# }
z = 1 + 1 # だから y を 1 で置き換えられる。
          # Constant Fold できるようになった!
DCE (Dead Code Elimination)

DCE (Dead Code Elimination, デッドコード削除) とは、冗長なコードや実行されることのないコードを削除する最適化です。ここでもデータフロー解析が必要になります。
例えば以下のような変換を行います。
# DCE 前
a = 1
b = 2
c = 3
return a + b
# DCE 後
a = 1
b = 2
# c = 3 # 削除
return a + b
# DCE 前
a = 1
b = 2
c = b + 1
return a
# DCE 後
a = 1
# c は使われないから削除
# c で参照されていた b も削除
# ↑ バックトラックが必要な時もある (→ SSAを導入すると楽になる)
# b = 2
# c = b + 1
return a
DCE 前後に Constant Fold (SCCP) を行うと、より多くのコードを削除できます。
# SCCP 前
a = 1
if (a == 1) 
    a = 2;
else
    a = 3;
return a
# SCCP 後 (DCE 前)
a = 1
a = 2
return a
# DCE 後
# a = 1 # 下の a = 2 が実行されるまでに、a の値は参照されていない
        # 冗長なので削除できる
a = 2
return a
# ここでまた SCCP するともっと簡潔になる
return 2
注意しないといけないのは、関数呼び出しは安易に削除できないということです。呼び出しには副作用（IO, グローバル変数への書き込み, etc）が伴うため、削除しても良いのか何かしらの方法で検証する必要があります。あまり簡単ではないので、実装する時は、まずは非常に限られたケースのみに対応させると良いでしょう。
# DCE 前
a = add(1, 2);
puts("hello world");
# DCE 後
a = add(1, 2); # 消していいのか？
puts("hello world"); # 消せなさそう
# 引数やローカル変数、足し算しか使っていない→副作用なさそう
int add(int x, int y) { return x + y; }
# なら消せそう
# a = add(1, 2);
参考: LLVMでの実装, isInstructionTriviallyDead()
Peephole

WIP :(
https://ja.wikipedia.org/wiki/%E3%81%AE%E3%81%9E%E3%81%8D%E7%A9%B4%E7%9A%84%E6%9C%80%E9%81%A9%E5%8C%96
Inline

https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%B3%E3%83%A9%E3%82%A4%E3%83%B3%E5%B1%95%E9%96%8B
Unroll

https://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%97%E5%B1%95%E9%96%8B
CSE (Common Subexpression Elimination)

https://ja.wikipedia.org/wiki/%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E5%BC%8F%E9%99%A4%E5%8E%BB
Code Motion

https://en.wikipedia.org/wiki/Code_motion (英語)

code motion, also known as code hoisting, code sinking, loop-invariant code motion, or code factoring, is a blanket term for any process that moves code within a program for performance or size benefits

参考: LLVM LICM
Vectorize

https://en.wikipedia.org/wiki/Automatic_vectorization (英語)
自作コンパイラに実装するとしても、優先度は低くなるでしょう
コンパイラ最適化に適した、プログラムの形式

コンパイラ最適化のさまざまな（変形）手法を実装するためには、多くの場合、まずはプログラムを解析しなければなりません。
解析には色々な種類があり、ここまでで登場したデータフロー解析や、基本ブロックの支配木の構成、Scalar Evolution の解析などちょっと難しいものも存在します。
ここでは、データフロー解析の観点から見て扱いやすい、プログラムの形式を紹介します。
それが SSA (Static Single Assignment, 静的単一代入) 形式です。
SSA (Static Single Assignment) form

なぜ SSA はコンパイラ最適化に適しているか

SSAが実世界で使われている例: LLVM IR

SSAが実世界で使われている例: Cranelift IR