GC And StackMap

[lfeng14]

当前 C3 的 GC 支持可以拆成两条链：对象根跟踪和 GC 屏障。这两件事不要混在一起理解。

Java 字节码
   ↓
oop 标记为 LLVM 特殊地址空间
   ↓
插入 safepoint / GC barrier
   ↓
LLVM 优化 O3
   ↓
RewriteStatepointsForGC
   ↓
生成 statepoint、gc-live、gc.relocate
   ↓
LLVM StackMap
   ↓
转换成 HotSpot OopMap
   ↓
安装到 nmethod
   ↓
GC 扫描并更新栈帧里的对象引用

1. 标识哪些值是 Java 对象

C3 使用 LLVM 地址空间区分：

• AddressSpace 1：普通 oop
• AddressSpace 3：压缩 oop

HotspotGC::isGCManagedPointer() 据此识别 GC 管理的指针。

代码：GCStrategy.cpp

2. 建立 safepoint

C3 把下面这些位置作为潜在 safepoint：

• 普通 Java method 调用
• 循环回边
• method return 前的 poll
• 显式 safepoint poll

poll 快路径只检查线程的 polling word；需要 GC 时走慢路径，调用 HotSpot safepoint handler。

同时调用会携带 deopt bundle，保存：

• BCI
• locals
• operand stack
• monitors
• 内联调用链

代码：jeandleRuntimeDefinedJavaOps.cpp

3. LLVM 计算 safepoint 处存活的 oop

函数会设置：

gc "hotspotgc"

随后 RewriteStatepointsForGC 将可能触发 GC 的调用改成：

普通 call/invoke
    ↓
llvm.experimental.gc.statepoint
    ↓
gc-live：此处存活的 oop
    ↓
gc.relocate：GC 后重新取得 oop

例如对象移动前：

obj ── safepoint ──> 旧地址可能失效

改写后使用：

obj ── statepoint ──> gc.relocate(obj) ──> 新地址

它还会记录字段地址等 derived pointer 与对象 base pointer 的关系。

流水线位置：Pipeline.cpp

4. StackMap 转成 HotSpot OopMap

LLVM 后端把以下信息写入 .llvm_stackmaps：

• oop 位于哪个寄存器或栈槽
• narrow oop
• base/derived pointer 关系
• statepoint 位置

C3 再解析 StackMap，构造 HotSpot 的 OopMap：

LLVM StackMap
    ↓
JeandleCompiledCode::parse_stackmap
    ↓
OopMap::set_oop
OopMap::set_narrowoop
OopMap::set_derived_oop

代码：jeandleCompiledCode.cpp

5. 安装到 nmethod

生成的 OopMap 和反优化信息通过 DebugInformationRecorder 记录到编译后的 nmethod。

运行 GC 时，HotSpot 遍历 C3 编译栈帧：

1. 根据 PC 找到 OopMap。
2. 找到寄存器和栈中的 oop。
3. 标记存活对象。
4. 对象移动后更新 oop、narrow oop 和 derived pointer。

代码：jeandleReloc.cpp

6. 对象读写的 GC barrier

这属于另一条链。C3 会识别 Java heap 中的引用写入：

store oop
  ↓
pre_barrier
  ↓
真正 store
  ↓
post_barrier

对于 G1：

• pre barrier：保存旧引用到 SATB 队列，保证并发标记正确。
• post barrier：更新 Card Table，记录跨区域引用。

barrier 先以高级 JavaOp 形式插入，经过 O3 后再展开成具体 G1 操作。

代码：InsertGCBarriers.cpp

当前支持范围

目前代码明确面向：

• Serial GC：基本不需要并发屏障。
• G1 GC：实现 pre/post barrier、SATB 和 Card Table。

ZGC、Shenandoah 依赖更复杂的 load barrier/colored pointer，目前这条 C3 barrier 链还没有完整支持。

一句话概括：

C3 通过 LLVM statepoint 跟踪栈上的存活 oop，通过 StackMap 转成 HotSpot OopMap；同时通过 G1 pre/post barrier 保证堆内引用关系正确。

---

可以把 Jeandle 的 LLVM StackMap 理解成：把 LLVM 寄存器分配后的物理位置，转换为 HotSpot 能消费的 OopMap + ScopeValue/PcDesc + call relocation。

Java bytecode
    ↓
