代码清单8-16LIR代码生成生成LIR(组图)

从 HIR 到 LIR

LIR 类似于三操作数实现,但具有更高级的指令,例如对象分配和锁定。C1遍历HIR的每个基本块,为每个基本块的每条SSA指令生成对应的LIR指令。HIR 到 LIR 的转换过程由 LIRGenerator 完成,如示例 8-15 所示。

代码清单 8-15 从 HIR 到 LIR

void LIRGenerator::block_do(BlockBegin* block) {
block_do_prolog(block); // 转换每个基本块前的操作
set_block(block);
// 遍历基本块中的所有HIR指令,调用do_root(instr)将它们转换为LIR指令
for (Instruction* instr = block; instr != NULL; instr = instr->next()) {
if (instr->is_pinned()) do_root(instr);
}
set_block(NULL);
block_do_epilog(block); // 转换每个基本块后的操作
}

do_root(instr) 负责根据HIR生成LIR指令,但生成的前提是HIR指令必须经过pin处理。假设HIR中有3条加法指令(i1:5, i2:5, i3:i1+i2),那么经过pin处理的指令会被编译器视为root,其中i3是pin处理的,而 i1 和 i2 是常量,没有固定,所以在生成 LIR 时会跳过 i1 和 i2,直接从 i3 开始。

回归一代

Pin 只是一个优化动作。即使它没有被固定,只要需要,编译器仍然会为它生成相应的 LIR。例如,在处理 i3 时,编译器需要使用 i2、i3 作为加法指令的操作数。这时候,它会使用LIRItem对i2和i3这两个操作数进行包装,并调用walk()为它们生成对应的LIR。. 生成 LIR 的过程如清单 8-16 所示。

代码清单 8-16 LIR 代码生成

void LIRGenerator::do_Return(Return* x) {
// 如果返回类型为void,则生成不包含操作数的return LIR指令
if (x->type()->is_void()) {
__ return_op(LIR_OprFact::illegalOpr);
} else {
// 否则为操作数创建虚拟寄存器,然后将虚拟机寄存器作为return指令的操作数
LIR_Opr reg = result_register_for(x->type(), /*callee=*/true);
LIRItem result(x->result(), this);
result.load_item_force(reg);
__ return_op(result.result());
}
set_no_result(x);
}

根据HIR的返回是否返回void,选择无操作数或有一个操作数的LIR指令。

新生代

C1在生成LIR时也遇到了很多问题。一些指令,例如新建和监控操作,需要与虚拟机的许多组件进行交互。为它们生成 LIR 指令是一项复杂而困难的任务,如清单 8-17 所示。

代码清单 8-17 新指令 LIR 生成

void LIRGenerator::do_NewInstance(NewInstance* x) {
CodeEmitInfo* info = state_for(x, x->state());
LIR_Opr reg = result_register_for(x->type()); // 使用rdx存放结果
new_instance(...);
LIR_Opr result = rlock_result(x);
__ move(reg, result); // reg->result
}
void LIRGenerator::new_instance(...) {
// 将klass移动到rdx寄存器
klass2reg_with_patching(klass_reg, klass, info, is_unresolved);
if (UseFastNewInstance && ...) {
... // 特殊处理
} else {
// 生成NewInstanceStub
CodeStub* slow_path = new NewInstanceStub(...);
// 跳转到NewInstanceStub的entry
__ branch(lir_cond_always, T_ILLEGAL, slow_path);
// 从NewInstanceStub跳转回来继续执行__ branch_destination(slow_path->continuation());
}
}

实际上,C1并没有为它们生成LIR指令,而是创建了一段NewInstanceStub代码,然后跳转到NewInstanceStub的入口执行,如图8-6所示。

NewInstanceStub 相当于一个蹦床,执行流程从外部跳转到它的入口,它调用 Runtime1::new_instance 分配对象,然后跳转到外部延续继续执行。

转到一代

LIRGenerator 将为 HIR 指令 goto 生成对应的 LIR 指令,如代码清单 8-18 所示。

代码清单 8-18 do_Goto

void LIRGenerator::do_Goto(Goto* x) {
set_no_result(x);
...
move_to_phi(x->state());
__ jump(x->default_sux());
}

goto的LIR其实就是jmp跳转指令。一个值得注意的问题是SSA形式中存在Phi指令,而LIR是接近物理机架构的低级中间表示,并且没有指令集支持Phi,因此在生成时必须对Phi指令进行逆变换。这一步由LIRGenerator::move_to_phi完成逆向程序员是什么意思,具体思路如图8-7所示。

在HIR中,不同的基本块给同一个变量(假设为x)赋值时,可能会用到不同的SSA指令,如图8-7a所示,左边基本块x的赋值表示为n1=10 , 对基本块 x 的赋值记为 n2=20,最后它们的后续基本块使用 phi 指令合并数据,x 记为 n3=[n1,n2],符合 SSA 的定义. 但是LIR不是SSA,它不需要遵循它的规则,而且LIR需要更多地了解底层架构,Phi应该被淘汰,此时同一个变量x存放在不同基本块的同一个寄存器R1中。

线性扫描寄存器分配

线性扫描寄存器分配方法会将一个物理寄存器分配给 LIR 的虚拟寄存器。如果物理寄存器的空间不足,就会被内存替换(溢出到内存,之前对寄存器的读写变成了内存地址的读写)。C1 使用线性扫描寄存器分配 (LSRA) 来满足其设计理念。LSRA算法的具体实现位于c1_LinearScan中,以do_linear_scan()开头,如清单8-19所示。

