动态二进制翻译系统中可重定向的寄存器分配方法

摘要

本发明涉及一种动态二进制翻译系统中可重定向的寄存器分配方法，基于基本块内变量的next－use信息实施替换策略，根据不同的目标平台，自适应的启用不同的寄存器分配器，进行目标平台寄存器的分配。根据动态二进制翻译领域的不同需要对基本块中的变量进行寄存器的分配，分为普通分配、强制要求特定寄存器分配、强制要求非特定寄存器分配。本发明具有可重定向性，结合了变量的使用信息特性，具有分配效果好、分配开销低的特点，对于动态二进制翻译领域有更好的适用性，对于多源多目标的二进制翻译器尤其适用。

说明书

技术领域

本发明涉及一种动态二进制翻译系统中可重定向的寄存器分配方法，具体涉及一种利用基本块内变量的next-use信息来进行寄存器分配，具备重定向特性的寄存器分配方法。本发明属于动态二进制翻译技术领域，尤其适用于多源多目标的二进制翻译平台。

背景技术

动态二进制翻译是虚拟执行技术中应用最为广泛的方法，是为遗留代码提供移植可能性和提高软件的平台适应性的一种有效手段，它在不需要可执行程序的源代码的情况下，可以动态地将源机器平台上的二进制程序经过转换，运行于其他目标机器平台上。对于动态二进制翻译器自身而言，执行性能是一个非常重要的衡量指标。所谓执行性能是指，以源程序在原架构下运行的效率为参照，其在动态二进制翻译器提供的运行环境下的效率损失度越低，翻译器的执行性能越好。

寄存器在计算机存储体系结构里处于最上层，是访问速度最快的存储介质，而且由于芯片大小的限制，通常寄存器数目不多，Intel的x86处理器只有8个通用寄存器，有些RISC(精简指令集计算机)体系结构的寄存器数目稍多一些，但也只有几十个左右的寄存器，当然里面还包含很多特殊寄存器，能够被翻译器使用的就更少了。为了提高翻译器翻译后的代码的执行性能，动态二进制翻译领域需要采用一种技术，它使得翻译后的代码块能够尽可能高效的利用寄存器这一稀缺资源。但是对于动态二进制翻译领域，考虑到动态执行的实时性，分配算法复杂度不能太高。因此技术人员必须在更高效的使用目标平台的寄存器和分配算法的复杂度之间寻求平衡。

就一般而言，在动态二进制翻译领域，对源程序的翻译、执行或优化等操作都是以源程序的基本块为单位。所谓基本块是指仅有单入口点和单出口点的一组指令序列，基本块的入口点仅存在于此基本块的开始，基本块的出口点仅存在于此基本块的末尾，程序的执行流从此基本块的入口点进入并执行块内指令，之后从出口点离开。动态二进制翻译领域的寄存器分配也是以基本块为单位，完成对基本块内代码中的变量进行寄存器的分配。

目前，在动态二进制翻译领域可以使用如下方法完成寄存器分配任务：

1、简单的寄存器分配方法，这种分配算法通过对基本块内的变量号按目标机寄存器数目进行一次取模运算，得出的数字即是被分配的寄存器编号。如果该寄存器被同一条指令的其他变量占用，则尝试下一个编号的寄存器。如果该寄存器没有被同一条指令内的其他变量占用，则把该寄存器内内容交换到内存，然后分配该寄存器给当前变量。如果该寄存器空闲，直接分配该寄存器给当前变量。这种方法简单有效，开销小，适用于动态二进制翻译领域的及时性特性，但没有利用基本块内变量的信息，使得分配结果不够高效，寄存器使用效率不高。

2、全局寄存器分配方法，这种方法把跨越多个基本块常用的一些变量存放在全局寄存器中，比如把循环中常用的变量保存在特定的寄存器中。因为在动态二进制翻译中，翻译和执行的基本单位是一个基本块，所以这里所指的全局也仅在一个基本块范围之内，全局变量是指在这个基本块内被使用次数(use-frequency)最多的那个变量，把这些变量存放在某些寄存器中，在整个基本块的生存期，对它们都不做替换。这种方法需要在分配前，先走查一下整个基本块，收集基本块内所有变量的使用频率信息。然后分配一些固定的寄存器给这些使用频次最高的变量，其余变量使用简单的寄存器分配方法进行分配。这种方法利用了基本块内变量的信息，但在使用上不够充分，只在开始阶段利用收集到的信息固定分配了若干变量，对后续变量的分配过程则完全丢弃了这些信息。

