# Compiler optimizations

# もくじ
- コンパイラ最適化とは何か
- コンパイラ最適化の代表例（概略）
- これさえ実装すれば良い：8つの最適化
- コンパイラ最適化に適した、プログラムの形式
- SSA (Static Single Assignment) form
- なぜ SSA はコンパイラ最適化に適しているか
- SSAが実世界で使われている例: LLVM IR
- SSAが実世界で使われている例: Cranelift IR
- コンパイラ最適化の具体的な実装方法
- 普通のプログラム→SSA 変換
- 8つの最適化 ...

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

コンパイラ最適化とはなんでしょうか。私のよく読む本（[コンパイラの構成と最適化](https://www.asakura.co.jp/detail.php?book_code=12177), p.243）では以下のように定義されています。（以降、この本で「目的プログラムの最適化」と呼んでいるものを、この文章では「コンパイラ最適化」と呼びます。）

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

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

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

おそらく、この定義が一般的な認識と大きくずれていることはないと思います。
要するに、コンパイラがプログラムをなんらかの方法で変換し、その結果、プログラムは（なんらかの指標において）より効率の良いものとなるのです。
（上の引用で述べられている通り、「最も良い」プログラムに変換することはできません。もしそのようなことが可能ならば、[停止性問題](https://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C)を解いてしまうことになるからです。）

この文章では、コンパイラ最適化について、理論と実装の両方について説明を試みます。誤字や特に知りたい内容などがあれば教えてください。

# コンパイラ最適化の代表例

世の中には非常に多くの最適化手法が存在しています。もちろん、すべてではありませんが、それらは実際にコンパイラに実装されているわけで、例えば [LLVM](https://ja.wikipedia.org/wiki/LLVM) には約100個の最適化手法が実装されています（Analysis + Transform passes の数, ターゲット依存のものも数えればもっと多いでしょう, ref. https://llvm.org/docs/Passes.html ）。

様々な最適化を適用すれば、その分より良いプログラムが生成されやすくなるでしょう。（実際は、最適化手法を適用する順番でプログラムが変わったりするので一概には言えないのですが...）
しかし、むやみにいろいろな最適化手法を実装してもあまり効率的ではありません。

そのため、ここでは**これさえ実装すれば十分な性能が出せるだろう**と言える8つの最適化に注目します。これ以外の最適化も後々紹介する予定です。（実際は、ひとつの最適化を実装するために、また他の手法を知らないといけない、ということがよく起きますからね。）
なお、ここで紹介する最適化は[こちらのスライド (p.19)](http://venge.net/graydon/talks/CompilerTalk-2019.pdf)で紹介されています。参考として、[最適化手法のカタログ](https://www.clear.rice.edu/comp512/Lectures/Papers/1971-allen-catalog.pdf)も目を通すと良いでしょう。

さて、さっそくですが、以下がその最適化の一覧です。（私が適当に並び替えたので、スライドでの並び順とは異なります。下のほうがより実装が難しいかなぁと思いますが結構適当です。）

- Constant Fold
- DCE
- Peephole
- Inline
- Unroll
- CSE
- Code Motion
- Vectorize

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

## Constant Fold

これは耳にしたことのある方も多いのではないでしょうか。日本語だと[定数畳み込み](https://ja.wikipedia.org/wiki/%E5%AE%9A%E6%95%B0%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF)と呼ばれている最適化です。

内容はとてもシンプルで、コンパイル時に計算できる部分は計算しておこうというものです。

具体的には以下のような変形を行います。

# Constant Fold 前
x = 1 * 60 * 60 * 24
# Constant Fold 後
x = 86400

また、コンパイル時に処理できれば良いので、例えば文字列同士の演算にも適用できます。（C言語だとあまり関係ないですが。）

# Constant Fold 前
s = "hello " + "world"
# Constant Fold 後
s = "hello world"

ただ、浮動小数点数を畳み込んでも良いのかは言語仕様によります。コンパイル時と実行時で丸めモードが異なったり、演算の順番によって結果が変わってくる（結合法則が成り立たない）ことがあるからです。

実際に実装するときは、とりあえず整数値の畳み込みを実装すれば良いでしょう。

参考: [LLVMでの実装](https://github.com/llvm/llvm-project/blob/main/llvm/lib/IR/ConstantFold.cpp)

## 余談: Constant Propagation と Sparse Conditional Constant Propagation

[定数伝播 (Constant Propagation)](https://ja.wikipedia.org/wiki/%E5%AE%9A%E6%95%B0%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF#%E5%AE%9A%E6%95%B0%E4%BC%9D%E6%92%AD) や [疎な条件分岐を考慮した定数伝播 (Sparse Conditional Constant Propagation, 長いので以下 SCCP)](https://ja.wikipedia.org/wiki/%E7%96%8E%E3%81%AA%E6%9D%A1%E4%BB%B6%E5%88%86%E5%B2%90%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F%E5%AE%9A%E6%95%B0%E4%BC%9D%E6%92%AD) を用いると、より多くのコードを定数へと畳み込むことができます。

定数伝播とは、（変数などの持つ）値が（ある範囲では）変化しないことを利用して、より多くのコードを定数畳み込みの対象とするものです。
例えば以下のような変形を行います。

# 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](https://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E3%83%95%E3%83%AD%E3%83%BC%E8%A7%A3%E6%9E%90), [うまくまとまっているQiitaの記事](https://qiita.com/fukkun/items/39c40abb1e9e5e53b7d7)）の実装が必要です。こちらについても後述予定です。

また、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での実装](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/DCE.cpp), [`isInstructionTriviallyDead()`](https://github.com/llvm/llvm-project/blob/3198364e6e4943512ed48f2a1c1ab4c418b72f42/llvm/lib/Transforms/Utils/Local.cpp#L395)

## Peephole

Peephole 最適化（のぞき穴的最適化）とは、命令列の一部分に対して行われるなんらかの最適化の総称です。

例えば、以下のような変換を行います。（ここでは適当なアセンブリを例に考えます）

# Peephole 前
mov rax, 1
push rax
pop rax
# Peephole 後
mov rax, 1

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](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/LICM.cpp)

## Vectorize

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

*自作コンパイラに実装するとしても、優先度は低くなるでしょう*

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

コンパイラ最適化のさまざまな（変形）手法を実装するためには、多くの場合、まずはプログラムを解析しなければなりません。
解析には色々な種類があり、ここまでで登場したデータフロー解析や、基本ブロックの支配木の構成、Scalar Evolution の解析などちょっと難しいものも存在します。

ここでは、データフロー解析の観点から見て扱いやすい、プログラムの形式を紹介します。
それが **SSA (Static Single Assignment, 静的単一代入)** 形式です。

## SSA (Static Single Assignment) form

> 静的単一代入形式、または SSA 形式（static single assignment form）とは、
> プログラムの表現形式の１つで、そのプログラム上のすべての変数の使用に対して、
> その使用に対応する定義は１ヶ所しかないように表現したものである。
> これは、変数の値の定義と使用の関係を明確に表現する形式であり、
> 従来のデータの流れの解析とは違う方法が、この形式を使うことによって可能になる。
>
> 引用元：[コンパイラの構成と最適化](https://www.asakura.co.jp/detail.php?book_code=12177), p.334

...

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

SSA 形式が、コンパイラ最適化において一番優れているというわけではありません。
ただ、世の中の多くのコンパイラやコンパイラ基盤ライブラリ（e.g. [LLVM](https://releases.llvm.org/13.0.0/docs/LangRef.html#abstract), [GCC](https://gcc.gnu.org/onlinedocs/gccint/SSA.html), [Cranelift](https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md), [COINS](http://coins-compiler.osdn.jp/COINSdoc/summary/summary.html), etc）は SSA 形式を（内部で）採用しており、これは SSA 形式が重要な役割を果たすことを裏付けています。

> なぜ、中間言語では SSA を使うとよいのでしょうか。それは、SSAを利用すると、実行コードの最適化（オプティマイズ）が行いやすくなるからです。（中略）変数を SSA で管理すると、一度変数に代入された値が変化しないことが保障されるため、処理と変数の関連性が追求しやすくなります。
> ―― 出村成和「LLVM / Clang 実践活用ハンドブック」p.62

...

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

https://godbolt.org/z/3YfYM4vEP

https://releases.llvm.org/14.0.0/docs/LangRef.html

...

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

https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md

...

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

## 普通のプログラム→SSA 変換

支配木、支配辺境、$\phi$関数...

## 8つの最適化

### Constant Fold
### DCE (Dead Code Elimination)
### Peephole
### Inline
### Unroll
### CSE (Common Subexpression Elimination)
### Code Motion
### Vectorize