古典コンパイラ入門（#JuliaLang）

# (#JuliaLang) Julia Advent Calendar 2014
# 12月7日担当 kimrin(twitter:kimrin)

やっぴー♡　みんなのアイドル（哀ドルともいうw）きむりんだよー。
小六女子のおっさん(40)だよー。いえーい、見てる見てるー？ www

さて、12月5日のAdventでJuliaたん使って、LLVM IRとnative codeを簡単にみる
ことができること、勉強したねo(^_^)o

なんと、今日はJuliaたんで、

### 古典コンパイラの理論に迫ってみましょー

おー（ぱちぱち！）

古典コンパイラ（昔のコンパイラ）なのです。だからJuliaの実装ではないこと、ここでお断りしておくですー。

---

真面目に言うと、この記事はみなさんに古典コンパイラのbackendの基礎知識を与えるものです。概念として、CFG(Control Flow Graph), PDG(Program Dependency Graph), data flow analysis, liveness analysis あたりを勉強しましょー。

---

では、レッツすたーとです！

---

### Collatzの予想
コラッツの予想を解くプログラムを例に、お勉強を進めてみましょー。
コラッツの予想とは、ある数Nが与えられたときに、

* N=N/2 (Nは偶数）
* N=3N+1 (Nは奇数）

ってのをひたすら繰り返してくと、最後に必ず`N=1`に帰着しない？（違う？）
みたいな数学の予想です。予想なので証明されてませんが、十分大きな数について
この予想は当たってるらしいです。

さて、straight-forwardに、この問題を実装したプログラム例を示します

```lang:Collatz
julia> function Collatz(n::Int64)
           while n != 1
               n = ((n&1)==0)?div(n,2):3n+1
           end
           n
       end
```

whileは必ず`1`で抜けるので、関数は停止するなら1を返り値として返します。
割り算は`div`という関数をあえて使ってみました。この方が浮動小数点介さないので、
IRがシンプルになります。

LLVM IRみてみましょー

```lang:LLVM_IR

julia> code_llvm(Collatz,(Int64,))

define i64 @"julia_Collatz;20292"(i64) {
top:
  %1 = icmp eq i64 %0, 1, !dbg !1875
  br i1 %1, label %L5, label %L, !dbg !1875

L:                                                ; preds = %top, %L3
  %n.0 = phi i64 [ %n.1, %L3 ], [ %0, %top ]
  %2 = and i64 %n.0, 1, !dbg !1876
  %3 = icmp eq i64 %2, 0, !dbg !1876
  br i1 %3, label %pass, label %L2, !dbg !1876

pass:                                             ; preds = %L
  %4 = sdiv i64 %n.0, 2, !dbg !1876
  br label %L3, !dbg !1876

L2:                                               ; preds = %L
  %5 = mul i64 %n.0, 3, !dbg !1876
  %6 = add i64 %5, 1, !dbg !1876
  br label %L3, !dbg !1876

L3:                                               ; preds = %L2, %pass
  %n.1 = phi i64 [ %6, %L2 ], [ %4, %pass ]
  %7 = icmp eq i64 %n.1, 1, !dbg !1876
  br i1 %7, label %L5, label %L, !dbg !1876

L5:                                               ; preds = %L3, %top
  ret i64 1, !dbg !1877
}

julia> 

```

わりと素直なコード出てきました〜。
さて、このLLVM IRはSSA形式になっているという話を以前したの、
覚えてるでしょうか。実はSSA形式だとこれから説明するdata flow analysisとliveness analysisは若干説明しずらいのです（諸般の事情によりw）。

そこで、SSA形式じゃなかったら、どんなIRになってるんだろうというのを
夢想した、`俺IR`を導入して話を進めてみます。いぇーい！

具体的には変数への再代入を許容し、`phi関数`のない表現を考えてみましょー。
で、それを俺が手で書いたのが下記です。ご確認ください。。。

```lang:俺IR
     1	define i64 @"julia_Collatz;20292"(i64) {
     2	top:
     3	  %n = %x
     4	  %1 = icmp eq i64 %x, 1
     5	  br i1 %1, label %END, label %L1
     6	
     7	L1:                                                ; preds = %top, %L4
     8	  %2 = and i64 %n, 1
     9	  %3 = icmp eq i64 %2, 0
    10	  br i1 %3, label %L2, label %L3
    11	
    12	L2:                                                ; preds = %L1
    13	  %n = sdiv i64 %n, 2
    14	  br label %L4
    15	
    16	L3:                                               ; preds = %L1
    17	  %5 = mul i64 %n, 3
    18	  %n = add i64 %5, 1
    19	  br label %L4
    20	
    21	L4:                                               ; preds = %L2, %L3
    22	  %6 = icmp eq i64 %n, 1
    23	  br i1 %6, label %END, label %L1
    24	
    25	END:                                               ; preds = %L4, %top
    26	  ret i64 1
    27	}
```

後々のために行番号を付与しています。また表現はほぼLLVM IRですが、変数の再代入を許しているのが特徴です。

この表現上でラベルと命令列がひとかたまりになっているのが、6つくらいあるの、わかるでしょーかー。たとえば

```lang:俺IR
     7	L1:                                                ; preds = %top, %L4
     8	  %2 = and i64 %n, 1
     9	  %3 = icmp eq i64 %2, 0
    10	  br i1 %3, label %L2, label %L3
    11	
```

とかですね。この、命令列の途中に分岐がなくて、最後に分岐の入っているかたまりのことを、Basic Blockといいまーす。で、ラベル名で区別することにします。つまり上記`L1`のラベルとその命令列は、Basic Block L1と呼ぶことにし、L1と略すことにします。

で、Basic Blockにはpredecessor(Pred)とsuccessor(Succ)という二つの集合をグラフから計算できます。これはPredがこのブロックに流入してくるブロックの集合、Succがこのブロックから流出していくブロックの集合です。各Basic Blockについて、PredとSuccを求めてみましょう。

```lang:BasicBlocks
 BB    Pred     Succ
---- -------- ---------
top             L1
L1    top,L4    L2,L3
L2    L1        L4
L3    L1        L4
L4    L2,L3     END,L1
END   L4,top        
--------------------------

```

Predが複数なのは複数のBasicBlockから流入（ジャンプしてくる）可能性があるということです。反対にSuccが複数なのは、複数のBasicBlockへと、条件ジャンプする可能性がある、ということになります。

------

もう一つ用語の準備をしましょう。data flow analysisなどにおいて、Defという概念を導入します。具体的には

* 左辺の変数（代入、write）はDef

で、各BasicBlockごとにDefを考えてみます。
ここで、それぞれのDef（代入）にd1のようにd+行番号という
Def Numberを付けて、同じ変数への重複した代入を区別することにします。
俺IRにこのDef Numberをアノテートすると、次のようになります。

```lang:俺IR2
     1 	define i64 @"julia_Collatz;20292"(i64) {
     2 	top:
     3	d3  %n = %x
     4	d4  %1 = icmp eq i64 %x, 1
     5	    br i1 %1, label %END, label %L1
     6	
     7	L1:                                                ; preds = %top, %L4
     8	d8  %2 = and i64 %n, 1
     9	d9  %3 = icmp eq i64 %2, 0
    10	    br i1 %3, label %L2, label %L3
    11	
    12	L2:                                                ; preds = %L1
    13	d13  %n = sdiv i64 %n, 2
    14	     br label %L4
    15	
    16	L3:                                               ; preds = %L1
    17	d17  %5 = mul i64 %n, 3
    18	d18  %n = add i64 %5, 1
    19	     br label %L4
    20	
    21	L4:                                               ; preds = %L2, %L3
    22	d22  %6 = icmp eq i64 %n, 1
    23	     br i1 %6, label %END, label %L1
    24	
    25	END:                                               ; preds = %L4, %top
    26	  ret i64 1
    27	}
```
あるBasicBlockでのDefの集合を、gen(b)と表現することにします。bはBasicBlockの名前です。gen(b)を求めてみましょう。


```lang:BasicBlock
 BB   gen(b)
---- --------
top   d3,d4       
L1    d8,d9 
L2    d13 
L3    d17,d18   
L4    d22
END          
--------------------------

```
d3,d13,d18が、同じ変数nへの代入になっています。
ここでもう一つ、kill(b)という集合を考えてみましょう。kill(b)は、自分のBasicBlock以外でDefと同じ変数に代入しているDefの集合です。わかりにくいですかね。計算してみます。

```lang:BasicBlock
 BB   gen(b)   kill(b)
---- -------- --------
top   d3,d4    d13,d18  
L1    d8,d9 
L2    d13      d3,d18
L3    d17,d18  d3,d13 
L4    d22
END          
--------------------------

```

今回のケースでは、変数nだけがkill(b)に関係しているので、kill(b)はこのようになります。他の`%5`のような数字の変数はBasicBlockを跨ぐことがありません。


---

さらにここで、`到達定義` という概念を導入してみましょう。
定義dがBasicBlock bに到達した、とは、定義dで変更した変数の値がBasicBlock bで
使われる可能性がある事を言い、このときの定義dの集合を、BasicBlock bにおける到達定義in[b]と書く事にします。反対にBasicBlock bから流出している定義dの集合を、今度はout[b]と書きます。

---

in[b]とout[b]を求めたいですね。求めたいですね！
でもin[b]とout[b]って、gen(b)やkill(b)が関係していて、簡単に求まりそうにありません。しゅん。。。

### でも大丈夫！

次の「データーフロー方程式」を解けば、なんとin[b]とout[b]が求まります！！
やったー＼(^o^)／

では方程式です。

```math
in[b] = \bigcup_{p ∈ Pred(b)} out[p]
```

```math
out[b] = gen(b) \cup (in[b] - kill(b))
```

ええ〜　これ、解くの。。。

つまりin[b]はすべての流入もとのoutの総和で、
out[b]はgenと(in-kill)の総和になります。
これがすべてのBasicBlockで成り立っている解を求めればOK!です！！！

### どうやって解くの。。。これ。。。

心配めさるな。Julia使って解いてみましょう。
方針としてはin[b]とout[b]に空集合を代入しておいて、
inとoutをこの順で計算します。すると定義dがinとoutに
入ります。これを何回も繰り返していくと、定義dがBasicBlock間（具体的にはinとout）を
移動します。最後にもうこれ以上やっても全然すすまないよー、
という`fix point`に到達したら、これを方程式の解とします。

さてプログラムに落とす前に、簡便のため、BasicBlockに番号ふりましょう。

```lang:BasicBlock
 BB  No.  gen(b)   kill(b)
---- --- -------- --------
top   0  d3,d4    d13,d18  
L1    1  d8,d9 
L2    2  d13      d3,d18
L3    3  d17,d18  d3,d13 
L4    4  d22
END   5       
--------------------------

```
で、定義dも番号で管理することにしましょう。
BasicBlockの番号で、もう一度Predを見てみましょう。

```lang:BasicBlocks
 BB  No.  Pred 
---- --- -------
top   0         
L1    1   0,4   
L2    2   1     
L3    3   1   
L4    4   2,3
END   5   4,0        
--------------------------

```

ですね。Succは使わないのでおいときます。

```jl:DataFlowAnalysis.jl
#!/usr/bin/env julia
# -*- code: UTF-8 -*-

function genTable()
    gen = (Int64 => Vector{Int64})[0 => Int64[3,4],
                                   1 => Int64[8,9],
                                   2 => Int64[13,],
                                   3 => Int64[17,18],
                                   4 => Int64[22,],
                                   5 => Int64[]]

    kill = (Int64 => Vector{Int64})[0 => Int64[13,18],
                                    1 => Int64[],
                                    2 => Int64[3,18],
                                    3 => Int64[3,13],
                                    4 => Int64[],
                                    5 => Int64[]]

    pred = (Int64 => Vector{Int64})[0 => Int64[],
                                    1 => Int64[0,4],
                                    2 => Int64[1,],
                                    3 => Int64[1,],
                                    4 => Int64[2,3],
                                    5 => Int64[4,0]]

    gen, kill, pred
end

function minus(a,b)
    ans = Int64[]
    for x in a
        if in(x,b)
            continue
        else
            ans = vcat(ans,Int64[x,])
        end
    end
    ans
end

function isdiff(a,b)
    v = hash(a)
    w = hash(b)
    v != w
end

function calcDataFlow(gen,kill,pred)
    out = (Int64 => Vector{Int64})[0 => Int64[],
                                   1 => Int64[],
                                   2 => Int64[],
                                   3 => Int64[],
                                   4 => Int64[],
                                   5 => Int64[]]
    inp = (Int64 => Vector{Int64})[0 => Int64[],
                                   1 => Int64[],
                                   2 => Int64[],
                                   3 => Int64[],
                                   4 => Int64[],
                                   5 => Int64[]]
    old_out = (Int64 => Vector{Int64})[0 => Int64[],
                                       1 => Int64[],
                                       2 => Int64[],
                                       3 => Int64[],
                                       4 => Int64[],
                                       5 => Int64[]]
    old_inp = (Int64 => Vector{Int64})[0 => Int64[],
                                       1 => Int64[],
                                       2 => Int64[],
                                       3 => Int64[],
                                       4 => Int64[],
                                       5 => Int64[]]
    change = true
    while change
        for b = 1:5
            p = pred[b]
            for x in p
                inp[b] = unique(vcat(inp[b],out[x]))
            end
            out[b] = unique(vcat(gen[b],minus(inp[b],kill[b])))
        end
        change = isdiff(out,old_out) || isdiff(inp,old_inp)
        old_out = deepcopy(out)
        old_inp = deepcopy(inp)
    end
    out, inp
end

function main()
    gen, kill, pred = genTable()
    out, inp = calcDataFlow(gen,kill,pred)
    println(out)
    println(inp)
end

main()
```

結果です！！！

```jlcon:console
[0=>[],4=>[13,8,9,4,17,18,22],2=>[8,9,3,4,22,13,17,18],3=>[8,9,3,4,22,13,17,18],5=>[22,13,8,9,4,17,18,3],1=>[3,4,22,13,8,9,17,18]]
[0=>[3,4],4=>[22,13,8,9,4,17,18],2=>[13,8,9,4,22,17],3=>[17,18,8,9,4,22],5=>[22,13,8,9,4,17,18,3],1=>[8,9,3,4,22,13,17,18]]
```

これをわかりやすくBasicBlockごとにinとoutを並べて見ましょう。

```lang:console
top:
    in[]
    gen[3,4]
    out[3,4]
L1:
    in[3,4,8,9,13,17,18,22]
    gen[8,9]
    out[3,4,8,9,13,17,18,22]
L2:
    in[3,4,8,9,13,17,18,22]
    gen[13]
    out[4,8,9,4,13,17,22]
L3:
    in[3,4,8,9,13,17,18,22]
    gen[17,18]
    out[4,8,9,17,18,22]
L4:
    in[4,8,9,13,17,18,22]
    gen[22]
    out[4,8,9,13,17,18,22]
END:
    in[3,4,8,9,13,17,18,22]
    gen[]
    out[3,4,8,9,13,17,18,22]
```

つまり、ほとんどの変数はすべてのBasicBlockに到達していることになります。
でもこれは、BasicBlock内で使っていない変数も計算に入れているので、
こんな感じになります。

じゃぁ、Defと使用が結びついている（実際に到達した定義を使っている）変数を見てみましょう。こんどはUseという変数の集合を考えてみます。

```lang:俺IR2
     1 	      use      def
     2 	top:
     3	       %x       %n
     4	       %x       %1
     5	       %1
     6	
     7	L1:                             ; preds = %top, %L4
     8	       %n       %2
     9	       %2       %3
    10	       %3
    11	
    12	L2:                             ; preds = %L1
    13	       %n       %n
    14
    15	
    16	L3:                             ; preds = %L1
    17	       %n       %5
    18	       %5       %n
    19	 
    20	
    21	L4:                             ; preds = %L2, %L3
    22	       %n       %6
    23	       %6
    24	
    25	END:                            ; preds = %L4, %top
    26	
    27	}
```

useのところに並んでいるのが、実際に使われた変数です。で、今度は変数`n`に着目してみましょう。`n`の使用に到達している`n`の定義`d`を並べて、reachという集合を求めてみます。

```lang:console
top:
    def[3]
    reach[]
L1:
    reach[3,13,18]
L2:
    def[13]
    reach[3,13,18]
L3:
    def[18]
    reach[3,13,18]
L4:
    reach[13,18]
END:
    reach[3,13,18]
```

### う〜ん、よくわかんないよ。。。

ごめんなさい。でも、行番号3番目、13番目、18番目でそれぞれ代入されている`n`
が、コントロールフロー上の特定のBasicBlockに到達しているかどうかがわかります。
で、ループを含んでいるので、`L1:`には3,13,18のうち、13,18が還流しているわけです。
面白いことに、`L4:`には3は到達していません。必ず13か18の定義しか到達していない
ことがわかります。

### Liveness Analysis

Reaching Definitionに似た概念で、Live-in, Live-outというのもまた、求められまする。これは変数の生存区間を求めるもので、変数は最初の定義で生まれ、最後の使用で死にます。また同じ変数に定義が繰り替えされると、前の定義は死に、新しい定義が生まれます。

```jl:LivenessAnalysis.jl
#!/usr/bin/env julia
# -*- code: UTF-8 -*-

function genTable()
    succ = (Int64 => Vector{Int64})[0 => Int64[1],
                                    1 => Int64[2,3],
                                    2 => Int64[4,],
                                    3 => Int64[4,],
                                    4 => Int64[1,5],
                                    5 => Int64[]]

    use = (Int64 => Vector{String})[0 => String["%x"],
                                    1 => String["%n"],
                                    2 => String["%n"],
                                    3 => String["%n"],
                                    4 => String["%n"],
                                    5 => String[]]

    def = (Int64 => Vector{String})[0 => String["%n","%1"],
                                    1 => String["%2","%3"],
                                    2 => String["%n",],
                                    3 => String["%n","%5"],
                                    4 => String["%6"],
                                    5 => String[]]
    def, use, succ
end

function minus(a,b)
    ans = String[]
    for x in a
        if in(x,b)
            continue
        else
            ans = vcat(ans,String[x,])
        end
    end
    ans
end

function isdiff(a,b)
    v = hash(a)
    w = hash(b)
    v != w
end

function calcLiveness(def,use,succ)
    out = (Int64 => Vector{String})[i => String[] for i = 0:5]
    inp = (Int64 => Vector{String})[i => String[] for i = 0:5]
    old_out = (Int64 => Vector{String})[i => String[] for i = 0:5]
    old_inp = (Int64 => Vector{String})[i => String[] for i = 0:5]
    change = true
    while change
        for b = 0:5
            s = succ[b]
            for x in s
                out[b] = unique(vcat(out[b],inp[x]))
            end
            inp[b] = unique(vcat(use[b],minus(out[b],def[b])))
        end
        change = isdiff(out,old_out) || isdiff(inp,old_inp)
        old_out = deepcopy(out)
        old_inp = deepcopy(inp)
    end
    out, inp
end

function main()
    def, use, succ = genTable()
    out, inp = calcLiveness(def,use,succ)
    println(inp)
    println(out)
end

main()
```

```jlcon:結果
[0=>String["%x"],4=>String["%n"],2=>String["%n"],3=>String["%n"],5=>String[],1=>String["%n"]]
[0=>String["%n"],4=>String["%n"],2=>String["%n"],3=>String["%n"],5=>String[],1=>String["%n"]]
```

`%x`(引数）の定義がtopに流入しているほか、
`%n`の定義が`L1`から`L4`まで生き続けてることが分かります。

Livenessの解析はレジスタアロケーション（レジスタをどう使うか、方針を決めて実際にレジスタに値を代入すること）と深い関係にあります。
基本生きている定義をレジスタに入れます。定義がたくさんありすぎる場合はメモリに一旦退避します。この例ではBlockをまたいで生き続けるのは`%n`だけであることがわかります。

---

以上、簡単な古典コンパイラのData Flow AnalysisとLiveness Analysisでした☆

こうやって、定義（代入）がどこまで生きて伝わるか、をコンパイラのbackendでは解析しているんですね。で、SSAの場合、kill=0だったりするので、より計算が楽になるわけですー。

みなさんがコンパイラ理論のほんの触りだけでも感じ取っていただけたらなと思います☆

ではね、文責kimrinでした。ちゃおーw