CN110187882B - 一种面向指令源操作数的寄存器对分配方法及存储介质 - Google Patents

Abstract

本发明公开一种面向指令源操作数的寄存器对分配方法及存储介质，该方法步骤包括：S1.分别将待处理指令中所有源操作数寄存器对所包含的两个寄存器均进行独立的寄存器分配；S2.依次获取各条指令进行寄存器修正分配，将寄存器对中错误使用寄存器使用替换寄存器进行替换，替换寄存器根据各寄存器的使用状态以及在指令入口处的空闲状态进行选取，优先使用同一指令中前面的源操作数寄存器对的替换寄存器替换后面相同的错误使用寄存器，被替换出来的寄存器若在指令入口处变为空闲则作为后续其他源操作数中寄存器对的替换寄存器。本发明面向指令源操作数实现寄存器对分配，具有实现方法简单、分配成功率及资源利用率高、灵活性强等优点。

Description

一种面向指令源操作数的寄存器对分配方法及存储介质

技术领域

本发明涉及编译优化技术领域，尤其涉及一种面向指令源操作数的寄存器对分配方法及存储介质。

背景技术

随着处理器技术特别是数字信号处理器(DSP)技术的发展，许多先进的处理器体系结构对数据的处理能力日益增强，一个重要的特点是体系结构中往往有许多指令的操作数被设计成是由成对的寄存器(即寄存器对)构成。针对上述特性，典型应用如用一个寄存器对来存储或处理更大字长的数据，或用一个寄存器对来存储超过单个寄存器表示范围的存储器地址等。为了发挥先进体系结构的性能，当前的核心问题即是如何充分利用稀缺的寄存器资源，因此在代码中充分利用寄存器是系统的编译软件的核心任务之一。编译器中对寄存器资源的利用是由寄存器分配这一过程来实现，因而寄存器分配是实现现代优化编译器优化的关键。

在目前流行的编译系统中，寄存器分配主要是采用线性扫描法和基于图着色思想的全局寄存器分配方法两类，其中后者基于对变量生命期的详细刻画，是寄存器分配效果较好的一类方法。但是上述传统的寄存器分配方法中，对寄存器对(往往是两个奇偶连号的寄存器构成的偶对)的分配均是把需要成对寄存器的地方对应的两个寄存器分配候选者作为一个整体，在寄存器指派时为其指派一个符合要求的物理寄存器对，该类方法尽管能够保证为操作数指派符合要求的寄存器对，但由于对同时指派连号寄存器偶对的需求会导致降低寄存器指派的成功率，尤其是对于数据密集型或地址量很多的程序，还会存在大量的溢出和访存操作，而实际上，相当一部分溢出和相应的访存操作是可以避免的，然而上述传统的寄存器分配方法的寄存器对分配策略不能处理该类问题，使得寄存器资源利用率低而不能充分利用寄存器资源。

发明内容

本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种实现方法简单、分配成功率及资源利用率高、灵活性强的面向指令源操作数的寄存器对分配方法及存储介质。

为解决上述技术问题，本发明提出的技术方案为：

一种面向指令源操作数的寄存器对分配方法，步骤包括：

S1.初始分配：分别将待处理指令中包括寄存器对的所有源操作数所包含的两个符号寄存器均作为单寄存器分配候选者进行独立的寄存器分配；

S2.修正分配：依次获取各条指令进行寄存器修正分配，如果指令中存在至少一个以上的源操作数涉及寄存器对，对指令中各源操作数依次进行寄存器对合法性检查，并根据检查结果将寄存器对中不符合使用规则的错误使用寄存器使用替换寄存器进行替换，所述替换寄存器根据各寄存器的使用状态以及在指令入口处的空闲状态进行选取，条件满足时优先使用同一指令中前面的源操作数寄存器对的替换寄存器替换后面相同的所述错误使用寄存器，被替换出来的寄存器若在指令入口处变为空闲状态则作为同一指令的后续其他源操作数中寄存器对的替换寄存器。

作为本发明的进一步改进，所述步骤S1中，具体将源操作数中成对的寄存器分配候选者中的每一个都当作对应着单个物理寄存器的独立单寄存器分配候选者，并与其他单寄存器分配候选者一起采用相同的寄存器分配方式分配各自的物理寄存器，得到所述初始寄存器分配结果。

作为本发明的进一步改进，所述步骤S2的步骤包括：

S21.从每条指令的第一个源操作数开始遍历各个源操作数，如果源操作数包含一个寄存器对，对该寄存器对进行合法性检查，判断该寄存器对中两个寄存器是否符合寄存器对使用规则，若不符合，判定需要修正，转入执行步骤S22；

S22.获取指令入口处各寄存器以及寄存器对的空闲状态；

S23.判断需要修正的寄存器对中错误使用寄存器的位置，根据所述错误使用寄存器的位置以及各寄存器在指令入口处的空闲状态、替换寄存器集合的状态选取替换寄存器对当前各所述错误使用寄存器进行修正，所述替换寄存器集合用于存放已用于替换的替换寄存器。

作为本发明的进一步改进，所述步骤S23的步骤包括：判断源操作数寄存器对是否是由两个连号的奇偶号寄存器构成，如果源操作数寄存器对中的两个寄存器序号均不符合，则判定需要全部替换源操作数寄存器对的两个寄存器，使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正；如果源操作数寄存器对中的左位寄存器或右位寄存器的序号不符合，则判定需要替换源操作数中的左位寄存器或右位寄存器，使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正；如果源操作数寄存器对中的两个寄存器序号不匹配，则判定需要替换源操作数寄存器对中的任意一个寄存器，使用第三修正模式对源操作数中任意一个寄存器进行修正，如果源操作数中仅含单个寄存器，使用第四修正模式对源操作数寄存器进行修正。

作为本发明的进一步改进，所述使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正时，根据需要修正的寄存器对中两个目标错误使用寄存器所分别对应的所述替换寄存器集合的状态、指令入口处各寄存器的空闲状态查找一个用于替换的寄存器对，使用查找到的寄存器对分别替换两个目标错误使用寄存器；所述查找一个用于替换的寄存器对的步骤包括：

a)从两个错误使用寄存器各自的所述替换寄存器集合中各取一个寄存器凑成一个合法寄存器对，若查找失败，转入执行步骤b)，否则转入执行步骤f)；

b)建立满足下述条件的寄存器对集合：寄存器对中其中一个寄存器在当前要被替换的一个寄存器的替换寄存器集合中，且符合所在源操作数的位置模式对寄存器序号的要求、另一个寄存器在指令入口处空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤c)；

c)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都空闲。然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤d)；

d)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的一个寄存器不空闲、另一个寄存器空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤e)；

e)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都不空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，然后转入执行步骤f)；

f)由当前查找到的寄存器对作为所述用于替换的寄存器对输出。

作为本发明的进一步改进，所述使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正的具体步骤包括：

Sa1.将当前需要修正的寄存器对中左寄存器rL和右寄存器rR都添加到错误使用寄存器ErrRegSet中；

Sa2.从所述左寄存器rL和右寄存器rR各自对应的替换寄存器集合中分别找一个能够构成合法寄存器对的寄存器Rx和Ry并形成寄存器对RP；

Sa3.判断所述寄存器对RP是否存在，如果存在，将所述寄存器对RP中两个寄存器添加至所述替换寄存器集合中，执行两次替换操作以将所述寄存器对RP替换出当前需要修正的寄存器对，否则转到执行步骤Sa4；

Sa4.判断指令入口处是否有SLI半闲对，所述SLI半空闲对为在指令入口处寄存器对中一个寄存器空闲、另一个寄存器不空闲，如果有则转入执行步骤Sa5，否则转入执行步骤Sa7；

Sa5.定义一个所述SLI半空闲对的形式为Rx:Ri或Ri:Rx，其中Rx为不空闲的寄存器，转入执行步骤Sa6；

