LLVM中的JIT

JIT编译简介

JIT（just-in-time）即时编译技术是在运行时（runtime）将调用的函数或程序段编译成机器码载入内存，以加快程序的执行。所以，JIT是一种提高程序时间和空间有效性的方法。

程序运行时编译和执行的概念最早出自John McCarthy在1960年发表的论文《Recursive functions of symbolic expressions and their computation by machine》，James Gosling在1993年在关于Java的论文中使用了”JIT”这个术语。

JIT可以分为两个阶段：在运行时生成机器码和在运行时执行机器码。其中，第一个阶段的生成机器码方式与静态编译并无本质不同，只不过生成的机器码被保存在内存中，而静态编译是在程序运行前将整个程序完全编译为机器码保存在二进制文件中。运行时JIT缓存编译后的机器码，当再次遇到该函数时，则直接从缓存中执行已编译好的机器。因此，从理论上来说，JIT编译技术的性能会越来越接近静态编译技术。

为了模拟JIT的运行原理，如下代码演示了如何在内存中动态生成add函数并执行，该函数的C语言原型如下：

long add(long num) {
    return num + 1;
}

void* alloc_writable_memory(size_t size) {
    void* ptr = mmap(0, size,
                      PROT_READ | PROT_WRITE,
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (ptr == (void*)-1) {
        perror("mmap");
        return NULL;
    }
    return ptr;
}

void emit_code_into_memory(unsigned char* m) {
    unsigned char code[] = {
        0x48, 0x89, 0xf8, // mov %rdi, %rax
        0x48, 0x83, 0xc0, 0x01, // add $1, %rax
        0xc3 // ret
    };
    memcpy(m, code, sizeof(code));
}

int make_memory_executable(void* m, size_t size) {
    if (mprotect(m, size, PROT_READ | PROT_EXEC) == -1) {
        perror("mprotect");
        return -1;
    }
    return 0;
}

const size_t SIZE = 1024;
typedef long (*JittedFunc)(long);

// Allocates RWX memory directly.
void emit_to_rw_run_from_rx() {
    void* m = alloc_writable_memory(SIZE);
    emit_code_into_memory(m);
    make_memory_executable(m, SIZE);

    JittedFunc func = m;
    int result = func(2);
    printf("result = %d\n", result);
}

上述代码主要可分为三步：

  1. alloc_writable_memory调用mmap在堆上分配可读/可写/可执行内存块；
  2. emit_code_into_memory将实现add函数的字符串形式机器码拷贝到内存块中。这一步骤可类比为JIT中调用运行时生成机器码；
  3. 将内存块转换为指针类型并调用执行。这一步骤可类比为JIT中通过获得函数地址调用函数。

LLVM执行引擎(LLVM Execution Engine)

LLVM JIT使用执行引擎(execution engine)来支持LLVM模块的执行。ExecutionEngine类的申明在/include/llvm/ExecutionEngine/ExecutionEngine.h中，执行引擎既可以用JIT也可以用解释器的方式支持执行。执行引擎负责管理整个客体(guest)程序的执行，分析需要执行的下一个程序片段。客体程序是指不能被硬件平台原生支持的代码，比如，对于x86平台来说，LLVM IR模块就是客体程序，因为x86平台不能直接执行LLVM IR代码。

在LLVM中有三个持续演进的JIT执行引擎实现：llvm::JIT类、llvm::MCJIT类和llvm::ORCJIT类，llvm::JIT类在新的LLVM已经不再支持。JIT客户端会首先产生一个ExecutionEngine对象。ExecutionEngine对象以IR模块为输入，通过调用ExecutionEngine::EngineBuilder()初始化。接下来，ExecutionEngine::create()方法生成一个JIT或MCJIT引擎实例。

内存管理

JIT引擎的ExecutionManager类调用LLVM代码生成器，产生目标平台机器指令的二进制代码保存在内存中，并返回指向编译后函数的指针。然后通过函数指针指向指令所在内存区域即可执行该函数。在此过程中，内存管理负责执行内存分配、释放、权限处理、库加载空间分配等操作。

JIT和MCJIT各自实现派生自RTDyldMemoryManager基类的定制内存管理类。执行引擎客户端也可以定制RTDyldMemoryManager子类，由该子类指定JIT部件在内存中的存放位置。RTDyldMemoryManager定义在/include/llvm/ExecutionEngine/RTDyldMemoryManager.h中。

RTDyldMemoryManager类声明了如下方法：

  • allocateCodeSection()和allocateDataSection()：这两个方法分配内存保存可执行代码和数据，内存管理客户端可以用一个内部节（section）标识符参数追踪分配的节。
  • getSymbolAddress()：该方法返回链接的库中可用符号表地址。注意，这个方法不能用于获取JIT编译产生的符号表。调用该方法时必须提供一个std::string实例保存符号名称。
  • finalizeMemory()：MCJIT客户端完成对象加载后调用此方法设定内存权限，必须在调用此方法后才能运行生成的代码。

JIT和MCJIT的缺省内存管理子类分别是JITMemoryManager和SectionMemoryManager。

llvm::JIT框架

支持JIT的LLVM后端要实现二进制代码发射，JIT类通过MachineCodeEmitter子类JITCodeEmitter发射二进制指令，将二进制块字节写入内存。MachineCodeEmitter类用于发射机器码，但与新的MC框架无关，只支持少数几个后端。

MachineCodeEmitter类成员函数完成以下工作：

  1. allocateSpace()：为当前要发射的函数分配空间。
  2. emitByte()、emitWordLE()、emitWordBE()、emitAlignment()等：将二进制块写入缓存。
  3. 追踪当前缓存地址，即指向下一条要发射指令地址的指针。
  4. 增加相对缓存中指令地址的重定位。

JIT执行引擎也会用到JITMemoryManager和JITResolver。JITMemoryManager负责管理内存的使用，实现低层内存处理方法。例如，allocateGlobal()方法为全局变量分配内存，startFunctionBody()方法为发射的指令分配内存，并标记为读/写可执行。JITMemoryManager类声明在<llvm_source>/include/llvm/ExecutionEngine/JITMemoryManager.h。

JITResolver负责记录在哪些位置调用了未编译函数。

支持JIT的LLVM后端要实现两个类：<target>CodeEmitter和<target>JITInfo。<target>CodeEmitter包含了一个机器函数（machine function）pass，将目标机器指令转换为可重定位的机器码。例如，MipsCodeEmitter会遍历所有函数基本块，为每一条机器指令调用emitInstruction()：

for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(), E = MBB->instr_end(); I != E;)
    emitInstruction(*I++, *MBB);
}

