ZEAM開発ログ v.0.4.1 型多相かつ型安全なNIFの LLVM IR コードを読み解く

# はじめに

ZACKY こと山崎進です。

前回[「ZEAM開発ログ v.0.4.0 型多相かつ型安全なNIFをC言語で書いてみる」](https://qiita.com/zacky1972/items/ddcbab5998d7864b3f18)から新シリーズということで，型多相で型安全なコード生成について検討しています。今回は生成された LLVM IR のコードを読み解いてみたいと思います。

[「ZEAM開発ログ 目次」はこちら](https://qiita.com/zacky1972/items/70593ab2b70d192813df)

# LLVM とは

LLVM というのは，最近のプログラミング言語処理系のコード生成で広く使われているライブラリです。さまざまな種類のプロセッサのコード生成をすることができます。CPUだけじゃなくて，GPUなんかもできますよ。

LLVM で使われているコードが LLVM IR です。高級言語から LLVM IR に変換するコンパイラを作ってあげれば，LLVM がサポートする様々な種類のプロセッサにコード生成できるようになるので大変ありがたいです。

[今回のコードはこちらの GitHub レポジトリに置いています。](https://github.com/zeam-vm/nif_llvm)どうやって LLVM のコードを生成するのかについては[Makefile](https://github.com/zeam-vm/nif_llvm/blob/master/Makefile)を読んでくださいね。

# 今回読み解くC言語のコード

元の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 にコンパイルするとこのようになります。

```llvm
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
}
```

デバッグ情報が入っていて読みにくいので，デバッグ情報を取り除いてみました。

```llvm
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のコードを分岐予測の観点で最適化する」](https://qiita.com/zacky1972/items/4d72b95be62b446ae4be)で取り組んでみましょう。

:stars::stars::stars:<b>　お知らせ：Elixirもくもく会（リモート参加OK、入門トラック有）を9月28日に開催します　</b>:stars::stars::stars:

[<b>「fukuoka.ex#14：Elixir／Phoenixもくもく会～入門もあるよ」</b>](https://fukuokaex.connpass.com/event/100659/)を2018年9月28日金曜日に開催します

前回は，ゲリラ的に募った「Zoomによるリモート参加」を，今回から正式に受け付けるようになりましたので，福岡以外の首都圏や地方からでも参加できます（申し込みいただいたら、追ってZoom URLをconnpassメールでお送りします）

また，これまではElixir／Phoenix経験者を対象とした，もくもく会オンリーでしたが，今回から，入門者トラックも併設し，fukuoka.exアドバイザーズ／キャストに質問できるようにアップグレードしました

私，山崎も参加します！ この記事の延長線上のものを作ろうと思っています。

お申込みはコチラから
https://fukuokaex.connpass.com/event/100659/
[![image.png](https://qiita-image-store.s3.amazonaws.com/0/155423/3f0fbb56-e5e8-2c4d-7c62-1b0b311d6d02.png)](https://fukuokaex.connpass.com/event/100659/)