Sa6.查找是否存在一个所述SLI半闲对满足其中的Rx在错误寄存器对中位模相同的Rm的替换寄存器集合中，其中Rm为在错误寄存器对中与Rx位置相同的寄存器，如果存在，将所述SLI半闲对的两个寄存器分别添加至所述替换寄存器集合中，并执行一次数据传送以及两次替换操作以将所述SLI半闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa7；

Sa7.判断是否有SLI空闲对，所述SLI空闲对为在指令入口处寄存器中两个寄存器均空闲，如果有，将所述SLI空闲对的两个寄存器分别添加至所述替换寄存器集合中，并执行两次数据传送以及两次替换操作以将所述SLI空闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa8；

Sa8.判断是否有所述SLI半闲对，如果有转到Sa9；

Sa9.排除由所有所述SLI半空闲对所构成的集合SH中所有含源变量集合内容的对，完成后判断所述集合SH是否为非空集合，如果是，取所述集合SH中编号最大的半空闲寄存器对作为替换寄存器对，执行两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将所述替换寄存器对中不空闲的寄存器Rx添加至需要保护寄存器中原有数据的被保护寄存器集合中，否则转入执行步骤Sa10；

Sa10.用所有不空闲对构成第二集合，从所述第二集合中删除所有含源变量或替换寄存器集合元素的寄存器对后，取其中编号最大的半空闲寄存器对作为替换寄存器对，执行两次数据传输以及两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将所述替换寄存器对中两个寄存器均添加至所述被保护寄存器集合中。

作为本发明的进一步改进，所述使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正的步骤包括：

Sb1.选取一个与正确使用寄存器能够构成寄存器偶对的寄存器作为目标替换寄存器，所述正确使用寄存器为当前需要修正的寄存器对中编号正确的寄存器；

Sb2.判断所述步骤Sb1选取的目标替换寄存器是否在总替换寄存器集合中，如果不在转入执行步骤Sb3，如果在且已是当前需要修正的寄存器对中错误使用寄存器R的替换寄存器，将目标替换寄存器添加至所述替换寄存器集合中，并执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器，如果在且目标替换寄存器已是其他错误使用寄存器的替换寄存器，转入执行步骤Sb4；

Sb3.判断目标替换寄存器是否在指令入口处活跃，如果是转入执行步骤Sb5，否则将当前需要修正的错误使用寄存器的数据传递给目标替换寄存器后，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb4.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正；

Sb5.判断目标替换寄存器是否属于指令源变量集合中的元素，如果是转入执行步骤Sb6，否则将目标替换寄存器分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb6.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正。

作为本发明的进一步改进，所述使用第三修正模式对源操作数中任意一个寄存器进行修正的步骤包括：

Sc1.为需要修正的寄存器中左位寄存器选取对应的左位替换寄存器PRB_L，以及为右位寄存器选取对应的右位替换寄存器PRB_R；

Sc2.判断所述左位替换寄存器PRB_L是否已是对应错误使用寄存器的替换寄存器，如果是，将所述左位替换寄存器PRB_L添加至所述替换寄存器集合中，并执行一次替换操作以将所述左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc3；

Sc3.判断所述右位替换寄存器PRB_R是否已是对应错误使用寄存器的替换寄存器，如果是，将所述右位替换寄存器PRB_R添加至所述替换寄存器集合中，并执行一次替换操作以将所示右位替换寄存器PRB_R替换出当前需要修正的右位寄存器，否则转入执行步骤Sc4；

Sc4.判断所述左位替换寄存器PRB_L是否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的右位寄存器的数据传递给所述左位替换寄存器PRB_L后，执行一次替换操作以将所述左位替换寄存器PRB_L替换出需要修正的左位寄存器，否则转入执行步骤Sc5；

Sc5.判断所述右位替换寄存器PRB_R否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的左位寄存器的数据传递给所述右位替换寄存器PRB_R后，执行一次替换操作以将所述右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转到Sc6；

Sc6.判断所述左位替换寄存器PRB_L是否同时满足不在所述替换寄存器集合中、在指令入口处活跃且不在源变量集合中，如果是，将所述左位替换寄存器PRB_L分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将所述左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc7；

Sc7.判断所述右位替换寄存器PRB_R是否同时满足不在所述替换寄存器集合、在指令入口处活跃且不在源变量集合中，如果是，将所述右位替换寄存器PRB_R分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合SetBeProt中，执行一次替换操作以将所述右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转入执行步骤Sc8；

Sc8.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正。

作为本发明的进一步改进，所述使用第四修正模式对源操作数寄存器进行修正时，具体判断对应源操作数中的目标单寄存器是否已经在同一指令之前的源操作数中分配过至少一个替换寄存器，如果是直接使用先前使用的替换寄存器替换目标单寄存器。

一种存储有计算机程序的计算机可读存储介质，所述计算机程序执行时实现如上述的方法。

与现有技术相比，本发明的优点在于：

1、本发明考虑该指令源操作数有任意多个且同一个寄存器可在不同源操作数中多次出现的特点，对指令源操作数进行寄存器对分配时，通过先对所有源操作按照独立单寄存器进行分配，如果存在源操作数涉及寄存器对，再对寄存器对进行合法性检查，对错误使用寄存器进行修正分配，根据各寄存器的使用状态以及在指令入口处的空闲状态选取替换寄存器，优先重复利用前面的源操作数寄存器对的结果来替换相同的错误使用寄存器，可以减少需要在被处理指令前插入的数据传送指令的数量，使用空闲的替换寄存器则可以减少访存指令，从而提高寄存器指派过程的成功率，同时减少溢出和访存操作指令，在减少冗余的寄存器溢出的同时保证寄存器对的使用正确，达到提升寄存器利用率的优化效果。

2、本发明通过将寄存器对分配分成单寄存器初始分配以及修正分配两个阶段，在单寄存器分配完成后通过源操作数寄存器对修正处理来保证指令源操作数中的寄存器对符合使用规则要求，因而对指令源操作数中的成对寄存器分配候选者无需如传统的必须要求在寄存器指派时就获得合法的寄存器偶对，能够提升指令源操作数对寄存器的使用灵活性，尤其是在代码的寄存器压力较大时能减少寄存器分配过程产生的寄存器溢出。

3、本发明对两个寄存器均不符合寄存器对使用规则的寄存器对进行修正时，按照两个寄存器的替换寄存器集合的动态情况、指令入口处的寄存器空闲情况和使用情况挑选替换寄存器时，按优先级依次考虑已经获得的替换结果寄存器、包含替换结果寄存器的半空闲寄存器对、空闲寄存器对、半空闲寄存器对、非空闲寄存器对的顺序来进行挑选，能够减少需要在被处理指令前插入的数据传送指令的数量，从而尽可能地减少对新的寄存器的需求。

4、本发明能够自动处理某个单寄存器分配候选者在某些源操作数寄存器对中位于左位但在另外一些源操作数寄存器对中位于右位的情况，从而提升在源操作数中使用变量方面的灵活性。

附图说明

图1是本实施例面向指令源操作数的寄存器对分配的实现流程示意图。

图2是本实施例修正一个源操作数时各种修正模式的原理示意图。

图3是本发明具体应用实施例中对一条指令的源操作数进行寄存器对修正的实现流程示意图。

图4是本发明具体应用实施例中进入处理模式A后的处理流程示意图。

图5是本发明具体应用实施例中进入处理模式B或C后的处理流程示意图。

图6是本发明具体应用实施例中进入处理模式D后的处理流程示意图。

图7是本发明具体应用实施例中执行修正时涉及的公共处理子过程的执行流程示意图。

图8是本发明具体应用实施例中寄存器替换方案生成后的公共处理子过程示意图。

具体实施方式

以下结合说明书附图和具体优选的实施例对本发明作进一步描述，但并不因此而限制本发明的保护范围。