为了支持JIT编译，编译器必须提供TargetJITInfo子类（见include/llvm/Target/TargetJITInfo.h），例如MipsJITInfo或X86JITInfo。TargetJITInfo类为所有目标平台编译器都需要实现的公共JIT功能提供了接口，包括为代码生成阶段中的各种活动，如代码发射，实现JIT接口。这些公共JIT功能包括：

  • 支持执行引擎重新编译经过修改的方法，实现TargetJITInfo::replaceMachineCodeForFunction()方法，并在原函数的对应位置通过补丁方式加入jump指令或调用新函数。这对自修改（self-modifing）代码是必须的。
  • TargetJITInfo::relocate()方法在当前发射的函数中的每一个符号引用打补丁以指向正确的存储地址，类似动态链接的做法。
  • TargetJITInfo::emitFunctionStub()方法发射一个桩函数，桩函数在给定地址调用另一个函数。每个目标平台编译器都应提供TargetJITInfo::StubLayout信息，包括发射的桩函数大小和对齐方式。在发射新的桩函数前，JITEmitter使用桩函数信息为其分配空间。

TargetJITInfo类方法的目标不是发射普通指令，但会发射生成桩函数的特殊指令（例如MipsJITInfo::emitFunctionStub()），以及调用新内存位置的特殊指令。

