LIR类似于三操作数的实现，但多了一些诸如对象分配和加锁的高级指令。C1遍历HIR的每个基本块，为每个基本块的每条SSA指令生成对应的LIR指令。从HIR到LIR的转换过程由LIRGenerator完成，如代码清单8-15所示。
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存在三条加法指令（i1:5，i2:5，i3:i1+i2），经过pin处理的指令会被编译器视作root，这里i3被pin处理，i1和i2作为常量未被pin处理，所以生成LIR时会跳过i1和i2直接从i3开始。
pin只是一个优化动作，即使未被pin住，只要有需要，编译器还是会为它生成对应的LIR。比如当处理i3时，编译器需要将i2、i3作为加法指令的操作数，此时它会使用LIRItem包装i2和i3两个操作数，并调用walk()为它们生成对应的LIR。生成LIR的过程如代码清单8-16所示。
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的return是否返回void选择生成无操作数还是含一个操作数的LIR指令。
C1在生成LIR时还会遇到很多问题，有些指令，如new、monitor操作，需要与虚拟机的许多组件交互，为它们生成LIR指令是一个复杂且困难的任务，如代码清单8-17所示。
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 {// 生成NewInstanceStubCodeStub* slow_path = new NewInstanceStub(...);// 跳转到NewInstanceStub的entry__ branch(lir_cond_always, T_ILLEGAL, slow_path);// 从NewInstanceStub跳转回来继续执行__ branch_destination(slow_path->continuation());}}
实际上C1并不会为它们生成LIR指令，而是创建一段NewInstanceStub代码，然后跳转到NewInstanceStub的entry执行，如图8-6所示。
NewInstanceStub相当于一个跳床（Trampoline），执行流从外部跳到它的entry，由它调用Runtime1::new_instance分配对象，然后跳到外部的continuation处继续执行。
LIRGenerator会为HIR指令goto生成对应的LIR指令，如代码清单8-18所示。
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使用线性扫描寄存器算法（Linear Scan Register Allocation，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算法首先通过数据流分析中的经典方式——活跃分析，计算出值的活跃性，以便后续配置构造值的存活范围。
compute_local_live_sets面向单个基本块，它会对基本块中的每条指令进行计算，得到一个live_gen集合和live_kill集合。
live_gen（生成集）：在当前基本块中使用，在前驱基本块定义的值。live_gen又称use集。
live_kill（杀死集）：在当前基本块定义的值，该值可能“杀死”其在前驱基本块的定义。live_kill又叫def集。
对于每一条LIR指令，这一步都会检查它的输入操作数、输出操作数、临时操作数。如果输入操作数没有位于live_kill集，即当前基本块没有定义，那么将它加入live_gen集。输出操作数和临时操作数都加入live_kill集，因为它们是对值的定义。接着使用compute_global_live_sets将数据流分析扩展至所有基本块，它的核心思想可用下面的数据流方程表示：
该数据流方程的思想源于这些简单的事实：如果在一个基本块内使用了一个值，那么该值一定存在于基本块的live_in集合；如果一个值存在于live_in集合，那么它一定存在于该基本块的某个前驱基本块的live_out集合，因为控制流的边不会生成新的值；如果一个值存在于live_out集合，而且它没有在当前基本块中定义，则当前基本块的live_in集一定包含它。
读者可能已经发现，根据live_gen、live_kill得到基本块live_in和live_out集的过程是一个由下至上的过程，所以活跃分析是一个反向数据流分析。当数据流分析完成后build_intervals开始构造存活范围，如代码清单8-20所示：
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集初始化构造值的存活范围。目前基本块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所示。深色黑条表示该值在该处使用（use_position）。
构造存活范围的核心思想是首先用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
本文转载自网易号【我们的百变生活】，更多内容请点击“阅读原文”
