跳转至

Dynarmic 设计文档

Dynarmic 是一个针对 ARMv6K 架构的动态重编译器。Dynarmic 的未来计划包括 支持其他版本的 ARM 架构、提供解释器模式,以及添加对其他架构的支持。

这个库的用户主要通过 src/dynarmic/interface 中提供的接口与其交互。用户通过提供相关 UserCallbacks 接口的实现来指定 Dynarmic 的 CPU 核心如何与系统其余部分交互。用户使用 Jit 的成员函数设置 CPU 状态,然后调用 Jit::Execute 开始 CPU 执行。UserCallbacks 上定义的回调可能会从动态生成的代码中调用,因此库的用户不应依赖栈处于可回溯(walkable)状态以进行展开(unwinding)。

Dynarmic 通过调用 UserCallbacks::MemoryReadCode 从内存读取指令。这些 指令随后经过以下几个阶段:

  1. 解码(识别指令的类型并将其拆分为字段)
  2. 翻译(从指令生成高级 IR)
  3. 优化(消除冗余微指令,以及其他速度改进)
  4. 发射(生成宿主可执行代码到内存中)
  5. 执行(宿主 CPU 跳转到已发射代码的起始处并运行)

以 A32 前端配合 x64 后端为例:

解码器

解码器是一个双重分派解码器。每条指令由相关指令表中的一行表示。以下是来自 arm.h 的示例行:

INST(&V::arm_ADC_imm,     "ADC (imm)",           "cccc0010101Snnnnddddrrrrvvvvvvvv")

(有关此指令的详细信息,请参阅 ARMv7-A 手册的 A8.8.1 节。这是编码 A1。)

INST 的第一个参数是要在访问器上调用的成员函数。第二个参数是用户可读的 指令名称。第三个参数是指令的位表示。

指令位表示

位串中的每个字符表示一个位。0 表示该位位置必须包含 0。1 表示该位位置必须包含 1。- 表示我们不关心该位位置的值。 相同字符的字符串表示一个字段。在上面的示例中,前四位 cccc 表示 ARM 带进位加法(立即数)指令的四位长 cond 字段。

访问器必须有一个名为 arm_ADC_imm 的函数,带有 6 个参数,分别对应每个字段(cccc、S、 nnnn、dddd、rrrr、vvvvvvvv)。如果字段数与参数数不匹配,会导致编译时 错误。

翻译器

翻译器是一个使用解码器对指令进行解码的访问器。翻译器在 IREmitter 类的帮助下生成 IR 代码。下面是一个翻译函数的示例:

bool ArmTranslatorVisitor::arm_ADC_imm(Cond cond, bool S, Reg n, Reg d, int rotate, Imm8 imm8) {
    u32 imm32 = ArmExpandImm(rotate, imm8);

    // ADC{S}<c> <Rd>, <Rn>, #<imm>

    if (ConditionPassed(cond)) {
        auto result = ir.AddWithCarry(ir.GetRegister(n), ir.Imm32(imm32), ir.GetCFlag());

        if (d == Reg::PC) {
            ASSERT(!S);
            ir.ALUWritePC(result.result);
            ir.SetTerm(IR::Term::ReturnToDispatch{});
            return false;
        }

        ir.SetRegister(d, result.result);
        if (S) {
            ir.SetNFlag(ir.MostSignificantBit(result.result));
            ir.SetZFlag(ir.IsZero(result.result));
            ir.SetCFlag(result.carry);
            ir.SetVFlag(result.overflow);
        }
    }

    return true;
}

其中 ir 是 IRBuilder 类的一个实例。IRBuilder 类的每个成员函数都会构造 一条 IR 微指令。

中间表示

Dynarmic 使用一种有序的 SSA 中间表示。它与 redream、nucleus 和 xenia 等其他类似项目中的中间表示有几分相似。主要区别在于:(1) 上下文微指令丰富, 而那些项目通常只有两个(load_context/store_context);(2) 标志被显式地作为独立值处理;(3) 基本块边的处理方式非常不同。