Jeandle Abstract Interpreter
    ↓
call/invoke + "deopt" operand bundle
            + statepoint-id
            + statepoint-num-patch-bytes
    ↓
LLVM Inline
父 scope deopt 参数 prepend 到子 scope
    ↓
RewriteStatepointsForGC
call/invoke → gc.statepoint
             + deopt args
             + GC live pointers
             + base/derived mapping
    ↓
SelectionDAG + 寄存器分配
LLVM Value → 寄存器 / 栈槽 / 常量
    ↓
StackMaps.cpp
生成 ELF .llvm_stackmaps
    ↓
JeandleCompiledCode::finalize()
解析 StackMap
    ↓
OopMap + ScopeDesc/PcDesc + CallReloc
    ↓
安装为 HotSpot nmethod

1. 前端生成 deopt 状态

Java invoke 在 jeandleAbstractInterpreter.cpp 中：

• 分配唯一的 statepoint-id
• 保存对应的 CallSiteInfo
• 创建带 "deopt" operand bundle 的 invoke
• 设置需要预留的 patch bytes

deopt bundle 由 deopt_args() 构造。

当前单个 scope 的协议大致是：

Root scope:
[
  should_reexecute,
  bci, bci,
  <local encode, value>...,
  <stack encode, value>...,
  <monitor encode, object, lock>...,
  <orig_pc encode, slot>
]

Inlinee scope:
[
  <MethodType encode, ciMethod*>,
  should_reexecute,
  bci, bci,
  locals...,
  stack...,
  monitors...
]

这里有几个要点：

• encode 负责补充 LLVM StackMap 本身没有的 Java 类型和 slot 类型。
• BCI 故意保存两次，作为 scope 开头的识别协议。
• num_deopts 数的是 LLVM operand 数量，不是 Java value 数量。
• local/stack 通常消费 2 个 operand，monitor 消费 3 个。

2. Inline 后形成 scope 链

LLVM inlining 时会把父调用点的 deopt bundle prepend 到子调用的 bundle，见 InlineFunction.cpp。

因此最终顺序是：

root scope
→ MethodType(callee1) + callee1 scope
→ MethodType(callee2) + callee2 scope
→ ...
→ youngest scope

如果 inline 导致一个 call site 被复制，Jeandle 还会通过 VM callback 分配新的 statepoint-id，保证：

record ID → _non_routine_call_sites[ID]

仍然是一一对应的。

3. RS4GC 生成真正的 statepoint

Pipeline 顺序在 Pipeline.cpp：

LLVM O3
→ ExpandNarrowOopCast
→ RewriteStatepointsForGC
→ JeandleNarrowOopMarker
→ 后续 lowering

RewriteStatepointsForGC 做两件核心事情：

1. 将非 leaf call/invoke 改写成 llvm.experimental.gc.statepoint。
2. 做 GC pointer liveness 和 base-pointer 分析，生成：

GCLive     = [derived0, derived1, ...]
BasePtrs   = [base0,    base1,    ...]

对应代码在 RewriteStatepointsForGC.cpp。

Compressed oop 则由 JeandleNarrowOopMarker 在 deopt bundle 尾部追加：

<NarrowOopMarkerType encode, narrow-oop value>

4. LLVM 后端生成 .llvm_stackmaps

SelectionDAG lowering 和寄存器分配完成后，抽象的 LLVM Value 已经变成：

• Register
• Indirect [SP + offset]
• Direct
• Constant
• ConstantIndex

StackMaps::parseStatepointOpers() 将一个 statepoint 写成如下 location 流，见 StackMaps.cpp：

[
  calling-convention,
  statepoint-flags,
  num-deopt-operands,

  deopt-operands...,

  base0, derived0,
  base1, derived1,
  ...
]

最后序列化进 ELF 的 .llvm_stackmaps section。

这里仓库中有一个误导注释：parse_stackmap_prologue() 把前两项写成了 frame size 和 frame offset，见 jeandleCompiledCode.cpp。实际上它们是：

#0 Calling Convention
#1 Statepoint Flags
#2 Number of Deopt Operands

目前代码只是忽略前两项，所以行为没错，注释需要后续修正。

5. HotSpot 解析 ELF StackMap

LLVM 生成 object 后，compile_module() 把 object 交给 JeandleCompiledCode。

安装阶段在 resolve_reloc_info()：

