mctoll

1. mctoll

1. mctoll

`This tool statically (AOT) translates (or raises) binaries to LLVM IR.`

https://github.com/Microsoft/llvm-mctoll

translating_x86_binaries_into_llvm_intermediate_representation

1.1. 测试

https://github.com/sunwayforever/llvm-toy/tree/mctoll

$> cd <path-to-llvm>/mctoll
$> ./mctoll_build.sh
$> make

原始的 c 代码:

#include <stdio.h>
int main(int argc, char **argv) {
  int a = argc;
  int b = argc + 1;
  return b;
}

原始的汇编:

# at&t 语法, `op src, dst`
main:
 1     pushq   %rbp
 2     movq    %rsp, %rbp
 3     movl    $0, -4(%rbp)
 4     movl    %edi, -8(%rbp)
 5     movq    %rsi, -16(%rbp)
 6     movl    -8(%rbp), %eax
 7     movl    %eax, -20(%rbp)
 8     movl    -8(%rbp), %eax
 9     addl    $1, %eax
10     movl    %eax, -24(%rbp)
11     movl    -24(%rbp), %eax
12     popq    %rbp
13     retq

用汇编生成 binary 后通过 mctoll 转换回来的 llvm ir:

define dso_local i32 @main(i32 %arg1, i64 %arg2) {
entry:
  ; %rbp 识别为 stktop_4 (stack top), 后续针对 stack 的使用 (-4(%rbp), -8(%rbp)...)
  ; 都使用 stktop_4 这个 llvm 局部变量来表示
  %stktop_4 = alloca i8, i32 32, align 1
  ; RBP_N.20/16/8/4 对应 {-20, -16, -8, -4}(%rbp), 其中 _N 表示 negative?
  %tos = ptrtoint ptr %stktop_4 to i64
  %0 = add i64 %tos, 12
  %RBP_N.20 = inttoptr i64 %0 to ptr
  %1 = add i64 %tos, 16
  %RBP_N.16 = inttoptr i64 %1 to ptr
  %2 = add i64 %tos, 24
  %RBP_N.8 = inttoptr i64 %2 to ptr
  %3 = add i64 %tos, 28
  %RBP_N.4 = inttoptr i64 %3 to ptr
  %4 = add i64 %tos, 0
  ; RSP_P.0 对应 $rsp, _P 表示 positive?
  %RSP_P.0 = inttoptr i64 %4 to ptr
  ; 写了一个 `DEADBEEF` 到 0(RSP), 表示未初始化
  store i64 3735928559, ptr %RSP_P.0, align 8
  ; 1 pushq   %rbp 是 prologue 生成的, 不需要翻译
  ; 2 movq    %rsp, %rbp
  %RBP = ptrtoint ptr %RSP_P.0 to i64
  ; 3 movl    $0, -4(%rbp)
  store i32 0, ptr %RBP_N.4, align 1
  ; mctoll 知道 x86 system-v abi 里 edi 代表 arg1
  ; 4 movl    %edi, -8(%rbp)
  store i32 %arg1, ptr %RBP_N.8, align 1
  ; mctoll 知道 rsi 代表 arg2
  ; 5 movq    %rsi, -16(%rbp)
  store i64 %arg2, ptr %RBP_N.16, align 1
  ; 6 movl    -8(%rbp), %eax
  %memload = load i32, ptr %RBP_N.8, align 1
  ; 7 movl    %eax, -20(%rbp)
  store i32 %memload, ptr %RBP_N.20, align 1
  ; 8 movl    -8(%rbp), %eax
  %memload1 = load i32, ptr %RBP_N.8, align 1

  ; eax 对应 %EAX 这个 llvm 局部变量
  ; 9 addl    $1, %eax
  %EAX = add i32 %memload1, 1
  ; x86 的 addl 指令会设置 cf, pf, zf, of, sf 这几个 flag 寄存器:
  ; https://en.wikipedia.org/wiki/FLAGS_register
  ; cf: carry, 表示无符号加法是否有进位
  ; of: overflow, 表示有符号加法是否有溢出
  ; zf: zero, 表示结果是否为 0
  ; sf: sign, 表示正负
  ; pf: parity, 表示结果低 8 位中 1 的个数是奇数还是偶数
  ; 这里通过 llvm.{s,u}add.with.overflow.i32 intrinsic 重新计算了 `addl $1, %eax`,
  ; 并根据结果设置各个 flag
  %5 = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %memload1, i32 1)
  ; 通过返回的 i1 类型的值判断是否有 cf
  %CF = extractvalue { i32, i1 } %5, 1
  %6 = and i32 %EAX, 255
  %7 = call i32 @llvm.ctpop.i32(i32 %6)
  %8 = and i32 %7, 1
  ; 根据 eax 低 8 位 1 的个数 (llvm.ctpop.i32) 设置 pf
  %PF = icmp eq i32 %8, 0
  ; 通过 %eax 的值是否为零设置 zf
  %ZF = icmp eq i32 %EAX, 0
  ; -2147483648 为 0x80000000, 根据符号位设置 sf
  %highbit = and i32 -2147483648, %EAX
  %SF = icmp ne i32 %highbit, 0
  ; OF 表示有符号加法溢出, 所以通过 llvm.sadd.with.overflow.i32 又计算了一次加法...
  %9 = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %memload1, i32 1)
  %OF = extractvalue { i32, i1 } %9, 1

  ; 10 movl    %eax, -24(%rbp)
  store i32 %EAX, ptr %stktop_4, align 1
  ; 11 movl    -24(%rbp), %eax
  %memload2 = load i32, ptr %stktop_4, align 1
  ; mctoll 知道 systemv abi 通过 eax 保存返回值
  ret i32 %memload2
}

