寄存器配置

科技工作者之家 2020-11-17

在编译器最优化的领域里,寄存器配置(Register Allocation)的用途,在于使一个在较少寄存器数量的CPU可使用较大数量的变量,寄存器配置可使用在一个基本区块(Basic block)区域寄存器配置)、函数或程序(全域寄存器配置)、或是透过Call Graph进行跨函数边域分析(跨程序寄存器配置),当完成每个函数或是程序,惯例上会要求每个调用函数的位置(Call site)必须插入存储或是还原。

简介许多编程语言,程序员会有任意地配置过多变量的错误观念,然而在编译时,编译器必须决定在一个较小及有限寄存器的系统中如何分配这些变量,并非所有变量都是在同一时间运行,所以有些寄存器可能被分配超过一个变量。然而,两个被分配在同一寄存器的变量,若在同一时间使用,若是不破坏他的数值就无法被分配在相同的寄存器。无法被分配在相同的寄存器的变量必须被保留在随机存取存储器,在需要读取或写入时才会被加载,这个过程称之为溢出(spilling)。存储器访问速度比访问寄存器还慢,这会降低程序的运行速度,所以一个最优化的编译器会尽可能的将更多的变量放置在寄存器。寄存器压力(Register pressure)这个词被使用在当硬件寄存器数量比起理想数量还少的状况,高压的情况通常代表会产生更多溢出以及更多重载的情况发生。

除此之外,程序可以被进一步的最优化,只要可行,任何地方都能透过move指令来使一个寄存器的数值可以被移进移出,这在编译器中相当重要,这被使用在一些最优化技术,例如静态单赋值形式,他会在中间码额外产生move指令。1

图着色性的同构透过活跃变量分析(Live variable analysis),编译器可以决定哪个变量的集合在同一时间是活跃的,也就是涉入move指令的变量。使用这些信息,编译器可以建构一张图,使每个点(Vertex)在程序中代表一个独立的变量。当变量被同时使用时,则利用干扰边(Interference edges)链接两个节点,当变量同时涉入move指令时,则创建优先边(preference edges)。可以透过K-coloring用来解决寄存器配置的问题(K为寄存器可用的数量)。两个共享一个干扰边的节点不会被分配相同的颜色,而共享一个优先边的节点可能会被分配相同的颜色,有些节点可能一开始就会被上色,代表这些变量因为惯例或是模块间沟通的因素而必须留在某些特定的寄存器,图着色问题广义来说是NP完全问题,然而一个好的算法必须平衡性能以及代码的品质。

图着色技术是相当有效率,因为它不只考虑到变量的寄存器配置,还考虑在同时间运行的变量,逻辑上,如果变量V所有活跃的邻近变量可以被配置寄存器,那么通过V则可以访问到所有邻近的变量,所以这是一个递归的案例,目的是移除活跃变量集合中的变量。这个循环将持续进行,直到所有活跃变量都可以被配置,而其他的变量则溢出到存储器。1

溢出在多数的寄存器分配,每个变量会存在寄存器或是存储器,换句话说,如果一个变量无法被分配到一个寄存器,那么当这个变量要被使用时就会从存储器加载。一个溢出的变量(Spilled Variable)代表一个变量在存储器中而不在CPU的寄存器。举例来说,一个32位的变量溢出到存储器,他会获取32位的堆栈空间,而所有使用到这个变量的位置将会指到存储器,这样的变量的处理速度相较于寄存器的变量就会比较慢,所以要决定哪些变量必须溢出,就必须考虑到运行时间、代码占用空间以及数据空间等因素。2

迭代寄存器接合寄存器分配有很多类型,迭代寄存器接合(Iterated Register Coalescing,IRC)则是常用的一种,IRC是由LAL George及Andrew Appel在1996年提出,IRC基于一些原理所运作,第一,如果在图中存在无法被移动的节点,而这些与这些节点的连接的数量小于K,则这些图可以直接移除掉这些节点,因为一旦这些节点被加回去,则可以保证找到他们的颜色(简化)。第二,两个节点共享一个优先边,而他们邻近集合的连接总数小于K,那么这两个点可以被结合为一个节点(接合),如果上述两个步骤可以简化图,简化的程序在移动相关节点时(冻结时),可以再运行一次。最后,如果没有任何其他工作了,节点可以被标示为可能溢出并且从图中移除(溢出)。以上步骤用以减少图中节点的连接数,节点的连接数可能从大于K的情况降为低连接数,使节点可以被简化或是接合。这个阶段的算法被迭代,以确保简化及接合的品质。虚拟代码如下:

function IRC_color g K : repeat if ∃v s.t. !moveRelated(v) ∧ degree(v)

科技工作者之家

科技工作者之家APP是专注科技人才,知识分享与人才交流的服务平台。