腾冲做兼职的网站,wordpress页面音乐播放器,沈阳建站模板系统包括,好用的网站链接线性扫描寄存器分配 文章目录 线性扫描寄存器分配1. 算法介绍2. 相关概念3. 算法的实现3.1 伪代码3.2 图示 参考文献 论文地址#xff1a;
Linear Scan Register Allocation
我们描述了一种称为线性扫描的快速全局寄存器分配的新算法。该算法不基于图形着色#xff0c;而…线性扫描寄存器分配 文章目录 线性扫描寄存器分配1. 算法介绍2. 相关概念3. 算法的实现3.1 伪代码3.2 图示 参考文献 论文地址
Linear Scan Register Allocation
我们描述了一种称为线性扫描的快速全局寄存器分配的新算法。该算法不基于图形着色而是在变量生存范围的单个线性时间扫描中将寄存器分配给变量。线性扫描算法比基于图形着色的算法要快得多并且易于实现并且生成的代码几乎与使用基于图形着色的更复杂且耗时的寄存器分配器获得的代码一样高效。该算法适用于关注编译时间的应用程序例如动态编译系统、“即时”编译器和交互式开发环境。
不使用图着色算法的根本原因是它要先构造好完整的干涉图才能在图上着色而干涉图的构造代价太过高昂。应该说图着色过程中的大部分开销都集中于干涉图的构造阶段。因此虽然图着色生成的代码质量很高但是对于讲究编译效率的现代编译器来说其时间成本是不可忽视的。对于对编译时间更加敏感的 JIT 编译器来说则更是如此。除此之外在实际的编译工作中人们发现了另外一个问题。由于在目前所有的硬件架构中寄存器的数目都是有限的故对于大型程序来说寄存器不够用可以说是必然存在的情况。换句话说大型程序一定会产生大量溢出。问题就出现在这里因为图着色算法把重点放在解决“如何把所有的程序变量尽可能地分配到寄存器中”如果程序一定会大量产生溢出那么关注“如何高效地溢出”比关注“如何尽量减少溢出”更有价值。
spill溢出是指目前的寄存器不够使用该部分数据需要借助sram或者堆栈区域的空间进行缓存协调的行为。 寄存器的数量是有限的因此当程序中使用了过多的变量或产生了大量的临时计算结果时编译器可能会出现寄存器不足的情况导致寄存器溢出。这可能会导致编译器将某些变量或数据存储在内存中而不是寄存器中从而降低了程序的执行效率。 1. 算法介绍
线性扫描寄存器分配算法是一种用于在编译器中分配寄存器的算法旨在将程序中的变量映射到计算机的寄存器以提高程序的执行效率。该算法通常用于编译器的代码生成阶段用于生成目标代码。
线性扫描寄存器分配算法的基本思想是通过一次线性扫描来分配寄存器从而在程序的不同位置为变量分配寄存器。该算法不需要进行复杂的数据流分析因此相对较快且简单。以下是线性扫描寄存器分配算法的主要步骤
构建活跃变量区间Live Range首先通过数据流分析计算每个变量的活跃区间即变量在程序中被使用的区间。活跃区间通常是变量在程序中的生命周期。排序活跃变量区间将所有活跃变量区间按照其结束位置从小到大进行排序。遍历活跃变量区间从排好序的活跃变量区间列表中按顺序遍历每个区间。在遍历过程中为每个区间分配一个可用的寄存器并在需要时将之前分配的寄存器释放。确定溢出如果某个区间没有足够的可用寄存器即产生溢出算法会尝试将某个寄存器的值移出到内存中以腾出空间来分配给新的变量。
线性扫描寄存器分配算法的优点在于简单易实现适用于中等规模的代码生成。然而它可能不如其他更复杂的寄存器分配算法如图着色法在某些情况下能够达到更高的性能。不同的编译器可能会使用不同的寄存器分配算法以根据特定的需求和目标平台进行优化。
2. 相关概念
live interval生命间隔 live range生命周期
interference相交conflict
active list已经分配物理内存的节点集合
3. 算法的实现
3.1 伪代码 3.2 图示 参考文献
[1] Register Allocation in LLVM 3.0 [2] Hacker News - Register Allocation [3] Linear Scan Register Allocation [4] Register Allocation [5] 博客圆-线性扫描寄存器分配