1. 找到 .llvm_stackmaps。
2. 遍历 record。
3. 使用两个坐标匹配 call site：

普通 Java/Stub call:
    record.ID → _non_routine_call_sites[ID]

Runtime routine call:
    record.instructionOffset → _routine_call_sites[offset]

4. 修正 LLVM code offset：

stackmap offset
- post-call nop
+ HotSpot 生成的 prolog length

6. 一个 record 被解析成 scope 链和 OopMap

parse_stackmap() 从 root method 开始解析，见 jeandleCompiledCode.cpp。

遇到 MethodType 时：

• 当前 scope 解析结束；
• 返回一个 JeandleStackMap；
• 把 ciMethod* 传给外层；
• 外层继续从同一个 record 的当前位置解析 inlinee scope。

因此得到：

_stack_maps = [
  root JeandleStackMap,
  inlinee1 JeandleStackMap,
  inlinee2 JeandleStackMap
]

只有最后、也就是最年轻的 scope 会继续消费 record 尾部的 GC pair，并构造 OopMap：

base == derived
    → oop_map->set_oop(derived)

base != derived
    → set_oop(base)
    → set_derived_oop(derived, base)

derived 被 NarrowOopMarker 标记
    → set_narrowoop(derived)

7. 转换为 HotSpot nmethod 信息

最终 process_stack_map()：

_stack_maps.back()->oop_map()
    → DebugInformationRecorder::add_safepoint()

每个 JeandleStackMap
    → create_scope_values()
    → create_monitor_values()
    → describe_scope()

最后
    → end_safepoint()

然后 JeandleCallReloc 还会 patch call instruction、生成 static call stub 等。

所以 StackMap 最终服务三件事：

• GC：生成 OopMap，找到 wide oop、narrow oop、derived oop。
• Deoptimization/StackWalk：生成 locals、expression stack、monitor 和 inline scope 链。
• Call relocation：根据 ID/PC 找到调用类型和目标，完成 call-site patch。

实际观察时，可以用：

-XX:+JeandleDumpIR
-XX:+JeandleDumpObjects
-Xlog:jeandle=trace
-XX:+PrintNMethods

然后查看 object：

jeandle-llvm/build-fastdebug/bin/llvm-readobj --stackmap <dumped-object.o>

最合适的现成入口是 TestScopeValues.java，它能同时观察 deopt bundle 和最终的 PcDesc/ScopeDesc。

[lfeng14]

单靠前面的 Java 例子不能证明完备。RS4GC 的正确性是“有前提的完备”：只有整个编译链满足一组不变量，它才能保证所有跨 safepoint 的 oop 都被正确处理。

核心证明目标可以写成：

对于每个 safepoint S：

所有在 S 之后仍可能被使用的 GC pointer p
    必须出现在 S 的 gc-live 集合中；

每个 p 必须有可追踪的 base(p)；

S 之后的每个 p 的使用
    必须改为使用 gc.relocate(S, base(p), p) 的结果。

需要证明的五个条件

1. 所有可能触发 GC 的调用都成为 statepoint

如果某个调用可能进入 safepoint，却被错误标成 GC leaf：

call void @actuallyMayGC()

RS4GC 不会改写它，也不会生成 StackMap。这时无论活跃性分析多准确都没用。

所以必须满足：

可能 GC 的调用 → statepoint
不生成 statepoint 的调用 → 确实是 GC leaf

这是 Jeandle runtime routine allowlist、call attribute 和 RS4GC 共同承担的契约。

2. 所有 Java oop 都能被识别

Jeandle 主要通过特殊 address space 标识 GC-managed pointer，例如：

ptr addrspace(1) %java_object

GC strategy 必须将它识别为 managed pointer。

如果 oop 被错误转换为：

i64 %raw_address

或者普通：

ptr addrspace(0)

RS4GC 可能不再知道它是 Java 对象。

因此必须禁止未受控的：

oop → integer → 跨 safepoint → pointer
oop → 未识别 address space

这也是为什么 raw oop、compressed oop 的转换位置非常敏感。

3. 活跃性分析覆盖所有使用方式

不仅普通计算使用算 live：

%value = load ..., %obj

deopt bundle 中保存的对象也必须算 live：

call ... [ "deopt"(ptr addrspace(1) %obj) ]

因为即使正常代码不再使用 %obj，反优化时仍然需要恢复它。

