Opeth,

Lua VM Bytecode Optimizer

NymphiumFebruary 12, 2017 at tsukuba.lua

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Introこんにちは、びしょ〜じょです。
I ここの大学に 4 年滞在中の 3 年生
I Lua/MoonScript をよく書く
I ライトなメタラー

Intro

1/37

• 流れ

1. tsukuba.pm というイベントで Lua のバイトコード解析 *1
2. あまり最適化されてないことが判明
3. optimizer 作るか

*1

Intro

http://nymphium.github.io/pdf/tsukubapm3-luavm.html

2/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Lua is . . . . . .
弱い動的型付けなスクリプト言語
I 文法が簡単、予約語も 22 個と少ない
I

Intro.Lua is . . . . . .

3/37

•Lua is . . . . . .
弱い動的型付けなスクリプト言語
I 文法が簡単、予約語も 22 個と少ない
I 関数がファーストクラス
I

I

Intro.Lua is . . . . . .

ナウい関数型プログラミングも可能

3/37

•Lua is . . . . . .
弱い動的型付けなスクリプト言語
I 文法が簡単、予約語も 22 個と少ない
I 関数がファーストクラス
I

I

I

ナウい関数型プログラミングも可能

唯一のデータ構造 table

簡単に言うと連想配列
I オブジェクトは全部キーにも要素にもI メタテーブルで色々拡張
I

Intro.Lua is . . . . . .

3/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Implementations

I(PUC-Lua)
I
I

I

I

I

リオデジャネイロ･カトリカ大学開発の、いわゆる本家
軽量、組み込みで広く活躍

LuaJITI

だいぶ速い。FFI モジュールなども提供

I

JVM 実装。

LuaJ、Rembulan
その他色々

Intro.Implementations

4/37

•Implementations

I(PUC-Lua)
I
I

I

I

I

リオデジャネイロ･カトリカ大学開発の、いわゆる本家
軽量、組み込みで広く活躍

LuaJITI

だいぶ速い。FFI モジュールなども提供

I

JVM 実装。

LuaJ、Rembulan
その他色々

Intro.Implementations

4/37

•Implementations
その他
I llixI

I

TypedLua
I
I

I

I

I

拙作。例外処理構文を追加
型アノテーション、型定義ファイルなど。トランスパイラ
GSoC で募集してたり *2

Ravi
I

LLVM+Lua の文法+α。別言語

I

multi-stage programming

Terra

MoonScript
I

altLua 的なモノ。

*2
https://summerofcode.withgoogle.com/archive/2016/organizations/4733835644239872/
Intro.Implementations

5/37

•Implementations
その他
I llixI

I

TypedLua
I
I

I

I

I

拙作。例外処理構文を追加
型アノテーション、型定義ファイルなど。トランスパイラ
GSoC で募集してたり *2

Ravi
I

LLVM+Lua の文法+α。別言語

I

multi-stage programming

Terra

MoonScript
I

altLua 的なモノ。ちょっとコントリビュート*2
https://summerofcode.withgoogle.com/archive/2016/organizations/4733835644239872/
Intro.Implementations

5/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•About Lua VM

PUC-Lua
I レジスターベース (Lua 5.0〜)
I 関数呼び出しはレジスターウィンドウI 47 個の命令 (Lua 5.3)
I

Intro.About Lua VM

6/37•IntroLua VM, register-based Virtual Machine
Lua source

Intro.About Lua VM

compilebytecode(run on the VM)

7/37

•IntroLua VM, register-based Virtual Machine
Lua source

Intro.About Lua VM

compilebytecode(run on the VM)

7/37

•IntroLua VM, register-based Virtual Machine
Lua sourcecompilebytecode

積極的に最適化が行われない
1
2
3

Intro.About Lua VM

local x = 3
local y = 5
print(x + y)1
2
3⇒
compile 4
5
6(run on the VM)

LOADK
0
LOADK
1
GETTABUP 2
ADD
3
CALL
2
RETURN
0

0
1
0
0
2
1

-3
1
1

7/37

•IntroLua VM, register-based Virtual Machine
Lua sourcecompilebytecode

積極的に最適化が行われない
1
2
3

local x = 3
local y = 5
print(x + y)

1 LOADK
0
2 LOADK
1
3
GETTABUP
2⇒
3
compile 4 ADD
5CALL
2
コンパイル時に値が ↑6 RETURN
0