上下文微指令和显式标志处理的目的是为未来的优化留出空间。边(edge)处理方式上的差异是当前实现的一个特殊行为,dynarmic 很可能在中期未来添加一个函数分析器。

Dynarmic 的 IR(中间表示)是类型化的。每条微指令可以接受零个或多个参数,也可以返回零个或多个参数。下面记录了可用的微指令的一个子集。

完整的微指令列表可以在 src/dynarmic/ir/opcodes.inc 中找到。

下面列出一些常用的微指令。

立即数:Imm{U1,U8,U32,RegRef}

<u1> ImmU1(u1 value)
<u8> ImmU8(u8 value)
<u32> ImmU32(u32 value)
<RegRef> ImmRegRef(Arm::Reg gpr)

这些指令接受一个 bool、u8 或 u32 值,并将其包装进一个 IR 节点,以便它们可以被 IR 使用。

上下文:{Get,Set}Register

<u32> GetRegister(<RegRef> reg)
<void> SetRegister(<RegRef> reg, <u32> value)

获取和设置 JitState::Reg[reg]。注意,SetRegister(Arm::Reg::R15, _) 不被 IRBuilder 允许。请改用 {ALU,BX}WritePC。

注意,类似 SetRegister(R4, _) 后接 GetRegister(R4) 的序列会被优化掉。

上下文:{Get,Set}{N,Z,C,V}Flag

<u1> GetNFlag()
<void> SetNFlag(<u1> value)
<u1> GetZFlag()
<void> SetZFlag(<u1> value)
<u1> GetCFlag()
<void> SetCFlag(<u1> value)
<u1> GetVFlag()
<void> SetVFlag(<u1> value)

获取和设置 JitState::Cpsr 中的位。与寄存器类似,冗余的 get/set 会被优化掉。

上下文:BXWritePC

<void> BXWritePC(<u32> value)

除非你在做一些特殊操作,否则这条指令很可能是翻译块中的最后一条指令。

这条微指令会适当地设置 R15 和 CPSR.T。

回调:CallSupervisor

<void> CallSupervisor(<u32> svc_imm32)

除非你在做一些特殊操作,否则这条指令很可能是翻译块中的最后一条指令。

计算:LastSignificant{Half,Byte}

<u16> LeastSignificantHalf(<u32> value)
<u8> LeastSignificantByte(<u32> value)

分别从 u32 中提取 u16 和 u8。

计算:MostSignificantBit, IsZero

<u1> MostSignificantBit(<u32> value)
<u1> IsZero(<u32> value)

这些用于实现 ARM 标志 N 和 Z。后端通常可以将它们优化为主机标志(host flag)读取。

计算:LogicalShiftLeft

(<u32> result, <u1> carry_out) LogicalShiftLeft(<u32> operand, <u8> shift_amount, <u1> carry_in)

伪代码:

    if shift_amount == 0:
        return (operand, carry_in)

    x = operand * (2 ** shift_amount)
    result = Bits<31,0>(x)
    carry_out = Bit<32>(x)

    return (result, carry_out)

这遵循 ARM 语义。注意 shift_amount 不会被掩码为 5 位(不像 x64 上的 SHL 那样)。

计算:LogicalShiftRight

(<u32> result, <u1> carry_out) LogicalShiftLeft(<u32> operand, <u8> shift_amount, <u1> carry_in)

伪代码:

    if shift_amount == 0:
        return (operand, carry_in)

    x = ZeroExtend(operand, from_size: 32, to_size: shift_amount+32)
    result = Bits<shift_amount+31,shift_amount>(x)
    carry_out = Bit<shift_amount-1>(x)

    return (result, carry_out)

这遵循 ARM 语义。注意 shift_amount 不会被掩码为 5 位(不像 x64 上的 SHR 那样)。

计算:ArithmeticShiftRight

(<u32> result, <u1> carry_out) ArithmeticShiftRight(<u32> operand, <u8> shift_amount, <u1> carry_in)