3、图染色分配方法，这种方法在静态编译器领域有着重要的地位，它是一种基于图简化思路的启发式分配方法。它包括如下几个步骤：

(1)变量存活期信息的收集

(2)干扰图的构造

(3)图精简以及寄存器分配

变量存活期的收集通过遍历整个基本块，从而获得每个变量的存活期。如果两个变量存活期有重叠，则表明这两个变量存在冲突，即不能同时分配到同一个寄存器。在干扰图里体现为这两个变量之间存在一条干扰边。通过这种方式构造出干扰图。然后基于干扰图的简化过程，把每个变量压栈，当所有变量都完全压栈后，则表明所有变量都能够分配到一个寄存器。如果干扰图不能继续简化下去，则采用spill out方式把这个变量放到内存去，从图中删除该结点，继续简化，直到干扰图简化完毕。然后通过弹栈操作进行寄存器分配。弹栈的过程只需找出一个没被和它存在干扰关系的变量占用的寄存器即可。这种方法收集了基本块内变量的信息，并充分利用了收集到的这些信息，最优化的进行了寄存器分配，使得寄存器分配的效果最好，但是整个分配过程比较耗时，开销很大，在开销和分配效果上需要根据分配对象进行确定。对于一个基本块内的寄存器分配，图染色算法不太适用。

从上述的三种寄存器分配方法可以看出，每种方法都有其固有的优缺点，三者收集并利用信息的丰富程度呈递增趋势，同时，分配开销和实现复杂度也随之增加。对于前两种寄存器分配方法，实现较简单，但是利用基本块内变量的信息十分有限，不能达到有效的效果。最后一种剖分信息虽然充分利用了收集到的信息，其执行性能损失将无法接受，或者说，在动态二进制翻译领域，在一个基本块内，按照此种分配方法所得到的寄存器使用效率的提高还不足以弥补为达到这种效果所付出的分配开销。

因此需要发明一种新型的适用于动态二进制翻译的寄存器分配方法，既能有效的利用基本块内变量的信息，产生良好的分配结果，又不能有太多分配开销。同时还需要满足动态二进制翻译领域多源多目标所要求的重定向特性。

发明内容

本发明的目的在于针对现有技术的不足，提供一种动态二进制翻译系统中可重定向的寄存器分配方法，对多种目标平台具有可重定向性，具有分配开销小，分配效率高等特性，满足动态二进制翻译器领域中多源多目标的翻译特性以及二进制翻译系统对分配开销的敏感性的特殊需求。

为实现上述目的，本发明设计的一种可重定向的寄存器分配方法，基于基本块内变量的next-use信息实施替换策略，根据不同的目标平台，自适应的启用不同的寄存器分配器，进行目标平台寄存器的分配。根据动态二进制翻译领域的不同需要对基本块中的变量进行寄存器的分配，分为普通分配、强制要求特定寄存器分配、强制要求非特定寄存器分配。

所谓next-use信息是指该变量下次被使用的位置。

本发明分配方法的作用位置：

动态二进制翻译器通常会包含中间代码层，因为如果要达到多源多目标的翻译特性，多了这一层将会减少从源平台翻译到目标平台的翻译过程。这样动态二进制翻译器就需要包含两个过程：一是把在源平台下运行的映像进行解构，按一个个基本块进行翻译，转换成由中间代码组成的中间代码块；二是把中间代码块翻译成在目标平台上能运行的目标代码块。在过程一中，源映像代码中的寄存器用数量不受限制的虚拟寄存器替代。在过程二中，需要把中间代码块中的虚拟寄存器用目标平台的实际寄存器来替代，而目标平台的寄存器数目都是有限的，个别平台寄存器资源极其宝贵，比如x86，充分使用这些资源能够使得整个计算系统性能得到很大的提高。本发明分配方法正是运用在过程二中，完成把目标平台寄存器合理有效的分配给目标指令的变量。

