Logo
Project Icon

mir

多平台轻量级JIT编译器框架

MIRJIT编译器中间表示代码优化编译器项目Github开源项目

MIR是一个轻量级JIT编译器框架，为快速高效的即时编译器实现提供基础。支持x86_64、ARM64、POWER等多种架构，采用强类型中间表示。MIR提供API用于创建模块、函数和指令，支持二进制和文本格式代码处理。编译器使用简化优化流程，包括函数内联和全局公共子表达式消除等，在编译速度和代码性能间取得平衡。MIR适用于需要快速、轻量级JIT编译的项目开发。

GithubGithub文档文档
介绍相关项目

GitHub MIR 测试状态 GitHub MIR 在 Apple Silicon 上的测试状态 GitHub MIR 在 aarch64 上的测试状态 GitHub MIR 在 ppc64le 上的测试状态 GitHub MIR 在 s390x 上的测试状态 GitHub MIR 在 riscv64 上的测试状态 GitHub MIR 基准测试状态

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

  • 内联：内联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 -O2gcc -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 -O2gcc -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 -O21.001.00
gcc -O00.630.57
c2m -eg0.960.91
c2m -eb0.920.85
chibicc0.380.30
clang -O21.121.09
cparser -O31.020.98
cproc0.680.65
lacc -O30.470.39
pcc -O0.800.78
tcc0.540.50
emcc -O2/wasmer0.600.55
wasi -O2/wasmer cranelift0.600.54
wasi -O2/wasmer LLVM0.780.72
wasi -O2/wasmer singlepass0.450.36
wasi -O2/wasmtime0.920.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）移植到另一个目标平台
相关项目
项目侧边栏1项目侧边栏2
推荐项目
Project Cover

豆包MarsCode

豆包 MarsCode 是一款革命性的编程助手，通过AI技术提供代码补全、单测生成、代码解释和智能问答等功能，支持100+编程语言，与主流编辑器无缝集成，显著提升开发效率和代码质量。

Project Cover

AI写歌

Suno AI是一个革命性的AI音乐创作平台，能在短短30秒内帮助用户创作出一首完整的歌曲。无论是寻找创作灵感还是需要快速制作音乐，Suno AI都是音乐爱好者和专业人士的理想选择。

Project Cover

有言AI

有言平台提供一站式AIGC视频创作解决方案，通过智能技术简化视频制作流程。无论是企业宣传还是个人分享，有言都能帮助用户快速、轻松地制作出专业级别的视频内容。

Project Cover

Kimi

Kimi AI助手提供多语言对话支持，能够阅读和理解用户上传的文件内容，解析网页信息，并结合搜索结果为用户提供详尽的答案。无论是日常咨询还是专业问题，Kimi都能以友好、专业的方式提供帮助。

Project Cover

阿里绘蛙

绘蛙是阿里巴巴集团推出的革命性AI电商营销平台。利用尖端人工智能技术，为商家提供一键生成商品图和营销文案的服务，显著提升内容创作效率和营销效果。适用于淘宝、天猫等电商平台，让商品第一时间被种草。

Project Cover

吐司

探索Tensor.Art平台的独特AI模型，免费访问各种图像生成与AI训练工具，从Stable Diffusion等基础模型开始，轻松实现创新图像生成。体验前沿的AI技术，推动个人和企业的创新发展。

Project Cover

SubCat字幕猫

SubCat字幕猫APP是一款创新的视频播放器，它将改变您观看视频的方式！SubCat结合了先进的人工智能技术，为您提供即时视频字幕翻译，无论是本地视频还是网络流媒体，让您轻松享受各种语言的内容。

Project Cover

美间AI

美间AI创意设计平台，利用前沿AI技术，为设计师和营销人员提供一站式设计解决方案。从智能海报到3D效果图，再到文案生成，美间让创意设计更简单、更高效。

Project Cover

AIWritePaper论文写作

AIWritePaper论文写作是一站式AI论文写作辅助工具，简化了选题、文献检索至论文撰写的整个过程。通过简单设定，平台可快速生成高质量论文大纲和全文，配合图表、参考文献等一应俱全，同时提供开题报告和答辩PPT等增值服务，保障数据安全，有效提升写作效率和论文质量。

使用协议隐私政策广告服务
投诉举报邮箱: service@vectorlightyear.com
@2024 懂AI·鲁ICP备2024100362号-6·鲁公网安备37021002001498号