伪代码:

    if shift_amount == 0:
        return (operand, carry_in)

    x = SignExtend(operand, from_size: 32, to_size: shift_amount+32)
    result = Bits<shift_amount+31,shift_amount>(x)
    carry_out = Bit<shift_amount-1>(x)

    return (result, carry_out)

这遵循 ARM 语义。注意 shift_amount 不会被掩码为 5 位(不像 x64 上的 SAR 那样)。

计算:RotateRight

(<u32> result, <u1> carry_out) RotateRight(<u32> operand, <u8> shift_amount, <u1> carry_in)

伪代码:

    if shift_amount == 0:
        return (operand, carry_in)

    shift_amount %= 32
    result = (operand << shift_amount) | (operand >> (32 - shift_amount))
    carry_out = Bit<31>(result)

    return (result, carry_out)

计算:AddWithCarry

(<u32> result, <u1> carry_out, <u1> overflow) AddWithCarry(<u32> a, <u32> b, <u1> carry_in)

a + b + carry_in

计算:SubWithCarry

(<u32> result, <u1> carry_out, <u1> overflow) SubWithCarry(<u32> a, <u32> b, <u1> carry_in)

这与 AddWithCarry(a, Not(b), carry_in) 具有等效语义。

a - b - !carry_in

计算:And

<u32> And(<u32> a, <u32> b)

计算:Eor

<u32> Eor(<u32> a, <u32> b)

异或(即:XOR)

计算:Or

<u32> Or(<u32> a, <u32> b)

计算:Not

<u32> Not(<u32> value)

回调:{Read,Write}Memory{8,16,32,64}

<u8> ReadMemory8(<u32> vaddr)
<u8> ReadMemory16(<u32> vaddr)
<u8> ReadMemory32(<u32> vaddr)
<u8> ReadMemory64(<u32> vaddr)
<void> WriteMemory8(<u32> vaddr, <u8> value_to_store)
<void> WriteMemory16(<u32> vaddr, <u16> value_to_store)
<void> WriteMemory32(<u32> vaddr, <u32> value_to_store)
<void> WriteMemory64(<u32> vaddr, <u64> value_to_store)

内存访问。

终止:ReturnToDispatch

SetTerm(IR::Term::ReturnToDispatch{})

该终止指令将控制权返回给调度器。调度器将使用 R15 中的值来决定接下来执行什么。

终止:LinkBlock

SetTerm(IR::Term::LinkBlock{next})

如果剩余周期足够,该终止指令会跳转到由 next 描述的基本块。如果剩余周期不足,则返回到调度器,调度器会将控制权返回给主机。

终止:LinkBlockFast

SetTerm(IR::Term::LinkBlockFast{next})

该终止指令无条件跳转到 next 所描述的基本块。这承诺了必须在运行时保持的保证——即程序不会挂起,

终止指令:PopRSBHint

SetTerm(IR::Term::PopRSBHint{})

该终止指令将返回栈缓冲区的顶部与 R15 进行比较。如果 RSB 查找失败,控制权将返回给调度器。这是为了加快函数调用而进行的一种优化。不支持此优化或不具备 RSB 的后端可以选择将其完全实现为 ReturnToDispatch。

终止指令:If

SetTerm(IR::Term::If{cond, term_then, term_else})

该终止指令根据 ARM 标志的运行时状态,条件性地执行一个或另一个终止指令。

寄存器分配(x64 后端)

HostLoc 包含值。HostLoc(“宿主机值位置”)要么是宿主机 CPU 寄存器,要么是宿主机溢出位置。

值一旦被设置便不能更改。不过,寄存器分配器可以在 HostLoc 之间移动值。这由寄存器分配器自身处理;使用寄存器分配器的代码不需要、也不应该在寄存器之间移动值。

寄存器分配器基于三个概念:Use、Def 和 Scratch。

  • Use:值的使用。
  • Define:值的定义,这是值被设置的唯一时机。
  • Scratch:分配一个可按需自由修改的寄存器。

请注意,Use 一个值会将其 use_count 减一。当 use_count 变为零时,该值会被丢弃,不再存在。

RegAlloc 上的成员函数只是上述概念的组合。

