FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

QEMUが分岐命令を処理する仕組み(Relocationによるラベルの解決)

QEMU

QEMUで分岐命令を取り扱う場合、主に以下のような手順で取り扱われることを見てきた。

  • source1に新しいオペランドを確保する。gen_get_gpr(source1, a->rs1)によりsource1にrs1の情報を格納する。

  • source2に新しいオペランドを確保する。gen_get_gpr(source2, a->rs2)によりsource2にrs2の情報を格納する。

  • lはラベルを示している。これは分岐命令によりジャンプ先を制御するために使用する。

  • tcg_gen_brcond_tl(cond, source1, source2, l)が分岐そのものを示している。source1とsource2を比較し、condで示す条件が成立すればlが配置されている場所まで飛ぶというものだと思われる（あくまで、lはホストコード上のジャンプ先で、goto:みたいなものだととらえれば良い。
    • gen_set_label(l)によりlの場所が指定される。もし分岐が成立すればlまでジャンプするため、その1行上のgen_goto_tb(ctx, 1, ctx->pc_succ_insn)は実行が省略されることになる。
  • もし分岐命令が成立しなければ、gen_goto_tb(ctx, 1, ctx->pc_succ_insn);が実行され次のPCに移動される。
  • もし分岐命令が成立すれば、gen_goto_tb(ctx, 0, ctx->base.pc_next + a->imm);によりPCが設定されジャンプする。

ここでラベルを示す変数labelが使用されている。このラベルに対してジャンプする分岐命令を生成する場合、アドレスへのジャンプは当該対象命令とラベルとの相対距離が計算できる状態でなければならない。命令を生成している状態でこれは不可能だ。従って少なくとも2回はパスを通過させる必要があるような気がする。つまり、

  • 1回目では命令の生成と分岐命令に対するプレースホルダを配置する。命令を生成させる中でラベルの位置を確定させる。
  • 2回目ではプレースホルダに対して、確定したアドレスのラベルを挿入する。

という作業が必要になる。これをQEMUではどのように実現しているのか確認していきたい。

QEMUがラベルの生成とリロケーションを行う仕組み

QEMUでは、ゲストマシンで分岐命令が発生すると、分岐に関するTCGとジャンプ先を示すラベルを生成する。条件分岐が成立すると、そのラベルに対してジャンプするように設定するわけだ。

  • qemu/target/riscv/insn_trans/trans_rvi.inc.c
