LLVM 中的堆栈映射和补丁点

定义

在本文档中,我们将 “运行时” 统称为充当 LLVM 客户端的所有组件,包括 LLVM IR 生成器、目标代码消费者和代码补丁程序。

堆栈映射记录在特定指令地址处 活跃值 的位置。这些 活跃值 并非指代跨越堆栈映射的所有 LLVM 活跃值。相反,它们仅是运行时要求在此点为活跃的值。例如,它们可能是运行时需要在此点恢复程序执行的值,而与包含堆栈映射的已编译函数无关。

LLVM 将堆栈映射数据发射到目标代码中指定的 堆栈映射段 内。此堆栈映射数据包含每个堆栈映射的记录。该记录存储堆栈映射的指令地址,并包含每个映射值的条目。每个条目将值的位置编码为寄存器、堆栈偏移量或常量。

补丁点是一个指令地址,在该地址处保留了空间,用于在运行时修补新的指令序列。补丁点看起来很像对 LLVM 的调用。它们接受遵循调用约定的参数,并且可能返回值。它们还意味着堆栈映射生成,这允许运行时定位补丁点并找到该点 活跃值 的位置。

动机

此功能目前是实验性的,但在各种设置中可能很有用,最明显的例子是运行时 (JIT) 编译器。补丁点内联函数的示例应用包括为多态方法分派实现内联调用缓存,或优化在动态类型语言(如 JavaScript)中检索属性。

本文档中记录的内联函数目前由开源 WebKit 项目中的 JavaScript 编译器使用,请参阅 FTL JIT,但它们旨在在需要堆栈映射或代码修补时使用。由于这些内联函数具有实验性状态,因此无法保证跨 LLVM 版本的兼容性。

本文档中描述的堆栈映射功能与 计算堆栈映射 中描述的功能是分开的。GCFunctionMetadata 提供了由 GCRoot 内联函数捕获的指向已回收堆的指针位置,这也可以被视为“堆栈映射”。与上面定义的堆栈映射不同,GCFunctionMetadata 堆栈映射接口没有提供将任意类型的活跃寄存器值与指令地址关联的方法,也没有指定结果堆栈映射的格式。这里描述的堆栈映射可能为垃圾回收运行时提供更丰富的信息,但本文档中不会讨论该用法。

内联函数

以下两种内联函数可用于实现堆栈映射和补丁点:llvm.experimental.stackmapllvm.experimental.patchpoint。这两种内联函数都生成堆栈映射记录,并且都允许某种形式的代码修补。它们可以独立使用(即 llvm.experimental.patchpoint 隐式生成堆栈映射,而无需额外调用 llvm.experimental.stackmap)。选择使用哪种取决于是否需要为代码修补保留空间,以及是否应根据调用约定降低任何内联函数参数。llvm.experimental.stackmap 不保留任何空间,也不期望任何调用参数。如果运行时在堆栈映射的地址处修补代码,它将破坏性地覆盖程序文本。这与 llvm.experimental.patchpoint 不同,后者保留了空间用于就地修补,而不会覆盖周围的代码。llvm.experimental.patchpoint 内联函数还根据其调用约定降低指定数量的参数。这允许修补后的代码进行就地函数调用而无需编组。

这些内联函数中的每一个实例都在 堆栈映射段 中生成一个堆栈映射记录。该记录包括一个 ID,允许运行时唯一标识堆栈映射,以及代码中从封闭函数开始的偏移量。

llvm.experimental.stackmap’ 内联函数

语法:

declare void
  @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>, ...)

概述:

llvm.experimental.stackmap’ 内联函数记录堆栈映射中指定值的位置,而不生成任何代码。

操作数:

第一个操作数是要在堆栈映射中编码的 ID。第二个操作数是内联函数后面的阴影字节数。前两个操作数应该是立即数,例如不能作为变量传递。后面的可变数量的操作数是 活跃值,其位置将记录在堆栈映射中。

要将此内联函数用作最基本的堆栈映射,而无需代码修补支持,可以将阴影字节数设置为零。

语义:

堆栈映射内联函数不会就地生成代码,除非需要 nop 来覆盖其阴影(见下文)。但是,其相对于函数入口的偏移量存储在堆栈映射中。这是紧随在堆栈映射之前的指令之后的相对指令地址。

堆栈映射 ID 允许运行时定位所需的堆栈映射记录。LLVM 将此 ID 直接传递到堆栈映射记录,而不检查唯一性。

