不可spill reload的异步用寄存器分配方案

工作的时候遇到了这样的一个场景，我们的异步器件通知程序结束的方式是将回答字写到一个内存地址，或者是一个特殊用途的寄存器中。写到内存的速度肯定是远远低于寄存器的，并且会一定程度抢占内存读写带宽，因此如何分配以及利用这个寄存器便是一个难题。以下为了和普通寄存器区分开，简称为SReg（special register）。

现有寄存器分配算法可行的原因是寄存器的值写到内存中保存，后续再取出来，可以保证值的正确性。但在异步操作的场景下，发起请求后不知道什么时候会将回答字写到寄存器中，假设在异步操作尚未写回值时，把SReg的值保存到内存，将这个SReg认为是可用并且给其他操作使用时，当异步器件实际写回值时，其他使用该SReg的操作得到的是一个和预期不符的值，并且从内存中将值重新加载回SReg时，读到的也是错误的值。因此该SReg用于异步操作时将值写回内存并且重新读取值无法保证正确性，也就是寄存器中分配常提到的spill reload操作。

由于硬件异步的特性，也可能同时发起多个异步请求，同时会有多个SReg被使用，不同函数之间很可能产生编号冲突。加上SReg的数量有限，无法无限分配SReg编号，因此难以在不同过程间去分配。

可选方案

根据该性质，SReg几乎无法被静态时分配。除非强制将执行的所有函数inline到一个大函数中进行分配，那么就从一个全程序区间的问题转换为一个函数内部的问题。但是总是inline并非总是好的，会造成代码体积严重膨胀，加大cache miss率，最后性能可能会下降，并且加大了用户与开发者的调试难度。

运行时分配可以通过一套简单的malloc free来实现，可以任意分配SReg，随时释放，方案最灵活，但是分配释放的开销略大。

我的方案

假设SReg有X个，那么我们将X个SReg的资源视为一个有X个元素的“栈”资源，每一个栈元素对应了一个SReg的编号。根据每个函数创建的SReg数量，控制栈桢的增减。其中函数中用到的SReg”指向“这个特殊栈的”栈桢”中的一个位置。当这个SReg作为参数传递时，不会分配新的SReg编号，会延续传入参数的编号，也不会导致新占用一个SReg。简单来说，使用SReg的时候，只需要视为一个普通的local变量来做即可。

相比于malloc，无需手动释放，可以通过编译时优化，来达到相同的使用效率，编码相对简单很多，并且分配的性能开销相对较小。不论是该方案还是基于普通的malloc，都无法直接解决数量用满时的问题，可以写代码时判断是否用满然后切换不同的实现方式，也可以编译器代替人工自动插入对应切换代码，不过如何高效实现又是一个问题，性能暂时难以评测，这个问题就暂时搁置。

另外有很多实际的硬件限制导致实际malloc方案有更多不可行的问题，这些限制太局限于专用硬件。将SReg资源视为栈资源的想法我觉得很有趣，使用角度来说和常规C语言局部变量一样自然，这也是我很想把这个方案记录下来的原因。

比如以下代码示例，其中async_request是发起异步请求，wait是同步等待直到异步请求结束并且将值写回SReg。

void foo1() {
	SReg reg1;
	SReg reg2;
	while(true) {
		async_request(reg1);
		async_request(reg2);
		foo2();
		wait(reg1);
		wait(reg2);
	}
}

void foo2() {
	SReg reg1;
	SReg reg2;
	foo3(reg2);
}

void foo3(SReg r) {
	SReg reg0;
}

当调用到foo1时

2 --------- SRegSP
  foo1::reg1 => SRegSP - 1
  foo1::reg2 => SRegSP - 2
0 ---------

当调用到foo2中时

4 --------- SRegSP
  foo2::reg1 => SRegSP - 1
  foo2::reg2 => SRegSP - 2
2 ---------
  foo1::reg1 // 等待异步器件中
  foo1::reg2 // 等待异步器件中
0 ---------

当调用到foo3中时

5 --------- SRegSP
	foo3::reg0 => SRegSP - 1
4 --------- 
  foo2::reg1 // 在foo2中创建，在foo2和foo3中使用，使用同一个资源
  foo2::reg2
2 ---------
  foo1::reg1
  foo1::reg2
0 ---------

鉴于硬件的一些特殊性质，工作中实际提出的方案还在这个基础上加了一些其他的限制，比如说需要清空值的时候只能一次性清空相连的Y个，因此栈需要按照Y去对齐，并且在销毁的时候清零，这都属于硬件绑定的实现细节的部分，就不详细介绍了。

整体开销较小，需要一个“栈指针”维持整个过程，因此开销包括了开栈和退栈，使用简单的加法计算每个SReg具体位置，另外释放的过程需要对其中的值置0。（硬件的特性导致）

SReg利用率优化

通过分析每个SReg的生命周期，根据生命周期结束时间排序，每个SReg结束的时候即可提前递减“栈指针”

例如

void foo1(bool check) {
	SReg reg1;
	SReg reg2;
	SReg reg3;
	async_request(reg1);
	foo2();
	wait(reg1);  // bb结束，reg1可以释放
	after_free();
	if (check) {
			async_request(reg3);
			foo2();
			wait(reg3); // reg3可以在这里释放	
			async_request(reg2);
			after_free();
			wait(reg2);
	} else {
			// reg3不被使用，释放
			async_request(reg2);
			foo4();
			wait(reg2);
	}
	after_free();
	// reg2在这里释放
}

void after_free() {
	SReg reg;
}

在这个例子中，根据lifetime从长到短是2 3 1，因此栈中排布顺序为

3 ---------
	foo1::reg1
  foo1::reg3
  foo1::reg2
0 ---------

三次执行after_free之前分别释放了栈顶的SReg变量reg1，reg3，reg2，因此三次执行的时候栈分别为

3 ---------
	after_free:reg
2 ---------
  foo1::reg3
  foo1::reg2
0 ---------

2 ---------
	after_free:reg
1 ---------
  foo1::reg2
0 ---------

1 ---------
	after_free:reg
0 --------- // foo1的栈已经完全被释放
0 ---------