如图1所示，本实施例面向指令源操作数的寄存器对分配方法步骤包括：

S1.初始分配：分别将待处理指令中包括寄存器对的所有源操作数所包含的两个符号寄存器均作为单寄存器分配候选者进行独立的寄存器分配；

S2.修正分配：依次获取各条指令进行寄存器修正分配，如果指令中存在至少一个以上的源操作数涉及寄存器对，对指令中各源操作数依次进行寄存器对合法性检查，并根据检查结果将寄存器对中不符合使用规则的错误使用寄存器使用替换寄存器进行替换，所述替换寄存器根据各寄存器的使用状态以及在指令入口处的空闲状态进行选取，条件满足时优先使用同一指令中前面的源操作数寄存器对的替换寄存器替换后面相同的所述错误使用寄存器，被替换出来的寄存器若在指令入口处变为空闲状态则作为同一指令的后续其他源操作数中寄存器对的替换寄存器。

一条指令中可以具有多个源操作数，且一个寄存器可能在指令中不同的源操作数中多次出现。本实施例考虑该指令源操作数有任意多个且同一个寄存器可在不同源操作数中多次出现的特点，对指令源操作数进行寄存器对分配时，通过先对所有源操作按照独立单寄存器进行分配，如果存在源操作数涉及寄存器对，再对寄存器对进行合法性检查，对错误使用寄存器进行修正分配，根据各寄存器的使用状态以及在指令入口处的空闲状态选取替换寄存器，优先重复利用前面的源操作数寄存器对的结果来替换相同的错误使用寄存器，即利用前面已使用过的寄存器对结果替换后面再次出现的相同错误使用寄存器，可以充分利用源操作数寄存器的特性，减少需要在被处理指令前插入的数据传送指令的数量，使用空闲的替换寄存器则可以减少访存指令，从而提高寄存器指派过程的成功率，同时减少溢出和访存操作指令，在减少冗余的寄存器溢出的同时保证寄存器对的使用正确，达到提升寄存器利用率的优化效果。

本实施例上述寄存器对分配方法，通过将寄存器对分配分成单寄存器初始分配以及修正分配两个阶段，在单寄存器分配完成后通过源操作数寄存器对修正处理来保证指令源操作数中的寄存器对符合使用规则要求，因而对指令源操作数中的成对寄存器分配候选者无需如传统的必须要求在寄存器指派时就获得合法的寄存器偶对，能够提升指令源操作数对寄存器的使用灵活性，尤其是在代码的寄存器压力较大时能减少寄存器分配过程产生的寄存器溢出。

本实施例步骤S1中，具体将源操作数中成对的寄存器分配候选者中的每一个都当作对应着单个物理寄存器的独立单寄存器分配候选者，并与其他单寄存器分配候选者一起采用相同的寄存器分配方式分配各自的物理寄存器，得到初始寄存器分配结果。即在寄存器分配时，首先将源操作数中的成对的寄存器分配候选者中的每一个都当作对应着单个物理寄存器的普通单寄存器分配候选者，采用与普通单寄存器分配候选者相同的寄存器分配方法，与普通的单寄存器分配候选者一起参与寄存器分配，得到各自的物理寄存器。

本实施例中，步骤S2的步骤包括：

S21.从每条指令的第一个源操作数开始遍历各个源操作数，如果源操作数包含一个寄存器对，对该寄存器对进行合法性检查，判断该寄存器对中两个寄存器是否符合寄存器对使用规则，若不符合，判定需要修正，转入执行步骤S22；

S22.获取指令入口处各寄存器以及寄存器对的空闲状态；

S23.判断需要修正的寄存器对中错误使用寄存器的位置，根据错误使用寄存器的位置以及各寄存器在指令入口处的空闲状态、替换寄存器集合的状态选取替换寄存器对当前各错误使用寄存器进行修正，替换寄存器集合用于存放已用于替换的替换寄存器。

本实施例在处理每一条指令之前，先进行该指令入口处的寄存器和寄存器对空闲状态分析，进行寄存器对修正分配时，由于指令可以具有多个源操作数，且一个寄存器可能在指令的不同源操作数中多次出现，修正后面的源操作数寄存器对时优先重复利用前面的源操作数寄存器对的结果来替换相同的错误使用寄存器，可以减少需要在被处理指令前插入的数据传送指令的数量，被替换出来的寄存器如果在指令入口处变得空闲，则作为其他替换寄存器的候选者，可以在减少冗余的寄存器溢出的同时保证寄存器对的使用正确。

对于源操作数寄存器对，举例来说，处理一个寄存器对(如A:B)时，最坏的情况即是A、B均不符合使用规则(不是由两个连号的奇偶号寄存器构成)，需要同时用C:D两个寄存器来进行修正替换，该情况下需要先用2条访存指令分别把C和D中的值临时保存到存储器，在被处理的指令之前，用2条传送指令再分别把A和B的值复制到C和D中，在被处理的指令之后再用2条访存指令分别从存储器中恢复C和D原来的值，总共需要6条指令(忽略访问存储器需要大的存储器偏移量时的地址偏移量设置指令)，在对A、B修正时，如果能够找到不需要保存的C或D，就能够减少访存指令，同时还能免除设置相应的大存储器地址偏移量的指令；如果能够找到已经使用过的C或D，则可以减少传送指令。本实施例通过每次对不符合寄存器对使用规则的寄存器进行替换修正时，将替换寄存器存放到一个对应的替换寄存器集合，每次根据替换寄存器集合的动态情况、指令入口处的寄存器空闲情况和使用情况挑选替换寄存器，若存在已使用的源操作数寄存器对，条件满足时优先使用同一指令中前面的源操作数寄存器对的替换寄存器替换后面相同的错误使用寄存器，可以极大的减少传送指令。

本实施例中，步骤S23的步骤包括：判断源操作数寄存器对是否是由两个连号的奇偶号寄存器构成，如果源操作数中的两个寄存器序号均不符合，则判定需要全部替换源操作数寄存器对的两个寄存器，使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正；如果源操作数寄存器对中的左位寄存器或右位寄存器的序号不符合，则判定需要替换源操作数中的左位寄存器或右位寄存器，使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正；如果源操作数寄存器对中的两个寄存器序号不匹配，则判定需要替换源操作数寄存器对中的任意一个寄存器，使用第三修正模式对源操作数中任意一个寄存器进行修正，如果源操作数中仅含单个寄存器，使用第四修正模式对源操作数寄存器进行修正。

如图2所示，本实施例对于要进行修正处理的源操作数，按照不同的处理模式采用不同的启发式优化方法进行处理，根据寄存器对须由两个连号的奇偶号寄存器构成这个基本要求，具体设置如下五种可能的修正处理模式：(A)源操作数中的两个寄存器序号都错误，(B)源操作数中的左位寄存器序号错误，(C)源操作数中的右位寄存器序号错误，(D)源操作数寄存器对中的两个寄存器序号不匹配，(E)源操作数仅含单个寄存器；上述寄存器序号错误为寄存器的编号不符合其所在的源操作数对寄存器编号的奇(或偶)号规则要求。各修正模式(A、B、C、D、E)分别对应一种修正处理方式(A1～A5)，其中B、C模式对应的处理方式原理相同，即A修正模式对应为第一修正模式，B、C模式对应为第二修正模式，D模式对应为第三修正模式，E模式对应为第四修正模式，在处理过程中，B、C、D三种处理模式可以根据实际状态转换成处理模式A。

本实施例中，使用第一修正模式(A)对源操作数寄存器对中的两个寄存器进行修正时，步骤包括：根据需要修正的寄存器对中两个目标错误使用寄存器所分别对应的替换寄存器集合的状态、指令入口处各寄存器的空闲状态查找一个用于替换的寄存器对，使用查找到的寄存器对分别替换两个目标错误使用寄存器；查找一个用于替换的寄存器对的步骤包括：

