はじめに
ZACKY こと山崎進です。
前回「ZEAM開発ログ v.0.4.0 型多相かつ型安全なNIFをC言語で書いてみる」から新シリーズということで，型多相で型安全なコード生成について検討しています。今回は生成された LLVM IR のコードを読み解いてみたいと思います。
LLVM とは
LLVM というのは，最近のプログラミング言語処理系のコード生成で広く使われているライブラリです。さまざまな種類のプロセッサのコード生成をすることができます。CPUだけじゃなくて，GPUなんかもできますよ。
LLVM で使われているコードが LLVM IR です。高級言語から LLVM IR に変換するコンパイラを作ってあげれば，LLVM がサポートする様々な種類のプロセッサにコード生成できるようになるので大変ありがたいです。
今回のコードはこちらの GitHub レポジトリに置いています。どうやって LLVM のコードを生成するのかについてはMakefileを読んでくださいね。
今回読み解くC言語のコード
元のC言語のプログラムはこちらです。
static
ERL_NIF_TERM asm_1_nif_ii(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
long a, b;
if(enif_get_int64(env, argv[0], &a) == 0) {
goto error;
}
if(enif_get_int64(env, argv[1], &b) == 0) {
goto error;
}
if(a > LONG_MAX - b) {
return error_atom;
}
long result = a + b;
return enif_make_int64(env, result);
error:
return arithmetic_error;
}
LLVM IR コード
LLVM IR にコンパイルするとこのようになります。
define internal i64 @asm_1_nif_ii(%struct.enif_environment_t*, i32, i64* nocapture readonly) #0 !dbg !152 {
%4 = alloca i64, align 8
%5 = alloca i64, align 8
call void @llvm.dbg.value(metadata %struct.enif_environment_t* %0, metadata !154, metadata !DIExpression()), !dbg !161
call void @llvm.dbg.value(metadata i32 %1, metadata !155, metadata !DIExpression()), !dbg !162
call void @llvm.dbg.value(metadata i64* %2, metadata !156, metadata !DIExpression()), !dbg !163
%6 = bitcast i64* %4 to i8*, !dbg !164
call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %6) #6, !dbg !164
%7 = bitcast i64* %5 to i8*, !dbg !164
call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %7) #6, !dbg !164
%8 = load i64, i64* %2, align 8, !dbg !165, !tbaa !107
call void @llvm.dbg.value(metadata i64* %4, metadata !157, metadata !DIExpression()), !dbg !167
%9 = call i32 @enif_get_long(%struct.enif_environment_t* %0, i64 %8, i64* nonnull %4) #6, !dbg !168
%10 = icmp eq i32 %9, 0, !dbg !169
br i1 %10, label %26, label %11, !dbg !170
; <label>:11: ; preds = %3
%12 = getelementptr inbounds i64, i64* %2, i64 1, !dbg !171
%13 = load i64, i64* %12, align 8, !dbg !171, !tbaa !107
call void @llvm.dbg.value(metadata i64* %5, metadata !159, metadata !DIExpression()), !dbg !173
%14 = call i32 @enif_get_long(%struct.enif_environment_t* %0, i64 %13, i64* nonnull %5) #6, !dbg !174
%15 = icmp eq i32 %14, 0, !dbg !175
br i1 %15, label %26, label %16, !dbg !176
; <label>:16: ; preds = %11
%17 = load i64, i64* %4, align 8, !dbg !177, !tbaa !107
call void @llvm.dbg.value(metadata i64 %17, metadata !157, metadata !DIExpression()), !dbg !167
%18 = load i64, i64* %5, align 8, !dbg !179, !tbaa !107
call void @llvm.dbg.value(metadata i64 %18, metadata !159, metadata !DIExpression()), !dbg !173
%19 = sub nsw i64 9223372036854775807, %18, !dbg !180
%20 = icmp sgt i64 %17, %19, !dbg !181
br i1 %20, label %21, label %23, !dbg !182
; <label>:21: ; preds = %16
%22 = load i64, i64* @error_atom, align 8, !dbg !183, !tbaa !107
br label %28, !dbg !185
; <label>:23: ; preds = %16
%24 = add nsw i64 %18, %17, !dbg !186
call void @llvm.dbg.value(metadata i64 %24, metadata !160, metadata !DIExpression()), !dbg !187
%25 = call i64 @enif_make_long(%struct.enif_environment_t* %0, i64 %24) #6, !dbg !188
br label %28, !dbg !189
; <label>:26: ; preds = %11, %3
%27 = load i64, i64* @arithmetic_error, align 8, !dbg !190, !tbaa !107
br label %28, !dbg !191
; <label>:28: ; preds = %26, %23, %21
%29 = phi i64 [ %27, %26 ], [ %22, %21 ], [ %25, %23 ]
call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %7) #6, !dbg !192
call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %6) #6, !dbg !192
ret i64 %29, !dbg !192
}
デバッグ情報が入っていて読みにくいので，デバッグ情報を取り除いてみました。
define internal i64 @asm_1_nif_ii(%struct.enif_environment_t*, i32, i64* nocapture readonly) #0 !dbg !152 {
%4 = alloca i64, align 8
%5 = alloca i64, align 8
%6 = bitcast i64* %4 to i8*, !dbg !164
%7 = bitcast i64* %5 to i8*, !dbg !164
%8 = load i64, i64* %2, align 8, !dbg !165, !tbaa !107
%9 = call i32 @enif_get_long(%struct.enif_environment_t* %0, i64 %8, i64* nonnull %4) #6, !dbg !168
%10 = icmp eq i32 %9, 0, !dbg !169
br i1 %10, label %26, label %11, !dbg !170
; <label>:11: ; preds = %3
%12 = getelementptr inbounds i64, i64* %2, i64 1, !dbg !171
%13 = load i64, i64* %12, align 8, !dbg !171, !tbaa !107
%14 = call i32 @enif_get_long(%struct.enif_environment_t* %0, i64 %13, i64* nonnull %5) #6, !dbg !174
%15 = icmp eq i32 %14, 0, !dbg !175
br i1 %15, label %26, label %16, !dbg !176
; <label>:16: ; preds = %11
%17 = load i64, i64* %4, align 8, !dbg !177, !tbaa !107
%18 = load i64, i64* %5, align 8, !dbg !179, !tbaa !107
%19 = sub nsw i64 9223372036854775807, %18, !dbg !180
%20 = icmp sgt i64 %17, %19, !dbg !181
br i1 %20, label %21, label %23, !dbg !182
; <label>:21: ; preds = %16
%22 = load i64, i64* @error_atom, align 8, !dbg !183, !tbaa !107
br label %28, !dbg !185
; <label>:23: ; preds = %16
%24 = add nsw i64 %18, %17, !dbg !186
%25 = call i64 @enif_make_long(%struct.enif_environment_t* %0, i64 %24) #6, !dbg !188
br label %28, !dbg !189
; <label>:26: ; preds = %11, %3
%27 = load i64, i64* @arithmetic_error, align 8, !dbg !190, !tbaa !107
br label %28, !dbg !191
; <label>:28: ; preds = %26, %23, %21
%29 = phi i64 [ %27, %26 ], [ %22, %21 ], [ %25, %23 ]
ret i64 %29, !dbg !192
}
x86_64 コード
x86_64 のアセンブリコードはこちらです。
.p2align 4, 0x90 ## -- Begin function asm_1_nif_ii
_asm_1_nif_ii: ## @asm_1_nif_ii
Lfunc_begin4:
.loc 3 16 0 ## native/lib.c:16:0
.cfi_startproc
## %bb.0:
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
pushq %r14
pushq %rbx
subq $16, %rsp
.cfi_offset %rbx, -32
.cfi_offset %r14, -24
##DEBUG_VALUE: asm_1_nif_ii:env <- %rdi
##DEBUG_VALUE: asm_1_nif_ii:argc <- %esi
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rdx
movq %rdx, %rbx
movq %rdi, %r14
Ltmp18:
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
.loc 3 18 25 prologue_end ## native/lib.c:18:25
movq (%rbx), %rsi
Ltmp19:
.loc 3 0 25 is_stmt 0 ## native/lib.c:0:25
leaq -32(%rbp), %rdx
Ltmp20:
##DEBUG_VALUE: asm_1_nif_ii:a <- [DW_OP_constu 32, DW_OP_minus] [%rbp+0]
.loc 3 18 5 ## native/lib.c:18:5
callq _enif_get_long
.loc 3 18 38 ## native/lib.c:18:38
testl %eax, %eax
Ltmp21:
.loc 3 18 5 ## native/lib.c:18:5
je LBB4_5
Ltmp22:
## %bb.1:
##DEBUG_VALUE: asm_1_nif_ii:a <- [DW_OP_constu 32, DW_OP_minus] [%rbp+0]
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 21 25 is_stmt 1 ## native/lib.c:21:25
movq 8(%rbx), %rsi
leaq -24(%rbp), %rdx
Ltmp23:
##DEBUG_VALUE: asm_1_nif_ii:b <- [DW_OP_constu 24, DW_OP_minus] [%rbp+0]
.loc 3 21 5 is_stmt 0 ## native/lib.c:21:5
movq %r14, %rdi
callq _enif_get_long
.loc 3 21 38 ## native/lib.c:21:38
testl %eax, %eax
Ltmp24:
.loc 3 21 5 ## native/lib.c:21:5
je LBB4_5
Ltmp25:
## %bb.2:
##DEBUG_VALUE: asm_1_nif_ii:b <- [DW_OP_constu 24, DW_OP_minus] [%rbp+0]
##DEBUG_VALUE: asm_1_nif_ii:a <- [DW_OP_constu 32, DW_OP_minus] [%rbp+0]
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 24 5 is_stmt 1 ## native/lib.c:24:5
movq -32(%rbp), %rax
Ltmp26:
##DEBUG_VALUE: asm_1_nif_ii:a <- %rax
.loc 3 24 20 is_stmt 0 ## native/lib.c:24:20
movq -24(%rbp), %rsi
Ltmp27:
##DEBUG_VALUE: asm_1_nif_ii:b <- %rsi
.loc 3 24 18 ## native/lib.c:24:18
movabsq $9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
subq %rsi, %rcx
.loc 3 24 7 ## native/lib.c:24:7
cmpq %rcx, %rax
Ltmp28:
.loc 3 24 5 ## native/lib.c:24:5
jle LBB4_4
Ltmp29:
## %bb.3:
##DEBUG_VALUE: asm_1_nif_ii:b <- %rsi
##DEBUG_VALUE: asm_1_nif_ii:a <- %rax
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 25 10 is_stmt 1 ## native/lib.c:25:10
movq _error_atom(%rip), %rax
Ltmp30:
.loc 3 0 10 is_stmt 0 ## native/lib.c:0:10
jmp LBB4_6
Ltmp31:
LBB4_5:
##DEBUG_VALUE: asm_1_nif_ii:a <- [DW_OP_constu 32, DW_OP_minus] [%rbp+0]
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 30 9 is_stmt 1 ## native/lib.c:30:9
movq _arithmetic_error(%rip), %rax
jmp LBB4_6
Ltmp32:
LBB4_4:
##DEBUG_VALUE: asm_1_nif_ii:b <- %rsi
##DEBUG_VALUE: asm_1_nif_ii:a <- %rax
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 27 19 ## native/lib.c:27:19
addq %rax, %rsi
Ltmp33:
##DEBUG_VALUE: asm_1_nif_ii:result <- %rsi
.loc 3 28 9 ## native/lib.c:28:9
movq %r14, %rdi
callq _enif_make_long
Ltmp34:
LBB4_6:
##DEBUG_VALUE: asm_1_nif_ii:env <- %r14
##DEBUG_VALUE: asm_1_nif_ii:argv <- %rbx
.loc 3 31 1 ## native/lib.c:31:1
addq $16, %rsp
popq %rbx
Ltmp35:
popq %r14
Ltmp36:
popq %rbp
retq
Ltmp37:
Lfunc_end4:
.cfi_endproc
これもデバッグ情報が入っていて読みにくいので，削除してみました。
.p2align 4, 0x90 ## -- Begin function asm_1_nif_ii
_asm_1_nif_ii: ## @asm_1_nif_ii
pushq %rbp
movq %rsp, %rbp
pushq %r14
pushq %rbx
subq $16, %rsp
movq %rdx, %rbx
movq %rdi, %r14
movq (%rbx), %rsi
leaq -32(%rbp), %rdx
callq _enif_get_long
testl %eax, %eax
je LBB4_5
movq 8(%rbx), %rsi
leaq -24(%rbp), %rdx
movq %r14, %rdi
callq _enif_get_long
testl %eax, %eax
je LBB4_5
movq -32(%rbp), %rax
movq -24(%rbp), %rsi
movabsq $9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
subq %rsi, %rcx
cmpq %rcx, %rax
jle LBB4_4
movq _error_atom(%rip), %rax
jmp LBB4_6
LBB4_5:
movq _arithmetic_error(%rip), %rax
jmp LBB4_6
LBB4_4:
addq %rax, %rsi
movq %r14, %rdi
callq _enif_make_long
LBB4_6:
addq $16, %rsp
popq %rbx
popq %r14
popq %rbp
retq
考察
ザッと読んでみたのですが，気に入らない点が1つ。
分岐予測の最適化の観点からは，正常フローをたどったときにジャンプせずに実行できてほしいです。つまり，こんな感じです。
.p2align 4, 0x90 ## -- Begin function asm_1_nif_ii
_asm_1_nif_ii: ## @asm_1_nif_ii
pushq %rbp
movq %rsp, %rbp
pushq %r14
pushq %rbx
subq $16, %rsp
movq %rdx, %rbx
movq %rdi, %r14
movq (%rbx), %rsi
leaq -32(%rbp), %rdx
callq _enif_get_long
testl %eax, %eax
je LBB4_5
movq 8(%rbx), %rsi
leaq -24(%rbp), %rdx
movq %r14, %rdi
callq _enif_get_long
testl %eax, %eax
je LBB4_5
movq -32(%rbp), %rax
movq -24(%rbp), %rsi
movabsq $9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
subq %rsi, %rcx
cmpq %rcx, %rax
jg LBB4_4
addq %rax, %rsi
movq %r14, %rdi
callq _enif_make_long
LBB4_6:
addq $16, %rsp
popq %rbx
popq %r14
popq %rbp
retq
LBB4_4:
movq _error_atom(%rip), %rax
jmp LBB4_6
LBB4_5:
movq _arithmetic_error(%rip), %rax
jmp LBB4_6
このようにすると，正常フローの時に一度もジャンプせずに最後までたどり着きます。
このようなコードを生成するにはどうしたらいいか？ 手がかりは掴んでいるので，次回「ZEAM開発ログ v.0.4.2 型多相かつ型安全なNIFのコードを分岐予測の観点で最適化する」で取り組んでみましょう。
お知らせ：Elixirもくもく会（リモート参加OK、入門トラック有）を9月28日に開催します
「fukuoka.ex#14：Elixir／Phoenixもくもく会～入門もあるよ」を2018年9月28日金曜日に開催します
前回は，ゲリラ的に募った「Zoomによるリモート参加」を，今回から正式に受け付けるようになりましたので，福岡以外の首都圏や地方からでも参加できます（申し込みいただいたら、追ってZoom URLをconnpassメールでお送りします）
また，これまではElixir／Phoenix経験者を対象とした，もくもく会オンリーでしたが，今回から，入門者トラックも併設し，fukuoka.exアドバイザーズ／キャストに質問できるようにアップグレードしました
私，山崎も参加します！ この記事の延長線上のものを作ろうと思っています。
お申込みはコチラから
https://fukuokaex.connpass.com/event/100659/
