Cコンパイラの末尾呼び出しを活用した
効率的命令ディスパッチ手法の研究開発
クックパッド笹田耕一

概要• Context Threading という VM の高速化技術を試しています• C コンパイラによる末尾呼び出しの最適化をうまく活用できることを発見しました• けど、そんなにも性能は上がらなかった感じなので、Ruby 2.7には少なくとも入らないだろうな

背景
Ruby
scriptBundledLibraries

Parse

Gem
Libraries

Embeddedclasses and methods

AST
Abstract Syntax Tree

Compile(codegen)

Ruby
Bytecode(ISeq)

Threading

Evaluator

Objectmanagement
Garbage collector

Interpret on RubyVM
3

VM – スタックマシン
Ruby Program

a=b+cCompile

YARV Instructions

getlocalgetlocalsend
setlocal

b
c
:+, 1
a

a
b+c
b

c

c

b+c
b
YARV Stack

今日は、スタックマシンをたくさん使うよ。
4

Ruby Bytecode 実例
0000 putobject
0002 setlocal
0005 getlocal
0008 putobject
0010 send# Rubyscripta = 10
if a > 1
p :ok
else
p :ng
end

0014 branchunless0016 jump
0018 putself
0019 putobject
0021 send

0025 jump
0027 putself
0028 putobject
0030 send
0034 leave

10
a, 0
a, 0
1
<callinfo!mid:>, argc:1, ARGS_SIMPLE>,<callcache>, nil
27
18
:ok
<callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>,<callcache>, nil
34:ng<callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>,<callcache>, nilスタックマシンの実行を解説
番地0000 putobject
0002 setlocal
0005 getlocal
0008 putobject
0010 send0014 branchunless0016 jump
0018 putself
0019 putobject
0021 send

0025 jump
0027 putself
0028 putobject
0030 send
0034 leave

スタックの状況（空でスタート）
解説
10
#
[10]
a, 0 #[]
a, 0 #[10]
1#[10, 1]<callinfo!mid:>, argc:1, ARGS_SIMPLE>,<callcache>, nil#[true]
27
#
[]
18
#
[]
#
[self]:ok #[self, :ok]<callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>,<callcache>, nil
#
[:ok]
34
#
[:ok]
:ng
<callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>,<callcache>, nil# []スタックに 10 をプッシュ
a にスタックトップの 10
a の値をスタックにプッシ
1 をスタックにプッシュ10.>(1) というメソッド呼び出し
その結果（true）をプッシュ
スタックトップの値が fa
無条件に 18 へジャンプ
self をスタックへプッシュ:ok をスタックへプッシュp(:ok) を実行
結果の :ok をスタックにプッシュ
無条件に 34 へジャンプ

このコードを終了する（積んであった

すべての計算が、「スタックから値を取り出し」、「スタックに積む」ことで実現されていることがわかればOKバイトコードをどう実行するか？
C の switch/case による素直な実装（code[i] に命令番号が入っているとする）
while (1) {switch (code[pc]) {# 命令を取り出す
case insnA:# switch/case で分岐
do_A();# 命令を実行break;# 最初に戻るcase insnB: do_B(); break;…
}}素直な方法の問題点• 命令を取り出す（フェッチ）• switch/case で分岐• 分岐先を調べるのに時間がかかる• 間接分岐で遅い（分岐予測が効きづらい）• 命令を実行• ここはどうやってしょうがない• 最初に戻る• 分岐アドレス同一化→ BTB を汚す可能性

CPU の用語• メモリキャッシュ• 命令キャッシュ
• 分岐予測• BTB (Branch Target Buffer)Direct Threading (DT)・code[i] に命令番地（&&label, gcc 拡張）が入っているとする
・つまり、事前に命令番号の列→命令番地の列へ変換が必要
insnA:
do_A();
goto *code[pc];insnB:
do_B();
goto *code[pc];}# 命令を実行# 次の命令番地をフェッチ# 次の命令番地に間接ジャンプ#
jmp *$rax 1命令