LLVM 保证在堆栈映射的指令偏移量之后的指令阴影期间,既不会出现基本块的结尾,也不会出现对 llvm.experimental.stackmapllvm.experimental.patchpoint 的另一次调用。这允许运行时响应于从代码外部触发的事件在此点修补代码。堆栈映射之后指令的代码可能会在堆栈映射的阴影中发出,并且这些指令可能会被破坏性修补覆盖。如果没有阴影字节,这种破坏性修补可能会覆盖当前函数之外的程序文本或数据。我们不允许重叠的堆栈映射阴影,以便运行时无需考虑此极端情况。

例如,具有 8 字节阴影的堆栈映射

call void @runtime()
call void (i64, i32, ...) @llvm.experimental.stackmap(i64 77, i32 8,
                                                      ptr %ptr)
%val = load i64, ptr %ptr
%add = add i64 %val, 3
ret i64 %add

可能需要一个字节的 nop 填充

0x00 callq _runtime
0x05 nop                <--- stack map address
0x06 movq (%rdi), %rax
0x07 addq $3, %rax
0x0a popq %rdx
0x0b ret                <---- end of 8-byte shadow

现在,如果运行时需要使已编译的代码无效,它可能会在堆栈映射的地址处修补 8 个字节的代码,如下所示

0x00 callq _runtime
0x05 movl  $0xffff, %rax <--- patched code at stack map address
0x0a callq *%rax         <---- end of 8-byte shadow

这样,在对运行时的正常调用返回后,代码将执行对特殊入口点的修补调用,该入口点可以从堆栈映射定位的值重建堆栈帧。

llvm.experimental.patchpoint.*’ 内联函数

语法:

declare void
  @llvm.experimental.patchpoint.void(i64 <id>, i32 <numBytes>,
                                     ptr <target>, i32 <numArgs>, ...)
declare i64
  @llvm.experimental.patchpoint.i64(i64 <id>, i32 <numBytes>,
                                    ptr <target>, i32 <numArgs>, ...)

概述:

llvm.experimental.patchpoint.*’ 内联函数创建对指定 <target> 的函数调用,并记录堆栈映射中指定值的位置。

操作数:

第一个操作数是 ID,第二个操作数是为可修补区域保留的字节数,第三个操作数是函数的目标地址(可选为空),第四个操作数指定以下可变操作数中有多少被视为函数调用参数。其余可变数量的操作数是 活跃值,其位置将记录在堆栈映射中。

语义:

补丁点内联函数生成堆栈映射。如果地址不是常量空值,它还会发出对 <target> 指定地址的函数调用。函数调用及其参数根据内联函数调用站点指定的调用约定进行降低。具有非 void 返回类型的内联函数变体也根据调用约定返回值。

在 PowerPC 上,请注意 <target> 必须是间接调用的预期目标的 ABI 函数指针。具体来说,当为 ELF V1 ABI 编译时,<target> 是通常用作 C/C++ 函数指针表示的函数描述符地址。

请求零补丁点参数是有效的。在这种情况下,所有可变操作数都像 llvm.experimental.stackmap.* 一样处理。不同之处在于,仍将为修补保留空间,将发出调用,并且允许返回值。

参数的位置通常不会记录在堆栈映射中,因为它们已经由调用约定固定。剩余的 活跃值 将记录其位置,可以是寄存器、堆栈位置或常量。已引入一种特殊的调用约定 anyregcc 用于堆栈映射,它强制将参数加载到寄存器中,但允许动态分配这些寄存器。除了剩余的 活跃值 外,这些参数寄存器还将在堆栈映射中记录其寄存器位置。

补丁点还发出 nop 以覆盖至少 <numBytes> 的指令编码空间。因此,客户端必须确保 <numBytes> 足够在支持的目标上编码对目标地址的调用。如果调用目标是常量空值,则没有最低要求。零字节空目标补丁点是有效的。

运行时可以修补为补丁点发出的代码,包括调用序列和 nop。但是,运行时不得对 LLVM 在保留空间内发出的代码做任何假设。不允许部分修补。运行时必须修补所有保留的字节,必要时用 nop 填充。

此示例显示了一个补丁点,根据本机调用约定,保留了 15 个字节,其中一个参数在 $rdi 中,返回值在 $rax 中

%target = inttoptr i64 -281474976710654 to ptr
%val = call i64 (i64, i32, ...)
         @llvm.experimental.patchpoint.i64(i64 78, i32 15,
                                           ptr %target, i32 1, ptr %ptr)
