JIT编译历险记(2017)

这是关于JIT编译器系列文章的第一篇。我们的计划是采用一种简单的输入语言，并为其开发一些解释器和JIT，其复杂程度大致递增。我希望在本系列结束时，读者能够很好地理解开发JIT编译器需要什么，以及有哪些工具可以帮助完成这项任务。

输入语言将是Brainfuck，或BF，因为我将从现在起和整个系列中都会提到它。我认为这是一种很好的语言，因为它真正将可编程性归结为本质。尽管在BF中编程非常乏味，但就编程语言而言，它是相当主流的，一些概念，如内存指针和循环直接映射到熟悉的C结构。

作为实现语言，我将使用C++。这可能不是最常用的入门语言；也就是说，我知道的大多数编译器都是用C++(或C)编写的，因此现有的许多最流行的低级代码生成库都是用这些语言编写的。在本系列的后面部分中，我们将使用一些C++库，这是目前为止从C++本身最容易做到的。此外，在整个系列中，我尽量使我的代码简单明了-这里很少使用高级C++特性。

BF语言很容易描述，但我在这里不做这方面的介绍。请看一下规范，阅读Wikipediapage，或其他现有资源。像这样的浏览器内解释器可能非常有用。

我只举一个例子来培养对这门语言的品味。下面的BF程序将数字1到5打印到屏幕上：

行1将存储单元0初始化为值48，恰好是0的ASCII码。

第3行是一个循环，它在每次迭代中递增单元格0并将其值打印出来，然后递减单元格1并检查它是否已达到值0。

为了对该语言有一个初步的了解并有一个可靠的参考实现，我们将从一个简单的解释器开始，该解释器一次处理一个BC字符，并执行执行它所必需的操作。

我选择BF作为源语言的原因之一是它的简单性。您会在网上找到许多教程，声称要开发解释器或编译器，但最终却将90%的时间集中在编写解析器上。我认为编译的后期阶段要有趣得多，所以我的BF解析器看起来如下所示：