1.2. 总结

想像中的 assembly lifting 的工作方式:

c -> llvm ir -> asm ---+
        ^              |
        |              |
        +---lifting----+

实现上 assembly lifting 的工作方式:

c -> llvm ir -> asm --lifting--> llvm ir

mctoll 的主要思路是:

汇编中的寄存器, stack 等均被转换为 llvm 局部变量
把汇编指令转换为 llvm 指令以及 llvm intrinsic
特别的, 需要根据调用约定识别出函数参数和返回值, 对应 llvm 的函数参数和返回值, 而不是普通的局部变量

由于 x86 指令的复杂性 (例如 addl 对各个 flag 寄存器的修改), 一条 x86 汇编往往需要生成多条 llvm 指令

mctoll 把寄存器做为 llvm 局部变量的做法, 和 QEMU TCG 类似. 不同的是, mctoll 可以使用 llvm opt 和 llc 对 llvm ir 进行优化和 lower, 最终这些局部变量极可能会重新变成寄存器. 另外, llvm opt 也可以去掉一些没有用到的 llvm ir (例如针对 flag 寄存器的处理)

例如, 通过 mctoll+opt+llc 生成的 riscv 汇编为:

main:
    addi    sp, sp, -32
    lui     a2, 228023
    slli    a2, a2, 2
    addi    a2, a2, -273
    sd      a2, 0(sp)
    li      a2, 0
    sw      a2, 28(sp)
    sw      a0, 24(sp)
    sd      a1, 16(sp)
    lw      a0, 24(sp)
    sw      a0, 12(sp)
    lw      a0, 24(sp)
    addiw   a0, a0, 1
    addi    sp, sp, 32
    ret

1.3. 为什么使用 llvm ir

尝试把 x86 asm 直接转换为 riscv asm:

main:
    # prologue:
    # riscv 的 prologue 类似于下面这种:
    # addi sp, sp, xxx
    # sw ra, xx(sp)
    # sw .....
    # 需要计算出 stack size, csr, 还要考虑 riscv 对 stack 对齐的要求
    pushq   %rbp
    movq    %rsp, %rbp
    # 可以把 rbp 可以映射为 fp, 但是若 target 不支持 fp 怎么处理? 手工转换为 sp?
    movl    $0, -4(%rbp)
    # edi, rsi 可以映射为 a0, a1, 但 riscv 的 calling convertion 与 x86 不同, 例
    # 如 x86 前 6 个参数放在寄存器, 其它放在栈上, 但 riscv 前 8 个放在寄存器上,
    # 需要怎么转换
    movl    %edi, -8(%rbp)
    # 如果 riscv 不支持 rv64g, 无法直接映射 64 位的 rsi 到 riscv 寄存器
    movq    %rsi, -16(%rbp)
    # x86_64 只有 10 个 gpr, 但 riscv 有 32 个 gpr, 直接映射无法利用全部 riscv 寄存器
    movl    -8(%rbp), %eax
    movl    %eax, -20(%rbp)
    movl    -8(%rbp), %eax
    # x86 的 addl 需要修改多个 flag, riscv 需要生成多条指令, 这些指令分配寄存器
    # 时怎么避免冲突? riscv 中如何检查 add 是否有溢出?
    addl    $1, %eax
    movl    %eax, -24(%rbp)
    movl    -24(%rbp), %eax
    popq    %rbp
    retq