%add = add i64 %val, 3
ret i64 %add

可能生成

0x00 movabsq $0xffff000000000002, %r11 <--- patch point address
0x0a callq   *%r11
0x0d nop
0x0e nop                               <--- end of reserved 15-bytes
0x0f addq    $0x3, %rax
0x10 movl    %rax, 8(%rsp)

请注意,不会记录任何堆栈映射位置。如果修补后的代码序列不需要将参数固定到特定的调用约定寄存器,则可以使用 anyregcc 约定

%val = call anyregcc @llvm.experimental.patchpoint(i64 78, i32 15,
                                                   ptr %target, i32 1,
                                                   ptr %ptr)

现在,堆栈映射指示 %ptr 参数和返回值的位置

Stack Map: ID=78, Loc0=%r9 Loc1=%r8

补丁代码序列现在可以使用恰好在 %r8 中分配的参数,并返回在 %r9 中分配的值

0x00 movslq 4(%r8) %r9              <--- patched code at patch point address
0x03 nop
...
0x0e nop                            <--- end of reserved 15-bytes
0x0f addq    $0x3, %r9
0x10 movl    %r9, 8(%rsp)

堆栈映射格式

在 LLVM 模块中存在堆栈映射或补丁点内联函数会强制代码发射以创建 堆栈映射段。此段的格式如下

Header {
  uint8  : Stack Map Version (current version is 3)
  uint8  : Reserved (expected to be 0)
  uint16 : Reserved (expected to be 0)
}
uint32 : NumFunctions
uint32 : NumConstants
uint32 : NumRecords
StkSizeRecord[NumFunctions] {
  uint64 : Function Address
  uint64 : Stack Size (or UINT64_MAX if not statically known)
  uint64 : Record Count
}
Constants[NumConstants] {
  uint64 : LargeConstant
}
StkMapRecord[NumRecords] {
  uint64 : PatchPoint ID
  uint32 : Instruction Offset
  uint16 : Reserved (record flags)
  uint16 : NumLocations
  Location[NumLocations] {
    uint8  : Register | Direct | Indirect | Constant | ConstantIndex
    uint8  : Reserved (expected to be 0)
    uint16 : Location Size
    uint16 : Dwarf RegNum
    uint16 : Reserved (expected to be 0)
    int32  : Offset or SmallConstant
  }
  uint32 : Padding (only if required to align to 8 byte)
  uint16 : Padding
  uint16 : NumLiveOuts
  LiveOuts[NumLiveOuts]
    uint16 : Dwarf RegNum
    uint8  : Reserved
    uint8  : Size in Bytes
  }
  uint32 : Padding (only if required to align to 8 byte)
}

每个位置的第一个字节编码一个类型,该类型指示如何解释 RegNumOffset 字段,如下所示

编码

类型

描述

0x1

寄存器

Reg

寄存器中的值

0x2

直接

Reg + Offset

帧索引值

0x3

间接

[Reg + Offset]

溢出的值

0x4

常量

Offset

小常量

0x5

常量索引

Constants[Offset]

大常量

在常见情况下,值在寄存器中可用,并且 Offset 字段将为零。溢出到堆栈的值被编码为 间接 位置。运行时必须从堆栈地址加载这些值,通常形式为 [BP + Offset]。如果将 alloca 值直接传递给堆栈映射内联函数,则 LLVM 可能会将帧索引折叠到堆栈映射中,作为一种优化,以避免分配寄存器或堆栈槽。这些帧索引将以 BP + Offset 的形式编码为 直接 位置。LLVM 还可以通过将常量直接发射到堆栈映射中来优化常量,无论是在 常量 位置的 Offset 中,还是在常量池中,由 常量索引 位置引用。

在每个调用站点,还会记录一个“liveout”寄存器列表。这些是在堆栈映射中活跃的寄存器,因此必须由运行时保存。当补丁点内联函数与默认情况下将大多数寄存器保留为被调用者保存的调用约定一起使用时,这是一个重要的优化。

liveout 寄存器列表中的每个条目都包含一个 DWARF 寄存器号和字节大小。堆栈映射格式有意省略了特定的子寄存器信息。相反,运行时必须保守地解释此信息。例如,如果堆栈映射报告 %rax 处有一个字节,则该值可能在 %al 或 %ah 中。这在实践中无关紧要,因为运行时将简单地保存 %rax。但是,如果堆栈映射报告 %ymm0 处有 16 个字节,则运行时可以通过仅保存 %xmm0 来安全地进行优化。