Struct Program{std：：String Instructions；}；Program parse_from_stream(std：：iStream&；stream){Program program；for(std：：string line；std：：getline(stream，line)；){for(auto c：line){if(c=='；>；'；||c=='；<；'；||c=='；+'；||c=。-'；||c=='；.'；||c=='；，'；||c=='；['；||c=='；]'；){程序。说明书。PUSH_BACK(C)；}返回程序；}。

请注意，根据BF规范，这是一个有效的实现：除8个受支持的字符外，所有字符都将被视为注释并忽略[1]。这个解析器将在整个系列中为我们服务。

Constexpr int memory_size=30000；void simpleinterp(const Program&；p，bool Verbose){//初始化状态。Std：：Vector<；uint8_t&>内存(MEMORY_SIZE，0)；size_t pc=0；size_t dataptr=0；while(pc<；p.。说明书。Size()){char指令=p。说明[pc]；开关(指令){case'；>；'；：dataptr++；Break；case'；<；'；：dataptr--；Break；case'；+'；：memory[dataptr]++；Break；-'；：memory[dataptr]--；Break；case'；.'；：std：：cout。PUT(MEMORY[DATAPTR])；BREAK；CASE'；，'；：MEMORY[DATAPTR]=STD：：CIN。Get()；Break；//[...]。

所有这些案例都是相当微不足道的。更有趣的是控制流操作-[和]。如果当前数据位置为零，我们将以[-向前跳转开始。此操作使跳过循环或实现简单的if-like条件成为可能。

案例'；['；：if(Memory[dataptr]==0){int括号_nesting=1；size_t saved_pc=pc；while(括号_嵌套&；&；++pc<；p..。说明书。Size()){if(p.。说明[pc]=='；]'；){BLARKET_NESTING--；}ELSE IF(p.。说明[pc]=='；['；){BLARKET_NETING++；}}如果(！支架嵌套){Break；}否则{模具<；<；"；不匹配'；['；在PC="；<；<；<；Saved_PC；}Break；

这里需要注意的最重要的一点是，BF中的[和]括号可以嵌套；因此，在计算从哪里跳转时，我们必须找到匹配的括号。如果这看起来像是在运行时做一些浪费的事情，那么您是对的-继续阅读！

因为]我们做的事情非常相似。在BF中，]跳转到较早的[如果当前数据位置不为零。这就是循环如何前进到下一次迭代(或停止)。

CASE'；]'；：IF(Memory[dataptr]！=0){int括号_nesting=1；size_t saved_pc=pc；While(括号_嵌套&；&；pc>；0){pc--；if(p..。说明[pc]=='；['；){括号_嵌套--；}Else if(p.。说明[pc]=='；]'；){BARRAKET_NETING++；}}如果(！BREAKET_NSTING){Break；}否则{PC="；<；<；}}在PC="；<；<；'；}{die<；<；<；}}Break；

默认：PC="；<；<；}}PC="；<；<；}上的{die<；<；"；"；<；<；指令<；<；'；错误字符'；<；<；<；指令<；<；'；}。

每当我们开发解释器或编译器之类的东西时，执行速度都是最重要的问题。因此，对于编译器编写人员来说，参考基准测试套件进行测量是很常见的。对于BF，我将在整个系列中使用几个程序来衡量我们的实现有多快。一个是曼德尔布洛特生成器，另一个是在大素数179424691[2]上调用的因式分解程序。

上面显示的简单解释器在mandelbrot上耗时38.6秒，在因子[3]上耗时16.5秒。现在让我们看看我们怎样才能大大改进这些数字。

对于简单解释器来说，最明显的优化机会是避免在每次遇到[或]时费力地寻找匹配的括号。想象一个具有热内循环的现实程序(这里我指的是它在整个程序的执行过程中运行很多很多-可能是数十亿次)。真的有必要每次都扫描源代码才能找到匹配的括号吗？当然不是。我们可以提前预先计算这些跳转目的地，因为BF程序在整个执行过程中不会改变。

这就是我们第一个优化的解释器optinterp.cpp背后的想法。大部分代码与简单解释器的代码相同，所以我只强调不同之处。一个重要的附加功能是这个函数，它在实际解释发生之前运行：

Std：：Vector<；size_t>；COMPUTE_JUMPTABLE(const Program&；p){size_t pc=0；size_t program_size=p。说明书。Size()；std：：Vector<；size_t>；Jumptable(PROGRAM_SIZE，0)；WHILE(pc<；PROGRAM_SIZE){char指令=p。指令[pc]；if(指令=='；['；){int括弧_嵌套=1；size_t Seek=pc；While(括号_嵌套&；&；++Seek<；Program_Size){IF(p.。说明[Seek]=='；]'；){BARRAKET_NESTING--；}ELSE IF(p.。说明[SEEK]=='；['；){BARRAKET_NETING++；}}如果(！BLARKET_NSTING){Jumptable[PC]=Seek；Jumptable[Seek]=PC；}否则{DIE<；<；"；['；at PC="；<；<；PC；}}PC++；}返回Jumptable；}。

它计算程序中所有[和]操作的跳转目的地。它的操作基本上等同于在简单解释器的主循环中向前/向后扫描匹配的括号。结果是向量跳转表，其中对于程序中偏移量i处的每个[and]，Jumptable[i]保存匹配括号的偏移量。对于偏移量i处的任何其他操作，Jumptable[i]仅仅是0。

Optinterp的实际主循环与simpleinterp中的相同，只是括号的子句不同，它们变得简单：

案例'；['；：IF(Memory[dataptr]==0){PC=Jumptable[PC]；}Break；Case'；]'；：IF(Memory[Datatr]！=0){PC=Jumptable[PC]；}Break；

正如您所期望的那样，optinterp相当快；运行mandelbrot只需要18.4秒，运行factor只需要6.7秒-提高了2倍以上！

上一节中应用的优化是非常有益的，但是它也相当微不足道--如果我们可以在编译时预先计算的话，我们可以避免在运行时完全不必要的工作。为了让我们的口译员做得更快，我们必须更有创意。

优化的第一步是测量和分析当前代码。一些过去的经验有助于避免这个过程中不必要的步骤。例如，很明显，解释器几乎100%的运行时间将花在解释程序的单个函数上；因此，函数/调用分析不会有太大帮助。

然而，主循环相当小，乍一看似乎没有太多需要优化的地方(忽略了我在这里不会担心的微优化)。嗯，除了这个循环对源程序中遇到的每条BF指令都运行，所以它可以运行很多次。因此，我们要做的是对典型程序运行期间执行的操作进行细分。Optinterp的代码已包含此跟踪-它受BFTRACE预处理器宏保护，因为它的开销很大，我们希望避免在实际运行时执行此操作。

下面是我们从素数179424691上典型运行的factorBenchmark获得的执行配置文件。左侧为操作，右侧为手头程序的解释器执行该操作的次数：

。-->；21，-->；10+-->；212,428,900]-->；242,695,606<；-->；1,220,387,704->；212,328,376>；-->；1,220,387,724[-->；118,341,127.。总数：3,226,569,468

操作的总数是巨大的：绕过主解释器循环超过30亿次。这是一件好事，我们正在使用C++作为解释器-用更高级别的语言运行30亿次迭代将是痛苦的！

指针移动指令与循环的比率高得令人怀疑。大约执行了2.42亿次循环迭代(计数为])，但总共有24亿次指针移动：<；和>；。

我们期望并希望热环是短而紧的--为什么每个环路都做得如此之多？

<；<；[<；<；]>；>；[>；>；>；>；>；[-]<；<；[->；+<；]<；[->；>；>；+<；<；<；]>；>；]<；<；[+>；>；[-<；<；<；<；+>；>；[-<；<；->；>；+>；[-<；<；+>；>；[-<；<；->；>；+>；[-<；<；+>；>；[-<；<；->；>；>；+>；[-<；<；+>；>；[-<；<；->；>；+>；[-<；<；+>；>；>；>；]<；<；[->；>；+<；<；]-<；<；]>；>；>；>；[-<；<；+>；>；]>；>；>；[>；>；[-<；<；<；<；+>；>；]>；>；>；]<；<；[+>；>；[-<；<；<；<；+>；>；[-<；<；->；>；+>；>；>；[-<；<；+>；>；>；>；>；[-<；<；->；>；+>；>；>；[-<；<；+>；>；[-<；<；<；<；<；->；>；+>；>；>；[-<；<；+>；>；[-<；<；->；>；>；+>；>；>；[-<；<；+>；>；]<；<；[->；>；+<；<；<；<；]-<；<；]>；>；[-<；<；+>；>；>；>；]>；>；[>；>；[-<；<；+>；>；>；>；>；]>；>；]<；<；[<；<；]>；>；>；>；]<；<；

请注意<；<；、>；>；的相当长的序列。稍微考虑一下BF的语义就可以清楚地表明这一点-这些对于完成任何事情都是必要的，因为我们希望能够从一个单元到另一个单元来更新数据。

现在，让我们考虑一下在我们的解释器中执行像<；<；这样的序列意味着什么。我们的主循环执行7次，每次执行：

那是相当贵的。如果我们能压缩<；<；的所有长序列会怎么样？毕竟，我们为单个<；所做的是：

这很容易概括。我们可以检测BF源中的任何连续序列，并将其编码为一对：操作和重复计数。然后，在执行时，我们只需将操作重复所需的次数。

这个解释器的完整代码是optinterp2.cpp.以前，我们保存了一个与输入程序中的[AND]指令相关联的单独跳转表。现在，我们需要每个B结构的额外信息，所以我们只需将该程序转换为以下类型的操作序列：

枚举类BfOpKind{INVALID_OP=0，INC_PTR，DEC_PTR，INC_DATA，DEC_DATA，READ_STDIN，WRITE_STDOUT，JUMP_IF_DATA_ZERO，JUMP_IF_DATA_NOT_ZERO}；//每个OP都有一个数字参数。对于JUMP_*OPS，它是//应该进行跳转的偏移量；对于所有其他操作，它是重复//OP的次数。Struct BfOp{BfOp(BfOpKind Kind_param，size_t参数_param)：KIND(KIND_Param)，Argument(Argument_Param){}BfOpKind Kind=BfOpKind：：INVALID_OP；SIZE_t ARGUMENT=0；}；

解释分两步进行。首先，我们运行Translate_Program来读取程序并生成std：：Vector<；BfOp>；。这个转换非常简单：它检测<；这样的操作中的重复项，并在参数字段中对它们进行编码。这里有一个稍微棘手的方面，那就是处理跳转，因为程序中所有操作的偏移量都会发生变化(例如，七个连续的<；会变成一个DEC_PTR)。有关完整的详细信息，请查看代码。

开关(种类){case BfOpKind：：Inc_ptr：dataptr+=op.。参数；中断；案例BfOpKind：：dec_ptr：dataptr-=op。参数；中断；案例BfOpKind：：INC_DATA：Memory[dataptr]+=op。参数；中断；案例BfOpKind：：DEC_DATA：Memory[dataptr]-=op。参数；中断；//[...]。等。

它有多快？现在，mandelbrot基准测试需要11.9秒，factor需要3.7秒；运行时间又减少了40%。

我们的优化解释器现在运行mandelbrot基准测试的速度比原始的、幼稚的解释器快3倍以上。我们还能做得更好吗？

。-->；21]-->；242,695,606，-->；10+-->；191,440,613<；-->；214,595,790->；205,040,514>；-->；270,123,690[-->；118,341,127.。总数：1242,237,371。

指令总数几乎减少了3倍。此外，现在BF循环执行的数量与其他指令的数量更接近，这意味着我们在每次迭代中不需要做太多工作。毕竟，这是我们优化重复的目标。

事实上，这个执行配置文件平坦得令人恼火。性能专家不喜欢扁平的配置文件，因为没有什么特别突出的东西可以优化。这通常意味着我们还应该测量/追踪其他东西。

一个值得回答的有趣问题是-每个BF循环都在做什么。换句话说，我们正在运行的最热门的循环是什么，我们可以花费更多的专业努力来优化它们吗？这将需要更复杂的跟踪机制，我已经将其包含在optinterp2的代码中。该机器跟踪循环并记录程序中每个循环迭代执行的指令序列。然后，它根据出现的次数对它们进行排序，并显示最常见(最热)的循环。以下是因子基准的结果：

-1<；10+1>；10->32,276,219-1--；28,538,377-1>；4+1>；4-->；15,701,515-1>；3+1>；1+1>；4-->；12,581,941-1>；3+1>；2+1<；5-。3+1；3-->6,085,735-1&>；1+1；3+1&>；4-853,530-1；3+2&>；3--5,586,229；2-->；5,416,630-1；1+1；1-->5,104,333。

这样做的循环被执行了3200万次！类似地，执行简单操作的循环递减当前单元格的次数为2800万次。如果您查看factor.bf的源代码，很容易发现这些循环。第一个是[-<；<；+>；>；]；，第二个是[-]。

如果我们可以完全地优化这些循环呢？毕竟，他们正在做的事情更容易用更高级的语言来表达。[-]仅将当前存储单元设置为0。[-<；<；+>；>；]更复杂，但也不多：它所做的就是将当前内存单元10的值向左相加。上面显示的轨迹具有许多此类循环以及另一个循环；像[>；>；>；]这样的循环以3为跳跃向右移动，直到遇到非零单元格。

在optinterp2中，我们向解释器添加了更高级别的操作。我们可以添加一些更高级别的操作来优化这些循环。Optinterp3.cpp就是这样做的。它增加了一些用于编码公共循环的操作类型：

枚举类BfOpKind{INVALID_OP=0，INC_PTR，DEC_PTR，INC_DATA，DEC_DATA，READ_STDIN，WRITE_STDOUT，LOOP_SET_TO_ZERO，LOOP_MOVE_PTR，LOOP_MOVE_DATA，JUMP_IF_DATA_ZERO，JUMP_IF_DATA_NOT_ZERO}；

新的循环是LOOP_SET_TO_ZERO，它替换了[-]、LOOP_MOVE_PTR for[>；>；>；]和LOOP_MOVE_DATA for LOOP_MOVE_DATA，比如[-<；<；<；+>；>；]。我们现在需要一个稍微更复杂的转换步骤来检测输入程序中的循环并发出正确的LOOP_*操作。关于如何做到这一点的一个例子，这里是[-]的翻译：

Std：：vect。

.