如何使用JIT类

JIT是ExecutionEngine子类，声明在<llvm_source>/lib/ExecutionEngine/JIT/JIT.h。JIT类是JIT编译函数的入口。

ExecutionEngine::create()以缺省JITMemoryManager为参数调用JIT::createJIT()，然后JIT构造函数执行以下任务：

  • 生成JITEmitter实例；
  • 初始化目标信息对象；
  • 添加代码生成pass；
  • 添加<Target>CodeEmitter pass；

当JIT编译某个函数时，引擎中的PassManager对象调用代码生成和JIT指令发射pass。

步骤如下：

  1. include各种头文件；

  2. InitializeNativeTarget()方法确保链接了JIT用到的库，LLVMContext对象和MemoryBuffer对象负责从硬盘读取bitcode文件； 

    InitializeNativeTarget();
LLVMContext Context;
OwningPtr<MemoryBuffer> Buffer;

  3. getFile()从硬盘读入文件到MemoryBuffer； 

    MemoryBuffer::getFile("./sum.bc", Buffer);

  4. 从MemoryBuffer读入数据并生成相应的LLVM模块; 

    Module *M = ParseBitcodeFile(Buffer.get(), Context, &ErrorMessage);

  5. 由EngineBuilder工厂生成ExecutionEngine实例，然后调用其create()方法： 

    OwningPtr<ExecutionEngine> EE(EngineBuilder(M).create());

  6. create()方法默认生成JIT执行引擎，间接调用JIT构造方法，生成JITEmitter、PassManager，并初始化代码生成和发射pass。这时引擎虽然已经生成了LLVM模块，但还没有编译其中任何函数。若要编译函数，需调用getPointerToFunction()获取指向经JIT编译的本地（native）函数的指针。如果还没有编译，此时可以启动JIT编译，并返回函数指针。

  7. getFunction()获取函数IR对象：
    Function *SumFn = M->getFunction(“sum”);

    触发JIT编译前要做函数指针类型转换，Sum函数在IR中的原型是define i32
    @sum(i32 %a, i32 %b)，所以这里C的函数指针类型是int (*)(int, int)：

    int (*Sum)(int, int) = (int (*)(int, int))
    EE->getPointerToFunction(SumFn);

    另外一种选项是不用getPointerToFunction()，而用getPointerToFunctionOrStub()启动lazy编译。这个方法会生成一个桩函数，并返回其指针。

  8. 接下来，通过Sum指向的JIT编译后的函数，调用原始Sum函数：

    int res = Sum(4,5);

    当使用lazy编译时，Sum会调用桩函数，桩函数再用一个编译回调方法编译真正的函数。然后桩函数会重定向到执行真正的函数。除非LLVM模块中的Sum函数被修改，否则不再会被编译。

  9. 再次调用Sum函数：

    res = Sum(res, 6);

    当使用lazy编译时，因为原始函数在第一次调用Sum时已经被编译过，以后的调用直接执行本地函数。

  10. 计算完成后，释放执行引擎分配的内存（其中保存了函数代码）：

    EE->freeMachineCodeForFunction(SumFn);
    llvm_shutdown();
    return 0;

在上述步骤f中，触发JIT编译前要做函数指针类型转换。执行引擎提供的另一个runFunction()方法，不需要在此之前调用getPointerToFunction()。runFunction()方法编译和运行函数时的参数是GenericValue向量。GenericValue结构定义在<llvm_source>/include/llvm/
ExecutionEngine/
GenericValue.h，可以保存任何数据类型。runFunction()用法如下：

Function* SumFn = M-&gt;getFunction("sum");
std::vector&lt;GenericValue&gt; FnArgs(2);
FnArgs[0].IntVal = APInt(32,4);
FnArgs[1].IntVal = APInt(32,5);
GenericValue Res = EE-&gt;runFunction(SumFn, FnArgs);

