LoginSignup
4
2

More than 5 years have passed since last update.

@zacky1972(山崎 進)infukuoka.ex：福岡Elixirコミュ

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

Last updated at Posted at 2018-09-12

はじめに

ZACKY こと山崎進です。

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

「ZEAM開発ログ 目次」はこちら

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のコードを分岐予測の観点で最適化する」で取り組んでみましょう。

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

「fukuoka.ex#14：Elixir／Phoenixもくもく会～入門もあるよ」を2018年9月28日金曜日に開催します

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

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

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

お申込みはコチラから
https://fukuokaex.connpass.com/event/100659/
image.png

4
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
2