V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Mohanson
V2EX  ›  程序员

手写 JIT 编译器, 三天时间能学会吗(狗头, 第一天)?

  •  6
     
  •   Mohanson · 2020-05-22 22:30:27 +08:00 · 2895 次点击
    这是一个创建于 1406 天前的主题,其中的信息可能已经有所发展或是发生改变。

    是这样的, 楼主正准备写 WebAssembly 的 JIT 编译器, 但苦于从未接触过这方面, 所以不得不开始找资料, 大概从开始 google 开始到写出第一个图灵完备语言 brainfuck 的 JIT 编译器大概耗时三天, 8 个小时左右. 感受是资料特别少, 是真的少... 因此将这三天我看的资料和写的代码整理分享一下.

    我做了三张图来直观展示纯解释器, IR 优化和 JIT 编译器的速度对比, 测试程序是 BF 编写的 mandelbrot 程序(第一张图这么慢并不是你网络不好, 真的).

    img

    img

    img

    那么, 正文开始吧.

    背景

    下文介绍摘取并翻译自: https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html.

    "JIT" 一词往往会唤起工程师内心最深处的恐惧和崇拜,通常这并没有什么错, 只有最核心的编译器团队才能梦想创建这种东西. 它会使你联想到 JVM 或 .NET, 这些家伙都是具有数十万行代码的超大型运行时. 你永远不会看到有人向你介绍 "Hello World!" 级别的 JIT 编译器, 但事实上只需少量代码即可完成一些有趣的工作. 本文试图改变这一点.

    编写一个 JIT 编译器只需要四步, 就和把大象装到冰箱里一样简单:

    • 申请一段可写和可执行的内存
    • 将源码翻译为汇编
    • 将汇编写入第一步申请的内存
    • 执行这部分内存

    Hello, JIT World: The Joy of Simple JITs

    事不宜迟, 让我们跳进我们的第一个 JIT 程序. 该代码是特定于 64 位 Unix 的, 因为它使用了 mmap. 因此读者需要拥有支持该代码的处理器和操作系统. 笔者已经测试了它可以在 Ubuntu 和 Mac OS X 上运行.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <sys/mman.h>
    
    int main(int argc, char *argv[]) {
      // Machine code for:
      //   mov eax, 0
      //   ret
      unsigned char code[] = {0xb8, 0x00, 0x00, 0x00, 0x00, 0xc3};
    
      if (argc < 2) {
        fprintf(stderr, "Usage: jit1 <integer>\n");
        return 1;
      }
    
      // Overwrite immediate value "0" in the instruction
      // with the user's value.  This will make our code:
      //   mov eax, <user's value>
      //   ret
      int num = atoi(argv[1]);
      memcpy(&code[1], &num, 4);
    
      // Allocate writable/executable memory.
      // Note: real programs should not map memory both writable
      // and executable because it is a security risk.
      void *mem = mmap(NULL, sizeof(code), PROT_WRITE | PROT_EXEC,
                       MAP_ANON | MAP_PRIVATE, -1, 0);
      memcpy(mem, code, sizeof(code));
    
      // The function will return the user's value.
      int (*func)() = mem;
      return func();
    }
    

    似乎很难相信上面的 33 行代码是一个合法的 JIT. 它动态生成一个函数, 该函数返回运行时指定的整数, 然后运行该函数. 读者可以验证其是否正常运行:

    JIT 生成的函数大概是下面这个样子, 但它是使用纯汇编编写的.

    int fn(int x) {
        return x;
    }
    
    $ gcc -o jit jit.c
    $ ./jit 42
    $ echo $?
    # 42
    

    您会注意到, 代码中使用 mmap() 分配内存, 而不是使用 malloc() 从堆中获取内存的常规方法. 这是必需的, 因为我们需要内存是可执行的, 因此我们可以跳转到它而不会导致程序崩溃. 在大多数系统上, 堆栈和堆都配置为不允许执行, 因为如果您要跳转到堆栈或堆, 则意味着发生了很大的错误. 更糟糕的是, 利用缓冲区溢出的黑客可以使用可执行堆栈来更轻松地利用该漏洞. 因此, 通常我们希望避免映射任何可写和可执行的内存, 这也是在您自己的程序中遵循此规则的好习惯. 我在上面打破了这个规则, 但这只是为了使我们的第一个程序尽可能简单.

    恭喜, 您已经学会了如何编写一个 JIT 编译器, 那么后面我们会尝试干些什么事情呢? 哦, 是的, 明天我们将为一门叫做 brainfuck 的图灵完备语言编写解释器, 中间代码和 JIT 编译器. 我稍微透露一点信息, 使用 IR 优化后的解释器将比纯解释执行快 5 倍, 在采用 JIT 编译后将快 60 倍.

    您可以在 https://github.com/mohanson/brainfuck 找到源代码, 那么, 明天见了.

    第 1 条附言  ·  2020-05-23 23:59:03 +08:00
    第 2 条附言  ·  2020-05-24 17:59:48 +08:00
    6 条回复    2020-05-23 23:37:52 +08:00
    nightwitch
        1
    nightwitch  
       2020-05-22 22:39:35 +08:00
    llvm 有一份教程正是关于如何做 jit 的, 后端的优化就不用自己做了.
    https://llvm.org/docs/tutorial/BuildingAJIT1.html
    lance6716
        2
    lance6716  
       2020-05-23 05:54:10 +08:00 via Android
    这个小例子说明 C 真是简单好用。期待更新
    Mohanson
        3
    Mohanson  
    OP
       2020-05-23 07:59:10 +08:00 via Android
    @lance6716 我会在今晚更新第二天的内容,主要介绍 bf 解释器与 IR 优化

    明天会介绍如何对 IR 做 JIT 编译,请随时关注 程序员 节点的新帖哦
    wzzzx
        4
    wzzzx  
       2020-05-23 13:24:51 +08:00
    哇,期待更新~
    Leigg
        5
    Leigg  
       2020-05-23 17:10:04 +08:00 via Android
    厉害
    Mohanson
        6
    Mohanson  
    OP
       2020-05-23 23:37:52 +08:00   ❤️ 1
    @lance6716 @wzzzx 已经更新第二天的内容了, 介绍编写 BF 解释器以及对源码进行中间语言的优化. https://v2ex.com/t/674795
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1000 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:53 · PVG 03:53 · LAX 12:53 · JFK 15:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.