初始化SumFn函数指针后，生成了一个GenericValue向量FnArgs，并用APInt接口为其元素赋值。然后，可以调用runFunction()，其返回值也是GenericValue类型。

GenericValue Res = EE->runFunction(SumFn, FnArgs);

LLVM机器码JIT（Machine Code JIT, MCJIT）执行引擎

MCJIT是LLVM中JIT编译的一种新的实现方式，MCJIT类声明在<llvm_source>/lib/ExecutionEngine/MCJIT/MCJIT.h。MCJIT与旧版JIT实现的不同之处在于MC（Machine Code）框架。MC提供了统一的指令表示，该框架可被汇编器、反汇编器、汇编打印和MCJIT共享。使用MC库的首要优点是编译器后端增加新的目标平台ISA支持时，只需要指定一次指令编码，而不需要对MCJIT做改动，因为这个修改会被所有子系统共享。因此，当开发后端时，如果实现了对象代码发射，也就可以具备了JIT功能。虽然MCJIT完全取代了旧版的JIT，但二者在诸多概念上是相似的，对MCJIT也适用。

给定一个LLVM IR模块，可以通过执行引擎addModule()接口添加该模块。该模块经过代码生成和MC层处理，会在内存中生成机器码。如果将此机器码写入硬盘，就可以得到目标平台对应的对象文件。但MCJIT不会将机器码写入硬盘，而是将其保留在内存中，并运行RuntimeDyld，将机器码转化为可执行代码块。客户端可通过执行引擎查询接口获得可执行代码块的函数地址，并执行函数。MCJIT工作过程如下图所示：

LLVM MCJIT执行引擎利用MC框架集成汇编器、反汇编器和对象连接器，MCJIT也可以共享MC框架的信息，即MCJIT重用了整个静态编译器流水线。MCJIT的这种设计是对代码和工具的高效重用。旧版JIT执行引擎的编译对象是LLVM IR函数，而MCJIT执行引擎编译整个模块。也就是说，在函数执行前，整个模块都已经被MCJIT编译过。

通常客户端不能直接调用MCJIT方法，因为MCJIT的实现隐藏在执行引擎中。MCJIT执行引擎由客户端EngineBuilder对象产生，并以llvm::Module对象作为构造函数参数。客户端可通过EngineBuilder的设置选项指定生成的引擎类型为MCJIT，然后调用ExecutionEngine::create()方法产生引擎实例。create()方法调用MCJIT::createJIT()执行MCJIT构造函数。MCJIT构造函数会产生一个缺省的内存管理器对象SectionMemoryManager，也可以调用EngineBuilder::
setMCJITMemoryManager()方法根据需要产生内存管理器。如果客户端调用createJIT()时没有传入TargetMachine对象作为参数，createJIT()会根据模块中的target
triple产生一个新的TargetMachine对象。指向模块的指针、内存管理器和TargetMachine对象这些数据结构都会作为MCJIT对象的成员。MCJIT对象随后将LLVM模块添加到其内部模块容器OwningModuleContainer中，并初始化目标架构信息。但是此时MCJIT不会立即开始为模块生成机器码，而是会推迟到客户端调用MCJIT::finalizeObject()方法或MCJIT::getPointerToFunction()方法时，调用这些方法时会用到机器码。

MCJIT类为LLVM模块标记状态，这些状态代表了模块的编译阶段，包括：

  • Added：模块还未编译，但已添加到执行引擎中。这个状态允许模块暴露函数定义给其它模块，并延缓对其编译，直到被调用。
  • Loaded：模块已被JIT编译，但还未准备好执行。还未重定位（relocation），还未给内存页合适权限。客户端通过使用loaded状态的模块重映射（remap）JIT编译过的函数可以避免重编译。
  • Finalized：包含函数的模块做好准备，可以执行。该状态中的函数不能被重映射，因为已经做过重定位。

MCJIT和JIT的一个主要区别就是模块状态。在MCJIT中，获取模块的符号地址（包括函数和全局变量）之前，模块必须处在finalized状态。