本发明进行寄存器分配的具体步骤如下：

1)初始化寄存器分配器的目标平台，包括寄存器数目，寄存器之间的数据移动机器指令，内存到寄存器的数据移动机器指令以及寄存器到内存的数据移动机器指令；

2)初始化块寄存器分配器内部数据结构，包括初始化寄存器状态的数据结构数据，所有寄存器状态设为空闲，所有目标平台寄存器所匹配的变量设为空，所有匹配的变量所在指令设为空；初始化基本块所有变量所在位置为内存；清空存放基本块变量next-use信息的所有队列；

3)从基本块头部到尾部扫描收集next-use信息，依次把基本块内变量的next-use信息分别放进变量各自的队列；

4)根据不同翻译需要对基本块中的变量进行寄存器的分配，分为普通分配、强制要求特定寄存器分配、强制要求非特定寄存器分配；

5)对于普通分配，依次查看寄存器的状态，如果有寄存器已被分配给该变量，则继续保持这种分配；否则再依次查看寄存器的状态，若有空闲寄存器或者有寄存器对应变量失去活性，且变量在后续指令是被定义的，则把该空闲寄存器或者对应变量失去活性的寄存器分配给该变量；若有空闲寄存器或者有寄存器对应变量失去活性，且变量在后续指令是被使用的，则把该空闲寄存器或者对应变量失去活性的寄存器分配给该变量，并把该变量对应的内存的数据装载到该空闲寄存器或者对应变量失去活性的寄存器；若无空闲寄存器且没有寄存器对应变量失去活性，且变量在后续指令是被定义的，则先找出next-use信息最大值的变量所对应的寄存器，如果next-use信息最大值的变量后续会被使用，则把该寄存器的值保存到对应变量的内存，然后把该寄存器分配给该变量，如果next-use信息最大值的变量后续不会被使用，则直接把该寄存器分配给该变量；若无空闲寄存器且没有寄存器对应变量失去活性，且变量在后续指令是被使用的，则先找出next-use信息最大值的变量所对应的寄存器，如果next-use信息最大值的变量后续会被使用，则把该寄存器的值保存到对应变量的内存，然后把该寄存器分配给该变量，并把该变量对应的内存的数据装载到该寄存器，如果next-use信息最大值的变量后续不会被使用，则直接把该寄存器分配给该变量，并把该变量对应的内存的数据装载到该寄存器；

6)对于强制要求特定寄存器分配，如果强制要求寄存器已被分配的变量恰好是该变量，则继续保持这种分配；如果强制要求寄存器被分配的变量不是该变量，且被分配的变量存在活性，则把强制要求特定寄存器的值保存到对应变量的内存，完成数据保护处理，把该强制要求特定寄存器分配给该变量，如果该变量后续指令是被使用的并且该变量在内存里，把该变量对应的内存的数据装载到强制要求特定寄存器，如果该变量后续指令是被使用的并且该变量在寄存器里，把该变量对应的寄存器的数据装载到强制要求特定寄存器；如果强制要求寄存器被分配的变量不是该变量，且被分配的变量失去活性，则把该强制要求特定寄存器分配给该变量，如果该变量后续指令是被使用的并且该变量在内存里，把该变量对应的内存的数据装载到强制要求特定寄存器，如果该变量后续指令是被使用的并且该变量在寄存器里，把该变量对应的寄存器的数据装载到强制要求特定寄存器；

7)对于强制要求非特定寄存器分配，先保存强制要求非特定寄存器的状态到一个临时变量，如果强制要求非特定寄存器已经分配给了该变量，并且该变量存在活性，则保存强制要求非特定寄存器到该变量对应的内存，更改临时变量的状态为空闲，更改强制要求非特定寄存器的状态为受保护的，然后对该变量进行普通分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果；如果强制要求非特定寄存器已经分配给了该变量，并且该变量失去活性，则更改临时变量的状态为空闲，更改强制要求非特定寄存器的状态为受保护的，然后对该变量进行普通分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果；如果强制要求非特定寄存器没有分配给该变量，更改强制要求非特定寄存器的状态为受保护的，然后对该变量进行普通分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果。

本发明的具有可重定向的寄存器分配方法具有实质性进步和显著的优点：