分かる (定数化可能)
Intro.About Lua VM(run on the VM)

0
1
0
0
2
1

-3
1
1

7/37

•IntroLua VM, register-based Virtual Machine
Lua sourcecompilebytecode(run on the VM)

足し算の結果が分かれば積極的に最適化が行われない
1 LOADK
この定数はいらない →12
3

local x = 3
local y = 5
print(x + y)

分かる (定数化可能)
Intro.About Lua VM

0

2 LOADK
1
3 GETTABUP 2⇒
3
compile 4 ADD
5CALL
2
コンパイル時に値が ↑6 RETURN
0

0
1
0
0
2
1

-3
1
1

7/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•OpethQ. Do you know a metal band, Opeth ?

Opeth

8/37

•OpethQ. Do you know a metal band, Opeth ?

Figure: Opeth、新譜出すってよ
Opeth

8/37

•Opeth
つくった optimizer

Opeth
https://github.com/Nymphium/opeth*3
I 『情報特別演習 II』という通年の講義で制作
I コマンドラインから使用可能
I モジュールとしても使える
I

*3

Opeth

http://www.coins.tsukuba.ac.jp/syllabus/GB13312_GB13322.html

9/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendixデモOpeth.Demo

10/37

•Demooptimizer = require'opeth.opeth'f = -> ......
......
g = optimizerf::::::::::::::::
g! -- wow

Opeth.Demo

11/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Architecture
analyzed databytecode

SourceControl
Flow Graph& DU ChainI

optimizer
Constant Folding

I

Constant PropagationI

Dead-code Elimination

I

Function Inlining

I

Unreachable Block Removal

I

Unused Resource Removal
optimized
bytecode

Implementation.Architecture

Figure: optimization image

12/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Bytecode

Lua VM 5.3 のバイトコードを操作したいImplementation.Bytecode⇒

バイトコードの document は
ない

13/37

•Bytecode

Lua VM 5.3 のバイトコードを操作したい⇒バイトコードの document はない⇒ 自分で読み解くしかない
Implementation.Bytecode

13/37

•Bytecode
有志の非公式ドキュメント
I Lua VM 5.3 instructions (bytecode ではない)*4
I Lua VM 5.1 reference*5*4https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst*5

http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf*6https://www.lua.org/source
Implementation.Bytecode

14/37

•Bytecode
有志の非公式ドキュメント
I Lua VM 5.3 instructions (bytecode ではない)*4
I Lua VM 5.1 reference*5
Lua VM bytecode を読むためのツール
I luac -l -l luac.out
I xxd -g 1 luac.out | nvim - -R

*4https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst*5

http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf*6https://www.lua.org/source
Implementation.Bytecode

14/37

•Bytecode
有志の非公式ドキュメント
I Lua VM 5.3 instructions (bytecode ではない)*4
I Lua VM 5.1 reference*5
Lua VM bytecode を読むためのツール
I luac -l -l luac.out
I xxd -g 1 luac.out | nvim - -R
I ソースコード *6*4https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst*5

http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf*6https://www.lua.org/source
Implementation.Bytecode

14/37

•Bytecode
有志の非公式ドキュメント
I Lua VM 5.3 instructions (bytecode ではない)*4
I Lua VM 5.1 reference*5
Lua VM bytecode を読むためのツール
I luac -l -l luac.out
I xxd -g 1 luac.out | nvim - -R
I ソースコード *6

気合

簡単に言うと*4

https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst*5

http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf*6https://www.lua.org/source
Implementation.Bytecode

14/37

•Bytecode

print("hello, world!")$ luac -l -l luac.out
main <hello.lua:0,0> (4 instructions at
0x16e79e0)0+ params, 2 slots, 1 upvalue, 0 locals,
2 constants, 0 functions
1 [1] GETTABUP 0 0 -1 ; _ENV "print"
2 [1] LOADK
1 -2 ; "hello, world!"
3 [1] CALL
0 2 1
4 [1] RETURN
0 1
constants (2) for 0x16e79e0:
1 "print"
2 "hello, world!"
locals (0) for 0x16e79e0:
upvalues (1) for 0x16e79e0:0 _ENV 1
0

Implementation.Bytecode

15/37

•Bytecode

