mir

米尔项目

• MIR 表示中等内部表示
• MIR 项目目标是为实现快速、轻量级 JIT 提供基础
• 计划首先尝试 MIR 轻量级 JIT 用于 CRuby 或/和 MRuby 实现
• 该项目的动机可以在这篇博客文章中找到
• C2MIR 编译器描述可以在这篇博文中找到
• 动态语言 JIT 的 MIR 代码专业化的未来可以在这篇博文中找到

免责声明

• 绝对不保证代码适用于任何测试，除了此处给出的测试以及 x86_64 Linux/OSX、aarch64 Linux/OSX(Apple M1) 和 ppc64le/s390x/riscv64 Linux 以外的平台上的测试

米尔

• MIR 是强类型 IR
• MIR可以表示不同架构的机器32位和64位insn
• MIR.md 包含 MIR 及其 API 的详细说明。以下是 MIR 的简要描述：
• MIR 由模块组成
  • 每个模块可以包含函数和一些声明和数据
  • 每个函数都有签名（参数和返回类型）、局部变量（包括函数参数）和指令
    • 每个局部变量的类型只能是 64 位整数、浮点、双精度或长双精度，并且可以绑定到特定的目标机器寄存器
    • 每条指令都有操作码和操作数
      • 操作数可以是局部变量（或函数参数）、立即数、内存、标签或引用
        • 立即操作数可以是 64 位整数、浮点、双精度或长双精度值
    • 内存操作数具有类型、位移、基数和索引整数局部变量，以及作为索引比例的整数常量
      • 内存类型可以是 8 位、16 位、32 位和 64 位有符号或无符号整数类型、浮点类型、双精度或长双精度类型
        • 当使用整数内存值时，它首先用符号或零扩展为 64 位整数值
    • 标签操作数有名称并用于控制流指令
    • 引用操作数用于引用当前模块、其他 MIR 模块或 C 外部函数或声明中的函数和声明
  • 操作码描述了指令的作用
  • 有用于不同 32 位和 64 位有符号和无符号值、float、double 和 long double 值之间转换的转换指令
  • 算术指令（加法、减法、乘法、除法、取模）可处理 32 位和 64 位有符号和无符号值、浮点型、双精度型和长双精度型值
  • 有一些逻辑指令（与、或、异或、不同的移位）可处理 32 位和 64 位有符号和无符号值
  • 有适用于 32 位和 64 位有符号和无符号值、浮点型、双精度型和长双精度型值的比较指令
  • 有局部变量地址指令来获取局部变量的地址
  • 有一些分支 insns （无条件跳转，以及在零或非零值上跳转），它们将标签作为其操作数之一
  • 有组合比较和分支指令，将标签作为一个操作数以及两个 32 位和 64 位有符号和无符号值、浮点、双精度和长双精度值
  • 有switch指令，根据作为第一个操作数给出的索引，从作为操作数给出的标签跳转到标签
  • 有获取标签地址的标签地址指令和操作数包含先前获取的标签地址的无条件间接跳转指令
  • 有函数和程序调用指令
  • 有返回指令可选择返回 32 位和 64 位整数值、浮点型、双精度型和长双精度型值
  • 有专门的轻量级调用和返回指令可用于从线程解释器快速切换到 JITted 代码，反之亦然
  • 当使用惰性基本块版本控制时，有一些属性指令可以生成专门的机器代码

米尔例子

• 您可以通过API创建MIR，该API由用于创建模块、函数、指令、操作数等的函数组成
• 您还可以从 MIR二进制或文本文件创建 MIR
• 了解 MIR 的最佳方法是使用文本 MIR 表示
• C 上的埃拉托色尼筛示例

 #define Size 819000
int sieve ( int N ) {
  int64_t i , k , prime , count , n ; char flags [ Size ];

  for ( n = 0 ; n < N ; n ++ ) {
    count = 0 ;
    for ( i = 0 ; i < Size ; i ++ )
      flags [ i ] = 1 ;
    for ( i = 0 ; i < Size ; i ++ )
      if ( flags [ i ]) {
        prime = i + i + 3 ;
        for ( k = i + prime ; k < Size ; k += prime )
          flags [ k ] = 0 ;
        count ++ ;
      }
  }
  return count ;
}
void ex100 ( void ) {
  printf ("sieve (100) = %d", sieve (100));
}

• 相同功能的 MIR 文本文件示例：

 m_sieve :  module
          export sieve
sieve :    func i32, i32:N
          local i64:iter, i64:count, i64:i, i64:k, i64:prime, i64:temp, i64:flags
          alloca flags, 819000
          mov iter, 0