①本发明可以根据不同的目标平台进行相应的寄存器分配，具有可重定向性，只需很小的改动，就能适用于多种目标平台。与现有寄存器分配方法比，对二进制翻译系统的支持有着特殊的处理，尤其是有着多源多目标的特性，只需变更两个回调函数和目标平台的寄存器数目，就能够应用，非常的便利。

②本发明对二进制翻译系统中寄存器分配需要的各种应用场景有着良好的支持。提供丰富的接口满足动态二进制翻译对寄存器的各种分配要求。

③本发明与简单的寄存器分配方法相比，具有结合变量的使用信息特性，分配效果好；与全局寄存器分配方法相比，具有变量信息使用充分的特点，分配效果好；与图染色寄存器分配方法相比，具有分配开销低的特性，对于动态二进制翻译领域有更好的适用性。基于next-use信息进行寄存器分配，是线性分配开销，很好的满足了动态二进制翻译领域时效性的要求。

具体实施方式

以下结合实施例对本发明的技术方案作进一步描述。以下实施例不构成对本发明的限定。

CrossBit是一个动态二进制翻译系统，它可以为执行在多种不同体系结构的源程序，通过翻译和优化的方法，提供异构架构下的执行环境。为了实现多源多目标，CrossBit使用了中间代码层，这样会减少翻译路径。只需要把前端二进制映像程序(前端)翻译成中间代码块，然后再把中间代码块翻译成对应的目标平台代码(后端)，就能形成一种二进制翻译器。如果目标平台改变，只需改变一个后端。目前，CrossBit支持SimpleScalar，MIPS，X86，SPARC前端，X86和SPARC后端。CrossBit采用VINST作为中间指令集，它是CrossBit项目组自己设计的一套中间指令集，是一种低层次的虚拟精简机器指令系统，具有无穷多个32位虚拟寄存器、Load-Store风格体系结构、单一的偏址寻址模式。寄存器分配方法面对的对象是这些中间指令组成的中间代码块。CrossBit的执行框架是，首先加载源二进制映像，找出源映像的入口地址，之后在TCache里查找对应该入口的目标代码块，所谓TCache是一块内存区域，用来存放翻译好的目标代码块，如果查找成功，则切换上下文，执行这个目标代码块，如果查找失败，则启动CrossBit的前端解码器，对源映像中对应该入口地址的基本块解码成中间指令，并封装成中间代码块(VBlock)，然后调用CrossBit的后端编码器把中间指令块转换成目标代码块(TBlock)。然后提交到TCache里，然后再次查找TCache，就会出现TCache命中，这时再进行上下文的切换，进行目标代码块的执行。当目标代码块执行完毕后，将会返回到CrossBit的上下文，进行下一个轮回的操作。如此往复，直到整个程序执行完毕。在把中间指令块转换成目标代码块的过程中，需要用目标平台的寄存器替换中间指令里面的虚拟寄存器，这时将会使用本发明提供的方法进行有效的分配。本发明主要包括如下几个过程，特定目标平台的寄存器分配器的初始化、寄存器分配前的初始化、信息收集以及分配过程。不失一般性，本实施例依托于CrossBit的执行框架以及目标代码块的生成技术。

1)初始化寄存器分配器的目标平台

初始化寄存器分配器的目标平台，包括寄存器数目，寄存器之间的数据移动机器指令，内存到寄存器的数据移动机器指令以及寄存器到内存的数据移动机器指令。本实施例使用构造函数RegAllocator(XTUInt8 num_regs，CBOfSpillIn cb_spill_in，CBOfSpillOut cb_spill_out，CBOfRegToRegcb_regtoreg)创建目标平台的寄存器分配器，寄存器的数目通过参数num_regs传递，cb_spill_in、cb_spill_out、cb_regtoreg都是函数指针，分别指向目标平台上能够完成内存到寄存器，寄存器到内存，寄存器到寄存器等功能的函数，这些函数的具体实现则是在目标代码块插入一条相同功能的机器指令。

2)寄存器分配前的初始化

