MIR 项目

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

免责声明

除了这里给出的测试和在 x86_64 Linux/OSX、aarch64 Linux/OSX(Apple M1)、ppc64le/s390x/riscv64 Linux 平台上的测试外，绝对不保证代码在任何其他测试或平台上能正常工作

MIR

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

MIR 示例

您可以通过由创建模块、函数、指令、操作数等函数组成的 API 来创建 MIR
您也可以从 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) = %d\n"
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 字符串可以直接用作指令操作数。在这种情况下，数据将被添加到模块中，并使用数据地址作为操作数
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 是由 MIR_init 创建的上下文 */
    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);
    /* 或使用 MIR_set_gen_interface 生成并使用机器代码 */
    /* 或使用 MIR_set_lazy_gen_interface 在函数首次调用时生成代码 */
    /* 使用 MIR_gen (ctx, func) 显式生成函数的机器代码 */
    MIR_interp (ctx, func, &result, 0); /* 这里的零是参数数量 */
    /* 或 ((void (*) (void)) func->addr) (); 通过接口调用解释或生成的代码 */

在 Linux 上通过 `binfmt_misc` 运行二进制 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项目的当前状态

当前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项目的可能未来状态

未来MIR

WASM到MIR的转换应该相当直接
- 只需为MIR提供一个小型WASM运行时，用于WASM浮点数舍入指令
将GCC移植到MIR也是可能的。有经验的GCC开发者可以在6到12个月内完成此工作
据我估计，将MIR JIT编译器移植到mips64或sparc64每个目标平台需要1-2个月的工作
为了性能考虑，将MIR JIT编译器移植到32位目标平台需要实施额外的小型分析过程，以获取哪些64位变量仅在32位指令中使用的信息

MIR JIT编译器

非常短的优化流程，以保证速度和轻量级
仅使用最有价值的优化：
- 函数内联
- 全局公共子表达式消除
- 变量重命名
- 寄存器压力敏感的循环不变代码移动
- 条件常量传播
- 死代码消除
- 代码选择
- 快速寄存器分配器，具有
  - 积极的寄存器和栈槽位合并以消除复制
  - 生存期分割
不同的优化级别，以调整编译速度和生成代码性能
在寄存器分配之前使用MIR的SSA形式
- 我们使用Braun算法的一种形式来构建SSA（M. Braun等人的"简单高效的静态单赋值形式构建"）
优化实现的简单性优先于极致的生成代码性能
关于完整JIT编译器流程的更多细节：
简化：降低MIR
内联：内联MIR调用
构建CFG：构建控制流图（基本块和CFG边）
构建SSA：通过向操作数添加phi节点和SSA边来构建静态单赋值形式
地址转换：移除或更改MIR ADDR指令
全局值编号：通过GVN移除冗余指令。这包括常量传播和冗余加载消除
复制传播：SSA复制传播和移除冗余扩展指令
死存储消除：移除冗余存储
死代码消除：移除未使用输出的指令
压力缓解：移动指令以减少寄存器压力
SSA合并：合并地址以及比较和分支指令对
SSA转出：移除phi节点和SSA边
跳转优化：各种跳转优化
机器化：运行机器相关代码，为调用ABI、2操作数指令等转换MIR
查找循环：查找自然循环并构建循环树
构建活跃信息：计算基本块的活跃入口和活跃出口
构建寄存器冲突：为移动中涉及的寄存器构建冲突矩阵。用于寄存器合并
合并：积极的寄存器合并
寄存器分配器（RA）：基于优先级的线性扫描RA，具有生存期分割
构建生存期范围：计算寄存器的程序点范围
分配：-O0使用快速RA，-O1及以上使用基于优先级的线性扫描RA
重写：根据分配使用保留的硬寄存器转换MIR
合并（代码选择）：将数据相关指令合并为一条
死代码消除：移除未使用输出的指令
生成机器指令：运行机器相关代码创建机器指令

C到MIR的转换

我们实现了一个小型C11（2011 ANSI C标准，带有一些GCC扩展）到MIR的编译器c2m。参见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的代码
文件mir-bin-driver.c和b2ctab工具可用于以可移植的方式从MIR二进制文件生成二进制文件
目录mir-utils包含用于处理MIR的各种工具，例如将二进制MIR转换为文本MIR，反之亦然
目录adt-tests、mir-tests、c-tests和c-benchmarks包含用于测试和基准测试MIR和c2m的代码

使用当前MIR项目代码

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

当前MIR性能数据

