为了解决这个问题我们为每个变量都标记一个版本号, 修改一次它的值就会出现一个新的版本.
这就是SSA(Static single assignment form), 一个变量+版本只能有一个值, 这时我们可以很简单的确定两个时点的y是否同一个y.
但是上图有一个问题, 最后一个BasicBlock使用的y在编译时是无法确定来源于哪个版本的.

为了解决这个问题, SSA引入了Φ(Phi)函数, 最后一个BasicBlock的开头添加一个新的版本y3 = Φ(y1, y2).

而VN(Value Number)则是基于SSA的标记, 会根据给GenTree分配一个唯一的ID, 例如x = 3和w = 3时, x和w的VN会相等.

下图是标记SSA和VN的实例:

Loop Optimizations

上面的"Flowgraph Analysis"提到的针对循环的一些优化, 在生成了SSA和VN以后我们可以做出进一步的优化.

例如这样的循环:

var a = SomeFunction(); for (var x = 0; x < 3; ++x) { Console.WriteLine(a * 3); }

注意a * 3这个表达式, 它每次循环都是一样的并且无副作用, 也就是我们可以提取(hoist)它到循环外面:

var a = SomeFunction(); var tmp = a * 3; for (var x = 0; x < 3; ++x) { Console.WriteLine(tmp); }

这样a * 3我们就只需要计算一次了, 但需要注意的是这种优化会增加一个临时变量, 所以实际不一定会执行.

Copy Propagation

这项优化会替换具有相同VN的本地变量,
例如var tmp = a; var b = tmp + 1;, 因为我们确定tmp和a的值(VN)是一致的, 可以优化为var b = a + 1.
在执行这项优化后, 多余的临时变量将不再需要, 例如上面的tmp变量如果引用计数为0即可删除.

CSE

这项优化会替换具有相同VN的表达式, 比起Copy Propagation这项优化的效果更强大.
例如:

var a = SomeFunction(); var b = (a + 5) * a; var c = (a + 5) + a;

注意a + 5这个表达式出现了两次, 这两次对应的GenTree的VN都是一样的,
因为它们无副作用(不会修改到全局状态), JIT可以把这段代码优化为:

var a = SomeFunction(); var tmp = a + 5; var b = tmp * a; var c = tmp + a;

和上面的Loop Optimizations一样, 这种优化会增加一个临时变量, 所以实际不一定会执行.

Assertion Propagation

在上面的Morph中JIT根据语句添加了一些断言, 在生成VN后JIT可以传播这些断言.
例如:

var x = 1; // x确定为1 var y = x + 2;

传播断言后:

var x = 1; // x确定为1 var y = x + 2; // y确定为3 Range Check Elimination

因为断言已经传播, 这项优化可以根据断言和VN来判断哪些数组的边界检查是多余的.
例如:

var length = 100; var index = 99; var a = new int[length]; // a的长度确定为100 var b = a[index]; // 确定访问不会越界, 所以这里的边界检查可以去掉 Backend Rationalization

这个步骤会正式把HIR转换为LIR, 后面的步骤使用的都是LIR形式.
前面的HIR中存在着一些问题, 例如ASG(=)节点:

看出问题了吗?lclVar在LIR中如果不访问后面的节点, 无法确定是读取变量还是写入变量.
Rationalizer会修改这些有问题的GenTree, 让后面的处理更加简单.
上面的lclVar =会修改为st.lclVar, 与lclVar区别开来.

Lowering

这个步骤会修改LIR中的GenTree节点, 让它更接近最终生成的机器代码形式.

以下是部分会转换的GenTree节点:

在完成了对GenTree节点的修改后, Lowering会对每个节点确定来源(src)和目标(dst)的寄存器数量.
例如lclVar节点需要一个目标寄存器, lclVar + lclVar节点需要两个来源寄存器和一个目标寄存器.

除了设置需要的寄存器数量外, Lowering还会标记哪些节点是contained,
标记为contained的节点代表它是上级节点的一部分, 生成指令时不需要针对contained节点单独生成.
典型的contained节点是常量, 例如b = a + 1可以生成add rbx, 1; mov rdi, rbx;, 这里的1并不需要一条单独的指令.

下图是Lowering的实例:

LSRA

在Lowering确认了寄存器需求以后, JIT还需要给这些节点实际的分配寄存器.
分配寄存器的算法有Graph coloring和LSRA等, RyuJIT使用的是LSRA, 和论文中的算法很相似.
使用LSRA算法可以让JIT中分配寄存器所需的计算量更少, 但是分配的结果(执行效率)会比Graph coloring差一些.

在LSRA中有以下概念:

下图是LSRA的实例:

在这张图中, Interval 0~2 是本地变量, 这里只有V01被使用, Interval 3~4是虚拟变量, 用于表示函数返回的结果或传入的参数.

DEF表示Interval被写入, USE表示Interval被读取,
Kill无对应的Interval, 只用于表示指定的寄存器的值是否在某个位置后被破坏,
FixedReg也无对应的Interval, 只用于表示对应的位置使用了固定的寄存器.

在确认Interval和RefPosition后, LSRA会开始分配寄存器,
一个寄存器在同一时间只能被一个Interval使用, 图上的寄存器都未出现Interval重叠的情况,
如果出现Interval重叠, 寄存器中的值会保存(spill)到堆栈上的变量.
如果一个变量从未被spill, 则该变量可以不使用堆栈保存, 如图上的V01可以一直存在rbx中, 不需要保存在内存里,
这可以带来很大幅度的性能提升.

LSRA会积极的使用Callee Saved Register(RBX, RBP, R12, R13, R14, R15)暂存变量,
这些寄存器在调用(call)其它函数后原来的值仍然会被保留, 不需要spill.

CodeGen

在以上步骤都完成后, JIT会根据cpu平台(x86, x64, arm)生成不一样的汇编指令.