Register Allocation
对于一个JIT而言，寄存器分配对系统的消耗通常是一个瓶径。之前有Graph Coloring Allocators, Chaitin style等分配方式，现在要介绍的是DFG JIT使用的Linear Scan算法。其基本工作方式是将占用寄存器的变量根据生命周期长短排列出来，在使用时查看可以回收哪些寄存器加以利用。
先看一些定义:
•Live interval:是某个变量可以存活的一个指令序列，也可以称为了连续性。这个也依赖于算法使用的是深度优先还是广度优先。如下图，B1~B4代表的是四个Basic Blocks，w/r代表的是读和写.
•Spilling:当变量存储到堆栈时就称为溢出。
•Interference: 当两个活动区间共同存在于一个程序中时，称他们之间会有干扰。
算法的执行过程简述如下:
1. 计算变量的live interval.
2. 遍历:
2.1 如果live interval已经过期就扔掉。
2.2 分配新的live interval和寄存器。
2.3 如果无法分配(所需的interval过长等)，则spill出去，再选择较低成本的变量。
复杂度:O(V logR) (V是变量数，R寄存器数)
下面是示意图:
Trampoline
再介绍一下JIT中应用的Trampoline,蹦床或者弹簧技术，可以达到延迟编译的效果(其它领域的效果不同，比如编译器里的PLT)。一个“弹簧床”就是一个函数存根，它能在被调用的时候，触发JIT执行。一旦JIT编译这个函数成为机器码，那么“弹簧床”的指针就会被替换为真实函数的指针。
在JSC中，相关代码查看JITStubs.cpp中的实现，如ctiTrampoline等。下面是一个调用堆栈：
然后再跳转到具体的操作(可能会调回到LLInt对应的slow path进行处理):
转载请注明出处: http://blog.csdn.net/horkychen
参考:
Massimilliano Poletto, Linear Scan Register Allocation
CS 380C Lecture 14, Register Allocation
Mono:Runtime:Documentation:Trampoline
系列索引:
高级篇(一) SSA (static single assignment)
高级篇(三) Register Allocation & Trampoline