a)从两个错误使用寄存器各自的所述替换寄存器集合中各取一个寄存器凑成一个合法寄存器对，若查找失败，转入执行步骤b)，否则转入执行步骤f)；

b)建立满足下述条件的寄存器对集合：寄存器对中其中一个寄存器在当前要被替换的一个寄存器的替换寄存器集合中，且符合所在源操作数的位置模式对寄存器序号的要求、另一个寄存器在指令入口处空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤c)；

c)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都空闲。然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤d)；

d)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的一个寄存器不空闲、另一个寄存器空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤e)；

e)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都不空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，然后转入执行步骤f)；

f)由当前查找到的寄存器对作为所述用于替换的寄存器对输出。

如上述示例，若处理一个寄存器对A:B需要用C:D来替换时，如果能够找到不需要保存的C或D，就能够减少访存指令，同时免除设置相应的大存储器地址偏移量的指令；如果能够找到已经使用过的C或D，可以减少传送指令；如果一对中只需要处理一个，相应的指令数量就可以再减半。本实施例利用上述特性，当需要对寄存器对中两个寄存器均不符合寄存器对使用规则时，按照两个寄存器的替换寄存器集合的动态情况、指令入口处的寄存器空闲情况和使用情况挑选替换寄存器，在处理指令各源操作数的过程中挑选替换寄存器时，按优先级依次考虑已经获得的替换结果寄存器、包含替换结果寄存器的半空闲寄存器对、空闲寄存器对、半空闲寄存器对、非空闲寄存器对的顺序来进行挑选，能够减少需要在被处理指令前插入的数据传送指令的数量，从而尽可能地减少对新的寄存器的需求。

本实施例中，使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正的具体步骤包括：

Sa1.将当前需要修正的寄存器对中左寄存器rL和右寄存器rR都添加到错误使用寄存器ErrRegSet中；

Sa2.从左寄存器rL和右寄存器rR各自对应的替换寄存器集合中分别找一个能够构成合法寄存器对的寄存器Rx和Ry并形成寄存器对RP；

Sa3.判断源操作数寄存器对RP是否存在，如果存在，将寄存器对RP中两个寄存器添加至替换寄存器集合中，执行两次替换操作以将寄存器对RP替换出当前需要修正的寄存器对，否则转到执行步骤Sa4；

Sa4.判断指令入口处是否有SLI半闲对，SLI半空闲对为在指令入口处寄存器对中一个寄存器空闲、另一个寄存器不空闲，如果有则转入执行步骤Sa5，否则转入执行步骤Sa7；

Sa5.定义一个SLI半空闲对的形式为Rx:Ri或Ri:Rx，其中Rx为不空闲的寄存器，转入执行步骤Sa6；

Sa6.Sa6.查找是否存在一个所述SLI半闲对满足其中的Rx在错误寄存器对中位模相同的Rm的替换寄存器集合中，其中Rm为在错误寄存器对中与Rx位置相同的寄存器，如果存在，将所述SLI半闲对的两个寄存器分别添加至所述替换寄存器集合中，并执行一次数据传送以及两次替换操作以将所述SLI半闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa7；

Sa7.判断是否有SLI空闲对，SLI空闲对为在指令入口处寄存器中两个寄存器均空闲，如果有，将SLI空闲对的两个寄存器分别添加至替换寄存器集合中，并执行两次数据传送以及两次替换操作以将SLI空闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa8；

Sa8.判断是否有SLI半闲对，如果有转到Sa9；

Sa9.排除由所有SLI半空闲对所构成的集合SH中所有含源变量集合内容的对，完成后判断集合SH是否为非空集合，如果是，取集合SH中编号最大的半空闲寄存器对作为替换寄存器对，执行两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将替换寄存器对中不空闲的寄存器Rx添加至需要保护寄存器中原有数据的被保护寄存器集合中，否则转入执行步骤Sa10；

Sa10.用所有不空闲对构成第二集合，从第二集合中删除所有含源变量或替换寄存器集合元素的寄存器对后，取其中编号最大的半空闲寄存器对作为替换寄存器对，执行两次数据传输以及两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将替换寄存器对中两个寄存器均添加至被保护寄存器集合中。

本实施例中B或C模式对应为第二修正模式，使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正的步骤包括：

Sb1.选取一个与正确使用寄存器能够构成寄存器偶对的寄存器作为目标替换寄存器，正确使用寄存器为当前需要修正的寄存器对中编号正确的寄存器；

Sb2.判断步骤Sb1选取的目标替换寄存器是否在总替换寄存器集合中，如果不在转入执行步骤Sb3，如果在且已是当前需要修正的寄存器对中错误使用寄存器R的替换寄存器，将目标替换寄存器添加至替换寄存器集合中，并执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器，如果在且目标替换寄存器已是其他错误使用寄存器的替换寄存器，转入执行步骤Sb4；

Sb3.判断目标替换寄存器是否在指令入口处活跃，如果是转入执行步骤Sb5，否则将当前需要修正的错误使用寄存器的数据传递给目标替换寄存器后，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb4.转入执行使用第一修正模式对各错误使用寄存器进行修正步骤，以使用第一修正模式对当前需要修正的错误使用寄存器进行修正；

Sb5.判断目标替换寄存器是否属于指令源变量集合中的元素，如果是转入执行步骤Sb6，否则将目标替换寄存器分别添加至替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb6.转入执行使用第一修正模式对各错误使用寄存器进行修正步骤，以使用第一修正模式对当前需要修正的错误使用寄存器进行修正。

本实施例在处理B或C类的第二修正模式时，通过先确定与编号正确的寄存器构成寄存器偶对的寄存器作为替换寄存器PRB，然后根据PRB的情况利用上述步骤进行启发式处理，优先选取已经使用过的替换寄存器以减少修正处理所需插入的新的数据传送指令、使用在指令入口处空闲的寄存器以减少修正处理所需插入的新的起保护现场作用的访存指令，根据替换寄存器的使用状态以及在指令入口处的活跃状态还可以转化为A类进行修正处理，可以实现寄存器对中左位或右位寄存器的修正，最终得到符合寄存器对使用规则的寄存器对。

本实施例上述D类修正模式对应为第三修正模式，使用第三修正模式对源操作数中任意一个寄存器进行修正的步骤包括：

Sc1.为需要修正的寄存器中左位寄存器选取对应的左位替换寄存器PRB_L，以及为右位寄存器选取对应的右位替换寄存器PRB_R；

Sc2.判断左位替换寄存器PRB_L是否已是对应错误使用寄存器(左位寄存器)的替换寄存器，如果是，将左位替换寄存器PRB_L添加至替换寄存器集合中，并执行一次替换操作以将左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc3；

Sc3.判断右位替换寄存器PRB_R是否已是对应错误使用寄存器(右位寄存器)的替换寄存器，如果是，将右位替换寄存器PRB_R添加至替换寄存器集合中，并执行一次替换操作以将所示右位替换寄存器PRB_R替换出当前需要修正的右位寄存器，否则转入执行步骤Sc4；

Sc4.判断左位替换寄存器PRB_L是否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的右位寄存器的数据传递给左位替换寄存器PRB_L后，执行一次替换操作以将左位替换寄存器PRB_L替换出需要修正的左位寄存器，否则转入执行步骤Sc5；

Sc5.判断右位替换寄存器PRB_R否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的左位寄存器的数据传递给右位替换寄存器PRB_R后，执行一次替换操作以将右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转到Sc6；

Sc6.判断左位替换寄存器PRB_L是否同时满足不在替换寄存器集合中、在指令入口处活跃且不在源变量集合中，如果是，将左位替换寄存器PRB_L分别添加至替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc7；