loop :     bge fin, iter, N
          mov count, 0;  mov i, 0
loop2 :    bge fin2, i, 819000
          mov u8:(flags, i), 1;  add i, i, 1
          jmp loop2
fin2 :     mov i, 0
loop3 :    bge fin3, i, 819000
          beq cont3, u8:(flags,i), 0
          add temp, i, i;  add prime, temp, 3;  add k, i, prime
loop4 :    bge fin4, k, 819000
          mov u8:(flags, k), 0;  add k, k, prime
          jmp loop4
fin4 :     add count, count, 1
cont3 :    add i, i, 1
          jmp loop3
fin3 :     add iter, iter, 1
          jmp loop
fin :      ret count
          endfunc
          endmodule
m_ex100 :  module
format :   string "sieve (10) = %dn"
p_printf : proto p:fmt, i32:result
p_sieve :  proto i32, i32:iter
          export ex100
          import sieve, printf
ex100 :    func v, 0
          local i64:r
          call p_sieve, sieve, r, 100
          call p_printf, printf, format, r
          endfunc
          endmodule

• func描述函数的签名（采用 32 位有符号整数参数并返回 32 位有符号整数值）和函数参数N ，它将是 64 位有符号整数类型的局部变量
  • 函数结果首先由其类型描述，并且没有名称。参数总是有名称并位于结果描述之后
  • 函数可能有多个结果，但结果类型的可能数量和组合当前由机器定义
• 如果用 ; 分隔的话，您可以在一行上编写多条指令;
• 指令结果（如果有）始终是第一个操作数
• 我们在计算中使用64位指令
• 我们可以在计算中使用 32 位指令，如果我们使用 32 位 CPU，这将是有意义的
  • 当我们使用 32 位指令时，我们仅采用 64 位操作数的 32 位有效部分，结果的高 32 位部分是机器定义的（因此，如果您编写可移植的 MIR 代码，请考虑高 32 位部分值是不明确的）
• string以C字符串的形式描述数据
  • C字符串可以直接用作insn操作数。在这种情况下，数据将被添加到模块中，并且数据地址将用作操作数
• export描述当前模块外部可见的模块功能或数据
• import描述了应该在其他 MIR 模块中定义的模块函数或数据
• proto描述了函数原型。其语法与func语法相同
• call是调用函数的 MIR 指令

运行 MIR 代码

• 创建 MIR 模块（通过 MIR API 或读取 MIR 二进制或文本文件）后，您应该加载模块
  • 加载模块使导出的模块功能和数据可见
  • 您可以使用MIR_load_external加载外部 C 函数
• 加载模块后，您应该链接加载的模块
  • 链接模块解析导入的模块引用、初始化数据并设置调用接口
• 链接后，您可以解释模块中的函数或调用 MIR JIT 编译器（生成器）生成的函数的机器代码。函数以何种方式执行通常由设置接口来定义。生成的代码的生成方式（第一次调用时延迟或提前）也可能取决于接口
• 运行上面示例中的代码可能如下所示（此处m1和m2是模块m_sieve和m_e100 ， func是函数ex100 ， sieve是函数sieve ）：

    /* ctx is a context created by MIR_init / MIR_init2 */
    MIR_load_module ( ctx , m1 ); MIR_load_module ( ctx , m2 );
    MIR_load_external ( ctx , "printf" , printf );
    MIR_link ( ctx , MIR_set_interp_interface , import_resolver );
    /* or use MIR_set_gen_interface to generate and use the machine code */
    /* or use MIR_set_lazy_gen_interface to generate function code on its 1st call */
    /* use MIR_gen (ctx, func) to explicitly generate the function machine code */
    MIR_interp ( ctx , func , & result , 0 ); /* zero here is arguments number  */
    /* or ((void (*) (void)) func->addr) (); to call interpr. or gen. code through the interface */

通过binfmt_misc在 Linux 上运行二进制 MIR 文件

mir-bin-run二进制文件已准备好通过binfmt_misc使用以下行（示例）：

line=:mir:M::MIR::/usr/local/bin/mir-bin-run:P
echo $line > /proc/sys/fs/binfmt_misc/register

请根据您的系统调整 mir-bin-run 二进制路径，这是默认路径

并运行

c2m your-file.c -o your-file
chmod +x your-file
./your-file your args

可执行文件可通过环境变量“配置”：