以下寄存器保留供内部使用,不应参与寄存器分配:

  • %xmm0、%xmm1、%xmm2:在独占内存访问中用作临时寄存器。
  • %rsp:栈指针。
  • %r15:JIT 指针。
  • %r14:页表指针。
  • %r13:Fastmem 指针。

该布局将 %r15 作为 JIT 状态指针——虽然将其变成合成指针可能很有吸引力,但保留一个完整寄存器(在总共 12 个可用寄存器中)比内联直接计算的立即数更可取。

切勿修改 %r15;我们必须明确,在整个 JIT 块持续期间,该寄存器是“不可变的”。

Scratch

Xbyak::Reg64 ScratchGpr(HostLocList desired_locations = any_gpr);
Xbyak::Xmm ScratchXmm(HostLocList desired_locations = any_xmm);

在运行时,分配 desired_locations 中的一个寄存器。你可以自由修改该寄存器。该寄存器在分配作用域结束时被丢弃。

纯 Use

Xbyak::Reg64 UseGpr(Argument& arg);
Xbyak::Xmm UseXmm(Argument& arg);
OpArg UseOpArg(Argument& arg);
void Use(Argument& arg, HostLoc host_loc);

在运行时,与 arg 对应的值会被放入一个寄存器。实际寄存器由调用上述哪个函数决定。UseGpr 将其放入一个未使用的 GPR,UseXmm 将其放入一个未使用的 XMM 寄存器,UseOpArg 可能将其放在寄存器中,也可能放在内存位置,而 Use 允许你指定一个特定的寄存器(GPR 或 XMM)来使用。

该寄存器的值不得被修改。

UseScratch

Xbyak::Reg64 UseScratchGpr(Argument& arg);
Xbyak::Xmm UseScratchXmm(Argument& arg);
void UseScratch(Argument& arg, HostLoc host_loc);

在运行时,与 arg 对应的值会被放入一个寄存器。实际寄存器由调用上述哪个函数决定。UseScratchGpr 将其放入一个未使用的 GPR,UseScratchXmm 将其放入一个未使用的 XMM 寄存器,而 UseScratch 允许你指定一个特定的寄存器(GPR 或 XMM)来使用。

返回值就是分配给你的寄存器。

你可以自由修改该寄存器中的值。该寄存器在分配作用域结束时被丢弃。

Define 作为寄存器

Define 是值的定义。这是值可能被设置的唯一时机。

void DefineValue(IR::Inst* inst, const Xbyak::Reg& reg);

通过调用 DefineValue,你表明希望为 inst 定义该值,并且已将值写入指定的寄存器 reg。

将 Define 用作不同值的别名

向现有值添加一个 Define。

void DefineValue(IR::Inst* inst, Argument& arg);

你声明 inst 的值与 arg 的值相同。不会发出任何宿主机机器指令。

何时使用每种?

  • 在可能的情况下,优先使用 Use 而不是 UseScratch。
  • 在可能的情况下,优先使用 OpArg 变体。
  • 在可能的情况下,优先不使用特定的 HostLoc 变体。

返回栈缓冲区优化(x64 后端)

dynarmic 所做的优化之一是块链接。当跳转的目标地址在 JIT 时期就可用时,就会进行块链接。我们可以在块结束时不必返回调度器,而是执行块链接:直接跳转到下一个块。这样做是有益的,因为返回调度器通常代价相当高。

在我们无法预测目标地址的情况下应该怎么做?典型的例子是在函数末尾执行返回语句时;返回地址在编译时并非静态已知。

我们通过使用返回栈缓冲区来处理这种情况:当执行调用指令时,我们将预测值压入 RSB。当执行返回指令时,我们从 RSB 弹出一个预测值。如果预测命中,我们会立即跳转到相关的已编译块。否则,我们返回调度器。

这就是此优化背后的核心思想。

UniqueHash

dynarmic 的一个复杂之处在于,已编译块无法仅由 PC 唯一标识,FPSCR 和 CPSR 中的某些位也具有相关性。我们通过计算一个 64 位的 UniqueHash 来解决这个问题,该哈希保证能唯一标识一个块。