Sc7.判断右位替换寄存器PRB_R是否同时满足不在替换寄存器集合、在指令入口处活跃且不在源变量集合中，如果是，将右位替换寄存器PRB_R分别添加至替换寄存器集合中以及需要保护原有数据的被保护寄存器集合SetBeProt中，执行一次替换操作以将右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转入执行步骤Sc8；

Sc8.转入执行使用第一修正模式对各错误使用寄存器进行修正步骤，以使用第一修正模式对当前需要修正的错误使用寄存器进行修正。

本实施例对于D类修正模式，先假定其中的任意一个寄存器的编号不正确，然后确定各自相应的替换寄存器PRB，根据两个PRB的情况利用上述步骤进行启发式处理，根据替换寄存器的使用状态以及在指令入口处的活跃状态可以转化为A类修正模式，可以实现寄存器对中两个寄存器序号不匹配的修正，最终得到符合寄存器对使用规则的寄存器对。

本实施例步骤S23中，如果源操作数为仅含单个寄存器，对应为E类修正模式，修正时，判断对应源操作数中的目标单寄存器是否已经在同一指令之前的源操作数中分配过至少一个替换寄存器，如果是直接使用先前使用的替换寄存器替换目标单寄存器。

通过本实施例上述分配方法，能够自动处理某个单寄存器分配候选者在某些源操作数寄存器对中位于左位但在另外一些源操作数寄存器对中位于右位的情况，从而提升在源操作数中使用变量方面的灵活性。

本实施例进行寄存器对分配时，具体将源操作数涉及的寄存器对分配分成两个阶段，一是普通单寄存器分配阶段，二是源操作数寄存器对修正阶段，在普通单寄存器分配阶段，将源操作数中的成对的寄存器分配候选者中的每一个都当作对应着单个物理寄存器的普通单寄存器分配候选者，采用与普通单寄存器分配候选者相同的寄存器分配方法，与普通的单寄存器分配候选者一起参与寄存器分配，得到各自的物理寄存器；在源操作数寄存器对修正阶段，对于每一条指令，如果它至少有一个源操作数涉及寄存器对，则对该指令的各源操作数进行寄存器对合法性检查，对于不满足硬件关于寄存器对的使用规则的源操作数中的寄存器对，先确定其所需的修正处理模式，分析其所需的修正处理模式并确定为A、B、C、D、E中的一种，再采用上述启发式优化方法将它们替换成符合规则要求的寄存器对，在这个过程中，仅涉及单个寄存器的源操作数中的寄存器可能连带地需要被替换，其中对指令序列中的每条指令处理时，步骤包括：

分析系统的各个寄存器和寄存器对在指令入口处的空闲状况，为单个寄存器确定是否空闲的标志，为寄存器对确定空闲类型；

从指令的第一个源操作数开始遍历它的各个源操作数，如果某个源操作数需要进行修正处理，则按前面步骤确定的源操作数修正处理模式进行相应的修正处理；

在指令的处理过程中，同一个寄存器在不同的源操作数中可能会被不同的寄存器替换。对于每个被替换的寄存器，将用来替换它的寄存器存放到一个对应的替换寄存器集合，为后面对后续源操作数的优化处理提供信息。

本实施例存储有计算机程序的计算机可读存储介质，计算机程序执行时实现如上述的寄存器对分配方法。

以下以在具体应用实施例中基于面向对象语言采用上述方法实现上述面向指令源操作的寄存器对修正分配为例，对本发明进行进一步说明。

在面向对象语言软件中，数据和相关的功能模块都封装在类中，本发明方法涉及的实施内容可封装成一个源操作数寄存器对修正分配类，把进行源操作数寄存器对修正处理所需的数据都作为这个类的数据成员，所需的各子方法都作为这个类的成员函数。由于本发明方法是针对指令源操作数寄存器对分配优化的问题，所以假定本方法所需的基本信息都已经准备好，主要有：

处理器体系结构的寄存器资源信息保存在相应的体系结构类对象中，包括能够出现在寄存器对中的寄存器的编号构成的集合、寄存器对与寄存器的映射关系、寄存器对的编号构成的集合等等。

各指令的基本信息和源操作数信息(包括指令所有源操作数涉及的物理寄存器变量)保存在相应的指令类对象中。

各指令入口处的活跃向量保存在活跃向量数组中。每条指令有一个入口活跃向量，从该向量可以获知代码已经使用的物理寄存器中哪些寄存器在该指令的入口处是活跃的。

由于单寄存器分配可以用任意一种已知的寄存器分配方法来处理，所以这里不赘述其具体实施方式。下面的实施过程只涉及到与本发明关于源操作数寄存器对修正直接相关的内容。

本实施例中定义有：

寄存器用例(RA)：一个寄存器在指令中的某一次应用。一个寄存器在一条指令的不同源操作数中可能有多个用例，这些寄存器用例都是同一个数据。

配对寄存器(PRA)：与某个寄存器写在一对中的另外一个寄存器。例如，在“Rx:Ry”中，Rx是Ry的配对寄存器，反之Ry也是Rx的配对寄存器。

错误寄存器对：位于指令的源操作数部分中，它所包含的两个寄存器在单寄存器分配阶段得到，但它们不满足连号奇偶寄存器对这个规则的要求。

替换寄存器(PRB)：用于替换指令某个源操作数中的某个寄存器的另外一个寄存器。

左位寄存器：指位于要处理的寄存器对的左边的那个寄存器。例如，在“Rx:Ry”这个寄存器对中，Rx就是左位寄存器。

右位寄存器：指位于要处理的寄存器对的右边的那个寄存器。例如，在“Rx:Ry”这个寄存器对中，Ry就是右位寄存器。

替换方案(rep)：修正某指令的一个源操作数所需要对该指令以及指令序列进行的操作的描述。

以及定义数据结构包括：

指令中最多可能出现的RA数量：这是由处理器指令集所决定的值。如果不能确定，可设置为一个较大的值，例如指令的位数。

指令中各源操作数RA对应的寄存器对位置模式数组：数组元素的下标代表RA在指令中的序号，值为该RA在其所在的源操作数寄存器对中的位置模式。该数组是一个一维数组，下面也简写为raPosModes。

RA在寄存器对中的可能位置模式枚举集合：rapPosForOddReg(RA在寄存器对中是左位寄存器)；rapNotInPair(RA没有在一个寄存器对中)；rapPosForEvenReg(RA在寄存器对中是右位寄存器)。

寄存器对修正模式枚举集合：pstUnknown(表示未确定)；pstBothPosModeError(表示两个RA对应的寄存器都不符合位置模式要求)；pstLeftPosModeError(表示左边的RA对应的寄存器不符合位置模式要求)；pstRightPosModeError(表示右边的RA对应的寄存器不符合位置模式要求)；pstIllegalPair(表示两个寄存器的编号都符合位置模式对奇偶性的要求，但两者不连号)；pstBothPosModeRight(表示一种过渡状态)；pstCorrect(表示正确的寄存器对)。

寄存器空闲状态数组：每个通用寄存器在数组中对应一个元素，其值可以为true或false，分别表示空闲或非空闲。

错误寄存器集合ErrRegSet：由指令的所有源操作数中所有被替换的寄存器构成的集合。

替换寄存器集合PrbSet：用于替换同一个源操作数寄存器的多个寄存器构成的集合。每一个被替换的寄存器都有一个对应的替换寄存器集合。

被保护寄存器集合SetBeProt：替换寄存器集合中需要保护其原有数据的那些寄存器构成的集合。

指令入口处空闲寄存器集合IdleRegSet：由在指令入口处空闲的那些寄存器的编号构成的集合。

指令入口处空闲寄存器对集合IdleRPSet：由在指令入口处空闲的那些寄存器对的编号构成的集合。

指令入口处半闲寄存器对集合HalfIdleRPSet：由在指令入口处只有其中一个寄存器空闲的那些寄存器对的编号构成的集合。