RS4GC 专门读取 deopt bundle operand，相关入口在 RewriteStatepointsForGC.cpp。

必须覆盖：

• 普通 successor 上的使用
• PHI 使用
• loop backedge
• invoke normal path
• invoke exceptional path
• deopt bundle
• base pointer 本身

4. 每个 derived pointer 都找到正确 base

例如：

array       = base
elementAddr = derived

必须证明：

base(elementAddr) == array

并且 base 自身也能跨 safepoint 保持可定位。

不安全的情况包括：

复杂 ptrtoint/inttoptr 运算
无法识别来源的地址计算
错误的 address-space cast
对象内部地址脱离 base 单独存活

如果 base 推导失败，可靠的实现应该拒绝编译或保守处理，不能静默漏报。

5. statepoint 后所有使用都被 relocate 支配

正常路径：

statepoint
    ↓
gc.relocate
    ↓
所有后续使用

对于 invoke 还需要覆盖两条路径：

                 normal path → relocate → use
statepoint invoke
                 unwind path → relocate → use

不能出现：

%new = gc.relocate(...)
use %old_obj               ; 错误：仍使用旧值

Jeandle 还要证明后半段没有丢信息

即使 RS4GC 的 IR 正确，后端协议也可能出错：

gc-live/base-derived
    ↓
SelectionDAG
    ↓
MachineInstr STATEPOINT
    ↓
.llvm_stackmaps
    ↓
Jeandle StackMap parser
    ↓
HotSpot OopMap

需要逐层验证：

1. StackMaps.cpp 写出的 base/derived 数量和顺序正确。
2. 寄存器 DWARF 编号能正确转换为 HotSpot VMReg。
3. stack offset 基于正确的 SP/frame。
4. narrow oop 没被误记成 wide oop。
5. inline scope 分割不会提前消费 GC pair。
6. StackMap PC 加上 Jeandle prolog 后仍指向正确 call return PC。

怎么实际验证

不能靠单个测试证明完备，但可以建立分层证据。

IR 层

检查 RS4GC 后：

每个非 leaf call 都是 gc.statepoint
每个跨 call 的 oop 都出现在 gc-live
call 后使用的是 *.relocated
每个 derived pointer 都有正确 base index

尤其检查 optimized IR，因为很多 derived pointer 是优化后才产生的。

StackMap 层

使用：

jeandle-llvm/build-fastdebug/bin/llvm-readobj --stackmap <file.o>

核对每个 record：

record ID
instruction offset
num deopt operands
deopt locations
base/derived location pairs

HotSpot 层

使用：

-Xlog:jeandle=trace
-XX:+PrintNMethods

核对最终：

StackMap record
→ CallSiteInfo
→ OopMap
→ PcDesc/ScopeDesc

运行时压力层

用移动式 GC，反复让对象跨越 safepoint：

static int test(Node node) {
    forceSafepointAndGC();
    return node.value;
}

配合：

-Xcomp
-Xbatch
-XX:-TieredCompilation
-XX:+UseJeandleCompiler
-Xmx小堆
-XX:+UseG1GC
-XX:+VerifyBeforeGC
-XX:+VerifyAfterGC

还要分别覆盖：

• oop 在寄存器中
• oop spill 到栈
• derived pointer
• compressed oop
• loop
• invoke 异常边
• inline 多层 scope
• deopt-only oop

结论是：

RS4GC 算法的完备性不是“它做了活跃性分析”就能保证的，而是建立在 safepoint 覆盖、oop 类型识别、base pointer 推导、relocate 支配关系，以及 StackMap 到 OopMap 协议全部正确之上。

其中任何一个前提被破坏，RS4GC 都可能产生结构合法、但 GC 语义不完整的代码。

[lfeng14]

可以。下面这个 Java 例子最直观地体现 RS4GC 的作用：

class Node {
    int value;
}

public class RS4GCExample {
    static void mayTriggerGC() {
        // 这里可能分配对象，也可能到达 safepoint
        Object[] objects = new Object[1000];
    }

    static int test(Node node) {
        int before = node.value;

        mayTriggerGC();          // safepoint，GC 可能移动 node

        int after = node.value;  // call 后仍然使用 node
        return before + after;
    }
}

关键点是：

node 在 mayTriggerGC() 之前存在
node 在 mayTriggerGC() 之后仍然需要使用