static bool gen_branch(DisasContext *ctx, arg_b *a, TCGCond cond)
{
    TCGLabel *l = gen_new_label();
...
    tcg_gen_brcond_tl(cond, source1, source2, l);
    gen_goto_tb(ctx, 1, ctx->pc_succ_insn);
    gen_set_label(l); /* branch taken */

    if (!has_ext(ctx, RVC) && ((ctx->base.pc_next + a->imm) & 0x3)) {
        /* misaligned */
        gen_exception_inst_addr_mis(ctx);
    } else {
        gen_goto_tb(ctx, 0, ctx->base.pc_next + a->imm);
    }
    ctx->base.is_jmp = DISAS_NORETURN;
...

上記のコードでは、tcg_gen_brcond_tlによる分岐操作の生成と、分岐が成立した場合にはラベルlにジャンプすることが指定されている。分岐が成立しない場合、直後のgen_goto_tb(ctx, 1, ctx->pc_succ_insn)が実行され、分岐が成立した場合はラベルlへジャンプする。gen_set_label(l)はラベルの場所を決定するために必要なマーカーを生成する。

命令を生成する段階になると、brcondのTCGは比較演算の種類に応じてx86の命令を生成する。具体的には、tcg_out_brcond64において比較命令と条件ジャンプ命令を生成する。

  • qemu/tcg/i386/tcg-target.inc.c
#if TCG_TARGET_REG_BITS == 64
static void tcg_out_brcond64(TCGContext *s, TCGCond cond,
                             TCGArg arg1, TCGArg arg2, int const_arg2,
                             TCGLabel *label, int small)
{
    tcg_out_cmp(s, arg1, arg2, const_arg2, P_REXW);
    tcg_out_jxx(s, tcg_cond_to_jcc[cond], label, small);
}
#else

tcg_out_jxx()ではラベルを引数として受け取り（これはtcg_gen_brcond_tlで生成したTCGに引数として付加していたラベルである）、条件分岐命令を生成すると同時に、ジャンプ先アドレスについてリロケーションが必要であるという情報を生成する。具体的には、ラベル変数に対して命令を生成した現在のPCアドレスを渡し、「リロケーション段階でこのアドレスに対して最終的なラベルのアドレスを格納してください」というラベルを埋め込む。

  • qemu/tcg/i386/tcg-target.inc.c
/* Use SMALL != 0 to force a short forward branch.  */
static void tcg_out_jxx(TCGContext *s, int opc, TCGLabel *l, int small)
{
    int32_t val, val1;
...
    } else if (small) {
        if (opc == -1) {
            tcg_out8(s, OPC_JMP_short);
        } else {
            tcg_out8(s, OPC_JCC_short + opc);
        }
        tcg_out_reloc(s, s->code_ptr, R_386_PC8, l, -1);
        s->code_ptr += 1;
...

tcg_out8でジャンプ命令の生成、そして後続にリロケーション情報を挿入する。

  • qemu/tcg/i386/tcg-target.inc.c
static void tcg_out_reloc(TCGContext *s, tcg_insn_unit *code_ptr, int type,
                          TCGLabel *l, intptr_t addend)
{
    TCGRelocation *r = tcg_malloc(sizeof(TCGRelocation));

    r->type = type;
    r->ptr = code_ptr;
    r->addend = addend;
    QSIMPLEQ_INSERT_TAIL(&l->relocs, r, next);
}

全ての命令の場所とラベルの場所が確定すると、今度はすべてのラベルに対してリロケーションすべき場所に確定したアドレスを挿入する。

  • qemu/tcg/tcg.c
static bool tcg_resolve_relocs(TCGContext *s)
{
    fprintf(stderr, "tcg_resolve_relocs\n");

    TCGLabel *l;

    QSIMPLEQ_FOREACH(l, &s->labels, next) {
        TCGRelocation *r;
        uintptr_t value = l->u.value;

        QSIMPLEQ_FOREACH(r, &l->relocs, next) {
            if (!patch_reloc(r->ptr, r->type, value, r->addend)) {
                return false;
            }
        }
    }
    return true;
}

例を見てみよう。以下のような命令をコンパイルしてx86上で実行することを考える。

0000000080000000 <_start>:
    80000000:   00100513                li      a0,1
    80000004:   00200593                li      a1,2
    80000008:   00b50c63                beq     a0,a1,80000020 <label>
    8000000c:   00a00a13                li      s4,10
    80000010:   00b00a93                li      s5,11
    80000014:   00c00b13                li      s6,12
    80000018:   00d00b93                li      s7,13
    8000001c:   00e00c13                li      s8,14

0000000080000020 <label>:
    80000020:   00008067                ret

これが変換された結果を見てみる。

jmp tcg generated. addr = 0x7f2000000105
tcg_out_reloc is called = 0x7f2000000107
patch_relocs(r->ptr = 0x7f2000000107, r->type = 2, value = 7f2000000156, r->addend = -4
OUT: [size=112]
0x7f2000000100:  8b 5d f0                 movl     -0x10(%rbp), %ebx
0x7f2000000103:  85 db                    testl    %ebx, %ebx
0x7f2000000105:  0f 8c 4b 00 00 00        jl       0x7f2000000156
0x7f200000010b:  48 c7 45 28 00 10 00 00  movq     $0x1000, 0x28(%rbp)
0x7f2000000113:  48 c7 45 58 20 10 00 00  movq     $0x1020, 0x58(%rbp)
0x7f200000011b:  48 c7 85 00 02 00 00 08  movq     $0x1008, 0x200(%rbp)
0x7f2000000123:  10 00 00
0x7f2000000126:  c7 85 8c f8 ff ff 01 00  movl     $1, -0x774(%rbp)
0x7f200000012e:  00 00
0x7f2000000130:  48 8b fd                 movq     %rbp, %rdi
0x7f2000000133:  33 f6                    xorl     %esi, %esi
0x7f2000000135:  ba 14 0f 00 00           movl     $0xf14, %edx
0x7f200000013a:  33 c9                    xorl     %ecx, %ecx
0x7f200000013c:  ff 15 26 00 00 00        callq    *0x26(%rip)
0x7f2000000142:  48 89 45 50              movq     %rax, 0x50(%rbp)
0x7f2000000146:  48 c7 85 00 02 00 00 0c  movq     $0x100c, 0x200(%rbp)
0x7f200000014e:  10 00 00
0x7f2000000151:  e9 c0 fe ff ff           jmp      0x7f2000000016
0x7f2000000156:  48 8d 05 e6 fe ff ff     leaq     -0x11a(%rip), %rax
0x7f200000015d:  e9 b6 fe ff ff           jmp      0x7f2000000018
0x7f2000000162:  90                       nop
0x7f2000000163:  90                       nop
0x7f2000000164:  90                       nop
0x7f2000000165:  90                       nop
0x7f2000000166:  90                       nop
0x7f2000000167:  90                       nop
0x7f2000000168:  .quad  0x000000000053c5ad
f:id:msyksphinz:20200829143154p:plain