DTの利点と問題点• 命令を実行• 次の命令番地をフェッチ• Good: 次の分岐先番地を調べるコストが0• 次の命令番地に間接ジャンプ• Good: 複数の場所で間接ジャンプするので、BTBを汚さない可能性増• Bad: 間接ジャンプなので分岐予測が効きづらいContext Threading (CT)• Marc Berndl, et.al.: Context Threading: A Flexible andEfficient Dispatch Technique for Virtual Machine Interpreters(2005)• 命令番号の列を、call A, call B, … という、実際に動作する機械語列（ネイティブコード）に変換しておく• 機械語ちょっとした JIT みたいなもの• いわゆるJITとは違い、それ以外の最適化はあまりしない• なお、このテクニックだけだと、Subroutine Threading (ST) という

CT の前提の ST
Bytecode

Generated
native code

A
B
C
C
A

call doA
call doB
call doC
call doC
call doA

事前に変換

call
returndoA(){…
}

call
returndoB(){…
}
doC(){…
}

STの良いところ・悪いところ• Good: ほとんどアセンブラを書かなくても良い• Good: 間接ジャンプがないので、分岐予測が外れない• 厳密には return が間接ジャンプ（stack 上に保存された戻り番地へのジャンプ）だが、たいていは専用ハードウェアによりキャッシュされるのでノーペナルティ• Good: 命令を増やしても命令キャッシュミスに悩まされない！

• Bad: 間接ジャンプはまだまだある• VM上命令で分岐した場合• VM上命令で関数（メソッド）呼び出した場合• → そういうのも全部ジャンプ先埋め込んじゃおう！

→ 全部埋め込んだやつが CT （今回はあまり触れません）

STの良いところ・悪いところ• Bad: goto $reg よりも call/ret は遅いIntel Skylake

https://www.agner.org/optimize/instruction_tables.pdf より一部抜粋

ST の悪いと思っていたところ• 命令の実体（doA() など）に、どうやって情報を伝えるか？
• 例えば、スタックポインタなどはどうやって伝えるか？
• Ruby では、ec, cfp, pc, sp など4要素が対象• ただし、cfp->pc, cfp->sp のようにすることで2要素に縮約可能（実際、今はそうしている）• 素直にやるなら引数だが、call doA 命令の前に、毎回引数をセットアップするのか？
• グローバル変数を使う？→スレッドで使えない• スレッドローカル変数 (TLS) を使う？→実は TLS は凄く遅い• この問題がよくわからないので、使えなかった末尾呼び出しを利用したSTの実現• 素直に、doA(ec, cfp) と呼び出したらどうなるか on x86_64• call 前に、引数をセットアップ• $rdi ← ec # 第一引数
• $rsi ← cfp # 第二引数
• call doA• $rdi ← ec # 第一引数
• $rsi ← cfp # 第二引数
• call doB• …

• さすがに同じことやるの無駄じゃないの？

doA(ec, cfp) {ec, cfp を使ってなにかする}末尾呼び出しを利用したSTの実現• なんとかならない？
• もし、doA() 内部で $rdi, $rsi のレジスタを、触らなければ…？
• $rdi ← ec # 第一引数
• $rsi ← cfp # 第二引数
• call doA• call doB• …

doA(ec, cfp) {ec, cfp を使ってなにかする}• しかし、$rdi, $rsi は破壊してもよいことになっている→ NG• なんとかならないか…？

末尾呼び出しを利用したSTの実現• 関数の最後に、$rdi, $rsi を再設定してくれれば良いのでは？
• doA(), doB() の定義をこんな感じにすればできる• $rdi ← ec # 第一引数
• $rsi ← cfp # 第二引数
• call doA• call doB• …

• C で、これどうやって実現しよう？

