代码生成

指令选择

Code_Gen中的Matcher::match表示C2的指令选择过程。

Matcher::match使用BURS算法，而BURS要求匹配的IR是树的形式，因此指令选择的第一步是将理想图转换为树，然后再进行匹配。图9-15展示了整数加法节点AddI的指令选择的匹配过程。

图9-15a为指令选择前的理想图，对应Java代码的p1+p2+12，其中p1、p2表示方法参数。在指令选择阶段，C2在x86_64.ad中寻找匹配的树规则，如代码清单9-24所示：

代码清单9-24 x86_64.ad

instruct addI_rReg(rRegI dst, rRegI src, rFlagsReg cr) %{
match(Set dst (AddI dst src));
effect(KILL cr);
format %{ "addl $dst, $src\t# int" %}
opcode(0x03);
ins_encode(REX_reg_reg(dst, src), OpcP, reg_reg(dst, src));
ins_pipe(ialu_reg_reg);
%}
instruct addI_rReg_imm(rRegI dst, immI src, rFlagsReg cr) %{
match(Set dst (AddI dst src));
effect(KILL cr);
format %{ "addl $dst, $src\t# int" %}
opcode(0x81, 0x00);
ins_encode(OpcSErm(dst, src), Con8or32(src));
ins_pipe( ialu_reg );
%}

instruct定义新的MachNode，match行表示树匹配规则。首先AddI#23节点作为根进行匹配，它的模式（AddI#23 Parm#10 Parm#11）和树规则（Set dst（AddI dst src））成功匹配，AddI#23被转化为addI_rReg#10。接下来AddI#25节点开始匹配，它的模式（AddI#25AddI#23 ConI#24）也与（Set dst （AddI dst src））匹配，但是要求dst是寄存器，src是常量（立即数），满足这些要求的只有addI_rReg_imm，因此AddI#25转化为addI_rReg_imm#9。指令选择最终会将理想图所有节点都转换为机器相关的MachNode，并在其上应用GCM和分配合适的寄存器。

图着色寄存器分配

通过寄存器分配，编译器可以知道在任何程序点，哪些变量可以保留在寄存器，哪些需要溢出到栈上，可见，寄存器分配对于最终编译产出的代码性能有决定性的影响。图着色寄存器分配算法是C2最复杂的算法之一，它的基本原理是用K种颜色为图中的N个节点着色，其中相邻节点颜色不能相同。具体到C2中，节点表示变量，即虚拟寄存器，颜色表示物理寄存器，相邻节点表示在同一时间存活的变量。由于图着色问题是NP完全问题，最优的全局寄存器分配代价太大，所以现实中一般使用启发式算法如Chaitin-Briggs方法或者Callahan Koblenz方法进行分配，两者最大的区别在于对程序控制流的处理。C2中使用最为广泛的是Chaitin-Briggs方法，代码位于PhaseChaitin::Register_Allocate，完整过程如图9-16所示。由于PhaseChaitin::Register_Allocate代码相当复杂，这里只简单介绍图着色算法的思想。

图着色算法涉及四个内容：IR代码、存活范围（Live Interval）、寄存器干扰图（Register Interference Graph，IFG）、着色图。图着色算法为IR代码的每个值分配一个虚拟寄存器，然后通过数据流活跃变量分析，得到每个值的存活范围，并根据存活范围得到一个寄存器干扰图，对IFG着色。IFG是一个无向图，节点表示虚拟寄存器，如果两个节点的虚拟寄存器不能映射到相同的物理寄存器，那么用线将它们连起来表示它们必须同时存活，如图9-17所示。

如图9-17所示，图着色算法为IR代码的每个值分配一个虚拟寄存器，即v1～v5。图9-17右侧是存活范围，存活范围从值被定义到值最后一次使用组成一个区间，中间的空洞（Hole）表示值被多次定义和使用。以图9-17为例，v1的值在（1）处被定义，在（3）处最后一次使用，在（5）处定义，在（7）处最后一次使用，所以它的存活范围是1～3和5～7，中间存在一个空洞。类似的，v2的值在（2）处被定义，在（4）处最后一次使用，所以它的存活范围是2～4。有了所有值的存活范围后，可以计算出寄存器干扰图。根据IFG的定义，v1与v2、v4、v5的存活范围有重合，这意味着它们的虚拟寄存器必须同时存活，所以v1干扰v2、v4、v5。类似的，v2干扰v3，v3干扰v4，最终的IFG如图9-18所示。

现在对IFG进行着色。物理寄存器数表示“色”数。假设有2个物理寄存器，现在的任务就是将7个虚拟寄存器映射到2个物理寄存器上，如果不能映射，那么一些值必须溢出（Spill）到内存。着色算法的迭代过程如图9-19所示。

每次从IFG上移出一个节点和关联的边，并将节点放入右边的栈。这一步有两条规则：如果一个节点的度（关联的边数）小于物理寄存器数，那么它是可着色的；如果节点的度大于等于物理寄存器数，那么仅当关联的节点没有相连时它们是可着色的。以图9-19为例，首先v5的度为1，小于物理寄存器数2，那么将它移出到栈。接着图9-19a中所有节点的度都为2，不能使用第一条规则，应用第二条规则，与节点v2关联的节点v3和v1没有相互连接，那么v2可以着色，移出到栈中，如此反复直到图为空。最后一步会将栈中的节点逐个弹出并为它选择一个颜色，然后重建着色图，结果如图9-20所示。

在选择颜色时要注意，只能选择一个与节点关联的节点没有使用的颜色，如果没有则虚拟寄存器溢出到内存。以图9-20为例，为v4选择r1作为颜色。v1关联的v4已经使用了r1，只能使用r2作为颜色。v3关联的v4使用了r1，所以使用r2作为颜色。v2关联的v3、v1都使用r2，所以v2使用r1作为颜色。v5关联的v1使用了r1，所以v5使用r2。着色的关键是只需要关心一个节点直接关联的节点所使用的颜色，没有直接关联的节点表示它们位于不同的生命周期，可以复用颜色。着色完成后的效果如图9-21所示。

C2使用图着色寄存器分配算法，使用两个物理寄存器就能处理五个值，极大地提升了程序的运行时效率。

本文给大家讲解的内容是深入解析java虚拟机：C2编译器，代码生成

1. 下篇文章给大家讲解的是深入解析java虚拟机：垃圾回收，垃圾回收基础概述；
2. 觉得文章不错的朋友可以转发此文关注小编；
3. 感谢大家的支持!