在搭载64GB内存的Intel i5-13600K上，运行FC37和GCC-12.3.1

	MIR生成器	MIR解释器	gcc -O2	gcc -O0
编译[1]	1.0 (249us)	0.09 (22us)	109 (27.1ms)	105 (26.1ms)
执行[2]	1.0 (1.74s)	13.7 (23.8s)	0.92 (1.6s)	2.28 (3.97s)
代码大小[3]	1.0 (557KB)	0.43 (240KB)	58 (32.2MB)	58 (32.2MB)
代码行数[4]	1.0 (23.4K)	0.48 (11.3K)	103 (2420K)	103 (2402K)

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

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

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

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

当前C2MIR性能数据

在搭载64GB内存的Intel i5-13600K上，运行FC37和GCC-12.3.1

	c2m -O2 -eg（生成器）	c2m -ei（解释器）	gcc -O2	gcc -O0
编译[1]	1.0 (336us)	1.0 (337us)	80 (27.1ms)	77 (26.1ms)
执行[2]	1.0 (1.74s)	13.7 (23.8s)	0.92 (1.6s)	2.28 (3.97s)
代码大小[3]	1.0 (961KB)	1.0 (961KB)	34 (32.2MB)	34 (32.2MB)
代码行数[4]	1.0 (54.8K)	1.0 (54.8K)	44 (2420K)	44 (2420K)

[1] 基于C筛选代码的编译耗时（不包含任何头文件，并为GCC使用内存文件系统）

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

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

[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）运行时的Emscripten编译器，用于WebAssembly
- wasi cranelift是基于cranelift后端的C到WebAssembly的clang编译器（11.0.0），使用wasmer（1.0.2）
- wasi LLVM是基于LLVM后端的C到WebAssembly的clang编译器（11.0.0），使用wasmer（1.0.2）
- wasi singlepass是基于singlepass后端的C到WebAssembly的clang编译器（11.0.0），使用wasmer（1.0.2）
- wasi wasmtime是基于cranelift后端的C到WebAssembly的clang编译器（11.0.0），使用wasmtime（0.26.0）运行时

	平均值	几何平均值
gcc -O2	1.00	1.00
gcc -O0	0.63	0.57
c2m -eg	0.96	0.91
c2m -eb	0.92	0.85
chibicc	0.38	0.30
clang -O2	1.12	1.09
cparser -O3	1.02	0.98
cproc	0.68	0.65
lacc -O3	0.47	0.39
pcc -O	0.80	0.78
tcc	0.54	0.50
emcc -O2/wasmer	0.60	0.55
wasi -O2/wasmer cranelift	0.60	0.54
wasi -O2/wasmer LLVM	0.78	0.72
wasi -O2/wasmer singlepass	0.45	0.36
wasi -O2/wasmtime	0.92	0.87

MIR项目的竞争对手

我只看到三个项目可以被视为或改编为真正的通用轻量级JIT竞争对手
QBE:
- 体积小（10K行C代码）
- 使用基于SSA的IR（类似简化版的LLVM IR）
- 具有与MIR生成器相同的优化，外加别名分析，但QBE没有内联
- 生成汇编代码，使QBE在机器代码生成速度上比MIR生成器慢30倍
- 在我的基准测试中，它生成的代码性能几何平均值仅为GCC -O2的65% （MIR生成的代码性能为GCC -O2的91%），同时编译速度与MIR相当
LIBJIT 起源于DotGNU项目：
- LIBJIT规模较大：
  - 80K行C代码（不包括动态Pascal编译器），而MIR只有20K行C代码（不包括C到MIR编译器）
- LIBJIT的优化较少：只有复制传播和寄存器分配
RyuJIT 是.NET Core运行时的一部分：
- RyuJIT规模更大：360K SLOC
- RyuJIT的优化基本上是MIR生成器的优化
- RyuJIT使用SSA
其他候选项：
- LIBFirm：独立性较差、规模大（140K LOC）、使用SSA、生成汇编代码、使用LGPL2许可
- CraneLift：独立性较差、规模大（70K行Rust代码）、使用SSA、Apache许可
- NanoJIT，独立性好、中等规模（40K行C++代码）、仅简单RA、 Mozilla公共许可证

移植MIR

目前MIR可在x86_64、aarch64、ppc64le、s390x、riscv64 Linux和x86_64/aarch64（Apple M1）MacOS上运行
HOW-TO-PORT-MIR.md概述了移植MIR的过程
- 据我估计，一个经验丰富的开发者可以在1-2个月内将MIR（包括c2m）移植到另一个目标平台