因此 node 是一个跨越 safepoint 的 live oop。

没有 RS4GC 时

概念上的 LLVM IR 类似：

define i32 @test(ptr addrspace(1) %node) {
entry:
  %before.addr = getelementptr %Node, ptr addrspace(1) %node, i32 0, i32 0
  %before = load i32, ptr addrspace(1) %before.addr

  call void @mayTriggerGC()

  ; 仍然使用 GC 前的 %node
  %after.addr = getelementptr %Node, ptr addrspace(1) %node, i32 0, i32 0
  %after = load i32, ptr addrspace(1) %after.addr

  %result = add i32 %before, %after
  ret i32 %result
}

问题在于：mayTriggerGC() 执行期间，移动式 GC 可能把 node 从旧地址移动到新地址。

例如：

调用前：node = 0x1000
GC 后： node = 0x8000

但 LLVM IR 还在使用旧的 %node = 0x1000，这可能导致读取失效地址。

RS4GC 第一步：识别 live oop

RS4GC 做活跃性分析，发现：

%node 在 statepoint 后仍然被使用

于是把 %node 加入 statepoint 的 GC live 集合。

概念上：

%token = call token @llvm.experimental.gc.statepoint(
    ...,
    @mayTriggerGC,
    ...,
    "gc-live"(%node)
)

这告诉 LLVM 后端：

到达这个调用点时，必须能从寄存器或栈中找到 %node。

它最终会进入 .llvm_stackmaps，例如：

node 位于寄存器 x19

或者：

node 位于 [sp + 48]

HotSpot 再根据这个位置构造 OopMap，GC 就能找到并更新该 oop。

RS4GC 第二步：生成 gc.relocate

RS4GC 还会在 statepoint 后生成：

%node.relocated =
    call ptr addrspace(1) @llvm.experimental.gc.relocate(
        token %token,
        i32 0,   ; base pointer index
        i32 0    ; derived pointer index
    )

然后将 call 后对 %node 的使用替换成 %node.relocated：

define i32 @test(ptr addrspace(1) %node) {
entry:
  %before.addr = getelementptr %Node, ptr addrspace(1) %node, i32 0, i32 0
  %before = load i32, ptr addrspace(1) %before.addr

  %token = call token @llvm.experimental.gc.statepoint(
      ...,
      @mayTriggerGC,
      ...,
      "gc-live"(%node)
  )

  %node.relocated =
      call ptr addrspace(1) @llvm.experimental.gc.relocate(
          token %token,
          i32 0,
          i32 0
      )

  ; 使用 GC 更新后的地址
  %after.addr =
      getelementptr %Node, ptr addrspace(1) %node.relocated, i32 0, i32 0

  %after = load i32, ptr addrspace(1) %after.addr
  %result = add i32 %before, %after
  ret i32 %result
}

如果 GC 没有发生：

%node.relocated == %node

如果 GC 移动了对象：

%node          = 0x1000
%node.relocated = 0x8000

call 后使用的是正确的新地址。

derived pointer 的例子

再看数组：

static int arrayTest(int[] array, int index) {
    int before = array[index];

    mayTriggerGC();

    return before + array[index];
}

LLVM 优化过程中可能产生：

array       → Java 数组对象基址，base pointer
elementAddr → array[index] 的元素地址，derived pointer

关系是：

elementAddr = array + headerSize + index * 4

如果 elementAddr 跨越 safepoint，RS4GC 不能只记录元素地址，因为 GC 无法仅凭内部地址可靠地更新对象。

因此它记录：

base    = array
derived = elementAddr

StackMap 中形成一对位置：

[base location, derived location]

Jeandle 解析后生成：

oop_map->set_oop(array_location);
oop_map->set_derived_oop(element_location, array_location);

如果数组被 GC 移动：

旧 array       = 0x1000
旧 elementAddr = 0x101c

新 array       = 0x8000
新 elementAddr = 0x801c

GC 可以根据 base 的移动量修正 derived pointer：

delta = 0x8000 - 0x1000
newDerived = 0x101c + delta = 0x801c

所以从 Java 代码视角看，RS4GC 保证的是：

Java 对象跨越 safepoint 后仍然有效

从 LLVM IR 视角看，它完成的是：

普通 call
→ gc.statepoint
→ 记录 live oop 和 base/derived
→ 生成 gc.relocate
→ call 后改用 relocated value