代码清单 8-19 do_linear_scan()

void LinearScan::do_linear_scan() {
number_instructions();
compute_local_live_sets();
compute_global_live_sets();
build_intervals();
sort_intervals_before_allocation();
allocate_registers();
resolve_data_flow();
if (compilation()->has_exception_handlers()) {
resolve_exception_handlers();
}
propagate_spill_slots();
sort_intervals_after_allocation();eliminate_spill_moves();
assign_reg_num();
...
}

LSRA算法首先通过数据流分析中的经典方法——活跃度分析计算出value的活跃度,从而在后续配置中配置value的存活范围。

compute_local_live_sets 面向单个基本块,它会计算基本块中的每条指令,得到一个live_gen set和live_kill set。

live_gen(generate set):在当前基本块中使用,在前一个基本块中定义的值。live_gen 也称为使用集。

live_kill (kill set):在当前基本块中定义的值,可以“杀死”它在前一个基本块中的定义。live_kill 也称为定义集。

对于每条 LIR 指令,此步骤检查其输入操作数、输出操作数和临时操作数。如果输入操作数不在 live_kill 集中,即当前基本块没有定义,则将其添加到 live_gen 集中。输出操作数和临时操作数都被添加到 live_kill 集中,因为它们是值的定义。然后使用 compute_global_live_sets 将数据流分析扩展到所有基本块。其核心思想可以用如下数据流方程表示:

这个数据流方程的想法源于这些简单的事实:如果一个值在基本块内使用,那么该值必须存在于基本块的 live_in 集合中;如果一个值存在于live_in 集合中,那么它必须存在于基本块的live_in 集合中 基本块的前一个基本块的live_out 集合,因为控制流的边缘不会产生新的值;如果一个值存在于live_out 集合中,并且它没有在当前基本块中定义逆向程序员是什么意思,则当前基本块的live_in 集合必须包含它。

读者可能已经发现,根据live_gen获取基本块live_in和live_out集合的过程,live_kill是一个自下而上的过程,所以liveness分析是一个逆向的数据流分析。当数据流分析完成后,build_intervals开始构建生存区间,如代码清单8-20所示:

代码清单 8-20 LIR 示例

B2 [6, 14] pred: B3 sux: B3
__id__Operation_____________________________________________
24 label [label:0x31da17c]
26 move [R43|I] [R44|I]
28 mul [R44|I] [R42|I] [R44|I]
30 move [R42|I] [R45|I]
32 sub [R45|I] [int:1|I] [R45|I]
34 move [R44|I] [R43|I]
36 move [R45|I] [R42|I]
38 safepoint [bci:14]
40 branch [AL] [B3]

当 build_interval 工作时,它会使用该基本块的 live_out 集初始化构建值的 live_out 范围。目前基本块B2的live_out集合有R42和R43,初始化它们,如图8-8所示。

图 8-8a 显示了 R42 和 R43 的初始化。指令 38、40 不影响生存范围。指令36将R42的生存范围修改为[36,42[,并添加R45的生存范围[24,36[。指令34将R43的生存范围修改为[34,42[,并增加了R44的生存范围[24,36[。此步骤完成后,生存范围如图 8-8b 所示。然后指令32将R45的生存范围修改为[32,36[。指令 30 将 R45 的生存范围修改为 [30,36[. 指令28将R44的生存范围修改为[28,34[,然后为R42添加生存范围[28,30[。指令 26 将 R44 的生存范围修改为 [26,34[,为 R43 添加生存范围 [24,26[。一切就绪后,生存范围如图 8-8c 所示。

构建生存范围的核心思想是先用live_out集合初始化生存范围,然后从基本块的最后一条指令向上遍历,然后根据指令的输入输出临时修改生存范围. 具体实现见代码表8-21。

代码清单 8-21 build_interval 的实现

void LinearScan::build_intervals() {
...
// 反向遍历所有基本块
for (i = block_count() - 1; i >= 0; i--) {...
// 由下至上遍历基本块的所有指令
for (int j = instructions->length() - 1; j >= 1; j--) {
...
// 访问指令的输出操作数
int k, n;
n = visitor.opr_count(LIR_OpVisitState::outputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr=visitor.opr_at(LIR_OpVisitState::outputMode, k);
// 将存活范围的起点修改为当前位置
add_def(opr, op_id, use_kind_of_output_operand(op, opr));
}
// 访问指令的临时操作数
n = visitor.opr_count(LIR_OpVisitState::tempMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
// 添加新的存活范围为[cur,cur+2]
add_temp(opr, op_id, mustHaveRegister);
}
// 访问指令的输入操作数
n = visitor.opr_count(LIR_OpVisitState::inputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
// 添加新的存活范围为[block_start,cur[
add_use(opr, block_from, op_id, use_kind_of_input(op, opr));
}
...}
}
...
}

最后,allocate_register 根据先前获得的生存范围将虚拟寄存器映射到物理寄存器。线性扫描寄存器分配可以获得近似图着色寄存器分配的效果,只需要线性时间复杂度,这也是C1选择它的主要原因。

本文讲解的内容是对java虚拟机的深入解析:C1编译器,从HIR到LIR 下一篇将为大家讲解java虚拟机的深入解析:C2编译器,编译过程;觉得文章不错的朋友可以转发这篇关注小编;谢谢您的支持!

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论