寄存器申请

前面提到在生成 IL(中间语言) 的时候使用了无限的寄存器，但是实际硬件是有寄存器限制的。

后续不使用的临时变量所占用的寄存器可以重复使用：

寄存器申请算法的历史：

算法抽象描述：

关于 live 的概念请见上一个章节。
举例来看一个找到 live 变量的示例：

RIG（register interference graph）

举例说明：

图着色

着色问题定义：

把寄存器分配的问题，转化成图着色的问题：

图着色问题并不好解决，这是一个 NP-HARD 的问题：

但是可以用近似和延迟的方法来处理。

近似方法：

通过两步实现：

举例：

当所有节点的连接数都小于 k 时停止：

spilling

spilling 定义：

着色数超过寄存器数量，就要移到内存里去处理了。。。
还是前面的例子，如果只有 3 种颜色，移除 a 之后就卡住了：

选择一个点进内存：

optimistic coloring

如果 optimistic coloring fail，需要对内存进行操作：

例子：

这里 f 会重新命名，也需要重新计算 liveness:

通过读写内存，设置不同的 f 可以做到：


那么怎么选择 spilling 的 node 呢？

寄存器申请是必须要实现的内容：

这里提到 CISC 的逻辑会比 RISC 复杂一些。

manage cache

编译器对 cache 的优化能力要弱于对寄存器的提升能力：

比如改变循环顺序，可以大幅提升性能：

因为 cache miss 的开销造成，但是大部分编译器都不支持改循环顺序的操作，还是需要人来操作。
ps:tvm 采取的办法是自己切片机器自己去试参数，但是找到合适参数的成本也非常高。