• MIR_TYPE设置代码执行的接口： interp （用于解释）、 jit （用于生成）和lazy （用于延迟生成，默认）；
• MIR_LIBS （冒号分隔列表）定义要加载的额外库的列表；
• MIR_LIB_DIRS或LD_LIBRARY_PATH （冒号分隔列表）定义用于搜索库的额外目录列表。

由于mir-bin-run与binfmt_misc的绑定性质，直接调用mir-bin-run可能有点奇怪。 binfmt_misc 上的P标志传递一个额外的参数，其中包含 MIR 二进制文件的完整路径。

MIR项目的现状

• 您可以使用 C setjmp/longjmp函数在 MIR 中实现longjump
• 二进制 MIR 代码通常比类似的 MIR 文本代码紧凑 10 倍，读取速度快 10 倍
• MIR 解释器比 MIR JIT 编译器生成的代码慢大约 6-10 倍
• LLVM IR 到 MIR 的转换器尚未完成，可能永远不会完全实现，因为 LLVM IR 比 MIR 丰富得多，但将从标准 C/C++ 生成的 LLVM IR 转换为 MIR 是一项可行的任务

MIR 项目未来可能的状态

• WASM 到 MIR 的转换应该非常简单
  • 只需要为 MIR 提供用于 WASM 浮点轮 insns 的小型 WASM 运行时
• 将 GCC 移植到 MIR 也是可能的。经验丰富的 GCC 开发人员可以花 6 到 12 个月的时间来实现这一点
• 据我估计，将 MIR JIT 编译器移植到 mips64 或 sparc64 将需要每个目标 1-2 个月的工作时间
• 考虑到性能，将 MIR JIT 编译器移植到 32 位目标将需要实现额外的小分析过程，以获取仅在 32 位指令中使用哪些 64 位变量的信息

MIR JIT 编译器

• 优化流程非常短，速度快且重量轻

• 仅最有价值的优化用途：

  • 函数内联
  • 全局公共子表达式消除
  • 变量重命名
  • 注册压敏循环不变代码运动
  • 条件常数传播
  • 死代码消除
  • 代码选择
  • 快速寄存器分配器
    • 积极合并寄存器和堆栈槽以消除复制
    • 生存范围分割

• 不同的优化级别可调整编译速度与生成的代码性能

• MIR 的SSA形式用于寄存器分配之前

  • 我们使用 Braun 算法的一种形式来构建 SSA（M. Braun 等人的“Simple and Efficient Construction of Static Single Assignment Form”）

• 针对极端生成代码性能的优化实施的简单性

• 有关完整 JIT 编译器管道的更多详细信息：

• 简化：降低 MIR

• Inline ：内联 MIR 调用

• Build CFG ：构建控制流图（基本块和CFG边）

• 构建 SSA ：通过向操作数添加 phi 节点和 SSA 边来构建单一静态赋值形式

• 地址转换：删除或更改 MIR ADDR 指令

• 全球价值编号：通过 GVN 删除冗余 insn。这包括恒定传播和冗余负载消除

• 复制传播：SSA复制传播并删除冗余扩展指令

• 死店消除：删除多余的店

• 死代码消除：删除具有未使用输出的insn

• 压力释放：移动insns以降低套准压力

• SSA组合：组合地址以及比较和分支指令对

• SSA 之外：删除 phi 节点和 SSA 边

• Jump opts ：不同的跳跃优化

• Machinize ：运行机器相关代码转换 MIR 以调用 ABI、2-op insns 等

• Find Loops ：寻找自然循环并构建循环树

• 构建活信息：计算基本块的活入和活出

• 构建寄存器冲突：为涉及移动的寄存器构建冲突矩阵。它用于寄存器合并

• Coalesce ：积极的寄存器合并

• 寄存器分配器 (RA) ：基于优先级的线性扫描 RA，具有生命范围分割

• 构建生命范围：计算寄存器的程序点范围

• 分配：用于-O0的快速RA或用于-O1及以上的基于优先级的线性扫描RA

• 重写：使用保留的硬寄存器根据分配转换 MIR

• 组合（代码选择）：将数据依赖的insn合并为一个

• 死代码消除：删除具有未使用输出的insn

• 生成机器 Insns ：运行与机器相关的代码创建机器 Insns

C 到 MIR 的翻译

• 我们为 MIR 编译器c2m实现了一个小型 C11（2011 ANSI C 标准，带有一些 GCC 扩展）。请参阅 README.md
• 除了 MIR 之外，C 代码还可以用作 JIT 编译器的输入
  • 使用 C 作为 JIT 编译器的输入会使编译速度降低多达 2 倍

项目代码结构