MCJIT::finalizeObject()方法负责将added模块转换到loaded，再finalize。首先，finalizeObject()方法调用generateCodeForModule()方法生成loaded模块，然后，调用finalizeLoadedModules()方法将所有模块转到finalized。调用MCJIT::getPointerToFunction()之前要求模块必须处在finalized状态。因此，在此之前必须调用finalizeObject()方法。

但在LLVM 3.4之后的新增方法getFunctionAddress()取消了上述限制。getPointerToFunction()被弃用。在请求符号地址之前，getFunctionAddress()会加载并定型（finalize）模块，不必调用finalizeObject()方法。

注意，在原有的JIT中，各个函数被JIT分别编译后，由执行引擎执行。在MCJIT中，整个模块，包括其中所有函数，在执行前都必须被JIT编译。所以，MCJIT实际上增大了编译粒度（从函数到模块），MCJIT不再是基于函数的，而是基于模块的编译引擎。

当MCJIT载入某个模块时，会触发代码生成。即，代码生成发生在模块对象的加载阶段，由MCJIT::generateCodeForModule()方法触发。generateCodeForModule()方法由客户端的finalizeObject()方法调用。generateCodeForModule()方法执行以下任务：

a.如果模块对象已经被加载和编译过，MCJIT首先尝试从ObjCache中获取一个对象image，并在随后将其标记为loaded状态，避免重复编译。

if (ObjCache)
ObjectToLoad = ObjCache-&gt;getObject(M);
…
OwnedModules.markModuleAsLoaded(M);

b. 如果模块之前没有被缓存和编译过，MCJIT调用MCJIT::emitObject()方法执行MC代码发射，emitObject()方法生成一个新的ObjectBufferStream实例。ObjectBufferStream是ObjectBuffer 的子类，ObjectBufferStream支持流处理。emitObject()方法使用本地PassManger实例、MCContext实例、ObjectBufferStream实例作为参数调用LLVMTargetMachine::addPassesToEmitMC()方法，生成目标对象的MCCodeEmitter、AsmStreamer以及AsmPrinter，并将对应pass添加到PassManager。

c.随后PassManager::run()触发MC代码生成机制，将中间表示形式的机器码通过ObjectBufferStream产生完整的、可重定位的二进制对象image。这时ObjectBufferStream包含的是原始对象image，在执行前还需要将其中的数据和代码去载入内存，并做重定位和内存权限设置。

d.MCJIT以生成的对象image为界，分为两个部分。代码生成模块和MC层的主要功能是编译，RuntimeDyld主要功能是链接。不论是从代码生成机制中获得对象image，还是从ObjectCache中获得对象image，最终都由RuntimeDyld载入内存。RuntimeDyld动态链接器载入存有输出机器码的ObjectBuffer对象，并通过调用RuntimeDyld::
loadObject()首先生成目标特定的RuntimeDyldImpl对象。RuntimeDyldImpl对象通过检查对象image决定其格式，并生成相应的RuntimeDyldELF或RuntimeDyldMachO子类对象。然后调用RuntimeDyldELFRuntimeDyldImpl::loadObject()构造符号表，完成实际加载过程，并生成一个ObjectImage对象保存加载的模块。ObjectImage封装了ObjectFile类，其中的ObjectFile对象类型可以是ELF、COFF等，ObjectImage对象可直接访问ObjectBuffer和ObjectFile对象，解析二进制对象image，从MemoryBuffer对象获得符号、重定位信息和节信息。处理过程如下图所示：

d.RuntimeDyldImpl::loadObject()随后会遍历image中的符号。公共符号信息收集后以备后用。与函数符号和数据符号关联的节被载入内存，符号被保存在一个符号表映射数据结构中。遍历结束后，公共符号作为单独一节发射。接下来遍历节以及节中的重定位信息，对每一重定位信息调用与格式相应的processRelocationRef()方法解析模块的重定位信息，并将重定位信息保存在节重定位表或外部符号（在本目标文件中引用，但不在本目标文件中定义的符号）重定位表中。

