Lazy Basic Block Versioning续

Interprocedural Type Specialization of JavaScript Programs Without Type Analysis 来自ECOOP2016，是在Simple and Effective Type Check Removal through Lazy Basic Block Versioning基础上实现的，主要将BBV扩展到interprocedural。

Interprocedural Basic Block Versioning

Type Object Shape

实现过程间BBV主要依赖以下两项：

Type Object Shape，因为在JS中，函数通常被存储在对象中，这包括对象方法和全局函数（JS将全局函数存储为全局对象的属性）。需要将类型标签附加到对象属性中，包括全局变量；
Object Shapes and Shape Tests，目前的商业JS引擎都有一个object shapes概念，与Self VM的属性图概念类似。对于任意对象都包含一个指向形状描述的指针，后者提供其内存布局：属性、属性的内存偏移量、属性标志(读写状态等)。而由于遍历这些属性的代价非常高昂，现代JS引擎会通过PICs(Polymorphic Inline Caches)来优化属性访问。通常情况下，通过shape tests来判断当前缓存是否适用，或者是否需要对PIC进行更新；

将上述两项结合，实现——Extending Shapes with Types，即一旦通过shape tests确定某个layout之后，同时也获得了对应属性的类型。

例如对于如下代码

function sumList (lst ) {
	if (lst == null )
		return 0
	return lst.val + sumList(lst.next )
}

可以获得三个带有type tag的object shape，其中G表示全局对象：

// Linked list node shape
S1: { val: (slot 0, int32), next: (slot 1, null) }
S2: { val: (slot 0, int32), next: (slot 1, object) }
// Global object shape
// Closures have method identity information
G: {
    ...,
    Error: (slot 1, closure/Error),
    ...,
    sumList: (slot 33, closure/sumList),
}

可以获得如下CFG：

A:	if is_null (lst) goto I:

B: 	if not is_object (lst) goto stub1

C: 	if not is_shape (lst , S1) goto C2
	val = read_slot (lst , 0) // val is known to be int32
	next = read_slot (lst , 1) // next is known to be null
D: 	if not is_shape ( globalObj , G) goto stub2
	sumfn = read_slot ( globalObj , 33) // sumfn is known to be a closure
E: 	t1 = sumfn ( next )
	if not is_int32 (t1) goto stub3
G: 	t2 = add_int32 (val , t1)
	if overflow goto stub4
H: 	return t2

I: 	return 0

C2: if not is_shape (lst , S2) goto stub5
	val = read_slot (lst , 0) // val is known to be int32
	next = read_slot (lst , 1) // next is known to be object
D2: if not is_shape ( globalObj , G) goto stub6
	sumfn = read_slot ( globalObj , 33) // sumfn is known to be a closure
E2: t1 = sumfn ( next )
	if not is_int32 (t1) goto stub7
G2: t2 = add_int32 (val , t1)
	if overflow goto stub8
H2: return t2

除了type tag之外，还可以附加函数签名信息，这样就可以在callsite上获取完整的callee。

Entry Point Versioning

当在一个callsite位置确定callee之后，同样也就可以确定paramater的类型，此时就可以在callee中生成Entry Basic Block的特化副本。在消除callee中多余的类型测试的同时，还可以在不对参数进行装箱的情况下传递参数，从而减少函数调用的开销。

Call Continuation Specialization

对于callsite另一个问题是返回值类型的传播。对于任意function来说，它可能在程序的任意位置被调用。因此这必然是一个context sensitive的。但是对于JIT而言，可以使用lazy的方式来低成本地执行优化。也就是直到第一次在一个callsite位置返回时才针对返回值类型进行特化，而不是像paramater，当callsite位置的类型确定之后就可以生成对应的machine code。