指令入口处非空闲寄存器对集合NonIdleRPSet：由在指令入口处其中的两个寄存器都不空闲的那些寄存器对的编号构成的集合。

总PRB集合：在对一条指令源操作数处理的过程中用到的所有PRB构成的集合。

ProtRegs集合：对一条指令的所有源操作数进行修正过程中发现的要保护其内容到存储器的那些寄存器构成的集合。

本实施例对一条指令进行源操作数修正的总体处理流程如图3所示，具体步骤包括：

1)初始化针对指令进行源操作数寄存器对修正的相关数据，包括分析指令入口处的寄存器空闲状态和寄存器对的空闲状态。

2)判断指令是否还有要修正的源操作数，如果没有，跳转到第7)步执行，如果有，则执行下一步。

3)切换到下一个要处理的源操作数RA或RA对(即寄存器对)。

4)初始化处理1个源操作数时所需的相关数据。

5)修正当前源操作数，即根据源操作数的情况，替换其中的RA或RA对相关的寄存器。如图2所示，其中每一条路径对应一种处理模式。

6)跳转到第2)步。

7)重新分析并更新当前指令的源操作数涉及的变量。

8)添加将ProtRegs中的寄存器的内容保护到存储器的指令到前插指令队列首，加相应的恢复其内容的指令到原寄存器的指令到后插指令队列尾。

9)将所有的前插指令插入到当前被处理指令之前，将所有的后插指令插入到当前被处理指令之后。

本实施例每条指令中每个源操作数的寄存器对各对应一个修正处理模式(A、B、C、D、E)，确定修正处理模式步骤在单寄存器分配后就要先完成，对指令的源操作数寄存器对信息及其修正处理模式分析时，从指令的第一个源操作数开始，依次遍历指令的每一个源操作数，如果源操作数包含1个寄存器对，按如下情况进行处理：

如果其中的两个寄存器的编号满足寄存器偶对的规则要求，则将处理模式设置为pstCorrect。

如果其中的两个寄存器的编号都不满足位置模式对寄存器编号的要求(即本来应该为奇/偶号的寄存器，但实际得到的是偶/奇号寄存器)，则将处理模式设置为pstBothPosModeError。

如果仅左位寄存器的编号不满足位置模式对寄存器编号的要求，则将处理模式设置为pstLeftPosModeError。

如果仅右位寄存器的编号不满足位置模式对寄存器编号的要求，则将处理模式设置为pstRightPosModeError。

如果两个寄存器都满足位置模式对奇偶编号的要求，但两者的编号不是相连的，则将处理模式设置为pstIllegalPair。

本实施例中对指令入口处的寄存器空闲状态分析的步骤包括：

指令入口处的寄存器空闲状态分析的目的是获取指令入口处的各个寄存器是否空闲的标志及空闲寄存器集合，分析过程中要用到已知数据流分析的结果中关于活跃向量的内容。在每条指令对应的入口活跃向量中，函数代码中用到的每个变量各占1位，如果某个变量在该指令入口处活跃，则对应的位的值为true，否则为false。具体分析方法是遍历体系结构中能够出现在寄存器对中的所有的通用寄存器，对每个寄存器，进行如下处理：如果寄存器在指令入口活跃向量中对应了1位且这一位的值为true，则设置为不空闲，否则，设置为空闲。在遍历完成之后，将IdleRegSet清空，并将遍历过程中所确定的空闲寄存器的编号都添加到IdleRegSet中。

对指令入口处的寄存器对空闲状态进行分析的步骤包括：

先将IdleRPSet、HalfIdleRPSet、NonIdleRPSet三个集合都清空，然后遍历所有寄存器对，对每个通用寄存器对进行下面的处理：

如果寄存器对中的两个寄存器都空闲(即都在IdleRegSet中)，则将寄存器对的编号添加到IdleRPSet中；

如果寄存器对中的两个寄存器都不空闲(即都不在IdleRegSet中)，则将寄存器对的编号添加到NonIdleRPSet中；

如果寄存器对中的两个寄存器只有一个空闲(即只有一个在IdleRegSet中)，则将寄存器对的编号添加到HalfIdleRPSet中。

如图4所示，本实施例修正处理模式A的处理具体步骤为：

S1:将寄存器对中的两个寄存器rL和rR都添加到空集合ErrRegSet中，然后转到S2；

S2:尝试从rL和rR各自对应的替换寄存器集合中分别找一个能够构成合法寄存器对的寄存器Rx和Ry形成寄存器对RP，然后转到S3；

S3:判断RP是否存在，如果存在，则转到A8对应的子过程继续处理，否则转到S4；

S4:判断是否有SLI半闲对(即HalfIdleRPSet是否有内容)，如果有则转到S5，否则转到S7；

S5:设一个新的寄存器对的形式为Rx:Ri或Ri:Rx，其中不空闲的是Rx，转到S6；

S6:尝试找一个这样的SLI半闲对RP，其中的Rx在错误寄存器对(ERP)中位模相同的寄存器Rm的PRB集合，如果存在这样的RP，则转到A9对应的子过程去继续处理，否则转到S7。

S7:判断是否有SLI空闲对(即IdleRPSet是否有内容)，如果有，转到A10对应的子过程去继续处理，否则转到S8；

S8:判断是否有SLI半闲对，如果有转到S9；

S9:设Rx为SLI半闲对中不空闲的那个寄存器，然后转到S10；

S10:用所有SLI半空闲对构成集合SH，然后转到S11；

S11:排除SH中所有含源变量集合内容的对，判断是否SH为非空集合，如果是，转到A11对应的子过程去继续处理，否则转到S12。

S12:用所有不空闲对构成集合SH，转到A12对应的子过程去继续处理。

如图5所示，本实施例修正处理模式B或C的处理步骤为：

S1:令错误寄存器为R。如果是处理模式2，则R为左位寄存器，如果是处理模式3，则R为右位寄存器。然后根据R的配对寄存器PRA得到R的替换寄存器PRB。如果PRB还不在总PRB集合，转到S2；如果PRB已是R的PRB，转到A15对应的过程去继续处理；如果PRB已是其他R的PRB，转到S3。

S2:判断PRB是否在指令入口处活跃。如果是，转到S4，否则转到A13对应的过程去继续处理。

S3:修改处理模式为A，然后转到A1对应的过程去继续处理。

S4:判断PRB是否属于源变量集合中的元素。如果是则转到S5，否则转到A14对应的过程去继续处理。

S5:修改处理模式为A，转到A1对应的过程去继续处理。

如图6所示，本实施例中修正处理模式D下的处理步骤具体为：

S1:令左位寄存器的PRB为PRB_L，令右位寄存器的PRB为PRB_R。然后转到S2。

S2:判断是否PRB_L已是相应R的PRB，如果是，转到A15对应的过程去继续处理，否则转到S3。

S3:判断是否PRB_R已是相应R的PRB，如果是，转到A15对应的过程去继续处理，否则转到S4。

S4:判断是否PRB_L同时满足如下条件:不在总PRB集合，且在SLI中不活跃。如果满足，则转到A13对应的过程去继续处理，否则转到S5。

S5:判断是否PRB_R同时满足如下条件:不总在PRB集合，且在SLI中不活跃，如果满足，则转到A13对应的过程去继续处理，否则转到S6。

S6:判断是否PRB_L同时满足如下条件:不在PRB集合，在SLI中活跃，不在源变量集合中。如果满足，则转到A14对应的过程去继续处理，否则转到S7。

S7:判断是否PRB_R同时满足如下条件:不在PRB集合，在SLI中活跃，不在源变量集合中。如果满足，则转到A14对应的过程去继续处理，否则转到S8。

S8:修改处理模式为A，转到A1对应的过程去继续处理。