堆栈映射格式是 LLVM SVN 修订版和运行时之间的契约。它目前是实验性的,并且可能在短期内更改,但最大限度地减少更新运行时的需求非常重要。因此,堆栈映射设计的动机是简单性和可扩展性。表示的紧凑性是次要的,因为运行时预计在编译模块后立即解析数据,并以其自己的格式编码信息。由于运行时控制段的分配,它可以为多个模块重用相同的堆栈映射空间。

堆栈映射支持目前仅在 64 位平台上实现。但是,32 位实现应该能够使用相同的格式,而不会浪费大量空间。

堆栈映射段

JIT 编译器可以通过 LLVM C API LLVMCreateSimpleMCJITMemoryManager() 提供自己的内存管理器来轻松访问此段。创建内存管理器时,JIT 提供一个回调:LLVMMemoryManagerAllocateDataSectionCallback()。当 LLVM 创建此段时,它会调用回调并传递段名称。JIT 可以在此时记录段的内存地址,并在以后解析它以恢复堆栈映射数据。

对于 MachO(例如在 Darwin 上),堆栈映射段名称为 “__llvm_stackmaps”。段名称为 “__LLVM_STACKMAPS”。

对于 ELF(例如在 Linux 上),堆栈映射段名称为 “.llvm_stackmaps”。段名称为 “__LLVM_STACKMAPS”。

堆栈映射用法

本文档中描述的堆栈映射支持可用于精确确定代码中特定位置的值的位置。LLVM 不维护这些值与任何更高级别实体之间的任何映射。运行时必须能够仅根据 ID、偏移量以及 LLVM 保留的位置、记录和函数的顺序来解释堆栈映射记录。

请注意,这与调试信息的目的截然不同,调试信息的目的是尽最大努力跟踪每个指令处命名变量的位置。

此设计的一个重要动机是允许运行时在执行到达与堆栈映射关联的指令地址时征用堆栈帧。运行时必须能够使用堆栈映射提供的信息重建堆栈帧并恢复程序执行。例如,执行可能会在解释器或同一函数的重新编译版本中恢复。

这种用法限制了 LLVM 优化。显然,LLVM 不得跨堆栈映射移动存储。但是,加载也必须保守处理。如果加载可能触发异常,则将其提升到堆栈映射之上可能是无效的。例如,运行时可以确定,在给定类型系统的当前状态下,加载可以安全执行而无需类型检查。如果类型系统在加载函数的某些激活存在于堆栈上时发生更改,则加载将变得不安全。运行时可以通过立即修补当前调用站点和加载之间存在的任何堆栈映射位置来阻止后续执行该加载(通常,运行时将简单地修补所有堆栈映射位置以使函数无效)。如果编译器已将加载提升到堆栈映射之上,则程序可能会在运行时可以重新获得控制权之前崩溃。

为了强制执行这些语义,stackmap 和 patchpoint 内联函数被认为可能读取和写入所有内存。这可能会比某些客户端期望的更限制优化。可以通过将调用站点标记为“readonly”来避免此限制。将来,我们可能还允许将元数据添加到内联函数调用中以表达别名,从而允许优化将某些加载提升到堆栈映射之上。

直接堆栈映射条目

堆栈映射段 中所示,直接堆栈映射位置记录帧索引的地址。此地址本身是运行时请求的值。这与 间接 位置不同,后者指的是必须从中加载请求值的堆栈位置。直接 位置可以在 alloca 的情况下传递地址,而 间接 位置处理寄存器溢出。

例如

entry:
  %a = alloca i64...
  llvm.experimental.stackmap(i64 <ID>, i32 <shadowBytes>, ptr %a)

运行时可以在编译后立即或在之后的任何时间确定此 alloca 在堆栈上的相对位置。这与 寄存器间接 位置不同,因为运行时只能在执行到达堆栈映射的指令地址时读取这些位置中的值。

此功能要求 LLVM 在入口块 alloca 直接被内联函数使用时对其进行特殊处理。(这与 llvm.gcroot 内联函数施加的要求相同。)LLVM 转换不得用任何中间值替换 alloca。运行时只需检查堆栈映射的位置是否为 直接 位置类型即可验证这一点。

支持的架构

对 StackMap 生成和相关内联函数的支持需要每个后端的一些代码。如今,仅支持 LLVM 后端的一个子集。当前支持的架构是 X86_64、PowerPC、AArch64 和 SystemZ。