u64 LocationDescriptor::UniqueHash() const {
    // This value MUST BE UNIQUE.
    // This calculation has to match up with EmitX64::EmitTerminalPopRSBHint
    u64 pc_u64 = u64(arm_pc) << 32;
    u64 fpscr_u64 = u64(fpscr.Value());
    u64 t_u64 = cpsr.T() ? 1 : 0;
    u64 e_u64 = cpsr.E() ? 2 : 0;
    return pc_u64 | fpscr_u64 | t_u64 | e_u64;
}

我们的实现实际上并不是一个栈

Dynarmic 的 RSB 实际上并不是一个栈。它是以环形缓冲区(ring buffer)的方式实现的,因为这在测试中表现出了更好的性能。

RSB 结构

RSB 以环形缓冲区实现。rsb_ptr 是插入点的索引。rsb_location_descriptors 中的每个元素都是一个 UniqueHash,且它们分别与 rsb_codeptrs 中的元素一一对应。rsb_codeptrs 保存着对应已编译块的主机地址。

RSB_SIZE 是通过性能测试选定的。请注意,这比硬件中实际 RSB 的大小(3 个条目)还要大。大于 8 的 RSB 会出现性能下降。

struct JitState {
    // ...

    static constexpr size_t RSB_SIZE = 8; // MUST be a power of 2.
    u32 rsb_ptr = 0;
    std::array<u64, RSB_SIZE> rsb_location_descriptors;
    std::array<u64, RSB_SIZE> rsb_codeptrs;
    void ResetRSB();

    // ...
};

RSB 压入

当且仅当 RSB 尚未包含具有相同 UniqueHash 的预测时,我们才将预测插入到插入点。

void EmitX64::EmitPushRSB(IR::Block&, IR::Inst* inst) {
    using namespace Xbyak::util;

    ASSERT(inst->GetArg(0).IsImmediate());
    u64 imm64 = inst->GetArg(0).GetU64();

    Xbyak::Reg64 code_ptr_reg = reg_alloc.ScratchGpr(code, {HostLoc::RCX});
    Xbyak::Reg64 loc_desc_reg = reg_alloc.ScratchGpr(code);
    Xbyak::Reg32 index_reg = reg_alloc.ScratchGpr(code).cvt32();
    u64 code_ptr = unique_hash_to_code_ptr.find(imm64) != unique_hash_to_code_ptr.end()
                    ? u64(unique_hash_to_code_ptr[imm64])
                    : u64(code->GetReturnFromRunCodeAddress());

    code->mov(index_reg, dword[code.ABI_JIT_PTR + offsetof(JitState, rsb_ptr)]);
    code->add(index_reg, 1);
    code->and_(index_reg, u32(JitState::RSB_SIZE - 1));

    code->mov(loc_desc_reg, u64(imm64));
    CodePtr patch_location = code->getCurr<CodePtr>();
    patch_unique_hash_locations[imm64].emplace_back(patch_location);
    code->mov(code_ptr_reg, u64(code_ptr)); // This line has to match up with EmitX64::Patch.
    code->EnsurePatchLocationSize(patch_location, 10);

    Xbyak::Label label;
    for (size_t i = 0; i < JitState::RSB_SIZE; ++i) {
        code->cmp(loc_desc_reg, qword[code.ABI_JIT_PTR + offsetof(JitState, rsb_location_descriptors) + i * sizeof(u64)]);
        code->je(label, code->T_SHORT);
    }

    code->mov(dword[code.ABI_JIT_PTR + offsetof(JitState, rsb_ptr)], index_reg);
    code->mov(qword[code.ABI_JIT_PTR + index_reg.cvt64() * 8 + offsetof(JitState, rsb_location_descriptors)], loc_desc_reg);
    code->mov(qword[code.ABI_JIT_PTR + index_reg.cvt64() * 8 + offsetof(JitState, rsb_codeptrs)], code_ptr_reg);
    code->L(label);
}