初始化块寄存器分配器内部数据结构，包括初始化寄存器状态的数据结构数据，所有寄存器状态设为空闲，所有目标平台寄存器所匹配的变量设为空，所有匹配的变量所在指令设为空；初始化基本块所有变量所在位置为内存；清空存放基本块变量next-use信息的所有队列。本实施例使用RegUsagera_reg_table[reg_num]保存目标平台寄存器的状态，reg_num是目标平台的寄存器数目，结构体RegUsage包含status(free，allocated，reserved)、mapped_to和inst信息，分别表示寄存器的状态，被匹配的虚拟寄存器编号，所处指令的编号；使用bool ra_vreg_spilled[MAX_VREG_NUM]保存中间指令中虚拟寄存器信息是否被溢出的状态，false表示被溢出到内存，true表示被溢入到寄存器，其中MAX_VREG_NUM表示VBlock里的最多包含的虚拟寄存器的数目，通常可以根据经验值设定为50；使用std::queue<std::pair<XTInt32，RegAccessMode>>ra_vreg_used_list[MAX_VREG_NUM]存储所有虚拟寄存器的next_use信息，其中数组的下标是每个虚拟寄存器的编号，std::pair里的XTInt32指虚拟寄存器所在指令在VBlock的位置，RegAccessMode包括DEF，USE两种，分别表示该虚拟寄存器在表达式的左侧和右侧。

i、ra_reg_table[reg_num]的初始化

初始化该数组里面所有元素的status域为free。表示所有寄存器都可以被分配。

ii、ra_vreg_spilled[MAX_VREG_NUM]的初始化

初始化该数组里的所有元素为false。表明所有虚拟寄存器都在内存里。

如果该值是true，则表明该虚拟寄存器在寄存器里。

iii、ra_vreg_used_list[MAX_VREG_NUM]的初始化

数组的每个元素都是一个队列，由于每次编码一个新的VBlock时，都将启用寄存器分配器，需要清空上次编码时遗留信息，因此需要清空每个队列。初始化的过程就是清空这些队列。

3)信息收集

从基本块头部到尾部扫描收集next-use信息，依次把基本块内变量的next-use信息分别放进变量各自的队列。本实施例使用了collectNextUseInfo(VBlock*vb)函数完成这个任务，其中vb是VBlock的指针，指向VBlock的地址。VBlock里存放的是一条条的VInst指令，next-use信息的收集过程就是需要从头到尾扫描所有VInst指令，取出每条指令的虚拟寄存器类型(VReg)的参数，根据其虚拟寄存器的编号以及其类型(Operand::VREG_DEF或者Operand::VREG_USE)，做进队列操作。比如一条指令seq(seq是该指令在VBlock中的位置)的某个参数类型是VREG_DEF，它的编号为i，则ra_vreg_used_list[i].push(std::make_pair(seq，DEF))；如果该参数类型是VREG_USE，则ra_vreg_used_list[i].push(std::make_pair(seq，USE))。存储的seq就是虚拟寄存器的next-use信息。

4)寄存器的分配

根据不同翻译需要对基本块中的变量进行寄存器的分配，分为普通分配、强制要求特定寄存器分配、强制要求非特定寄存器分配。当变量没有特殊寄存器要求，即目标平台上任何一个寄存器都可以，这种情况将使用普通分配。当变量有寄存器的要求，比如当目标平台为x86的情况，某个变量必须要用ESP寄存器，这种情况下将使用强制要求特定寄存器分配。当变量需要除了某个特定寄存器之外的其他寄存器，这种情况下将使用强制要求非特定寄存器分配。

5)普通分配

对于普通分配，本实施例使用regAlloc(XTRegNum vreg，RegAccessModemode)完成基本的寄存器分配任务。参数vreg是需要寄存器的虚拟寄存器，mode表示该虚拟寄存器的访问类型(DEF或者USE)。主要有如下步骤：

①如果有寄存器已被分配给该变量，则继续保持这种分配。具体为顺序查看每个寄存器的状态，如果是allocated并且和它匹配的是vreg，则查看vreg是否在寄存器里(通过查看spilled标志)，如果不在寄存器里，需要做spillin，并修改spilled标志。更新寄存器的inst值。返回该寄存器给vreg用。如果遍历所有的寄存器状态，没有符合这种条件的，进入步骤②。