• 文件mir.h和mir.c包含主要 API 代码，包括 MIR 二进制和 MIR 文本表示的输入/输出
• 文件mir-dlist.h 、 mir-mp.h 、 mir-varr.h 、 mir-bitmap.h 、 mir-hash.h 、 mir-htab.h 、 mir-reduce.h包含相应的双链接通用代码列表、内存池、可变长度数组、位图、哈希计算、哈希表以及压缩/解压缩数据。文件mir-hash.h是哈希表使用的通用、简单、高质量的哈希函数
• 文件mir-interp.c包含用于解释 MIR 代码的代码。它包含在mir.c中并且从不单独编译
• 文件mir-gen.h 、 mir-gen.c 、 mir-gen-x86_64.c 、 mir-gen-aarch64.c 、 mir-gen-ppc64.c 、 mir-gen-s390x.c和mir-gen-riscv64.c包含 MIR JIT 编译器的代码
  • 文件mir-gen-x86_64.c 、 mir-gen-aarch64.c 、 mir-gen-ppc64.c 、 mir-gen-s390x.c和mir-gen-riscv64.c是 JIT 编译器的机器相关代码
• 文件mir-<target>.c包含解释器和 JIT 编译器常见的简单机器相关代码
• 文件mir-<target>.h包含解释器和 JIT 编译器通用的声明
• 文件mir2c/mir2c.h和mir2c/mir2c.c包含 MIR 到 C 编译器的代码。生成的代码可能不可移植
• 文件c2mir/c2mir.h 、 c2mir/c2mir.c 、 c2mir/c2mir-driver.c和c2mir/mirc.h包含 C 到 MIR 编译器的代码。目录c2mir/x86_64和c2mir/aarch64 、 c2mir/ppc64 、 c2mir/s390x和c2mir/riscv64中的文件相应包含用于 C 到 MIR 编译器的 x86_64、aarch64、ppc64le、s390x 和 riscv 机器相关代码
• 文件mir-bin-run.c包含上述mir-bin-run的代码
• 带有b2ctab实用程序的文件mir-bin-driver.c可用于从 MIR 二进制文件生成二进制文件的便携式方式
• 目录mir-utils包含使用 MIR 的不同实用程序，例如将二进制 MIR 转换为文本 MIR，反之亦然
• 目录adt-tests 、 mir-tests 、 c-tests和c-benchmarks包含用于测试和基准测试 MIR 和c2m的代码

使用当前的 MIR 项目代码

• 您可以通过make bench和make test运行一些基准测试和测试

当前 MIR 性能数据

• Intel i5-13600K，FC37 下 64GB 内存，GCC-12.3.1

  	MIR 发生器	MIR 解释器	海合会-O2	海湾合作委员会-O0
  编译[1]	1.0 （249 秒）	0.09（22 微秒）	109 （27.1 毫秒）	105（26.1 毫秒）
  执行 [2]	1.0 （1.74秒）	13.7（23.8秒）	0.92 （1.6秒）	2.28（3.97 秒）
  代码大小 [3]	1.0 (557KB)	0.43 (240KB)	58 (32.2MB)	58 (32.2MB)
  LOC [4]	1.0 (23.4K)	0.48（11.3K）	103 (2420K)	103 (2402K)

[1] 基于 C 筛代码的编译时间（没有任何包含文件，并且使用 GCC 的内存文件系统）以及由优化级别 2 的 MIR 解释器和 MIR 生成器生成的相应 MIR 筛代码

[2] 基于使用 MIR 生成器优化级别 2 的 10 次运行的最佳运行时间

[3] 基于 GCC 和 MIR 核心的 cc1 的剥离大小以及 MIR 的解释器或生成器

[4] 我的估计仅基于 x86-64 GNU C 编译器所需的文件和用于创建和运行 MIR 代码的最小程序的 MIR 文件

当前 C2MIR 性能数据

• Intel i5-13600K，FC37 下 64GB 内存，GCC-12.3.1

  	c2m -O2 -eg（发电机）	c2m-ei（解释器）	海合会-O2	海湾合作委员会-O0
  编译[1]	1.0 （336us）	1.0（337 秒）	80 （27.1 毫秒）	77（26.1 毫秒）
  执行 [2]	1.0 （1.74秒）	13.7（23.8秒）	0.92 （1.6秒）	2.28（3.97 秒）
  代码大小 [3]	1.0 (961KB)	1.0 (961KB)	34 (32.2MB)	34 (32.2MB)
  LOC [4]	1.0 (54.8K)	1.0 (54.8K)	44 (2420K)	44 (2420K)

[1] 基于 C sieve 代码的编译时间（没有任何包含文件并使用 GCC 内存文件系统）