本实施例中修正处理模式E时，具体如果对应源操作数中的单个寄存器已经在同一指令之前的源操作数中有过至少一个替换寄存器，则转到A15对应的过程去继续处理，否则结束对该源操作数的处理。

在进行实际的寄存器替换之前，本实施例具体涉及9个公共处理子过程，即上述A7～A15子过程，如图7所示，各过程具体为：

a)在A7代表的起点处开始，在S1步骤中将SetBeProt集合中的内容添加到ProtRegs中。然后转到A6对应的过程去继续处理；

b)在A8代表的起点处开始，执行步骤：

S1:将寄存器对RP中的两个寄存器添加到PrbSet集合中。转到S2。

S2:生成替换方案rep(2个替换操作)，然后转到A6对应的过程去继续处理。

c)在A9代表的起点处开始，执行步骤：

S1:将寄存器对RP中的两个寄存器添加到PrbSet集合中。转到S2。

S2:生成替换方案rep(1个将数据从传送被替换寄存器Rn传送到替换寄存器Ri的操作，2个替换操作)，然后转到A6对应的过程去继续处理。

d)在A10代表的起点处开始，执行步骤：

S1:取编号最大的空闲寄存器对作为RP。转到S2。

S2:将RP中的两个寄存器添加到PrbSet集合中。转到S3。

S3:生成替换方案rep(2个将数据从被替换寄存器传送到替换寄存器的操作，2个替换操作)，然后转到A6对应的过程去继续处理。

e)在A11代表的起点处开始，执行步骤：

S1:取SH中编号最大的半闲寄存器对作为RP。转到S2。

S2:将RP中的两个寄存器添加到PrbSet集合中。转到S3。

S3:生成替换方案rep(2个将数据从被替换寄存器传送到替换寄存器的操作，2个替换操作)，转到S4。

S4:将Rx添加到SetBeProt集合中。然后转到A7对应的过程去继续处理。

f)在A12代表的起点处开始，执行步骤：

S1:从SH中删除所有含指令源变量或PRB集合元素的寄存器对。转到S2。

S2:取SH中编号最大的半闲寄存器对作为RP。转到S3。

S3:将RP中的两个寄存器添加到PrbSet集合中。转到S4。

S4:生成替换方案rep(2个将数据从被替换寄存器传送到替换寄存器的操作，2个替换操作)，转到S5。

S5:将RP中的两个寄存器添加到SetBeProt集合中，然后转到A7对应的过程去继续处理。

g)在A14代表的起点处开始，执行下面的步骤：

S1:将寄存器R添加到集合SetErr中。转到S2。

S2:将PRB添加到集合PrbSet中。转到S3。

S3:生成替换方案rep(1个将R传送到PRB的操作，1个替换操作)。转到S4。

S4:将PRB添加到SetBeProt集合中。然后转到A7对应的过程去继续处理。

h)在A13代表的起点处开始，执行步骤：

S1:将寄存器R添加到集合SetErr中，转到S2。

S2:将PRB添加到集合PrbSet中，转到S3。

S3:生成替换方案rep(1个将R传送到PRB的操作，1个替换操作)，转到S4，然后转到A6对应的过程去继续处理。

i)在A15代表的起点处开始，执行步骤：

S1:将寄存器R添加到集合SetErr中，转到S2。

S2:将PRB添加到集合PrbSet中，转到S3。

S3:生成替换方案rep(1个替换操作)，转到S4，然后转到A6对应的过程去继续处理。

上面各个步骤中提及的替换操作均是指：在源操作数的代码中用替换寄存器(PRB)代替相应的被替换寄存器的操作。

本实施例在寄存器替换方案生成之后需要进行一些数据的更新，如图8所示，步骤具体如下：

S1：修改ErrRegSet内的各寄存器的源空闲状态。对于ErrRegSet中的任意一个寄存器，如果在指令中不再把它作为源数据，并且在指令的出口处(即下一条指令的入口处)它也不活跃，则将其在指令入口处的活跃向量中所对应的位的值改成false。ErrRegSet内的所有寄存器处理完毕后，转到S2；

S2:在指令入口处的活跃向量中将PrbSet内的各寄存器设置为活跃，并将它们添加到指令的总PRB集合，然后转到S3；

S3:根据更新后的指令入口处活跃向量，更新所有寄存器和寄存器对的空闲状态。然后转到S4；

S4:按rep的内容，添加数据传送指令到前插指令队列尾，记录各要被替换的RA对应的PRB，然后转到S5；

S5:按rep的内容，在指令中替换相应的RA，记录各要被替换的RA对应的PRB。设置RA相应的标识为已替换状态。结束处理。

上述只是本发明的较佳实施例，并非对本发明作任何形式上的限制。虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明。因此，凡是未脱离本发明技术方案的内容，依据本发明技术实质对以上实施例所做的任何简单修改、等同变化及修饰，均应落在本发明技术方案保护的范围内。

Claims (10)

1.一种面向指令源操作数的寄存器对分配方法，其特征在于，步骤包括：

S1.初始分配：分别将待处理指令中包括寄存器对的所有源操作数所包含的两个符号寄存器均作为单寄存器分配候选者进行独立的寄存器分配；

S2.修正分配：依次获取各条指令进行寄存器修正分配，如果指令中存在至少一个以上的源操作数涉及寄存器对，对指令中各源操作数依次进行寄存器对合法性检查，并根据检查结果将寄存器对中不符合使用规则的错误使用寄存器使用替换寄存器进行替换，所述替换寄存器根据各寄存器的使用状态以及在指令入口处的空闲状态进行选取，条件满足时优先使用同一指令中前面的源操作数寄存器对的替换寄存器替换后面相同的所述错误使用寄存器，被替换出来的寄存器若在指令入口处变为空闲状态则作为同一指令的后续其他源操作数中寄存器对的替换寄存器。

2.根据权利要求1所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述步骤S1中，具体将源操作数中成对的寄存器分配候选者中的每一个都当作对应着单个物理寄存器的独立单寄存器分配候选者，并与其他单寄存器分配候选者一起采用相同的寄存器分配方式分配各自的物理寄存器。

3.根据权利要求1所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述步骤S2的步骤包括：

S21.从每条指令的第一个源操作数开始遍历各个源操作数，如果源操作数包含一个寄存器对，对该寄存器对进行合法性检查，判断该寄存器对中两个寄存器是否符合寄存器对使用规则，若不符合，判定需要修正，转入执行步骤S22；

S22.获取指令入口处各寄存器以及寄存器对的空闲状态；

S23.判断需要修正的寄存器对中错误使用寄存器的位置，根据所述错误使用寄存器的位置以及各寄存器在指令入口处的空闲状态、替换寄存器集合的状态选取替换寄存器对当前各所述错误使用寄存器进行修正，所述替换寄存器集合用于存放已用于替换的替换寄存器。

4.根据权利要求3所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述步骤S23的步骤包括：判断源操作数寄存器对是否是由两个连号的奇偶号寄存器构成，如果源操作数寄存器对中的两个寄存器序号均不符合，则判定需要全部替换源操作数寄存器对的两个寄存器，使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正；如果源操作数寄存器对中的左位寄存器或右位寄存器的序号不符合，则判定需要替换源操作数中的左位寄存器或右位寄存器，使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正；如果源操作数寄存器对中的两个寄存器序号不匹配，则判定需要替换源操作数寄存器对中的任意一个寄存器，使用第三修正模式对源操作数中任意一个寄存器进行修正，如果源操作数中仅含单个寄存器，使用第四修正模式对源操作数寄存器进行修正。

5.根据权利要求4所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正时，根据需要修正的寄存器对中两个错误使用寄存器所分别对应的所述替换寄存器集合的状态、指令入口处各寄存器的空闲状态查找一个用于替换的寄存器对，使用查找到的寄存器对分别替换两个错误使用寄存器；所述查找一个用于替换的寄存器对的步骤包括：