doA(ec, cfp) {ec, cfp を使ってなにかする$rdi = ec; $rsi = cfp;
return;}末尾呼び出しを利用したSTの実現• そこで末尾呼び出し！
• doA() の最後に tail(ec, cfp) を呼ぶ• $rdi ← ec # 第一引数
• $rsi ← cfp # 第二引数
• call doA• call doB• …

• 1. tail 呼び出しのために $rdi, $rsi がセッ
トアップされる• 2. tail では何もせずに返るため、$rdi, $rsi
がセットアップされて戻る• できた！

doA(ec, cfp) {ec, cfp を使ってなにかする
return tail(ec, cfp);}
tail(ec, cfp) {// 何もしない
return;}末尾呼び出しを利用したSTの実現• 疑問点：call/return が増えて遅くなるんで doA(ec, cfp) {は？
ec, cfp を使ってなにかする• gcc -O3 だと、末尾呼び出しの最適化により、
jmp tail になる（call doA()→ jmp tail → ret）

• 疑問点：jmp tail が一個余計に入るんでは？
• そう。なので、dynamic に jmp tail 命令を、
ret に書き換えることも可能• 疑問点：何もしない tail って inline 化されちゃうんでは？
• されちゃう。ので、別コンパイル単位（別ファイル）におく必要がある$rdi = ec; $rsi = cfp;
return tail(ec, cfp);}
tail(ec, cfp) {// 何もしない
return;}Generated
native code

call doA
call doB
call doC
call doC
call doA

call

A(*ec, *cfp) {// A body, dirty parameter regs
tail(ec, cfp); // setup regs and jump
}

ret

NOTE:
Most of case, tailcall
will be “jump” CPU insn

