こんにちは､びしょ〜じょです｡これは言語実装 Advent Calendar 201611日目の記事です｡ 百合が好きなんですが､百合以外にも活動はしているということで､百合以外の活動について今回触れたいと､えぇ､思います｡
1. はじめに
今年は通年の講義でLua VMのバイトコードの最適化器を作っています｡ 去年はこんなものを作ってました｡ 最適化器は最終報告会の後に公開しようと思っています｡
さて､とある文による定義(や代入)がそれ以降使われないとき､その文を削除したいなんていうケースがあります｡ はい､dead code eliminationなどです｡ この"それ以降使われない"かどうかの判別にDefine-Use Chainを使います｡
1-1. prerequirements
まずひとつに､example codesは実装言語に倣ってMoonScriptを使います｡ あまり分からなくてもいいですが､Luaのtableについて知っておいてもらえるとありがたいです､まぁだいたい連想配列でいいですはい｡
それともう一つ､今回はLua VMというレジスターベースのVMの命令をターゲットにして進めます｡ Lua VM 5.3には47個の命令がありますが､今回簡単のため以下の5つで戦わせていただきます｡
-
LOADK A BレジスターAにconstant listのB番目の値をブッ込みます｡A = Cst(B)といった感じで｡ -
ADD A B CレジスターAにレジスターBとCを足したものを格納する｡ つまりA = B + Cと考えればいい｡ -
EQ A B CXOR(A == 0, レジスターBの値 == レジスターCの値)のときにプログラムカウンターをインクリメントする｡つまり
XOR(A == 0, レジスターBの値 == レジスターCの値)が真のときに次の命令を無視する｡ -
JMP A Bプログラムカウンターに
Bを足す｡Aに関しては今回関係ないので省略｡JumpEqみたいなものはEQとJMPを並べて使うわけですね｡ -
RETURN A B今回はトップレベルだけ考えるので､まぁプログラムの終了位置と考えてください｡本当は全然違うぞ｡
まぁこれだけでいいか｡ 簡単のためにだいぶ端折ってますんで､詳細はドキュメント…公式にそんなものはない1)2)…Luaのソースコードを見てください｡
最後に一つ､後述しますがほとんど手探りなので間違ってる可能性が極めて高いです｡｢そうじゃなくてこうだ｣というのがあったら大変ありがたいですのでどしどしご指摘願います｡
こんな感じのLua VMの命令を見てみましょうか｡
LOADK 0 0 -- load `3`
LOADK 1 1 -- load `5`
LOADK 1 2 -- load `7` *<!>*
EQ 0 0 1 -- R(0) == R(1) ?
JMP 0 2
LOADK 2 2 -- load `7`
JMP 0 1
LOADK 2 3 -- load `9`
RETURN 0 1
constant list: [3, 5, 7, 9]
上から見ていくと､
-
レジスター0に3をロードして -
レジスター1に5をロードして､ -
レジスター1に7をロードする｡ -
レジスター0とレジスター1の値が同じかどうかを比較する - 同じ場合は8. に飛ぶ
-
レジスター2に7をロードして - 9.に飛ぶ
-
レジスター2に9をロードする - おわり
なるほど｡3行目<!>はレジスター1の値を上書きしています｡
とすると2行目の彼は無駄なのでは…ということが人間はすぐに分かります｡すぐに分かる｡
しかしプログラムは書かないといけない｡
人間も､もっと複雑なものがでてくるとあっぷあっぷになる｡
ということで書く｡
2. What is Define-Use Chain?
Wikipediaを読んで知った気になるのが趣味なので､Wikipediaを引用します｡
A Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A definition can have many forms, but is generally taken to mean the assignment of some value to a variable (which is different from the use of the term that refers to the language construct involving a data type and allocating storage).
オイオイこれはUse-Define Chainの記事じゃねーかってすみません｡
Use-Define Chainは､変数を使用する部分から､その変数の定義位置を逆引きするようなイメージですか｡
例で見ると､EQからどこで定義されたレジスター1の値を使いたいか､ということになりますね｡
Define-Use Chainはその逆で､定義から使用先が紐付けられています｡
例でいくと､2行目の宣言は誰も使ってないので参照する使用先が無い､3行目はEQで使われるので使用先が1つある､となり2行目が不要であることが分かるわけですね!
3. Reachable Definition
ただ､資料に乏しく､なんかウマイ感じのアルゴリズムの説明もありません｡ 仕方なく雰囲気だけで我流の実装をしてみたところもちろんガバガバで爆死しました｡
先生に伺ったところ､｢Reachable Definitionからちょっと発展させればできる｣とのことでした｡ Reachable Definition､それならちょっと前に読んだ本3に出てきたなとなってなんとかなりそうだった｡
段階を追うのが下手なので､ここで強制的に段階を追わせていただきます｡ まず､Reachable Definitionについて語るために､Control Flow Graphについて語る必要があります｡
3-1. Control Flow Graph (CFG)
簡単に言ってしまうと､プログラムの実行の流れをグラフにしたようなものです｡context-free grammarではないよ｡ 最適化などでしょっちゅう使われる物体ですね4｡ 各ノードは基本ブロックと呼ばれ､各ブロックには文が突っ込まれている｡ 1)によると､
ブロック\(B_1\)からブロック\(B_2\)に有向辺が引かれるのは, 以下の場合である.
1) \(B_1\)の最後の文から\(B_2\)の最初の文へ無条件あるいは条件付き飛越しがある
2) \(B_1\)の最後が無条件飛越し文以外の文で終わっていて, プログラムの字面上で\(B_1\)の直後に\(B_2\)が来る
とのこと｡
ブロックBから有向辺が伸びている先のブロックの集合を先行ブロック(successor)､ Bに向かって有向辺を向けているブロックの集合を後続ブロック(predecessor)となる｡
Lua VMの命令で見ていくと､EQ､JPとRETURNがブロックの出口となります｡
特にRETURNがブロック最後の命令のときは､先行ブロックがそのブロックに付きません｡
説明のため､基本ブロックは次のようなtableとなる:
{
start: (基本ブロックの開始行: number) -- これいる
end: (終了行: number) -- これいる
succ: {......} -- 先行ブロック､これ要らない
pred: {......} -- 後続ブロック これいる
}
さてこれにより命令は以下のようなCFGになります(inspect5による整形)｡
cfg = { <1>{
end = 4,
pred = {},
start = 1,
succ = { <2>{
end = 5,
pred = { <table 1> },
start = 5,
succ = { <3>{
end = 8,
pred = { <table 2> },
start = 8,
succ = { <4>{
end = 9,
pred = { <5>{
end = 7,
pred = { <table 1> },
start = 6,
succ = { <table 4> }
}, <table 3> },
start = 9,
succ = {}
} }
} }
}, <table 5> }
}, <table 2>, <table 5>, <table 3>, <table 4> }
ビジュアライザーも作ったんでよかったら見ていってください｡
CFGそれ自体は本題でないので､説明はこの辺にとどめます｡
さて､Reachable Definitionに話を戻します｡
まず､各ブロックについて定義と使用を取っていきます｡
各ブロックのメンバーにgen, useというリストを追加し､以下のようなtableを突っ込みます｡
-- for gen
{
reg: (レジスター)
line: (行番号)
}
-- for use
{
reg: (レジスター)
line: (行番号)
}
例をまた引っ張ってきます｡
-- block 1 to 2, 3
LOADK 0 0
LOADK 1 1
LOADK 1 2
EQ 0 0 1
-- block 2 to 4
JMP 0 2
-- block 3 to 5
LOADK 2 2
JMP 0 1
-- block 4 to 5
LOADK 2 3
-- block 5
RETURN 0 1
constant list: [3, 5, 7, 9]
これよりgenとuseを取っていくと､次のようになります( 5)による整形を一部改変)｡
cfg = { <1>{
start = 1,
end = 4,
-- gen/use of block 1
gen = {
{line = 1, reg = 0},
{line = 2, reg = 1},
{line = 3, geg = 1}
},
use = {
{line = 4, reg = 0},
{line = 4, reg = 1}
},
pred = {},
succ = { <2>{
start = 5,
end = 5,
-- gen/use of block 2
gen = {},
use = {},
pred = { <table 1> },
succ = { <3>{
start = 8,
end = 8,
-- gen/use of block 3
gen = {
{line = 8, reg = 2}
},
use = {},
pred = { <table 2> },
succ = { <4>{
start = 9,
end = 9,
-- gen/use of block 4
gen = {},
use = {
{line = 9, reg = 0}
},
pred = { <5>{
end = 7,
-- gen/use of block 5
gen = {
{line = 6, reg = 2}
},
use = {},
pred = { <table 1> },
start = 6,
succ = { <table 4> }
}, <table 3> },
succ = {}
} },
} },
}, <table 5> }
}, <table 2>, <table 5>, <table 3>, <table 4> }
これを踏まえ､Reachable Definitionの実装はこんな感じになる:
modified = {true}
while foldl ((acc, mod) -> acc or mod), false, modified
for i = 1, #cfg
block = cfg[i]
block.in = foldl ((acc, pred) -> union acc, pred.out), {}, block.pred
block.kill = intersec block.in, block.gen
out = block.out
block.out = union (latest block.gen), (diff block.in, block.kill)
table.insert modified, (diff out, block.out)
フ〜ム…解説します｡
-
block.genCFGの要素のブロック
blockで新たに生成される定義の集合｡これはプログラムの代入文から明らか｡ -
block.inblockの入り口に到達する定義の集合｡ 後続ブロックblock.predの各要素pについてp.outの和集合となる｡ -
block.killblockに到達したが､ブロック中で無効になる､つまりブロック中で新たな代入により不要になるものの集まり｡block.inとblock.genのintersectionを取ればいいわけだな｡ -
block.outブロックの出口に到達する定義の集合｡ (
block.inとblock.killの差集合)とblock.genの和集合とすればいいか｡ここで一つ､例えば変数
xへの代入が同一ブロック中に2回あったらちょっと困る｡そこで､最新の
xへの代入(つまりブロック内で最後に実行されるxへの代入)のみに注目し､他は無視することで対処する (関数latest())｡
で､それを各ブロックのblock.outの変更がなくなるまで繰り返しておりますわけですな｡
これでCFGにReachable Definitionをくっつけた感じになりました｡
4. DU Chainの構成
さてここまでくれば後は簡単｡かも｡
今の所CFG'に定義の集合block.defが無く､block.defから使用をたどるといったギミックがありません｡
逆にこの2つを実装するとゴールです｡がんばります｡
for i = 1, #cfg
block = cfg[i]
block.def = union block.gen, block.in
for u = 1, #block.use
use = block.use[u]
use.defined = {}
if defr = last latest filter ((g) -> g.line < use.line and g.reg == use.reg), block.gen
insert use.defined, defr unless have use.defined, defr
unless defr.used
defr.used = {use}
else
insert defr.used, use unless have use.defined, use
else
for defr in *(filter ((i) -> i.reg == use.reg), block.in)
insert use.defined, defr unless have use.defined, defr
unless defr.used
defr.used = {use}
else
insert defr.used, use unless have defr.used, use
まず3行目でblock.defを作ります｡Define-UseのDefineです｡block.egnとblock.inのunionというのは直感で分かると思います｡
さて､あとはこのdefからuseがわかればOKとなりました｡早い｡
中のイテレーションでblock.useから定義をたどるギミックを作ります｡
イテレーションした各blockのuseのメンバーにdefinedを生やし､使用しているレジスターの定義を突っ込んでいきます｡
まずblock内での定義を探します｡
ここでblock.defから探さないのはなぜかというと､そうですね､block内(直近)での定義がもちろん最優先なので｡
block内のさらに直近を最優先するのでlatest()でuseに最も近い定義を拾います｡かぶりがないように(unless have ......)use.definedに突っ込みます｡
block内に定義が無い場合はblock.inから定義全部引っ張ります｡
use.definedを基にdef.usedを作ります｡これは簡単ですね｡
use.definedの各構成ステップでuse自体を､useが引っ張ってくるdefrのdefr.usedに突っ込めばいいわけですから｡ポインター最高!!!!! :p
あれ? 定義から使用も､使用から定義も参照できるようになってるな…
これで欲しかったものが手に入りました( 5)による整形)｡
{ <1>{
def = { <2>{
line = 1,
reg = 0,
used = { <3>{
defined = { <table 2> },
line = 4,
reg = 0
}, <4>{
defined = { <table 2> },
line = 9,
reg = 0
} }
}, {
line = 2,
reg = 1,
used = {}
}, <5>{
line = 3,
reg = 1,
used = { <6>{
defined = { <table 5> },
line = 4,
reg = 1
} }
} },
end = 4,
pred = {},
start = 1,
succ = { <7>{
def = { <table 2>, <table 5> },
end = 5,
pred = { <table 1> },
start = 5,
succ = { <8>{
def = { <9>{
line = 8,
reg = 2,
used = {}
}, <table 2>, <table 5> },
end = 8,
pred = { <table 7> },
start = 8,
succ = { <10>{
def = { <11>{
line = 6,
reg = 2,
used = {}
}, <table 2>, <table 5>, <table 9> },
end = 9,
pred = { <12>{
def = { <table 11>, <table 2>, <table 5> },
end = 7,
pred = { <table 1> },
start = 6,
succ = { <table 10> },
use = {}
}, <table 8> },
start = 9,
succ = {},
use = { <table 4> }
} },
use = {}
} },
use = {}
}, <table 12> },
use = { <table 3>, <table 6> }
}, <table 7>, <table 12>, <table 8>, <table 10> }
5. おわりに
それでは皆さんもガンガン最適化をしていってください｡ ちなみに､現在鋭意製作中の最適化器を用いると､例は以下のように最適化されます｡
JMP 0 0
RETURN 0 1
そうだね…｡
『Vivid Strike!』8話までイッキ見しましたが面白いですね｡今季は他に何もアニメを観てない｡
-
Dibyendu Majumdar. Lua 5.3 Bytecode Reference ↩
-
Kein-Hong Man. A No-Frills Introduction to Lua 5.1 VM Instructions ↩
-
中田 育男, 佐々木 正孝, 滝本 宗宏, 渡邉 担. コンパイラの基盤技術と実践―コンパイラ・インフラストラクチャCOINSを用いて ↩
-
Zdenek Dvorák, Jan Hubicka, Pavel Nejedlý, Josef Zlomek. Control Flow Graph - Infrastructure for Profile Driven Optimizations in GCC Compiler ↩
-
Enrique Garcíao. inspect.lua ↩