a)从两个错误使用寄存器各自的所述替换寄存器集合中各取一个寄存器凑成一个合法寄存器对，若查找失败，转入执行步骤b)，否则转入执行步骤f)；

b)建立满足下述条件的寄存器对集合：寄存器对中其中一个寄存器在当前要被替换的一个寄存器的替换寄存器集合中，且符合所在源操作数的位置模式对寄存器序号的要求、另一个寄存器在指令入口处空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤c)；

c)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都空闲。然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤d)；

d)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的一个寄存器不空闲、另一个寄存器空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，若挑选到转入执行步骤f)，若失败转入执行步骤e)；

e)建立满足下述条件的寄存器对集合：在指令的入口处寄存器对中的两个寄存器都不空闲，然后从当前建立的所述寄存器对集合中挑选一个寄存器对，然后转入执行步骤f)；

f)由当前查找到的寄存器对作为所述用于替换的寄存器对输出；

6.根据权利要求5所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述使用第一修正模式对源操作数寄存器对中的两个寄存器进行修正的具体步骤包括：

Sa1.将当前需要修正的寄存器对中左寄存器rL和右寄存器rR都添加到错误使用寄存器集合ErrRegSet中；

Sa2.从所述左寄存器rL和右寄存器rR各自对应的替换寄存器集合中分别找一个能够构成合法寄存器对的寄存器Rx和Ry并形成寄存器对RP；

Sa3.判断所述寄存器对RP是否存在，如果存在，将所述寄存器对RP中两个寄存器添加至所述替换寄存器集合中，执行两次替换操作以将所述寄存器对RP替换出当前需要修正的寄存器对，否则转到执行步骤Sa4；

Sa4.判断指令入口处是否有SLI半闲对，所述SLI半空闲对为在指令入口处寄存器对中一个寄存器空闲、另一个寄存器不空闲，如果有则转入执行步骤Sa5，否则转入执行步骤Sa7；

Sa5.定义一个所述SLI半空闲对的形式为Rx:Ri或Ri:Rx，其中Rx为不空闲的寄存器，转入执行步骤Sa6；

Sa6.查找是否存在一个所述SLI半闲对满足其中的Rx在错误寄存器对中位模相同的Rm的替换寄存器集合中，其中Rm为在错误寄存器对中与Rx位置相同的寄存器，如果存在，将所述SLI半闲对的两个寄存器分别添加至所述替换寄存器集合中，并执行一次数据传送以及两次替换操作以将所述SLI半闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa7；

Sa7.判断是否有SLI空闲对，所述SLI空闲对为在指令入口处寄存器中两个寄存器均空闲，如果有，将所述SLI空闲对的两个寄存器分别添加至所述替换寄存器集合中，并执行两次数据传送以及两次替换操作以将所述SLI空闲对替换出当前需要修正的寄存器对，否则转入执行步骤Sa8；

Sa8.判断是否有所述SLI半闲对，如果有转到Sa9；

Sa9.排除由所有所述SLI半空闲对所构成的集合SH中所有含源变量集合内容的对，完成后判断所述集合SH是否为非空集合，如果是，取所述集合SH中编号最大的半空闲寄存器对作为替换寄存器对，执行两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将所述替换寄存器对中不空闲的寄存器Rx添加至需要保护寄存器中原有数据的被保护寄存器集合中，否则转入执行步骤Sa10；

Sa10.用所有不空闲对构成第二集合，从所述第二集合中删除所有含源变量或替换寄存器集合元素的寄存器对后，取其中编号最大的半空闲寄存器对作为替换寄存器对，执行两次数据传输以及两次替换操作以将当前替换寄存器对替换出当前需要修正的寄存器中，并将所述替换寄存器对中两个寄存器均添加至所述被保护寄存器集合中。

7.根据权利要求4～6中任意一项所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述使用第二修正模式对源操作数中左位寄存器或右位寄存器进行修正的步骤包括：

Sb1.选取一个与正确使用寄存器能够构成寄存器偶对的寄存器作为目标替换寄存器，所述正确使用寄存器为当前需要修正的寄存器对中编号正确的寄存器；

Sb2.判断所述步骤Sb1选取的目标替换寄存器是否在总替换寄存器集合中，如果不在转入执行步骤Sb3，如果在且已是当前需要修正的寄存器对中错误使用寄存器R的替换寄存器，将目标替换寄存器添加至所述替换寄存器集合中，并执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器，如果在且目标替换寄存器已是其他错误使用寄存器的替换寄存器，转入执行步骤Sb4；

Sb3.判断目标替换寄存器是否在指令入口处活跃，如果是转入执行步骤Sb5，否则将当前需要修正的错误使用寄存器的数据传递给目标替换寄存器后，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb4.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正；

Sb5.判断目标替换寄存器是否属于指令源变量集合中的元素，如果是转入执行步骤Sb6，否则将目标替换寄存器分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将目标替换寄存器替换出当前需要修正的错误使用寄存器；

Sb6.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正。

8.根据权利要求4～6中任意一项所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述使用第三修正模式对源操作数中任意一个寄存器进行修正的步骤包括：

Sc1.为需要修正的寄存器中左位寄存器选取对应的左位替换寄存器PRB_L，以及为右位寄存器选取对应的右位替换寄存器PRB_R；

Sc2.判断所述左位替换寄存器PRB_L是否已是对应错误使用寄存器的替换寄存器，如果是，将所述左位替换寄存器PRB_L添加至所述替换寄存器集合中，并执行一次替换操作以将所述左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc3；

Sc3.判断所述右位替换寄存器PRB_R是否已是对应错误使用寄存器的替换寄存器，如果是，将所述右位替换寄存器PRB_R添加至所述替换寄存器集合中，并执行一次替换操作以将所示右位替换寄存器PRB_R替换出当前需要修正的右位寄存器，否则转入执行步骤Sc4；

Sc4.判断所述左位替换寄存器PRB_L是否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的右位寄存器的数据传递给所述左位替换寄存器PRB_L后，执行一次替换操作以将所述左位替换寄存器PRB_L替换出需要修正的左位寄存器，否则转入执行步骤Sc5；

Sc5.判断所述右位替换寄存器PRB_R否同时满足不在总替换寄存器集合中且在指令入口处不活跃，如果是，将当前需要修正的左位寄存器的数据传递给所述右位替换寄存器PRB_R后，执行一次替换操作以将所述右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转到Sc6；

Sc6.判断所述左位替换寄存器PRB_L是否同时满足不在所述替换寄存器集合中、在指令入口处活跃且不在源变量集合中，如果是，将所述左位替换寄存器PRB_L分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合中，执行一次替换操作以将所述左位替换寄存器PRB_L替换出当前需要修正的左位寄存器，否则转入执行步骤Sc7；

Sc7.判断所述右位替换寄存器PRB_R是否同时满足不在所述替换寄存器集合、在指令入口处活跃且不在源变量集合中，如果是，将所述右位替换寄存器PRB_R分别添加至所述替换寄存器集合中以及需要保护原有数据的被保护寄存器集合SetBeProt中，执行一次替换操作以将所述右位替换寄存器PRB_R替换出需要修正的右位寄存器，否则转入执行步骤Sc8；

Sc8.转入执行所述使用第一修正模式对各错误使用寄存器进行修正步骤，以使用所述第一修正模式对当前需要修正的错误使用寄存器进行修正。

9.根据权利要求4～6中任意一项所述的面向指令源操作数的寄存器对分配方法，其特征在于，所述使用第四修正模式对源操作数寄存器进行修正时，具体判断对应源操作数中的目标单寄存器是否已经在同一指令之前的源操作数中分配过至少一个替换寄存器，如果是直接使用先前使用的替换寄存器替换目标单寄存器。

10.一种存储有计算机程序的计算机可读存储介质，所述计算机程序执行时实现如权利要求1～9中任意一项所述的方法。

Images