tail(*ec, *cfp) {// empty → A function only has “ret”}

末尾呼び出しを利用したSTの実現• 疑問点：本当に動くの？
• 動いた！

が、罠がいくつかあった• 罠：-fstack-protector-strong• スタックが壊れてないかチェックする機構• なんと、$rsi を関数から返るときに破壊→ このオプションとは共存できない

doA(ec, cfp) {ec, cfp を使ってなにかする$rdi = ec; $rsi = cfp;
return tail(ec, cfp);}
tail(ec, cfp) {// 何もしない
return;}末尾呼び出しを利用したST
実装の工夫• pc, sp をレジスタに• x86_64 のABIでは、レジスタ渡しに 6 レジスタまで利用可能• ec, cfp, pc, sp をレジスタに# DTでの nop
0x5555557dc870 <vm_exec_core+1888>:
0x5555557dc874 <vm_exec_core+1892>:
0x5555557dc877 <vm_exec_core+1895>:
0x5555557dc87a <vm_exec_core+1898>:
0x5555557dc87d <vm_exec_core+1901>:# ST での nop
call insn_func_nop…
00000000000013e0 <insn_func_nop>:
13e0:
48 83 c2 08
13e4:
e9 00 00 00 00…
000000000001a830 <rb_insn_tail>:
1a830:
f3 c3

lea
mov
mov
mov
jmpq

0x8(%r14),%rdx # PC (cfp->pc) の操作%r14,%rax%rdx,(%r15)%rdx,%r14*0x8(%rax)# 次の命令にadd
jmpq$0x8,%rdx
rb_insn_tail

repz retq# PC の操作

末尾呼び出しを利用したST
実装の工夫• いくつかの命令を call ではなく直接埋め込み

末尾呼び出しを利用したST
実装の工夫• 命令の追加• いままでは、ある命令の中で型ごとに分岐• 命令を増やしてもあまりペナルティはなさそうなので、型ごとに命令を分岐（実験のために、特定の型だけを想定）

末尾呼び出しを利用したST
実装の工夫• いくつかの簡単な命令をインライン化• call/return が不用• Cで関数をコンパイル→貼り付け#if USE_SUBR_OPTIMIZE
case BIN(putobject):{
VALUE obj = orig_iseq[i+1];
if ((int32_t)obj == (int64_t)obj) {if ((int32_t)obj >= 0) {unsigned char mov_to_eax[5] = {0xb8, 0, 0, 0, 0, // mov $0x??,%eax};((int32_t*)&mov_to_eax[1])[0] = (int32_t)obj;
j += emit_code(&encoded[j], mov_to_eax, sizeof(mov_to_eax));}
else {
unsigned char mov_to_rax[7] = {0x48, 0xc7, 0xc0, // mov $0x??,%rax};((int32_t*)&mov_to_rax[3])[0] = (int32_t)obj;
j += emit_code(&encoded[j], mov_to_rax, sizeof(mov_to_rax));}}
else {
unsigned char mov_to_rax[10] = {0x48, 0xb8, // movabs $0x??, %rax};((VALUE *)&mov_to_rax[2])[0] = obj;
j += emit_code(&encoded[j], mov_to_rax, sizeof(mov_to_rax));}
const unsigned char code[] = {0x48, 0x83, 0xc1, 0x08,// add $0x8,%rcx0x48, 0x83, 0xc2, 0x10,// add $0x10,%rdx
0x48, 0x89, 0x41, 0xf8,// mov %rax,-0x8(%rcx)};
j += emit_code(&encoded[j], code, sizeof(code));}break;#endif#if USE_SUBR_OPTIMIZE
case BIN(getlocal_WC_0):{
unsigned long idx = (unsigned long)orig_iseq[i+1];
if (idx >= 3 && idx < 10) {unsigned char idx_code = 0 - 8 * idx;
const unsigned char code[] = {0x48, 0x8b, 0x46, 0x20,// mov 0x20(%rsi),%rax0x48, 0x83, 0xc1, 0x08,// add $0x8,%rcx0x48, 0x83, 0xc2, 0x10,// add $0x10,%rdx
0x48, 0x8b, 0x40, idx_code,// mov ?? (%rax),%rax0x48, 0x89, 0x41, 0xf8,// mov %rax,-0x8(%rcx)};
j += emit_code(&encoded[j], code, sizeof(code));}else {
j += emit_call(&encoded[j], func_ptr);}}
break;#endif#if USE_SUBR_OPTIMIZE// simple copy instructions
case BIN(putself):{const unsigned char code[] = {0x48, 0x8b, 0x46, 0x18,// mov 0x18(%rsi),%rax0x48, 0x83, 0xc1, 0x08,// add $0x8,%rcx0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx
0x48, 0x89, 0x41, 0xf8,// mov %rax,-0x8(%rcx)};
j += emit_code(&encoded[j], code, sizeof(code));}break;
case BIN(nop):{
const unsigned char code[] = {0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx};
j += emit_code(&encoded[j], code, sizeof(code));}break;
case BIN(putnil):{const unsigned char code[] = {0x48, 0xc7, 0x01, 0x08, 0x00, 0x00, 0x00,// movq $0x8,(%rcx)
0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx
0x48, 0x83, 0xc1, 0x08,// add $0x8,%rcx};
j += emit_code(&encoded[j], code, sizeof(code));}break;
case BIN(pop):{
const unsigned char code[] = {0x48, 0x83, 0xe9, 0x08,// sub $0x8,%rcx0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx};
j += emit_code(&encoded[j], code, sizeof(code));}break;
case BIN(dup):{
const unsigned char code[] = {0x48, 0x8b, 0x41, 0xf8,// mov -0x8(%rcx),%rax0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx
0x48, 0x83, 0xc1, 0x08,// add $0x8,%rcx0x48, 0x89, 0x41, 0xf8,// mov %rax,-0x8(%rcx)};
j += emit_code(&encoded[j], code, sizeof(code));}break;
case BIN(swap):{
const unsigned char code[] = {0x48, 0x8b, 0x41, 0xf8,// mov -0x8(%rcx),%rax
0x4c, 0x8b, 0x41, 0xf0,// mov -0x10(%rcx),%r8
0x48, 0x83, 0xc2, 0x08,// add $0x8,%rdx
0x4c, 0x89, 0x41, 0xf8,// mov %r8,-0x8(%rcx)
0x48, 0x89, 0x41, 0xf0,// mov %rax,-0x10(%rcx)};
j += emit_code(&encoded[j], code, sizeof(code));}break;#endif

100行くらいのアセンブラ

評価：フィボナッチ
def fib n
if n < 2nelse
fib(n-1) + fib(n-2)
endend
fib(37)

Master
Proposal

実行時間 (s)1.13
0.85

876.550221

task-clock (msec)#

1.000 CPUs utilized

1249.288522

task-clock (msec)#

1.000 CPUs utilized2

context-switches#

0.002 K/sec

2

context-switches#

0.002 K/sec

0

cpu-migrations#

0.000 K/sec

0

cpu-migrations#

0.000 K/sec

page-faults#

0.002 M/sec

1,540

page-faults#

0.001 M/sec

3,230,313,777

cycles

#3.685 GHz

(30.18%)4,636,477,038

cycles

#3.711 GHz

(30.84%)

10,601,611,221

instructions

#

3.28

(37.94%)

12,375,549,381

instructions

#

2.67

(38.53%)

1,636,349,497

branches# 1866.806 M/sec(37.94%)

1,667,763,942

branches# 1334.971 M/sec(38.53%)branch-misses#(38.19%)11,676,347

branch-misses#(38.53%)

L1-dcache-loads# 3730.555 M/sec(38.65%)

4,165,508,205

L1-dcache-loads# 3334.304 M/sec(38.53%)

L1-dcache-load-misses#

0.01% of all L1-dcache hits

(38.79%)375,707

L1-dcache-load-misses#

0.01% of all L1-dcache hits

(38.42%)

LLC-loads#

0.006 M/sec(31.03%)

5,287

LLC-loads#

0.004 M/sec(30.74%)168

LLC-load-misses#

3.44% of all LL-cache hits

(31.03%)143

LLC-load-misses#

2.70% of all LL-cache hits

(30.74%)<not supported>

L1-icache-loads<not supported>

L1-icache-loads

1,546

2,892,903
3,270,018,693
377,713
4,882

81,7193,304,954,152

insn per cycle

0.18% of all branches

L1-icache-load-misses(31.03%)

143,364

dTLB-loads# 3770.410 M/sec(31.03%)

4,197,109,130

24,067dTLB-load-misses#

0.00% of all dTLB cache hits

(31.03%)

10

2,551

iTLB-loads#

0.003 M/sec(30.78%)76,943

1,194

iTLB-load-misses#

46.81% of all iTLB cache hits

(30.32%)670(30.74%)dTLB-loads# 3359.600 M/sec(30.74%)dTLB-load-misses#

0.00% of all dTLB cache hits

(30.74%)

iTLB-loads#

0.062 M/sec(30.74%)

iTLB-load-misses#

0.87% of all iTLB cache hits

(30.74%)

L1-dcache-prefetches<not supported>

L1-dcache-prefetches<not supported>

L1-dcache-prefetch-misses<not supported>

L1-dcache-prefetch-misses

1.249460020 seconds time elapsed

perf stat –ddd の結果
st <-> master

0.70% of all branches

L1-icache-load-misses<not supported>

0.876710034 seconds time elapsed

insn per cycle評価：Optcarrot• あるゲーム機のシミュレータ

Master
Proposal
Proposal+

FPS（高い方が速い）
46.4
52.4
53.0
そんなに速くない…

3842.746149

task-clock (msec)#

1.000 CPUs utilized

4331.488939

task-clock (msec)#

1.000 CPUs utilized

4

context-switches#

0.001 K/sec

5context-switches#

0.001 K/sec

0

cpu-migrations#

0.000 K/sec

0

cpu-migrations#

0.000 K/sec

page-faults#

0.005 M/sec

18,560page-faults#

0.004 M/sec

14,481,884,052

cycles

#3.769 GHz

(30.68%)16,369,051,211

cycles

#3.779 GHz

(30.73%)42,320,810,357

instructions

#

2.92

(38.38%)45,627,951,290

instructions

#

2.79

(38.49%)9,222,141,605

branches# 2399.883 M/sec(38.38%)8,307,968,885

branches# 1918.040 M/sec(38.58%)branch-misses#(38.41%)45,682,787

branch-misses#(38.67%)

L1-dcache-loads# 3334.759 M/sec(38.51%)

15,185,108,345

L1-dcache-loads# 3505.748 M/sec(38.68%)

L1-dcache-load-misses#

1.10% of all L1-dcache hits

(38.51%)

178,826,801

L1-dcache-load-misses#

1.18% of all L1-dcache hits

(38.61%)

LLC-loads#

0.773 M/sec(30.81%)

2,968,733

LLC-loads#

0.685 M/sec(30.76%)

287,856

LLC-load-misses#

9.69% of all LL-cache hits

(30.81%)

109,344

LLC-load-misses#

3.68% of all LL-cache hits

(30.67%)<not supported>

L1-icache-loads<not supported>

L1-icache-loads

18,70910,654,527
12,814,632,520
140,452,010
2,969,299

12,377,374
12,898,660,140

insn per cycle

0.12% of all branches

L1-icache-load-misses(30.81%)

3,856,244

dTLB-loads# 3356.626 M/sec(30.81%)

15,312,688,143

161,584dTLB-load-misses#

0.00% of all dTLB cache hits

(30.81%)

322,839

154,492

iTLB-loads#

0.040 M/sec(30.78%)64,487

iTLB-load-misses#

41.74% of all iTLB cache hits

(30.68%)

0.55% of all branches

L1-icache-load-misses(30.66%)

dTLB-loads# 3535.202 M/sec(30.66%)

dTLB-load-misses#

0.00% of all dTLB cache hits

(30.66%)2,422,832

iTLB-loads#

0.559 M/sec(30.66%)

1,449,688

iTLB-load-misses#

59.83% of all iTLB cache hits

(30.66%)<not supported>

L1-dcache-prefetches<not supported>

L1-dcache-prefetches<not supported>

L1-dcache-prefetch-misses<not supported>

L1-dcache-prefetch-misses

3.843336476 seconds time elapsed

insn per cycle

4.331753222 seconds time elapsed

perf stat –ddd の結果
st <-> master末尾呼び出しを利用したST実装の工夫 +
• jmp tail を、ret に書き換えてしまえばいいのでは？
→ 実行開始時に書き換えてしまおう# ST での nop
call insn_func_nop…
00000000000013e0 <insn_func_nop>:
13e0:
48 83 c2 08
13e4:
e9 00 00 00 00…
000000000001a830 <rb_insn_tail>:
1a830:
f3 c3# ST での nop +00000000000013e0 <insn_func_nop>:
13e0:
48 83 c2 08

add
jmpq

$0x8,%rdx
rb_insn_tail# PC の操作

repz retq

add
ret$0x8,%rdx# PC の操作未評価• まだバグが…
• icache が問題になりそうな大きいプログラムでは、まだ実行できていないので、真価が計れない末尾呼び出しを利用したST
問題点• 命令ボディから引数付き関数呼び出しをすると、ec等を保存しないといけない• → 関数 prologue, epilogue での待避・復帰のコストが大きい• → 致命的な問題• どうしようかなあ、どうにもならないかなぁ• レジスタの値を復帰する命令を指定する？
• global register variable を使う？（gcc 拡張）• callee save register を無理矢理増やす？（gcc 拡張）

末尾呼び出しを利用したST
問題点• メモリ管理• GC どうしよう• call 32bit 相対縛り

• pc, sp をレジスタに持たせた問題• バックトレース生成時に pc が必要だが…
• GC 時に sp が必要だが…

発展• Stack caching ときっと相性が良い• 命令をすごく増やしてちゃんと動くか検証したい• 費用対効果、あるのかなあ？

試すには• https://github.com/ko1/ruby/tree/subr_tailcall