分配寄存器也是类似的思路,图中的结点可以被看作是中间代码中的虚拟寄存器(或者叫临时变量,这里就叫做变量好了),而颜色可以被看作是物理寄存器,每个物理寄存器对应一种颜色,分配物理寄存器就是对结点进行着色。而结点之间的边代表了两个虚拟寄存器的冲突也就是两个虚拟寄存器不可以分配到同一个物理寄存器,因为这两个虚...
图着色算法是溢出代价最小的寄存器分配算法。 该方法的具体步骤为: S1:给机器指令分配虚拟寄存器,此时假设虚拟寄存器有无限多个; S2:构建寄存器冲突图,图中的节点是虚拟寄存器,对于两个虚拟寄存器,其中一个在另一个被定值的地方是活跃的则说两者是冲突的即这两个节点之间存在一条边。如:在第二条指令Rd被定值时Ra...
图着色算法就是看用N中颜色给这个图着色,如果能够让相邻的边的颜色不同,那么就可以着色完成。如果不可以,可能就需要spill寄存器。(把内容存到内存里)。 具体步骤如下: 1,构造冲突图,就是上面所画的,如果两个变量的live range有重叠,那么他们之间就有一条冲突边。 2.用启发式的算法,尝试N-color着色。 具体分...
全局分配器在一个函数的范围内工作。Chaitin的分配器就在这样的例子。程序间的寄存器分配是对一些函数工作,通常是一个完整的程序。为了支持全局的优化,全局的寄存器分配是必须的。1.3寄存器分配和图着色法实现好的寄存器分配总是很困难。即使是最简单的实现也会因为机器的特殊细节变得复杂。可靠的分配器必要能...
寄存器分配的目的是将程序中的变量尽可能保存在寄存器中, 而一旦寄存器不够用, 就要把变量保存到内存中去。 从八十年代到九十年代, 对全局寄存器分配研究得最多的是图着色的分配方法。 1 寄存器分配基本理论 1.1 编译器和优化 寄存器分配是编译过程中的一个重要阶段。 寄存器是计算体系结构中最快的存储空间 同时也是...
一种向量VLIW体系结构图着色寄存器分组分配方法,其步骤为:S1:数据模型的构造;S2:网的构造及属性分析;S3:冲突分析;S4:合并寄存器;依次遍历各个基本块的每一条指令,如果该指令不是寄存器传送指令,则不对它进行任何处理,否则根据寄存器类别和分组属性围绕该指令进行分析和处理;S5:修剪冲突图;按寄存器类别和分组属性的要求...
特殊的情况直接从需要分配的变量列表里面 spill 掉就行了。linear scan 只考虑：有多少可用的寄存器 每个...
在冲突图中,把复制的源寄存器和目标寄存器看做是同一个node,这样分配的时候就是同一个寄存器,这个技术就教coalescing。 coalsscing x 和 y 以及 (y = x), 需要满足以下条件: y的定义点就是 y = x x和 y 没有冲突边 但是,有的时候,做coalsescing不一定是我们期待的,因为虽然减少了一条复制指令,但是,可...