②顺序查看每个寄存器的状态，若有空闲寄存器或者有寄存器对应变量失去活性，且变量在后续指令是被定义的，则把该空闲寄存器或者对应变量失去活性的寄存器分配给该变量。具体为顺序查看每个寄存器的状态，如果是free，则分配该寄存器给vreg。或者如果是allocated，设该寄存器对应的虚拟寄存器为temp_reg，则对ra_vreg_used_list[temp_reg]进行pop操作，把在当前指令之前的next-use信息进行清除。然后查看ra_vreg_used_list[temp_reg]是否为空或者ra_vreg_used_list[temp_reg].front().second的类型是否DEF，如果空，说明该虚拟寄存器以后不再被用到，生命周期结束，可以分配出去；如果队列头部元素中显示的类型是DEF，则表示该虚拟寄存器生命周期结束，也可以分配出去。这两种情况下，直接分配该寄存器给vreg，其他情况下进入步骤③。

③若有空闲寄存器或者有寄存器对应变量失去活性，且变量在后续指令是被使用的，则把该空闲寄存器或者对应变量失去活性的寄存器分配给该变量，并把该变量对应的内存的数据装载到该空闲寄存器或者对应变量失去活性的寄存器。具体为顺序查看每个寄存器的状态，如果是free，则分配该寄存器给vreg，并把vreg的内容spill in到该寄存器，并更新该寄存器的状态ra_vreg_spilled[vreg]＝true。或者如果是allocated，设该寄存器对应的虚拟寄存器为temp_reg，则对ra_vreg_used_list[temp_reg]进行pop操作，把在当前指令之前的next-use信息进行清除。然后查看ra_vreg_used_list[temp_reg]是否为空或者ra_vreg_used_list[temp_reg].front().second的类型是否DEF，如果空，说明该虚拟寄存器以后不再被用到，生命周期结束，可以分配出去；如果队列头部元素中显示的类型是DEF，则表示该虚拟寄存器生命周期结束，也可以分配出去。这两种情况下，直接分配该寄存器给vreg，把vreg的内容spill in到该寄存器，并更新该寄存器的状态ra_vreg_spilled[vreg]＝true，其他情况下进入步骤④。

④若无空闲寄存器且没有寄存器对应变量失去活性，且变量在后续指令是被定义的，则先找出next-use信息最大值的变量所对应的寄存器，把该寄存器的值保存到对应变量的内存，然后把该寄存器分配给该变量。具体如下，依次查看每个寄存器，设寄存器对应的虚拟寄存器为temp_reg，则对ra_vreg_used_list[temp_reg]进行pop操作，把在当前指令之前的next-use信息进行清除。比较ra_vreg_used_list[temp_reg].front().first和max_next(最大next_use值)，如果超过max_next，则修改max_next值为ra_vreg_used_list[temp_reg].front().first，并修改max_pos(最大next_use对应的寄存器编号)值为i(i为当前寄存器编号)。如果变量max_pos对应的寄存器的状态是allocated并且该寄存器对应的虚拟寄存器的next-use信息类型为USE，则说明该寄存器在后续步骤中将会被用到，需要spill out该寄存器，然后更改该寄存器的状态ra_vreg_spilled[temp_reg]＝false；其他情况不需要做保护处理。最终用max_pos作为分配结果。其他情况下进入步骤⑤。

⑤若无空闲寄存器且没有寄存器对应变量失去活性，且变量在后续指令是被使用的，则先找出next-use信息最大值的变量所对应的寄存器，如果next-use信息最大值的变量后续会被使用，把该寄存器的值保存到对应变量的内存，如果next-use信息最大值的变量后续不会被使用，不需把该寄存器的值保存到对应变量的内存，直接把该寄存器分配给该变量，并把该变量对应的内存的数据装载到该寄存器。具体如下：依次查看每个寄存器，设寄存器对应的虚拟寄存器为temp_reg，则对ra_vreg_used_list[temp_reg]进行pop操作，把在当前指令之前的next-use信息进行清除。比较ra_vreg_used_list[temp_reg].front().first和max_next(最大next_use值)，如果超过max_next，则修改max_next值为ra_vreg_used_list[temp_reg].front().first，并修改max_pos(最大next_use对应的寄存器编号)值为i(i为当前寄存器编号)。如果变量max_pos对应的寄存器的状态是allocated并且该寄存器对应的虚拟寄存器的next-use信息类型为USE，则说明该寄存器在后续步骤中将会被用到，需要spill out该寄存器，然后更改该寄存器的状态ra_vreg_spilled[temp_reg]＝false；其他情况不需要做保护处理。最终用max_pos作为分配结果。并把该变量对应的内存的数据装载到该寄存器。

