(#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に、この問題を実装したプログラム例を示します
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みてみましょー
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関数のない表現を考えてみましょー。
で、それを俺が手で書いたのが下記です。ご確認ください。。。
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つくらいあるの、わかるでしょーかー。たとえば
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を求めてみましょう。
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をアノテートすると、次のようになります。
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)を求めてみましょう。
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の集合です。わかりにくいですかね。計算してみます。
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^)／
では方程式です。
in[b] = \bigcup_{p ∈ Pred(b)} out[p]
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に番号ふりましょう。
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を見てみましょう。
BB No. Pred
---- --- -------
top 0
L1 1 0,4
L2 2 1
L3 3 1
L4 4 2,3
END 5 4,0
--------------------------
ですね。Succは使わないのでおいときます。
#!/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()
結果です！！！
[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を並べて見ましょう。
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という変数の集合を考えてみます。
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という集合を求めてみます。
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というのもまた、求められまする。これは変数の生存区間を求めるもので、変数は最初の定義で生まれ、最後の使用で死にます。また同じ変数に定義が繰り替えされると、前の定義は死に、新しい定義が生まれます。
#!/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()
[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