[2] 基于使用 MIR 生成器优化级别 2 的 10 次运行的最佳运行时间

[3] 基于 GCC 和 C2MIR、MIR 核心、解释器和 MIR 生成器的 cc1 的剥离大小

[4] 基于除测试之外的所有源文件

• 下面是在同一台机器上针对不同 C 编译器在 15 个小型 C 基准测试（来自目录c-benchmarks ）上生成的与 GCC -O2 相关的代码性能，其中

  • gcc版本是12.3.1
  • clang 版本是 15.0.7
  • chibicc 是 Rui Ueyama 的最新 C11 实现
  • cparser 是一个基于相当复杂的后端 libFirm 版本 1.22 的 C99 实现
  • cproc 是 Michael Forney 基于QBE编译器后端的 C11 实现
  • lacc 是 C89 实现
  • pcc (1.2.0.DEVEL) 是便携式 C 编译器的现代版本
  • tcc (0.9.27) 是微型 C11 编译器
  • emcc (2.0.20) 是带有 wasmer (1.0.2) 运行时的 WebAssembly 的 emscripten 编译器
  • wasi Cranelift 是一个 C 到 webassember clang 编译器 (11.0.0)，带有基于 Cranelift 后端的 wasmer (1.0.2)
  • wasi LLVM 是一个 C 到 webassember clang 编译器 (11.0.0)，带有基于 LLVM 后端的 wasmer (1.0.2)
  • wasi singlepass 是一个 C 到 webassember clang 编译器 (11.0.0)，带有基于 singlepass 后端的 wasmer (1.0.2)
  • wasi wasmtime 是一个 C 到 webassember clang 编译器 (11.0.0)，具有基于 Cranelift 后端的 wasmtime (0.26.0) 运行时

  	平均的	几何平均法
  海合会-O2	1.00	1.00
  海湾合作委员会-O0	0.63	0.57
  c2m-eg	0.96	0.91
  c2m-eb	0.92	0.85
  奇比克	0.38	0.30
  铿锵-O2	1.12	1.09
  cparser-O3	1.02	0.98
  进程	0.68	0.65
  紫胶-O3	0.47	0.39
  聚碳酸酯-O	0.80	0.78
  TCC	0.54	0.50
  emcc-O2/wasmer	0.60	0.55
  wasi -O2/wasmer 起重机	0.60	0.54
  wasi-O2/wasmer LLVM	0.78	0.72
  wasi-O2/wasmer 单通道	0.45	0.36
  瓦西-O2/wasmtime	0.92	0.87

MIR 项目竞争对手

• 我只看到三个项目可以被考虑或改编为真正的通用轻量级 JIT 竞争对手
• 质量保证：
  • 体积小（10K C 线）
  • 它使用基于 SSA 的 IR（一种简化的 LLVM IR）
  • 它具有与 MIR 生成器相同的优化以及别名，但 QBE 没有内联
  • 它生成汇编代码，这使得 QBE 30 的机器代码生成速度比 MIR 生成器慢
  • 在我的基准测试中，它生成的代码的 geomean 性能仅为带有 -O2 的 GCC 的 65%（MIR 生成的代码的性能是带有 -O2 的 GCC 的 91%），同时具有与 MIR 相同的编译速度
• LIBJIT作为 DotGNU 项目的一部分开始：
  • LIBJIT 更大：
    • 80K C 行（对于没有动态 Pascal 编译器的 LIBJIT）与 MIR 的 20K C 行（不包括 C 到 MIR 编译器）
  • LIBJIT 的优化较少：仅复制传播和寄存器分配
• RyuJIT是 .NET Core 运行时的一部分：
  • RyuJIT 更大：360K SLOC
  • RyuJIT 优化基本上是 MIR 生成器优化
  • RyuJIT 使用 SSA
• 其他候选人：
  • LIBFirm ：较少独立、大（140K LOC）、SSA、ASM 生成、LGPL2
  • CraneLift ：较少独立、大（Rust 的 70K LOC）、SSA、Apache 许可证
  • NanoJIT ，独立+，中等（40K C++ LOC），仅简单的 RA-，Mozilla 公共许可证

移植米尔

• 目前，MIR 适用于 x86_64、aarch64、ppc64le、s390x、riscv64 Linux 和 x86_64/aarch64 (Apple M1) MacOS
• HOW-TO-PORT-MIR.md 概述了移植 MIR 的过程
  • 据我估计，经验丰富的开发人员可以将 MIR （包括c2m ）移植到另一个目标 1-2 个月