精华内容
下载资源
问答
  • 寄存器分配算法. 研究编译器后端的可以参考下
  • 图着色寄存器分配

    千次阅读 2020-01-21 15:28:52
    如果寄存器分配问题被抽象成图着色问题,那么图中的每个节点代表某个变量的活跃期或生存期(Live range)。活跃期定义是从变量第一次被定义(赋值)开始,到它下一次被赋值前的最后一次被使用为止。两个节点之间的边...

    如果寄存器分配问题被抽象成图着色问题,那么图中的每个节点代表某个变量的活跃期或生存期(Live range)。活跃期定义是从变量第一次被定义(赋值)开始,到它下一次被赋值前的最后一次被使用为止。两个节点之间的边表示这两个变量活跃期因为生命期(lifetime)重叠导致互相冲突或干涉。一般说来,如果两个变量在函数的某一点是同时活跃(live)的,它们就相互冲突,不能占有同一个寄存器。

    详情参考知乎:https://zhuanlan.zhihu.com/p/55287942

     

    展开全文
  • 在上一篇博文 LLVM 里的寄存器分配 - 准备工作(一) 里,我主要整理了 LLVM 在做寄存器分配前所做的准备工作,介绍了 LLVM 是在怎样的 MIR 上做的寄存器分配。接下来,就需要讲讲 LLVM 是如何做寄存器分配了。虽然...

    1 背景介绍

    在上一篇博文 LLVM 里的寄存器分配 - 准备工作(一) 里,我主要整理了 LLVM 在做寄存器分配前所做的准备工作,介绍了 LLVM 是在怎样的 MIR 上做的寄存器分配。接下来,就需要讲讲 LLVM 是如何做寄存器分配了。虽然我学习的第一个寄存器分配算法是图着色算法,但由于目前的 LLVM 版本里使用的寄存器分配器均是线性扫描算法的变种(事实上 LLVM3.0 版本以前的寄存器分配器默认使用的就是线性扫描算法),因此本文主要介绍线性扫描算法的理论知识以及相关术语,图着色算法的具体过程可以参考文档 Global Register Allocation

    2 为什么不使用图着色算法?

    在开始研究 LLVM 里的寄存器分配算法之前,我一直以为 LLVM 使用的是图着色算法,后来了解多一点才发现 LLVM 至始至终就没有考虑过图着色。这是为什么呢?这个问题其实在 LLVM3.0 的发布会议上,这一版本寄存器分配器的开发者 Olesen 在他的 报告 里提到过,如下所示:

    ![Graph Coloring](https://img-blog.csdn.net/20180119194338963?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk2NzQzNTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
    不难发现,不使用图着色算法的根本原因是它要先构造好完整的干涉图,才能在图上着色,而干涉图的构造代价太过高昂。应该说,图着色过程中的大部分开销都集中于干涉图的构造阶段。因此,虽然图着色生成的代码质量很高,但是对于讲究编译效率的现代编译器来说,其时间成本是不可忽视的。对于对编译时间更加敏感的 JIT 编译器来说,则更是如此。

    除此之外,在实际的编译工作中,人们发现了另外一个问题。由于在目前所有的硬件架构中,寄存器的数目都是有限的,故对于大型程序来说,寄存器不够用可以说是必然存在的情况。换句话说,大型程序一定会产生大量溢出。问题就出现在这里,因为图着色算法把重点放在解决“如何把所有的程序变量尽可能地分配到寄存器中”,如果程序一定会大量产生溢出,那么,关注“如何高效地溢出”比关注“如何尽量减少溢出”更有价值。例如,可以关注如何选择溢出的变量,以达到尽可能减少对性能的影响这一问题。这一着重点的改变,就是目前 LLVM 里贪心寄存器分配器的中心思想。

    图着色算法的最后一个问题,就是它难以处理实际寄存器分配问题中碰到的复杂局面。例如,在 X86 架构中,存在 register alias(如 AL/AH/AX)、pre-color 等问题,图着色算法在解决这类问题时需要较为复杂的调整。这些因素都促使 LLVM 选择了线性扫描算法。

    3 线性扫描算法

    在 LLVM3.0 版本以前,默认的寄存器分配器的核心算法就是线性扫描算法。这种算法生成的代码相对图着色有 10%-30% 的冗余代码(见参考文献【2】),但速度远快于图着色。在 LLVM3.0 版本以后,新加入的 basic/greedy 寄存器分配器在线性扫描算法的基础上进行了进一步强化,可以看作是线性扫描算法的变种。正因如此,新版分配器里的一些关键概念与线性扫描经典论文 Linear Scan Register Allocation 中并无出入。

    3.1 术语

    live interval:这是线性扫描算法的一个至关重要的概念。假设 IR 里的指令按数字编号,变量 v 的 live interval 是区间 [i, j],需要满足下述条件:不存在编号为 j’(j’> j)的指令,使得变量 v 在 j’处活跃,且不存在编号为 i’(i’< i)的指令,使得变量 v 在 i’处活跃。这个定义是对 live ranges 的保守估计,因为在区间 [i, j] 里,可能存在部分子区间变量 v 并不活跃,这些区间在 live interval 的定义里被忽视掉了,这就是传统的线性扫描算法未能充分利用寄存器的原因。

    live range:这里采取文献 Register Allocation 中的定义,即认为 live range 是严格意义上变量活跃时所有程序点的集合。例如,若有一变量的生命期是 [12, 96], [96, 112], [112, 256],上述三个区间都是此变量的 live range,而区间 [12, 256] 则是此变量的 live interval。注意,这里的这个概念和 LLVM 里的 Segment 是一样的。

    注释:由于上述英文术语的中文含义很接近,难以区分,故本文不对其进行翻译,下文直接采取其英文名称。

    interference:在线性扫描里,不存在相交图(interference graph),相交发生在各个 live interval 重叠的部分。显然,需要特别关注每个 interval 的起始位置和结束位置,各个 live interval 的相交关系只会在这两个位置发生改变。下面给出了一个例子,在不同的程序点,不同的 live interval 存在相交关系,g 与其它的 live interval 均不相交:

    ![interference](https://img-blog.csdn.net/20180119213343451?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk2NzQzNTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
    **original list**:这个名字是我自己起的,用于表示最开始存放了所有 live interval 的表。要注意的是,该表里各个 live interval 是按照起始位置的升序排列的。从下文中的算法可以看到,起始位置最小的 live interval,也就是最早出现的 live interval,最先被扫描到。

    active list:用于表示已经分配了寄存器的 live interval 的表,表中的 live interval 都按照结束位置递增的顺序排列。这么排的原因不难想象,结束位置最小的 live interval 最先结束,然后就可以把分配给该 live interval 的寄存器回收到寄存器池中,等待下一次分配。

    3.2 计算 live interval

    在开始执行线性扫描算法前,要先获得 live interval,算法分配寄存器都是给 live interval 分配的,因此编译器还要事先做一点准备工作。首先,编译器要将控制流图 CFG 线性化并给每条指令编号。在 LLVM 里,是通过深度优先序来线性化 CFG 的,同时通过 slot index 来给每条指令编号,相邻指令之间编号的差值为 16。Poletto 的论文里,也选择了深度优先序列。实际上,这并不是一个巧合。其次,需要对 IR 做后向数据流分析,就可以获得每个变量的活跃信息,并进一步得到 live interval。迭代数据流分析的关键过程每本编译原理的教材都会介绍,在此不再赘述。

    3.3 工作过程

    在线性扫描算法里,active list 是最核心的数据结构,其作用可以在下图中的伪代码看出来:

    ![linear scan](https://img-blog.csdn.net/20180119220650177?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk2NzQzNTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
    在上述的线性扫描算法中,LinearScanRegisterAllocation 函数按照 original list 里的顺序(起始位置的升序)对 live interval 进行扫描,每一次扫描是对一个新的 live interval 执行一系列操作。我们可以在此函数中发现 active list 的使用,该 list 用于存放当前程序点(即正在扫描的 live interval 起始位置处指令后的程序点)分配了寄存器的 live interval,这些 interval 是互相干涉的。

    每当开始扫描一个新的 live interval 时,算法会调用 ExpireOldInterval 函数,从头到尾遍历 active list。一旦发现 active list 里有哪个 interval 的结束位置是在新扫描的 interval 开始位置之后,就把它从 active list 中移除,并把它所占有的寄存器回收到寄存器池中。这说明这两个 interval 不相交,分配到同一个物理寄存器也不打紧。

    显然,active list 的大小最多等同于可分配寄存器的总数。在最坏的情况下,当新一轮扫描开始时,active list 的大小可能已经达到了最大。若此时新扫描的 live interval 的起始位置在 active list 中所有 interval 的结束位置后,即它与之前所有的 interval 相交,此时寄存器就不够用了,必须溢出到内存中。溢出的 live interval 可以是 active list 里的任意一个 interval,也可以是新扫描的 interval,具体如何抉择就看分配器的设计者如何选择启发式了。在 Poletto 的论文里,作为溢出选择的是结束位置距离当前程序点最远的 live interval(图中的 last interval),或者当前扫描的 live interval。如果是当前的 interval 结束得更迟,则直接给它分配一个栈槽;否则,把分配给 last interval 的寄存器分配给当前的 interval,并把 last interval 溢出到栈槽中。

    选择这样的启发式的原因不难理解:如果把这样的 interval 溢出了,剩下的 interval 的剩余干涉期较短,更容易被移出 active list,从而更容易回收寄存器。根据 Poletto 论文的说法,这一启发式效果非常好。

    3.4 例子

    可以参照文献 Register Allocation 中的实例来思考线性扫描算法,该文档给出的例子十分详细。

    4 线性扫描算法的问题

    根据 LLVM 官方的说法,线性扫描这样简单的一个算法,工作效果却“令人惊奇”的好。为什么说它简单?从前面的介绍不难发现,线性扫描里的 live interval 概念是十分粗糙的,这个概念忽视了区间内所有变量并不活跃的 hole,这样的设计导致算法十分简洁。正因如此,我们才可以进一步“压榨”此算法,得到质量更好的代码,这也是 LLVM 后来提出 Greedy 寄存器分配算法的原因。

    此外,线性扫描在做了分配后,还要依赖后面的虚拟寄存器重写器(rewriter)来清除代码。理论上,重写器只需要把 MIR 中的虚拟寄存器替换成分配到的物理寄存器即可。然而,由于线性扫描可能会做一些“愚蠢”的事情(例如两次把一个栈槽中的值加载到同一个寄存器中),重写器必须采取一些技巧来解决这些问题。这导致代码极其难以维护,且代价极其高昂,线性扫描算法有一半的时间都花在重写器中。新式的 Greedy 寄存器分配算法尽可能避免了这类问题,从而使得重写器代码干净简洁,只需要实现重写虚拟寄存器的功能,不需要搞定那些“愚蠢”的问题。

    其实,上面那些“愚蠢”问题的出现很大一部分是因为线性扫描不支持变量生命期的拆分,这也是新式寄存器分配算法所解决的问题。至于 Basic/Greedy 等寄存器分配算法是如何运行的,这就是我们后面系列的内容。

    5 参考文献

    [1] Register Allocation in LLVM 3.0
    [2] Hacker News - Register Allocation
    [3] Linear Scan Register Allocation
    [4] Register Allocation
    [5] 知乎 - 寄存器分配问题?XlousZeng 的回答

    展开全文
  • 本文档是基于 LLVM 的寄存器分配系列科研笔记第一篇,以一个 C 语言程序为主干介绍 LLVM 在寄存器分配前做的一些主要工作,分析在寄存器分配前期可能的写操作来源,并记录了我在研究 LLVM 后端中 SSA 形式的中间表示...

    1 背景介绍

    本文档是基于 LLVM 的寄存器分配系列科研笔记第一篇,以一个 C 语言程序为主干介绍 LLVM 在寄存器分配前做的一些主要工作,分析在寄存器分配前期可能的写操作来源,并记录了我在研究 LLVM 后端中 SSA 形式的中间表示时的一些想法(私货)。


    2 进入寄存器分配

    我们以下述 C 语言源码为例开始本文的说明:

    int foo(int a, int b, int e) {
      b = a + e;
      a = b * e;
      e = a * b;
      b = a * e;
      b = b * e;
      return b;
    }
    

    根据我的上一篇博文 LLVM SSA 介绍 可知,经过 mem2reg pass 后,最初 Clang 默认生成的 Alloca/Load/Store 形式的 IR 被转化成了完全 SSA 形式的 IR。这时,源变量在 SSA IR 中已经有了许多重命名,如下述代码所示,%add、%mul2、%mul3 都是源程序变量(以下简称源变量)b 的重命名:

    define i32 @foo(i32 %a, i32 %b, i32 %e) #0 {
    entry:
      %add = add nsw i32 %a, %e
      %mul = mul nsw i32 %add, %e
      %mul1 = mul nsw i32 %mul, %add
      %mul2 = mul nsw i32 %mul, %mul1
      %mul3 = mul nsw i32 %mul2, %mul1
      ret i32 %mul3
    }
    

    这个结果是很直观的,SSA IR 中的每一条指令都与源程序中每一条语句一一对应。在此 SSA IR 里,所有重命名都是虚拟寄存器,这些重命名在后面的 MIR 中是以 <%vreg + idx> (%vreg0、%vreg1…) 的虚拟寄存器形式表示的。但是,并不是 SSA IR 中所有的重命名都会在 MIR 中生成相应的<%vreg + idx>。我们可以分析刚刚进入寄存器分配时此程序的 MIR,通过给 llc 添加 -print-after=livevars 选项(给 llc 加上 -help-hidden 选项可以查看 -print-after 支持的所有 pass 名称)可以观察做了活变量分析后的 MIR,此阶段的 MIR 尚未做 PHI 指令消除和二地址转换:

    Frame Objects:
      fi#-3: size=4, align=4, fixed, at location [SP+12]
      fi#-2: size=4, align=4, fixed, at location [SP+8]
      fi#-1: size=4, align=4, fixed, at location [SP+4]
    
    BB#0: derived from LLVM BB %entry
            %vreg0<def> = MOV32rm <fi#-3>, 1, %noreg, 0, %noreg; mem:LD4[FixedStack-3] GR32:%vreg0
            %vreg1<def,tied1> = ADD32rm %vreg0<tied0>, <fi#-1>, 1, %noreg, 0, %noreg, %EFLAGS<imp-def,dead>; mem:LD4[FixedStack-1] GR32:%vreg1,%vreg0
            %vreg2<def,tied1> = IMUL32rr %vreg1<tied0>, %vreg0<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg2,%vreg1,%vreg0
            %vreg3<def,tied1> = IMUL32rr %vreg2<tied0>, %vreg1<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg2,%vreg1
            %vreg6<def,tied1> = IMUL32rr %vreg3<kill,tied0>, %vreg3, %EFLAGS<imp-def,dead>; GR32:%vreg6,%vreg3,%vreg3
            %vreg5<def,tied1> = IMUL32rr %vreg2<kill,tied0>, %vreg6<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg5,%vreg2,%vreg6
            %EAX<def> = COPY %vreg5<kill>; GR32:%vreg5
            RETL %EAX<kill>
    

    显然,我们注意到在该 MIR 中,最后两条 IMUL32rr 语句和源程序的 mul 运算的操作数并不一致。这是后端在代码生成过程中做的特殊处理(即优化,vreg4 可能就在这个过程中被优化掉了?),最终返回的结果是没有问题的。从这两句代码可以看出,MIR 里的某些虚拟寄存器可能并不对应任何一个源变量,它是用于存放中间变量的。还有,MIR 里的某些虚拟寄存器可能与 SSA IR 中的重命名(虚拟寄存器)也不对应,如倒数第二条 IMUL32rr 指令中的 %vreg6 在 SSA IR 中就找不到对应的重命名。

    基于这种观察,我们知道在寄存器分配阶段要以虚拟寄存器为单位进行思考,而不再把思维局限在源程序中,不再按照分析源程序的思维来分析寄存器分配中的问题。虽然 MIR 与 SSA IR 中的虚拟寄存器并不对应,但 MIR 与 SSA IR 有个共同点,就是他们都是 SSA 形式的,每个虚拟寄存器仅仅进行了一次赋值。

    注释:关于活跃分析,LLVM 里的活跃分析与我们平时在教材里看到的不完全一样。在大多数编译原理教材里,活跃分析的内容是直接以源程序中的变量为基础进行分析的。但是在 LLVM 里却不是这样,LLVM 里的活跃分析是后端的工作,换句话说,是基于 LLVM IR 做的。因此,LLVM 收集到的活跃信息来源于所有的虚拟寄存器和少部分物理寄存器,后面的 LiveInterval 的计算便依赖于此活跃信息。由于 LLVM IR 采用的 SSA 形式,所有虚拟寄存器都是单一赋值,从而导致 LLVM 里的活跃分析简单而高效。

    3 寄存器分配的准备工作

    下面开始讨论活跃分析后的流程,最关键的两个 pass 就是 PHI 指令消除(PHIElimination pass)和二地址转换(TwoAddressInstructionPass pass),这两个 pass 引入了大量 COPY 指令。当然,在执行这两个 pass 之前,编译器还要收集一些静态信息,比如支配结点树(MachineDominatorTree)和循环信息(MachineLoopInfo)等。

    3.1 PHI 消除

    SSA 解构阶段是做寄存器分配时的一个重要转换过程。虽然 SSA 形式简化了作用在程序控制流图上的许多分析,但一般的指令集并没有包含 PHI 指令的实现。因此,为了得到可执行的代码,编译器必须在不改变语义的前提下用其他指令来取代 PHI 指令。

    考虑如下场景:有三个基本块 B0, B1, B2,其中,B1、B2 是 B0 的前驱,即 B1->B0,B2->B0。如果 B1、B2 中都有对同一变量 x 的定义 x1、x2,那么 B0 中就需要插入 PHI 函数来决定选取哪个定义:x3 = PHI(x1, x2)。

    B1:						B2:
        ...                     ...
    	x1 = a + b;             x2 = a - b;
    	...                     ...
    	
    B0:
        ...
    	x3 = PHI(x1, x2)
    	...
    

    由于目前的硬件平台都没有支持 PHI 函数的指令,因此这个工作要交给编译器来做。在 LLVM 中,是通过插入复制指令(COPY Instruction)来消除 PHI 函数的,这一过程又叫做 Lower PHI。我们对上面场景中的 PHI 进行 lower 可以得到下面这样的基本块:

    B1:						B2:
        ...                     ...
    	x1 = a + b;             x2 = a - b;
    	x0 = x1; (COPY)         x0 = x2; (COPY)
    	...                     ...
    	
    B0:
        ...
    	x3 = x0;
    	...
    

    3.2 二地址转换

    除了很少一部分指令外(如函数调用),LLVM 机器码指令都是三地址指令。也就是说,每条指令最多只能定义一个寄存器,并且最多使用两个寄存器。然而,很多架构普遍使用了双地址指令。在这种情况下,发生定义的寄存器同时也是被使用的寄存器之一。举个例子,X86 中类似“ADD %EAX, %EBX”的指令实际上等同于“%EAX = %EAX + %EBX”。

    为了正确生成代码,LLVM 必须把 LLVM 中间表示中的三地址指令转化为真正的双地址指令。为此,LLVM 提供了 TwoAddressInstructionPass pass,该 pass 必须在做寄存器分配之前运行。在它运行完毕后,产出的代码就不再是 SSA 形式了。以下述场景为例,三地址指令“%a = ADD %b %c”被转化为下面的两条指令:

    %a = MOVE %b
    %a = ADD %a %c
    

    上述代码块的第二条指令被表示为“ADD %a[def/use] %c”这样的形式,指令既使用了寄存器操作数 %a,又定义了它。本文的例子中的 COPY 指令便是在二地址转换的过程中引入的,可以给 llc 加上 -debug-only=twoaddrinstr 选项来观察该过程。

    注释:对于X86等采用二地址指令的架构才需要执行本步骤,对于MIPS等采用三地址指令的架构则不需要本步骤。

    3.3 回归例子

    上述过程做完后,编译器就可以在此时的 MIR 基础上计算 LiveInterval 了。我们来观察做了 PHI 消除和二地址转换过程后的 MIR,这也是打开 -debug-only=regalloc 选项后最先输出的 MIR,如下:

    Frame Objects:
      fi#-3: size=4, align=4, fixed, at location [SP+12]
      fi#-2: size=4, align=4, fixed, at location [SP+8]
      fi#-1: size=4, align=4, fixed, at location [SP+4]
    
    0B      BB#0: derived from LLVM BB %entry
    16B             %vreg0<def> = MOV32rm <fi#-3>, 1, %noreg, 0, %noreg; mem:LD4[FixedStack-3] GR32:%vreg0
    32B             %vreg7<def> = MOV32rm <fi#-1>, 1, %noreg, 0, %noreg; mem:LD4[FixedStack-1] GR32:%vreg7
    48B             %vreg1<def> = COPY %vreg7; GR32:%vreg1,%vreg7
    64B             %vreg1<def,tied1> = ADD32rr %vreg1<tied0>, %vreg0, %EFLAGS<imp-def,dead>; GR32:%vreg1,%vreg0
    80B             %vreg2<def> = COPY %vreg0; GR32:%vreg2,%vreg0
    96B             %vreg2<def,tied1> = IMUL32rr %vreg2<tied0>, %vreg1, %EFLAGS<imp-def,dead>; GR32:%vreg2,%vreg1
    112B            %vreg3<def> = COPY %vreg1; GR32:%vreg3,%vreg1
    128B            %vreg3<def,tied1> = IMUL32rr %vreg3<tied0>, %vreg2, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg2
    144B            %vreg6<def> = COPY %vreg3; GR32:%vreg6,%vreg3
    160B            %vreg6<def,tied1> = IMUL32rr %vreg6<tied0>, %vreg6, %EFLAGS<imp-def,dead>; GR32:%vreg6
    176B            %vreg5<def> = COPY %vreg6; GR32:%vreg5,%vreg6
    192B            %vreg5<def,tied1> = IMUL32rr %vreg5<tied0>, %vreg2, %EFLAGS<imp-def,dead>; GR32:%vreg5,%vreg2
    208B            %EAX<def> = COPY %vreg5; GR32:%vreg5
    224B            RETL %EAX<kill>
    

    把上述 MIR 中各虚拟寄存器的 LiveInterval 打印出来:

    %vreg0 [16r,80r:0)  0@16r
    %vreg1 [48r,64r:0)[64r,112r:1)  0@48r 1@64r
    %vreg2 [80r,96r:0)[96r,192r:1)  0@80r 1@96r
    %vreg3 [112r,128r:0)[128r,144r:1)  0@112r 1@128r
    %vreg5 [176r,192r:0)[192r,208r:1)  0@176r 1@192r
    %vreg6 [144r,160r:0)[160r,176r:1)  0@144r 1@160r
    %vreg7 [32r,48r:0)  0@32r
    

    这里,每一行代表一个 LiveInterval,也就是一个虚拟寄存器。显然,由于虚拟寄存器与源变量没有关联,LiveInterval 与源变量也没有关联。现在,我们从“虚拟寄存器 / LiveInterval”的角度来考虑问题,而不是从源程序的角度来考虑问题。在上面的 LiveInlterval 列表中,最右侧的信息给出的是该虚拟寄存器的定义点(def point),而不是源变量的定义点(def point)。

    要注意的是,在寄存器分配初始阶段,每个寄存器的定义点除了 COPY 赋值之外仅仅包含了一次赋值。这个不难理解,因为在 PHI 消除之前的 MIR 就是 SSA 形式的,每个虚拟寄存器最多只包含一次赋值。而 PHI 消除和二地址转换过程又各自引入了 COPY 指令,添加了几次赋值。由于本例不存在 PHI 指令,故上述赋值中只有二地址转换的过程会引入一次赋值操作,因此各个虚拟寄存器最多经历了两次赋值。

    3.4 合并

    从上面的 MIR 中,我们可以发现在源代码如此简短的情况下仍然生成了大量的 COPY,从而引入了大量的虚拟寄存器,这对后续的物理寄存器分配带来了很大的压力。由于 COPY 指令的特殊性(它连接的两个虚拟寄存器的值相同),我们可以在一些特殊情况下合并 LiveInterval 的生命期(live range),这个过程叫做合并(coalesce)。以上面的 %vreg0 和 %vreg2 为例:

    %vreg0 [16r,80r:0)  0@16r
    %vreg2 [80r,96r:0)[96r,192r:1)  0@80r 1@96r
    

    可以发现,这两个虚拟寄存器的生命期互不重叠,恰好错开了,同时它们生命期的交界处是 COPY 指令。显然,这样的两个寄存器生命期是可以进行合并的,这样可以把交界处的COPY指令消除掉。在所有合并工作完成后,源程序中的 LiveInterval 为:

    %vreg2 [16r,96r:0)[96r,192r:1)  0@16r 1@96r
    %vreg3 [32r,64r:2)[64r,128r:0)[128r,160r:1)[160r,192r:3)[192r,208r:4)  0@64r 1@128r 2@32r 3@160r 4@192r
    

    最终的寄存器分配是在这种做了合并后的 LiveInterval 上做的,这个时候的虚拟寄存器经过了一系列 pass 的处理,和源变量可以说是天壤之别了,基本没有什么联系。在虚拟寄存器发生 spill 时,栈槽上经受的操作是该虚拟寄存器本身会经受的操作,并不唯一对应哪个源变量。或者说,各个源变量都有可能在栈槽上发生写操作。

    要注意的是,在消除了 COPY 指令之后,MIR 的 SSA 结构已经被彻底破坏掉了(其实引入 COPY 时就已经不是 SSA 了,但是不是很明显)。因此,最终做寄存器分配时的虚拟寄存器并非 SSA 形式,可能会承担多次写操作。以这个例子为例,其最终进行寄存器分配的MIR如下:

    Frame Objects:
      fi#-3: size=4, align=4, fixed, at location [SP+12]
      fi#-2: size=4, align=4, fixed, at location [SP+8]
      fi#-1: size=4, align=4, fixed, at location [SP+4]
    
    0B      BB#0: derived from LLVM BB %entry
    16B             %vreg2<def> = MOV32rm <fi#-3>, 1, %noreg, 0, %noreg; mem:LD4[FixedStack-3] GR32:%vreg2
    32B             %vreg3<def> = MOV32rm <fi#-1>, 1, %noreg, 0, %noreg; mem:LD4[FixedStack-1] GR32:%vreg3
    64B             %vreg3<def,tied1> = ADD32rr %vreg3<tied0>, %vreg2, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg2
    96B             %vreg2<def,tied1> = IMUL32rr %vreg2<tied0>, %vreg3, %EFLAGS<imp-def,dead>; GR32:%vreg2,%vreg3
    128B            %vreg3<def,tied1> = IMUL32rr %vreg3<tied0>, %vreg2, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg2
    160B            %vreg3<def,tied1> = IMUL32rr %vreg3<tied0>, %vreg3, %EFLAGS<imp-def,dead>; GR32:%vreg3
    192B            %vreg3<def,tied1> = IMUL32rr %vreg3<tied0>, %vreg2, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg2
    208B            %EAX<def> = COPY %vreg3; GR32:%vreg3
    224B            RETL %EAX<kill>
    

    不难发现,此 MIR 中 %vreg2 和 %vreg3 都经受了多次写操作。最终做分配的 LiveIntervals 求出来之后,LLVM 会执行一些 pass,用于给接下来的寄存器分配做一些准备工作,例如执行MachineBlockFrequencyInfo pass 用于获取各个基本块频率、执行 VirtRegMap pass 用于设置一些虚拟寄存器的映射关系(Virt2PhysMap、Virt2StackSlotMap 等),接下来就可以执行寄存器分配的 pass 了。

    4 题外话

    我在查阅 LLVM 寄存器分配的 官方文档 时看到了这样一段话:

    Live Intervals are the ranges (intervals) where a variable is live. They are used by some register allocator passes to determine if two or more virtual registers which require the same physical register are live at the same point in the program (i.e., they conflict). When this situation occurs, one virtual register must be spilled.

    我最开始以为虚拟寄存器和物理寄存器是一对一的关系,即在一个虚拟寄存器的 live interval 范围内(包括 hole 在内),相应的物理寄存器只能被它占有。但是看这段话的意思,虚拟寄存器和物理寄存器是存在多对一的关系的,即多个虚拟寄存器可以分配给同一个物理寄存器,只要他们的 live interval 不相交。这个映射关系,我尚未能在代码中发现,还需要继续研究。

    根据资料 Register Allocation,设置这种多对一关系的原因是为了进一步压榨寄存器的性能。例如,假设有一变量 x 的生命期为 [16, 80)[196, 208),称区间 [16, 208) 为 live range,区间 [16, 80) 和 [196, 208) 为 segment,区间 [80, 196) 为 hole。按照我最开始理解的虚拟寄存器与物理寄存器的一一对应关系,在整个 live range 内物理寄存器都被 x 霸占了。因为 hole 的存在,这就导致了 hole 期间物理寄存器不能被充分使用。其实 hole 期间物理寄存器是可以被其他变量使用的,只要它的生命期与 x 不相交,如变量 y: [80, 196)。

    5 参考资料

    [1] Register Allocation
    [2] How To Write An LLVM Register Allocator
    [3] The LLVM Target-Independent Code Generator
    [4] Linear Scan

    展开全文
  • 本系列的前两篇博文分别介绍了 LLVM 在做寄存器分配前的准备工作和线性扫描算法的理论基础,有了这些背景知识后,就可以开始进入 LLVM 中真实的寄存器分配器了。在 LLVM3.0 中,新提出了两个寄存器分配器:basic/...

    1 背景介绍

    本系列的前两篇博文分别介绍了 LLVM 在做寄存器分配前的准备工作和线性扫描算法的理论基础,有了这些背景知识后,就可以开始进入 LLVM 中真实的寄存器分配器了。在 LLVM3.0 中,新提出了两个寄存器分配器:basic/greedy 分配器,它们的核心算法都是线性扫描算法的变种。其中,greedy 分配器是新版本 LLVM 默认的寄存器分配器,而 basic 分配器可以理解为一个简化版的 greedy 分配器。因此,这两个分配器的中心思想相差不大,所使用的关键数据结构也没什么区别。所以,本篇博文先介绍 basic 分配器,为后续学习 greedy 分配器打下基础。

    2 basic 分配算法与线性扫描算法

    事实上,basic 分配器生成的代码质量与线性扫描算法相差无几。同时,为了提高代码质量,basic 分配器也依赖虚拟寄存器重写器(rewriter)来清除冗余代码。可以说,basic 分配算法与线性扫描算法相比并没有特别大的提高。那么,LLVM 为何要提供此分配器呢?其实,我们可以把 basic 分配器理解为一个实验性质的分配器,LLVM 提出 basic 分配器主要为了用它来测试新式分配框架的性能。因此,basic 分配器实现得十分简单,只是把大体的分配框架实现出来,并没有充分压榨分配算法。相对而言,默认的 greedy 分配器才是成熟的寄存器分配器,充分压榨了分配算法的每一处潜能。两种分配器的基本框架如下图所示(其中左图为 basic 分配器,右图为 greedy 分配器):

    ![allocator](https://img-blog.csdn.net/20180127194748952?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk2NzQzNTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
    不难发现,两种分配器的框架都是基于优先级队列(priority queues)和生命期联合体(live interval unions)的,这两个数据结构是新分配算法中用以区别线性扫描算法的最关键部分。从之前的博文 [LLVM里的寄存器分配 - 线性扫描算法(二)](http://blog.csdn.net/qq_29674357/article/details/79110417) 中我们知道,original list 和 active list 是线性扫描算法的核心数据结构。其中,original list 决定了虚拟寄存器的分配顺序(按照 interval 起始位置的升序),而 active list 则指导了线性扫描算法的干涉检查(interference check)。新分配算法正是在这两个关键步骤上做出改变,priority queues 给算法指定了新的分配顺序,而基于 live interval unions 我们则可以提出一种高效而全面的干涉检查方法。

    3 basic 分配器详解

    LLVM 给各个寄存器分配器提供了一套公用的接口,即 RegAllocBase 类。在这个类里,寄存器分配器的基本框架已经构造完成了,我们只需要重载部分函数即可以实现想要的寄存器分配器。一个寄存器分配器必须做以下两个工作:第一,该分配器必须覆盖 selectOrSplit 方法,我们可以在这里给分配器加各种有趣的启发式;第二,该分配器必须覆盖 enqueue/dequeue 方法,用于提供自己的寄存器分配顺序。下面,开始介绍 basic 寄存器中所做的这两样工作。

    3.1 priority queues 与分配顺序

    在线性扫描算法中,active list 决定了扫描顺序必须是线性的,即按 interval 起始位置的升序扫描。这种分配顺序显然是有问题的,它没有考虑到溢出的代价。考虑这样一种情况,假设我们现在有一个 active list,所有寄存器都分配给里面的 interval 了,如若下一次扫描到的 interval 溢出代价很大,且与 active list 中所有的 interval 相交。那么,当该 interval 溢出时,会对性能造成很大的影响,basic 分配器中通过引入 priority queues 来解决这个问题。

    由于 basic 分配器用 live interval union 来替代 active list,不管我们按照什么样的因素来构造 priority queues,这种数据结构都可以正常工作。在 basic 分配器中,为了充分减少溢出对性能造成的影响,priority queues 是按照溢出权重(spill weight)来排序的。也就是说,每次分配物理寄存器时,优先分配给那些溢出权重大的 interval。这类 interval 的读写较为频繁,把它们溢出到内存中后对性能的影响较大,因此要优先分配到物理寄存器中。

    注释:这里的溢出权重是静态分析的典型例子,一个虚拟寄存器的溢出权重是通过结合读写次数和基本块频率等因素计算出来的。博文 LLVM 基本块频率术语 介绍了基本块频率的计算方法。

    要说明的是,这里所说的 priority queues 并不是真正的队列。实际上在 LLVM 里,priority queues 是由 interval 构成的最大堆。最大堆又叫大顶堆,堆顶 interval 的溢出权重最大。因此,每当要选择一个新的 interval 来分配寄存器时,都会弹出堆顶的 interval,此 interval 在当前溢出代价最高。

    3.2 live interval union 与干涉检查

    在上一篇博文 LLVM里的寄存器分配 - 线性扫描算法(二) 里我们说过,线性扫描里的 interval 概念十分粗糙,它忽视了 interval 区间内所有变量并不活跃的 hole,live interval union 的提出就是为了解决这个问题。我们借助一个例子来理解 live interval union,假设有两个 interval 如下所示:

    LiveInterval1: [16,64), [256,512)
    LiveInterval2: [64,160), [512,1024)
    

    在线性扫描算法里,这样的两个 interval 需要分配两个物理寄存器。因为在算法眼中,它们的实际生命期是:

    LiveInterval1: [16,512)
    LiveInterval2: [64,1024)
    

    显然,这样的两个 interval 是相交的。但是如果我们仔细研究,可以发现,这个例子里的相交其实是“假相交”,它们相交的地方均位于变量并不活跃的 hole 中。从 live interval union 的角度来说,可以给上述两个 interval 分配同一个物理寄存器:

    LiveIntervalUnion: [16,64), [64,160), [256,512), [512,1024)
    

    显然,这两个 interval 其实并不相交,这就是 live interval union 的基本思想,即可以充分利用好 interval 各段生命期之间的 hole。在寄存器分配阶段,我们可以把一个 live interval union 看作一个物理寄存器,此二者是一一对应的关系。当我们判断是否可以给某个 interval 分配某个物理寄存器时,就需要检查该 interval 的生命期是否与此物理寄存器的生命期相交。若相交,则继续分配下一个物理寄存器直至溢出;若不相交,则可以给该 interval 分配此物理寄存器,同时把该 interval 的生命期插入物理寄存器的生命期中。

    下面是基于 live interval union 的干涉检查代码。要说明的是,由于部分架构存在 register unit 等复杂结构,导致寄存器分配过程中出现了多种不同类型的干涉,如 IK_RegMask、IK_RegUnit。这里刨去不同体系结构带来的差异,只分析最主要的 IK_VirtReg,即虚拟寄存器与物理寄存器之间的干涉检查:

    unsigned LiveIntervalUnion::Query::
    collectInterferingVRegs(unsigned MaxInterferingRegs) {
      // Fast path return if we already have the desired information.
      if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
        return InterferingVRegs.size();
    
      // Set up iterators on the first call.
      if (!CheckedFirstInterference) {
        CheckedFirstInterference = true;
    
        // Quickly skip interference check for empty sets.
        if (VirtReg->empty() || LiveUnion->empty()) {
          SeenAllInterferences = true;
          return 0;
        }
    
        // In most cases, the union will start before VirtReg.
        VirtRegI = VirtReg->begin();
        LiveUnionI.setMap(LiveUnion->getMap());
        LiveUnionI.find(VirtRegI->start);
      }
    
      LiveInterval::iterator VirtRegEnd = VirtReg->end();
      LiveInterval *RecentReg = nullptr;
      while (LiveUnionI.valid()) {
        assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg");
    
        // Check for overlapping interference.
        while (VirtRegI->start < LiveUnionI.stop() &&
               VirtRegI->end > LiveUnionI.start()) {
          // This is an overlap, record the interfering register.
          LiveInterval *VReg = LiveUnionI.value();
          if (VReg != RecentReg && !isSeenInterference(VReg)) {
            RecentReg = VReg;
            InterferingVRegs.push_back(VReg);
            if (InterferingVRegs.size() >= MaxInterferingRegs)
              return InterferingVRegs.size();
          }
          // This LiveUnion segment is no longer interesting.
          if (!(++LiveUnionI).valid()) {
            SeenAllInterferences = true;
            return InterferingVRegs.size();
          }
        }
    
        // The iterators are now not overlapping, LiveUnionI has been advanced
        // beyond VirtRegI.
        assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap");
    
        // Advance the iterator that ends first.
        VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start());
        if (VirtRegI == VirtRegEnd)
          break;
    
        // Detect overlap, handle above.
        if (VirtRegI->start < LiveUnionI.stop())
          continue;
    
        // Still not overlapping. Catch up LiveUnionI.
        LiveUnionI.advanceTo(VirtRegI->start);
      }
      SeenAllInterferences = true;
      return InterferingVRegs.size();
    }
    

    在上面的代码中,我们需要判断 VirtReg 和 LiveUnion 之间的相交关系。其中, VirtRegI 是 VirtReg 中 segment 的迭代,初始值为 VirtReg 中第一段 segment;LiveUnionI 是 LiveUnion 中部分 segment 的迭代,初始值是第一段 stop 点大于 VirtRegI 起始位置的 segment。注意,在 VirtReg 和 LiveUnion 中,segment 的端点位置表示方法并不相同。在 VirtReg 中,使用 start/end 来表示起始/终止位置,LiveUnion 中则使用 start()/stop() 来表示起始/终止位置。

    注释:上述代码中,干涉条件为:VirtRegI->start < LiveUnionI.stop() && VirtRegI->end > LiveUnionI.start();LiveUnionI 的迭代条件为:VirtRegI->start >= LiveUnionI.stop()

    我们通过几个实例来说明上述干涉算法的流程:

    1. VirtReg: [16,32), [96,112) + LiveUnion: [48,96), [128, 256)
    迭代过程如下:
    a. VirtRegI = [16,32), LiveUnion = [48,96) 不满足干涉条件,迭代 VirtRegI 得 [96,112),满足 LiveUnionI 的迭代条件,故也要迭代 LiveUnionI;
    b. VirtRegI = [96,112), LiveUnion = [128,256) 不满足干涉条件,迭代 VirtRegI 到结尾,退出干涉检查函数,检查结果为不相交。

    2. VirtReg: [96,112), [128, 160) + LiveUnion: [16,32), [48,96), [128, 256)
    迭代过程如下:
    a. VirtReg = [96,112), LiveUnion = [128,256) 不满足干涉条件,迭代 VirtRegI 得 [128,160),不满足 LiveUnionI 的迭代条件,故无需迭代 LiveUnionI;
    b. VirtRegI = [128,160), LiveUnion = [128,256) 满足干涉条件,把当前的 LiveUnionI 对应的 LiveInterval 加入干涉集 InterferingVRegs,检查结果为发生相交。

    3. VirtReg: [96,112), [160,320) + LiveUnion: [16,32), [48,96), [128, 256)
    迭代过程如下:
    a. VirtReg = [96,112), LiveUnion = [128,256) 不满足干涉条件,迭代 VirtRegI 得 [128,160),不满足 LiveUnionI 的迭代条件,故无需迭代 LiveUnionI;
    b. VirtReg = [160,320), LiveUnion = [128,256) 满足干涉条件,检查结果为相交。

    4. VirtReg: [96,112), [256,320) + LiveUnion: [16,32), [48,96), [128, 256)
    迭代过程如下:
    a. VirtReg = [96,112), LiveUnion = [128,256) 不满足干涉条件,迭代 VirtRegI 得 [256,320),满足 LiveUnionI 的迭代条件,故迭代 LiveUnionI;
    b. 由于当前的 segment 是 LiveUnionI 最后一个 segment,迭代后的 LiveUnionI 应该是“无效的”,即不满足循环条件 LiveUnionI.valid(),此时返回结果 InterferingVRegs.size() 为空,即检查结果为不相交。

    3.3 selectOrSplit()

    这个函数决定了各个寄存器分配器的根本差异。当 priority queues 构造好后,每从中弹出一个 interval,就调用一次 selectOrSplit(),寄存器分配器的主要工作就在这里完成。basic 分配器中要完成的工作如下:

    unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
                                    SmallVectorImpl<unsigned> &SplitVRegs) {
      // Populate a list of physical register spill candidates.
      SmallVector<unsigned, 8> PhysRegSpillCands;
    
      // Check for an available register in this class.
      AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
      while (unsigned PhysReg = Order.next()) {
        // Check for interference in PhysReg
        switch (Matrix->checkInterference(VirtReg, PhysReg)) {
        case LiveRegMatrix::IK_Free:
          // PhysReg is available, allocate it.
          return PhysReg;
    
        case LiveRegMatrix::IK_VirtReg:
          // Only virtual registers in the way, we may be able to spill them.
          PhysRegSpillCands.push_back(PhysReg);
          continue;
    
        default:
          // RegMask or RegUnit interference.
          continue;
        }
      }
    
      // Try to spill another interfering reg with less spill weight.
      for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
           PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
        if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
          continue;
    
        assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
               "Interference after spill.");
        // Tell the caller to allocate to this newly freed physical register.
        return *PhysRegI;
      }
    
      // No other spill candidates were found, so spill the current VirtReg.
      DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
      if (!VirtReg.isSpillable())
        return ~0u;
      LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM);
      spiller().spill(LRE);
    
      // The live virtual register requesting allocation was spilled, so tell
      // the caller not to allocate anything during this round.
      return 0;
    }
    

    从上面的代码可以看出,分配初期首先会为每种寄存器类(register class)构造一个待分配的物理寄存器序列。每次分配时,从序列中选出一个物理寄存器,并判断当前 interval 与之是否相交。若不相交,直接分配该物理寄存器;若相交,则把该物理寄存器加入溢出候选列表(PhysRegSpillCands)。如果我们从后续待分配的物理寄存器序列中找到了可以分配的物理寄存器,函数会直接退出,此列表作废;如果物理寄存器序列遍历完毕还未找到可以分配的物理寄存器,我们会把此过程中与 interval 相交的物理寄存器均加入溢出候选列表,在后面的 for 循环里找到逐出到内存中的物理寄存器。

    要说明的是,在溢出候选列表和当前 interval 中,真正溢出的是溢出权重最小的。for 循环里调用的 spillInterferences 函数会比较当前 interval 的溢出权重和溢出候选列表中所有物理寄存器上存放的 interval 的溢出权重,除非物理寄存器上存储的所有 interval 的溢出权重都小于当前 interval 的溢出权重,否则不会溢出物理寄存器。由于 basic 分配器中先分配的总是溢出权重最大的 interval,所以已经分配到物理寄存器上的 interval 的溢出权重一定大于当前 interval 的溢出权重。也就是说,basic 分配器中,被溢出的总是当前的 interval。

    展开全文
  • 图染色法寄存器分配

    2014-03-09 11:49:22
    图染色法的寄存器分配,用于编译的代码优化阶段
  • 本文提出了一种动态寄存器分配器,该分配器可动态检测并利用群集VLIW处理器的生存期漏洞。生存期漏洞是一个变量不包含有效值的时间间隔。可以将保存生存期漏洞的寄存器分配给有效范围适合生存期漏洞的另一个变量,...
  • 寄存器分配,是通过将程序变量尽可能地分配到寄存器,从而提高程序执行速度的一种方法。寄存器是编译器优化中最为重要的问题之一(好的寄存器分配能够提高程序执行速度超过250%);也是编译器理论中最热点的研究领域...
  • 常用的寄存器分配算法将寄存器分配看作图着色问题,时间复杂度是O(n^4),不适用于Java的JIT编译。原来的JVM里是根据一些本地启发式规则来分配寄存器,效果不太好,Java 6中使用的线性扫描寄存器算法能够达到与图颜色...
  • RA, 寄存器分配

    千次阅读 2016-05-26 17:21:20
    寄存器分配1. 如何计算D-U链(1) 首先遍历整个routine,保存所有def值; 问题: 你如何去保存这些def值呢?要保证能快速的得到每个def值,因为每一 个 def 值不仅仅只包含dst寄存器号,还包括这条指令,以及其它...
  • BWDSP是一款自主设计的国产VLIW(超长指令字)数字信号处理器,支持SIMD技术,其SIMD指令可以在4个宏上同时执行4个32位计算,对寄存器使用有特殊规则,Open64编译器的寄存器分配策略并不适用于这种规则。本文对BWDSP...
  • 为了提高综合后电路的可测性,提出了一种面向电路可测性的寄存器分配方案。该方案首先从已调度的数据流图着手,建立了一种可用于高层次综合的行为级可测性分析方法:对算子模块的门级实现进行门级可测性分析,并进而...
  • 编译器后端,寄存器分配算法

    千次阅读 2017-01-19 10:40:03
    寄存器分配,是通过将程序变量尽可能地分配到寄存器,从而提高程序执行速度的一种方法。寄存器是编译器优化中最为重要的问题之一(好的寄存器分配能够提高程序执行速度超过250%);也是编译器理论中最热点的研究领域...
  • 提出使用网表示可分配寄存器对象,通过对网的活跃性数据流分析,构造网的冲突图。与变量冲突图相比,将基于变量的节点分裂成基于网的节点,将同一变量的冲突关系分摊到多个网上,虽增加冲突图节点数量,但降低节点...
  • 适用于JavaScript的Linearscan寄存器分配器 原料药 // Declare some instructions var linearscan = require ( 'linearscan' ) ; function gp ( kind , value ) { return { kind : kind , group : 'gp' , value : ...
  • 提出了很多结合技术使得指令调度与寄存器分配之间进行一些信息交互,在没有引入过多溢出代码的情况下提高了指令级并行度,从而提高了性能。按照算法的特征分类介绍了几种影响力较大的算法,同时作了简单的评价和效果...
  • 经典的基于图着色模型的寄存器分配: 1、如果变量(在指令/语句序列中,或称程序“基本块”?)不再被use(def也是use),则它dead 2、否则变量live(活着) 3、如果2个变量在一个block/program中都是live,则不...
  • 51单片机寄存器分配
  • 基于C语言实现寄存器分配 采用图着色法 涉及编译原理 图论 数据结构与算法 计算机科学等知识点
  • 嵌入式处理器寄存器分配的一种混合演化算法.pdf
  • 行业分类-设备装置-使用写入掩码的具有SIMD架构的寄存器分配.zip
  • 第四编译器:本地内联常量折叠寄存器分配Forth编译器
  • 行业分类-嵌入式设备-基于最大完全子图的嵌入式系统寄存器分配方法.zip
  • 行业分类-嵌入式设备-基于反图描述的嵌入式系统寄存器分配方法.zip
  • 具有无限寄存器的x86虚拟机 建立 依存关系 CMake(2.8.12.2+) LLVM(3.8本地) Google测试( libgtest )(1.7.0+) 建造 mkdir build cd build cmake .. -G Ninja # if you want to use ninja ninja nolimix86 ...
  • 64位寄存器分配的不同

    千次阅读 2017-07-15 09:12:14
    64位寄存器分配的不同 区别有: 64位有16个寄存器,32位只有8个。但是32位前8个都有不同的命名,分别是e _ ,而64位前8个使用了r代替e,也就是r _。e开头的寄存器命名依然可以直接运用于相应寄存器...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 180,377
精华内容 72,150
关键字:

寄存器分配