用伪代码表示为:

    for (i := 0 .. RSB_SIZE-1)
        if (rsb_location_descriptors[i] == imm64)
        goto label;
    rsb_ptr++;
    rsb_ptr %= RSB_SIZE;
    rsb_location_desciptors[rsb_ptr] = imm64; //< The UniqueHash
    rsb_codeptr[rsb_ptr] = /* codeptr corresponding to the UniqueHash */;
label:

RSB 弹出

为了检查 RSB 中是否存在某个预测,我们会对 RSB 进行线性扫描。

void EmitX64::EmitTerminalPopRSBHint(IR::Term::PopRSBHint, IR::LocationDescriptor initial_location) {
    using namespace Xbyak::util;

    // This calculation has to match up with IREmitter::PushRSB
    code->mov(ecx, MJitStateReg(Arm::Reg::PC));
    code->shl(rcx, 32);
    code->mov(ebx, dword[code.ABI_JIT_PTR + offsetof(JitState, FPSCR_mode)]);
    code->or_(ebx, dword[code.ABI_JIT_PTR + offsetof(JitState, CPSR_et)]);
    code->or_(rbx, rcx);

    code->mov(rax, u64(code->GetReturnFromRunCodeAddress()));
    for (size_t i = 0; i < JitState::RSB_SIZE; ++i) {
        code->cmp(rbx, qword[code.ABI_JIT_PTR + offsetof(JitState, rsb_location_descriptors) + i * sizeof(u64)]);
        code->cmove(rax, qword[code.ABI_JIT_PTR + offsetof(JitState, rsb_codeptrs) + i * sizeof(u64)]);
    }

    code->jmp(rax);
}

用伪代码表示为:

rbx := ComputeUniqueHash()
rax := ReturnToDispatch
for (i := 0 .. RSB_SIZE-1)
    if (rbx == rsb_location_descriptors[i])
        rax = rsb_codeptrs[i]
goto rax

快速内存(Fastmem)

在 JIT 编译的程序中,访问内存的主要方式是通过被调用的函数,例如 Read() 和 Write()。在我们的翻译器中,这类函数通常会占用可观的代码空间(push + call + pop)。它们会破坏指令缓存(i-cache)(由于间接调用),并总体上使代码生成更加臃肿。

解决办法是什么?将无效访问委托给一个专用区域,类似于交换区(swap)。这种机制的核心思想是让操作系统将无效访问产生的页错误直接传递给 JIT 翻译器,从而绕过地址空间调用。虽然这牺牲了指令缓存一致性,但可以减小代码体积并获得“更高”的吞吐量。

然而,许多内核并不支持快速信号分发(Solaris、OpenBSD、FreeBSD)。只有 Linux 和 Windows 支持相对“快速”的信号分发。因此,此功能更适合它们。

Host to guest translation

Fastmem translation

例如在 x86_64 上,当发生页错误时,CPU 会通过控制寄存器和栈(参见 IRETQ)传递页错误处理程序所需的参数,然后操作系统会将其转换为可以发送到用户空间的内容。

大多数现代操作系统实现了内核页表隔离(kernel-page-table-isolation),这意味着某些系统调用会触发上下文切换(即不常用的系统调用),而另一些则由同一进程地址空间处理(较小的内核部分,即常用的系统调用),无需上下文切换。在支持 PCID(最多 4096 个唯一 ID)的系统上,这种影响可以被抵消。

信号分发会因重新加载 %cr3 而损失性能——但 Linux 的做法更巧妙,可以避免重新加载:VDSO 会在同一地址空间内处理整个过程。这使得信号分发的开销仅相当于一次间接调用,而不会带来代码体积增加的风险。

这样做的主要缺点是 VDSO 信号处理程序带来的持续 i-cache 抖动和流水线冒险。不过在大多数基准测试中,启用 fastmem 确实比不启用时表现更快(仅限 Linux)。此外,它还利用了连续地址空间模拟的特性,使用一个 arena——该 arena 随后可能被透明地映射到 hugepage 中,从而减少 TLB 遍历时间。

本页原文 Markdown:在 AtomGit 查看·内容源自开源项目 eg/Eglantine