e.RuntimeDyldImpl::loadObject()结束后，对象的所有数据和代码节都已载入内存管理器分配的内存中，重定位信息已准备好但还未应用，生成的代码还不能执行。在应用重定位信息前，还应重映射（remap）节地址。因为代码可能是用于外部进程，需要被映射到那个进程的地址空间。在将节拷贝到其新内存地址前要重映射节地址，方法是调用MCJIT::mapSectionAddress()。这时，MCJIT会通过RuntimeDyldImpl将新地址保存到其内部数据结构，但还不会更新代码，因为此时其它节还有可能变化。当客户端完成节地址重映射后，才会调用MCJIT::finalizeObject()方法，完成整个重映射过程。

f.MCJIT::finalizeObject()方法调用RuntimeDyld::resolveRelocations()方法定位外部符号，并将重定位信息应用于对象。定位外部符号的方法是调用内存管理器的getPointerToNamedFunction()方法，该方法会返回所请求对象在目标地址空间中地址。然后RuntimeDyld会遍历之前保存的外部符号重定位信息列表，从中找到和符号关联的重定位信息，将其应用于加载的节内存。接下来RuntimeDyld会遍历节列表，并遍历之前保存的每一个节的节重定位表，对表中的每一项调用resolveRelocation()方法。与节重定位表中重定位信息关联的符号位于该重定位表对应的节中。重定位信息应用于目标位置定位，目标位置可能在另一个不同的节中。

重定位完成后，MCJIT调用RuntimeDyld::getEHFrameSection()方法。如果返回非0值，便将节数据传给内存管理器的registerEHFrames()方法，内存管理器可以将EH帧信息注册给调试器。

g.最后，MCJIT调用内存管理器的finalizeMemory()方法将标记为loaded状态的模块移入模块组，设置内存读写权限。这之后，模块准备好运行。

ObjectBuffer类是MemoryBuffer类的包装。MemoryBuffer类被MCObjectStreamer子类用于向内存发射代码和数据。另外，ObjectCache类直接引用MemoryBuffer实例，并从MemoryBuffer实例获得ObjectBuffer。

在模块定型（finalization）时，使用运行时RuntimeDyld动态链接器为模块解析重定位以及注册异常处理帧。前面已经提到，执行引擎方法getFunctionAddress()和getPointerToFunction()要求引擎要知道符号地址。所以MCJIT会通过RuntimeDyld::getSymbolLoadAddress()方法查询任何符号地址。

LinkingMemoryManager类是另一个RTDyldMemoryManager子类，MCJIT引擎使用的真正的内存管理器，其中集成了一个SectionMemoryManager实例，并将代理请求发给这个实例。

RuntimeDyld动态链接器通过LinkingMemoryManager::getSymbolAddress()获得符号地址有两种方法：如果符号已经在编译过的模块中，可以通过MCJIT获得符号地址；模块中没有符号，可以从SectionMemoryManager实例加载和映射的外部库中获得符号地址。

  1. MC代码发射

NCJIT通过调用MCJIT::emitObject()发射MC代码。emitObject()完成以下任务：

  • 生成一个PassManager对象；
  • 添加一个目标layout
    pass并调用addPassesToEmitMC()添加所有代码生成pass和MC代码发射；
  • 调用PassManager::run()方法运行所有pass。输出结果保存在ObjectBufferStream对象中；
  • 将编译后对象添加到ObjectCache实例并返回。

代码发射完成后，调用MCJIT::finalizeLoadedModules()将模块定型，解析重定位信息，将加载的模块移到定型模块组中，并调用LinkingMemoryManager::finalizeMemory()修改内存页权限。此后，MCJIT编译过的函数准备好执行。

来源：zhuanlan.zhihu.com/p/60936932

作者：汪岩

剖析LLVM寄存器分配（1）
使用LLVM写WebAssembly

最新文章

归档