6)强制要求特定寄存器分配

本实施例使用regAllocForce(XTRegNum vreg，XTRegNum expect，RegAccessMode)来完成强制要求某个特定寄存器给虚拟寄存器。主要有如下步骤：

①查看寄存器expect的状态，如果是reserved，发生死锁，返回错误码，结束。否则进入②。

②如果强制要求寄存器已被分配的变量恰好是该变量，则继续保持这种分配。具体为如果expect的状态是allocated，则查看其map对象是否vreg，如果是，则用当前指令位置vinst_seq更新ra_reg_table[expect].inst，然后查看spilled标志，如果被溢出了，并且是USE类型，还需要spill in操作把vreg的内容spill in到expect寄存器里，并且修改spilled标志，然后返回expect，结束。如果其map对象不是vreg进入步骤③。

③如果强制要求寄存器被分配的变量不是该变量，且被分配的变量存在活性，则把强制要求特定寄存器的值保存到对应变量的内存，完成数据保护处理，把该强制要求特定寄存器分配给该变量，如果该变量后续指令是被使用的并且该变量在内存里，把该变量对应的内存的数据装载到强制要求特定寄存器，如果该变量后续指令是被使用的并且该变量在寄存器里，把该变量对应的寄存器的数据装载到强制要求特定寄存器。如果该变量后续指令是被定义的，不需要把该变量对应的内存或者对应的寄存器的数据装载到强制要求特定寄存器。如果强制要求寄存器被分配的变量不是该变量，且被分配的变量失去活性，则把该强制要求特定寄存器分配给该变量，如果该变量后续指令是被使用的并且该变量在内存里，把该变量对应的内存的数据装载到强制要求特定寄存器，如果该变量后续指令是被使用的并且该变量在寄存器里，把该变量对应的寄存器的数据装载到强制要求特定寄存器。如果该变量后续指令是被定义的，不需要把该变量对应的内存或者对应的寄存器的数据装载到强制要求特定寄存器。具体为找到expect的map对象，假设是temp_vreg，然后对ra_vreg_used_list[temp_reg]进行pop操作，把在当前指令之前的next-use信息进行清除。然后查看ra_vreg_used_list[temp_reg]如果非空并且ra_vreg_used_list[temp_reg].front().second的类型是USE，这种情况表明temp_vreg后续指令还会用到，需要保存其内容，本实施例使用regSpillOut(expect)把expect的内容交换到内存，并更改temp_reg的spilled标志为溢出到内存。如果能找到一个寄存器i，其map对象是vreg，然后使用(*ra_cb_reg_to_reg)(i，expect)函数指针所指向的实体函数进行寄存器间的数据移动，即完成vreg的内容到expect寄存器的转移。然后修改expect状态值为allocated，inst更新为当前指令，mapped_to更新为vreg以及修改i的status值为free。返回expect。结束。如果没有找到这样的一个寄存器。并且如果函数参数mode是USE，则使用regSpillIn(vreg，expect)函数完成vreg到expect的数据转移。然后使用ra_vreg_spilled[vreg]＝true指令更新vreg的状态(表明vreg在寄存器里)。然后修改expect状态值为allocated，inst更新为当前指令，mapped_to更新为vreg。返回expect。结束。其他情况修改expect状态值为allocated，inst更新为当前指令，mapped_to更新为vreg。返回expect。结束。

7)强制要求非特定寄存器分配

本实施例使用regAllocForceExcept(XTRegNum vreg，XTRegNum except，RegAccessMode mode)完成分配除了except以外的其他任一个寄存器给vreg的功能。主要有如下步骤：