print("hello, world!")$ luac -l -l luac.out
main <hello.lua:0,0> (4 instructions at
0x16e79e0)0+ params, 2 slots, 1 upvalue, 0 locals,
2 constants, 0 functions
1 [1] GETTABUP 0 0 -1 ; _ENV "print"
2 [1] LOADK
1 -2 ; "hello, world!"
3 [1] CALL
0 2 1
4 [1] RETURN
0 1
constants (2) for 0x16e79e0:
1 "print"
2 "hello, world!"
locals (0) for 0x16e79e0:
upvalues (1) for 0x16e79e0:0 _ENV 1
0

Implementation.Bytecode$ xxd -g 1 luac.out
00000000: 1b 4c 75 61 53 00 19 93 0d 0a 1a 0a 04 08 04 08 .LuaS...........
00000010: 08 78 56 00 00 00 00 00 00 00 00 00 00 00 28 77 .xV...........(w00000020: 40 01 0b 40 68 65 6c 6c 6f 2e 6c 75 61 00 00 00 @..@hello.lua...
00000030: 00 00 00 00 00 00 02 02 04 00 00 00 06 00 40 00 ..............@.
00000040: 41 40 00 00 24 40 00 01 26 00 80 00 02 00 00 00 A@..$@..&.......
00000050: 04 06 70 72 69 6e 74 04 0e 68 65 6c 6c 6f 2c 20 ..print..hello,
00000060: 77 6f 72 6c 64 21 01 00 00 00 01 00 00 00 00 00 world!..........
00000070: 04 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00 ................
00000080: 01 00 00 00 00 00 00 00 01 00 00 00 05 5f 45 4e ............._EN
00000090: 56
V

15/37

•Bytecode

print("hello, world!")$ luac -l -l luac.out
main <hello.lua:0,0> (4 instructions at
0x16e79e0)0+ params, 2 slots, 1 upvalue, 0 locals,
2 constants, 0 functions
1 [1] GETTABUP 0 0 -1 ; _ENV "print"
2 [1] LOADK
1 -2 ; "hello, world!"
3 [1] CALL
0 2 1
4 [1] RETURN
0 1
constants (2) for 0x16e79e0:
1 "print"
2 "hello, world!"
locals (0) for 0x16e79e0:
upvalues (1) for 0x16e79e0:0 _ENV 1
0

Implementation.Bytecode$ xxd -g 1 luac.out
00000000: 1b 4c 75 61 53 00 19 93 0d 0a 1a 0a 04 08 04 08 .LuaS...........
00000010: 08 78 56 00 00 00 00 00 00 00 00 00 00 00 28 77 .xV...........(w00000020: 40 01 0b 40 68 65 6c 6c 6f 2e 6c 75 61 00 00 00 @..@hello.lua...
00000030: 00 00 00 00 00 00 02 02 04 00 00 00 06 00 40 00 ..............@.
00000040: 41 40 00 00 24 40 00 01 26 00 80 00 02 00 00 00 A@..$@..&.......
00000050: 04 06 70 72 69 6e 74 04 0e 68 65 6c 6c 6f 2c 20 ..print..hello,
00000060: 77 6f 72 6c 64 21 01 00 00 00 01 00 00 00 00 00 world!..........
00000070: 04 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00 ................
00000080: 01 00 00 00 00 00 00 00 01 00 00 00 05 5f 45 4e ............._EN
00000090: 56
V

???
15/37

•Bytecode

1b 4c 75 61 53 00 19 93 0d 0a 1a 0a 04 08 04 08
08 78 56 00 00 00 00 00 00 00 00 00 00 00 28 77
40 01 0b 40 68 65 6c 6c 6f 2e 6c 75 61 00 00 00
00 00 00 00 00 00 02 02 04 00 00 00 06 00 40 00
41 40 00 00 24 40 00 01 26 00 80 00 02 00 00 00
04 06 70 72 69 6e 74 04 0e 68 65 6c 6c 6f 2c 20
77 6f 72 6c 64 21 01 00 00 00 01 00 00 00 00 00
04 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 00 00 00 00 01 00 00 00 05 5f 45 4e
56

Implementation.Bytecode

16/37

•Bytecode
header block
1b 4c 75 61 53 00 19 93 0d 0a 1a 0a 04 08 04 08
08 78 56 00 00 00 00 00 00 00 00 00 00 00 28 77
40 01 0b 40 68 65 6c 6c 6f 2e 6c 75 61 00 00 00
00 00 00 00 00 00 02 02 04 00 00 00 06 00 40 00
41 40 00 00 24 40 00 01 26 00 80 00 02 00 00 00
04 06 70 72 69 6e 74 04 0e 68 65 6c 6c 6f 2c 20
77 6f 72 6c 64 21 01 00 00 00 01 00 00 00 00 00
04 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 00 00 00 00 01 00 00 00 05 5f 45 4e
56

Implementation.Bytecode

16/37

•Bytecode
header block
1b 4c 75 61 53 00 19 93 0d 0a 1a 0a 04 08 04 08
08 78 56 00 00 00 00 00 00 00 00 00 00 00 28 77
40 01 0b 40 68 65 6c 6c 6f 2e 6c 75 61 00 00 00
00 00 00 00 00 00 02 02 04 00 00 00 06 00 40 00
41 40 00 00 24 40 00 01 26 00 80 00 02 00 00 00
04 06 70 72 69 6e 74 04 0e 68 65 6c 6c 6f 2c 20
77 6f 72 6c 64 21 01 00 00 00 01 00 00 00 00 00
04 00 00 00 01 00 00 00 01 00 00 00 01 00 00 00
01 00 00 00 00 00 00 00 01 00 00 00 05 5f 45 4e56function block

Implementation.Bytecode

16/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Dataﬂow analysis

I

Control Flow Graph (CFG)
I

I

プログラムの流れをグラフで表したもの

Deﬁne-Use / Use-Deﬁne Chain (DU/UD Chain)
I
I

変数の定義、使用を調べる
役割としては SSA、A 正規形

Implementation.Dataﬂow analysis

17/37

•Dataﬂow analysis
local b = true
if b thenprint("hello")
else
print"world"
end

Implementation.Dataﬂow analysis

18/37

•Dataﬂow analysis
local b = true
if b thenprint("hello")
else
print"world"
end⇓
LOADBOOLTESTJMPGETTABUP
LOADK
CALL
JMP
GETTABUPLOADKCALL
RETURN

0
0
0
1
2
1
0
1
2
1
0

1
0
4
0
1
2
3
0
2
2
1

0

-1
1
-1
1

Implementation.Dataﬂow analysis

18/37

•Dataﬂow analysis
local b = true
if b thenprint("hello")
else
print"world"
end

main_b1: [1 ~ 2]
1: LOADBOOL
0
1
2: TEST00

main_b2: [3 ~ 3]
3: JMP
0
4⇓
LOADBOOLTESTJMPGETTABUP
LOADK
CALL
JMP
GETTABUPLOADKCALL
RETURN

0
0
0
1
2
1
0
1
2
1
0

0
0

1
0
4
0
1
2
3
0
2
2
1

0

-1
1
-1
1

Implementation.Dataﬂow analysis⇒
main_b4: [8 ~ 10]
8: GETTABUP
1
0
9: LOADK
2
2
10: CALL12-1
1

main_b3: [4 ~ 7]
4: GETTABUP
1
0
5: LOADK
2
1
6: CALL
1
2
7: JMP03

main_b5: [11 ~ 11]
11: RETURN
0
1

-1
1

0
18/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Optimizations

Constant Folding
I Constant Propagation
I Dead-Code Elimination
I Function Inlining
I Unreachable Block Removal
I Unused Resource Removal
I

Implementation.Optimizations

19/37

•Constant Folding

1. 演算命令のオペランドの型を調べて
2. table、userdata以外なら3. 値を取ってきて4. 演算をおこない
5. 即値命令に swap

Implementation.Optimizations

20/37

•Constant Folding

1. 演算命令のオペランドの型を調べて
2. table、userdata以外なら3. 値を取ってきて4. 演算をおこない
5. 即値命令に swap

Implementation.Optimizations

20/37

•Constant Folding

1. 演算命令のオペランドの型を調べて
2. table、userdata以外なら ⇐ メタメソッドを考慮
3. 値を取ってきて4. 演算をおこない
5. 即値命令に swap

Implementation.Optimizations

20/37

•Constant Propagation

1. MOVE命令が参照してる register の定義位置を見て
2. LOADKなら MOVEを LOADKにする

Implementation.Optimizations

21/37

•Constant Propagation

1. MOVE命令が参照してる register の定義位置を見て
2. LOADKなら MOVEを LOADKにする
単体では速度改善なさそう
I LOADKへの依存が減るので、他の最適化を有利に進められる
I

Implementation.Optimizations

21/37

•Constant Propagation

1. MOVE命令が参照してる register の定義位置を見て
2. LOADKなら MOVEを LOADKにする
単体では速度改善なさそう
I LOADKへの依存が減るので、他の最適化を有利に進められる(今回の実装では) いまいちぱっとしない
I

Implementation.Optimizations

21/37

•Dead-Code Elimination

1. LOADK、MOVE、CLOSURE、LOADNILが生成する registr の使用を調べ
2. 0 個の場合命令を消す

Implementation.Optimizations

22/37

•Dead-Code Elimination

1. LOADK、MOVE、CLOSURE、LOADNILが生成する registr の使用を調べ
2. 0 個の場合命令を消す
I

DU/UD Chain のわかりやすい使用例

Implementation.Optimizations

22/37

•Function Inlining
1. CALL命令が引っ張ってくる closure を見て
2. 再帰関数でなければ展開

Implementation.Optimizations

23/37

•Function Inlining
1. CALL命令が引っ張ってくる closure を見て
2. 再帰関数でなければ展開I

register window の使用を抑えられる

Implementation.Optimizations

23/37

•Function Inlining
1. CALL命令が引っ張ってくる closure を見て
2. 再帰関数でなければ展開
register window の使用を抑えられるI 実は頼みの綱I

Implementation.Optimizations

23/37

•Function Inlining
1. CALL命令が引っ張ってくる closure を見て
2. 再帰関数でなければ展開
register window の使用を抑えられるI 実は頼みの綱
I バグがヤバいアIImplementation.Optimizations

23/37

•Unreachable Block Removal

1. 後続ブロックを持たない基本ブロックを丸々削除
2. だけI

速くはならないがバイトコードのサイズ縮小に貢献

Implementation.Optimizations

24/37

•Unused Resource Removal

1. constant list、prototype list から不要なものを削除
2. だけI

速くはならないがバイトコードのサイズ縮小に貢献

Implementation.Optimizations

25/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Benchmark
local function pow(i)return i * iendlocal a = {}for i = 1, 10000000 do
a[i] = pow(i)endBenchmark26/37

•Benchmark
local function pow(i)return i * iendlocal a = {}for i = 1, 10000000 do
a[i] = pow(i)endBenchmark⇒......
FORPREP
MOVE
MOVE
CALL
SETTABLEFORLOOP......

2 4
6 0
7 5
6 2 2
1 5 6
2 -5

26/37

•Benchmark
local function pow(i)return i * iendlocal a = {}for i = 1, 10000000 do
a[i] = pow(i)end⇒......
FORPREP
MOVE
MOVE
CALL
SETTABLEFORLOOP......

2 4
6 0
7 5
6 2 2
1 5 6
2 -5

⇓
......
FORPREP
MOVE
MUL
MOVE
SETTABLEFORLOOP......
Benchmark

2 4
7 5
8 7 7
6 8
1 5 6
2 -5
26/37

•Benchmark
local function pow(i)return i * iendlocal a = {}for i = 1, 10000000 do
a[i] = pow(i)end⇒......
FORPREP
MOVE
MOVE
CALL
SETTABLEFORLOOP......

2 4
6 0
7 5
6 2 2
1 5 6
2 -5

⇓
......
FORPREP
MOVE
MUL
MOVE
SETTABLEFORLOOP......
Benchmark

2 4
7 5
8 7 7
6 8
1 5 6
2 -5
26/37

•Benchmark
local function pow(i)return i * iendlocal a = {}for i = 1, 10000000 do
a[i] = pow(i)end⇒......
FORPREP
MOVE
MOVE
CALL
SETTABLEFORLOOP......

2 4
6 0
7 5
6 2 2
1 5 6
2 -5

⇓
......
FORPREP
MOVE
MUL
MOVE
SETTABLEFORLOOP......
Benchmark

2 4
7 5
8 7 7
6 8
1 5 6
2 -5
26/37

•Benchmark
local function pow(i)return i * iendlocal a = {}⇒for i = 1, 10000000 do
a[i] = pow(i)end......
FORPREP
MOVE
MOVE
CALL
SETTABLEFORLOOP......

2 4
6 0
7 5
6 2 2
1 5 6
2 -5

⇓

1.4 倍の高速化
Benchmark⇐......
FORPREP
MOVE
MUL
MOVE
SETTABLEFORLOOP......

2 4
7 5
8 7 7
6 8
1 5 6
2 -5
26/37

ぶっちゃけ function inlining 以外微妙

もう少し何かいいケースがあればあるいは

Benchmark27/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Tools
今回のマズイ点
I ツールなさすぎ
I 気合では解決できない
I 興味が逸れる

Tools

28/37

•Tools
今回のマズイ点
I ツールなさすぎ
I 気合では解決できない
I 興味が逸れるツール制作で英気を養う 

Tools

28/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•lvis
これの描画ツール ⇒I ちょうど Graphviz の Luabinding(嘘)*7 作ってたI 目 grep から急速文明化
Imain_b1: [1 ~ 2]
1: LOADBOOL
0
1
2: TEST00

00

main_b2: [3 ~ 3]
3: JMP04

main_b4: [8 ~ 10]
8: GETTABUP
1
0
9: LOADK
2
2
10: CALL12-1
1

main_b3: [4 ~ 7]
4: GETTABUP
1
0
5: LOADK
2
1
6: CALL
1
2
7: JMP03

main_b5: [11 ~ 11]
11: RETURN
0
1

-1
1

0

Figure: visualise で小学生にも人気*7
https://github.com/Nymphium/lua-graphviz
Tools.lvis

29/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•moonstep

step-by-step execution Lua VM
I gdb を目指した
I つい最近関数呼び出し内を追えるようにI

Tools.moonstep

30/37

•moonstep

step-by-step execution Lua VM
I gdb を目指した
I つい最近関数呼び出し内を追えるように
もっとまともなデバッグツール出してほしい
I

Tools.moonstep

30/37

デモ

Tools.moonstep

31/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•lasmc

アセンブリみたいに Lua VM の命令を書きたいという願い
I いろいろ機能をたそうとしたら構
文がごちゃごちゃになってやる気 0
I 意外にもデバッグに貢献
I

Tools.lasmc

main: 0 2
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 2LOADK 2 2 -- load `7`
JMP 0 1LOADK 2 3 -- load `9`
RETURN 0 1{3 5 7 9} -- constant list

32/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•Conclusion
I

最適化器の実装
I
I

I

しんどかったI

I

一部高速化に成功
バイトコードの縮小化もぼちぼち

課題II

ドキュメントは書こう
他の最適化も取り入れたい (for 展開とか)最適化器の最適化!
I

Conclusion

アルゴリズムが適当すぎ

33/37

Opeth, Lua VM Bytecode Optimizer
Intro
Lua is . . . . . .
Implementations
Other

About Lua VM
Opeth
Demo
Implementation
Architecture
Bytecode
Dataﬂow analysis
Control Flow Graph

Optimizations

Constant Folding
Constant Propagation
Dead-Code Elimination
Function Inlining
Unreachable Block Removal
Unused Resource Removal

Benchmark
Tools
lvis
moonsteplasmc
Conclusion
appendix•appendix I

I

font

the King 26 Queen*8*8
http://www.dfonts.net/the_King__26_Queen_font.font/20679/
appendix

34/37

•appendix I
Nullstone Corporation, Compiler optimizations,
http://www.compileroptimizations.com/.
Jason D. Davies, Optimizing lua, 2005,
https://www.jasondavies.com/optimising-lua/
JasonDaviesDissertation.pdf.
Ikuo Tanaka, Masataka Sasa, Munahiro Takimoto, and Tan
Watanabe, コンパイラの基盤技術と実践 –コンパイラ · インフラストラクチャ coins を用いて, 2008.
appendix

35/37

•appendix II
Dibyendu Majumdar, Lua 5.3 bytecode reference, http://the-ravi-programming-language.readthedocs.
io/en/latest/lua_bytecode_reference.html.
Kein-Hong Man, A no-frills introduction to lua 5.1 vm
instructions, 2006, http://luaforge.net/docman/83/
98/ANoFrillsIntroToLua51VMInstructions.pdf.
PUC Rio, source code for lua 5.3,
https://www.lua.org/source/5.3/.
appendix

36/37

•appendix III
Roberto Ierusalimuschy, Luiz Henrique de Figueiredo, andWaldemar Celes, The implementation of lua 5.0, 2003,
https://www.lua.org/doc/jucs05.pdf.
Michael Schroder, Optimizing lua using run-time typespecialization, 2012,https://www.complang.tuwien.ac.at/anton/
praktika-fertig/schroeder/thesis.pdf.

appendix

37/37