①对于强制要求非特定寄存器分配，先保存强制要求非特定寄存器的状态到一个临时变量，如果强制要求非特定寄存器已经分配给了该变量，并且该变量存在活性，则保存强制要求非特定寄存器到该变量对应的内存，更改临时变量的状态为空闲，更改强制要求非特定寄存器的状态为受保护的。然后按照普通分配的方法对该变量进行分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果。具体为保存寄存器except的状态到temp。查看寄存器except对应的虚拟寄存器是否vreg，如果是，则对vreg的next_use信息队列中早于当前指令的next_use信息进行清除操作，具体为ra_vreg_used_list[vreg]的pop操作。如果队列头部的next_use信息的类型为USE，表明vreg将会不久被使用，则需要spill out操作，具体为regSpillOut(except)。修改except状态为reserved，本例中具体操作为ra_reg_table[except]＝reserved。修改为reserved状态的目的是杜绝调用regAlloc函数对vreg进行分配时，得到except的结果。然后调用函数regAlloc(vreg，mode)进行分配工作。最后使用temp值恢复except的状态。返回分配结果。结束。其他情况进入步骤②。

②如果强制要求非特定寄存器已经分配给了该变量，并且该变量失去活性，则更改临时变量的状态为空闲，更改强制要求非特定寄存器的状态为受保护的，然后按照普通分配的方法对该变量进行分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果。具体为保存寄存器except的状态到temp。查看寄存器except对应的虚拟寄存器是否vreg，如果是，则对vreg的next_use信息队列中早于当前指令的next_use信息进行清除操作，具体为ra_vreg_used_list[vreg]的pop操作。如果队列头部的next_use信息的类型为DEF或者队列空，表明vreg将不会被使用，不需要spill out操作，具体为regSpillOut(except)。修改except状态为reserved，本例中具体操作为ra_reg_table[except]＝reserved。修改为reserved状态的目的是杜绝调用regAlloc函数对vreg进行分配时，得到except的结果。然后调用函数regAlloc(vreg，mode)进行分配工作。最后使用temp值恢复except的状态。返回分配结果。结束。其他情况进入步骤③。

③如果强制要求非特定寄存器没有分配给该变量，更改强制要求非特定寄存器的状态为受保护的，然后按照普通分配的方法对该变量进行分配，将受保护的强制要求非特定寄存器改回临时变量的值，并以普通分配的结果作为分配结果。具体为保存寄存器except的状态到temp。查看寄存器except对应的虚拟寄存器是否vreg，如果不是，修改except状态为reserved，本实施例中具体操作为ra_reg_table[except]＝reserved。修改为reserved状态的目的是杜绝调用regAlloc函数对vreg进行分配时，得到except的结果。然后调用函数regAlloc(vreg，mode)进行分配工作。最后使用temp值恢复except的状态。返回分配结果。结束。

本实施例还使用了regAllocReserve(XTRegNum treg)完成寄存器的保护工作。主要应用于避免某个寄存器被使用。主要步骤如下：

①如果treg状态不是allocated，则修改其状态为reserved，返回。结束。否则进入步骤②。

②找到treg对应的vreg，然后对vreg的next_use信息队列进行清理工作，把先于当前指令位置的next_use信息进行清除工作。然后查看队列首元素类型，如果是USE，则表示vreg将会被用到，需要保存其值。本实施例使用regSpillOut(treg)操作完成寄存器值保存的工作，并使用ra_vreg_spilled[vreg]＝false来更新vreg的溢出状态。然后修改treg的状态为reserved，返回。结束。

本实施例使用了regAllocRelease(XTRegNum treg)完成寄存器释放的工作，这部分工作主要回收不再被使用的寄存器，以备其他寄存器使用。也主动应对regAllocReserve函数对寄存器的reserved操作。

具体操作为修改treg的状态为free。

本实施例使用regSpillOut(XTRegNum physical_reg)完成寄存器到内存的数据转移工作。具体实现为找到physical_reg对应的vreg，然后调用对应平台的回调函数(*ra_cb_spill_out)(physical_reg，(XTMemAddr)ra_spill_pool+vreg)完成physical_reg的内容到vreg对应的内存池位置的移动。结束。函数ra_cb_spill_out是条根据目标平台设定的寄存器到内存的数据移动机器码指令。

对于寄存器溢入，采用regSpillIn的操作，即regSpillOut的镜像操作。