分区寄存器库的库指配

摘要

可通过识别操作数的可能的候选寄存器库把操作数指配给分区寄存器库内的物理寄存器。如果候选寄存器库之间存在冲突的话可在把操作数分配给候选寄存器库之前识别并解决。

权利要求

1.一种用于把操作数分配到寄存器库中的方法，所述方法包括：为所述操作数识别所有的候选寄存器库，所述识别包括：识别所述操作数的所有出现；

把每个出现分类到多个类中的一个中，每类具有至少一个关联的寄存器库；

比较关联的寄存器库集合的相交的类；以及基于关联的寄存器库集合的所述相交产生交集；

确定在所述候选寄存器库之间是否存在冲突；

解决任何冲突；以及

把所述操作数分配给所述寄存器库，所述分配包括：确定操作数的单个出现是否作为指令的两个操作数出现；

确定单个算术逻辑单元指令的两个操作数是否出现在单个通用寄存器库中；

通过采用符号寄存器冲突图解决在操作数的单个出现作为指令的两个操作数出现时的冲突；以及通过采用图着色解决在单个算术逻辑单元指令的两个操作数出现在单个通用寄存器库中时的冲突。

2.根据权利要求1所述的方法，所述确定包括：确定所述交集是否为空集合；

如果所述交集集合是空的话进行所述解决任何冲突；以及如果所述交集集合不为空集合的话进行所述分配。

3.根据权利要求1所述的方法，所述解决任何冲突包括：把所述交集拆分成最小的无冲突部分；以及增加移动以经过所述无冲突部分传递值。

4.根据权利要求3所述的方法，所述拆分包括：为所述操作数的所有出现构建规定-使用图；

基于一组预定的条件来识别所述规定-使用图中的所有冲突传送边缘；以及对所述规定-使用图进行分区。

5.根据权利要求4所述的方法，所述规定-使用图包括：引用所述操作数的每个相应出现的多个节点；以及表示每个相应出现的所述规定d由指令u所用的规定-使用边缘，其中，所述冲突传送边缘可以是规定-使用图中的所述边缘，其两端满足一个或多个以下条件：1)所述边缘的尾部是是输入/输出规定类型并且相同所述边缘的首部是输入/输出使用类型；2)所述边缘的尾部是输入/输出规定类型并且相同所述边缘的首部的前导是算术逻辑单元规定；3)所述边缘的首部是输入/输出使用类型且相同所述边缘的尾部的后续是算术逻辑单元使用。

6.根据权利要求3所述的方法，所述增加包括：采用最小割集算法增加移动。

7.根据权利要求1所述的方法，所述分配包括：在不存在任何冲突的时候采用图着色。

8.一种用于把操作数分配到寄存器库中的装置，包括：识别操作数的所有候选寄存器库的部件，所述识别包括：识别所述操作数的所有出现；

把每个出现分类到多个类中的一个中，每类具有至少一个关联的寄存器库；

比较关联的寄存器库集合的相交的类；以及基于关联的寄存器库集合的所述相交产生交集；

如果所述候选寄存器库之间存在冲突的话解决所述冲突的部件；以及把所述操作数分配给寄存器库的部件，所述分配包括：确定操作数的单个出现是否作为指令的两个操作数出现；

确定单个算术逻辑单元指令的两个操作数是否出现在单个通用寄存器库中；

通过采用符号寄存器冲突图解决在操作数的单个出现作为指令的两个操作数出现时的冲突；以及通过采用图着色解决在单个算术逻辑单元指令的两个操作数出现在单个通用寄存器库中时的冲突。

9.根据权利要求8所述装置，还包括：确定所述交集是否为空集合的部件；

如果所述交集是空的话解决所述冲突的部件；以及如果所述交集是非空的话进行分配的部件。

10.根据权利要求8所述的装置，还包括：把所述交集分成最小无冲突部分的部件；以及增加移动以经过所述无冲突部分传递值的部件。

11.根据权利要求10所述的装置，还包括：为所述操作数的所有出现构建规定-使用图的部件；

基于一组预定的条件识别所述规定-使用图中的所有冲突传送边缘的部件；以及对所述规定-使用图进行分区的部件。

12.根据权利要求10所述的装置，还包括：采用最小割集算法增加移动的部件。

说明书

背景技术

在通用微处理器中，可把寄存器分成寄存器库(bank)(或文件)，如整数寄存器库和浮点寄存器库。不同库中的寄存器在大小和格式上可以各不相同，并且在寄存器库之间不存在直接的数据路径。寄存器分配(RA)会在现代最优编译器中起重要作用。RA的任务可以是把符号寄存器映射到物理寄存器中。通常，指令中的目的或源操作数的寄存器库可由指令的操作码来确定。因此，RA可只将符号寄存器独立地指配给每个物理寄存器库。

特定域或嵌入的处理器可具有高度分区的寄存器库。为对这些寄存器库进行分配，可给编译器分派任务，选择寄存器库以及用于符号寄存器的库中物理寄存器。然而，这些处理器可能具有导致寄存器库冲突的硬件约束。这种冲突可能需要在编译器选择寄存器库和用于符号寄存器选择的库中物理寄存器之前被解决。

发明内容

根据第一实施例，本发明提供了一种用于把操作数分配到寄存器库中的方法，所述方法包括：
为所述操作数识别所有的候选寄存器库，所述识别包括：
识别所述操作数的所有出现；
把每个出现分类到多个类中的一个中，每类具有至少一个关联的寄存器库；
比较关联的寄存器库集合的相交的类；以及
基于关联的寄存器库集合的所述相交产生交集；
确定在所述候选寄存器库之间是否存在冲突；
解决任何冲突；以及
把所述操作数分配给所述寄存器库，所述分配包括：
确定操作数的单个出现是否作为指令的两个操作数出现；
确定单个算术逻辑单元指令的两个操作数是否出现在单个通用寄存器库中；
通过采用符号寄存器冲突图解决在操作数的单个出现作为指令的两个操作数出现时的冲突；以及
通过采用图着色解决在单个算术逻辑单元指令的两个操作数出现在单个通用寄存器库中时的冲突。
根据第二实施例，本发明提供了一种用于把操作数分配到寄存器库中的装置，包括：
识别操作数的所有候选寄存器库的部件，所述识别包括：
识别所述操作数的所有出现；
把每个出现分类到多个类中的一个中，每类具有至少一个关联的寄存器库；
比较关联的寄存器库集合的相交的类；以及
基于关联的寄存器库集合的所述相交产生交集；
如果所述候选寄存器库之间存在冲突的话解决所述冲突的部件；以及
把所述操作数分配给寄存器库的部件，所述分配包括：
确定操作数的单个出现是否作为指令的两个操作数出现；
确定单个算术逻辑单元指令的两个操作数是否出现在单个通用寄存器库中；
通过采用符号寄存器冲突图解决在操作数的单个出现作为指令的两个操作数出现时的冲突；以及
通过采用图着色解决在单个算术逻辑单元指令的两个操作数出现在单个通用寄存器库中时的冲突。

附图说明

根据以下对本发明的示范性实施例进行的更具体的说明，将会明白本发明实施例的各种示范性特征和优点，如附图所示，其中相似的标号一般指示等同的、功能相似的和/或结构上相似的单元。
图1描述了根据本发明的示范性实施例的系统的示范性实施例
图2描述了根据本发明的示范性实施例的示范性方法实施例；
图3描述了根据本发明的示范性实施例的表的示范性实施例；
图4描述了根据本发明的示范性实施例的方法的示范性实施例；
图5描述了根据本发明的示范性实施例的规定-使用图的示范性实施例；
图6描述了根据本发明的示范性实施例的规定-使用子图的示范性实施例；
图7a描述了根据本发明的示范性实施例的定向非循环图的示范性实施例；
图7b描述了根据本发明的示范性实施例的定向非循环图的示范性实施例；以及
图8描述了可用于本发明的示范性实施例中的几个部件的计算机和/或通信系统的示范性实施例。

具体实施方式

以下详细讨论本发明的示范性实施例。虽然讨论的是示范性实施例，但应当理解这样做的目的仅是为了说明。相关领域的技术人员将会认识到在不背离本发明的精神和范围的情况下可采用其他部件和配置。
本发明的示范性实施例可提供把操作数指配到分区寄存器库中的物理寄存器的系统和方法。图1说明了具有多个库寄存器结构的示范性寄存器库结构100。在本发明示范性实施例中，结构100可包括算术逻辑单元(ALU)101、操作数寄存器102a，102b、通用寄存器(GPR)库103a，103b、动态随机访问存储器(DRAM)传送入寄存器库104、静态随机访问存储器(SRAM)传送入寄存器库105、下一邻近(NN)寄存器库106、DRAM传送出寄存器库107、SRAM传送出寄存器库108、本地存储器109和本地存储器地址110a，110b。
在本发明示范性实施例中，网络处理器(未示出)可具有16个连接的微引擎(ME)。每个ME可以是精简指令集计算机(RISC)处理器并可具有八个硬件线程，例如。为降低寄存器硬件的复杂性以及支持硬件多线程，每个ME可具有七个寄存器库。这些寄存器库可包括GPR A和B库、SRAM传送入和传送出库、DRAM传送入和传送出库以及下一邻近(NN)库，如图1所示。
在本发明示范性实施例中，寄存器库可以不必是独立的。例如，这些寄存器库可以具有32比特的宽度并能够表示相同的值，以便这些值可从一个库被传送到另一个库中。ME指令的一个操作数可驻留在多个库中，不过存在某种约束。
根据ME的示范性指令集结构(ISA)规范，许多ME指令的操作数可驻留在多个寄存器库中。例如，ALU指令的源操作数可驻留在GPR A和B库、SRAM和DRAM传送入库以及下一邻近库中的任何一个库中。在这种实施例中，对于具有两个源操作数A和B的指令类型，两个源操作数选择规则还可限制寄存器库的选择。一条这样的规则可规定相同库不能用于两个A和B操作数。第二条这样的规则可规定SRAM/DRAM传送入寄存器库和下一邻近寄存器库不能用作A和B操作数二者。第三个规则可规定立即值不能用作A和B操作数二者。
例如，在ALU加法指令“r1＝r2+r3”中，r2和r3不能都驻留在GPR A库或B库中。
在本发明的示范性实施例中，可以在不同的寄存器库之间移动值以满足这些约束。因此，ME的寄存器分配(RA)可正确地指配库和分配寄存器以满足以上约束，同时使由在寄存器库之间进行数据移动引起的花费最小。
图2说明了流程图200，其说明用于指配库并分配寄存器以满足以上约束并使由寄存器库之间数据移动引起的花费最小的示范性方法。如本领域的普通技术人员所理解的，这里所称的符号寄存器(TN)例如可以是每次代码生成器或编译器需要目标系统上的物理寄存器时所请求的位置标志符。
参照图2，在框201中可识别针对每个TN的候选库。在本发明示范性实施例中，候选库可指TN可驻留的库。由于在引用TN的不同程序点上对库选择有不同的约束，因此针对此TN的候选库集合可能是空的。在这种情况下，该TN被称为有库冲突。在框202中，可确定出这些冲突是否存在。如果不存在冲突的话，在框204中，每个TN可被分配到寄存器。如果的确存在冲突，在框203中，可解决针对每个TN的库冲突。在解决库冲突后，每个TN可具有其自身的非空候选库。在本发明的示范性实施例中，可把TN划分成TN集合，其中特定集合中的TN可具有相同的候选库。在框204中，对于每个TN集合的传统的集合内寄存器分配可采用例如着色和溢出的任务来执行。
以下详细描述图2中的这四个框。注意ME中的下一邻近库因为它的特定用途(对其进行写实际转向下一ME)被单独对待而没有与其他库进行细微的交互，因此以下不进行详细说明。
如上所述，TN的候选库可由采用TN作为操作数的指令来确定。在本发明的示范性实施例中，比特矢量可用来表示TN的候选库，如0x01表示GPR A库，0x02表示GPR B库等等。对于RA之前的所有指令，它们的源和目的操作数的候选库(即TN的具体实例)可仅根据指令的操作码和类型来设置。如这里所指出的，有效范围可以是TN的规定和使用的连接的web网。每个有效范围可唯一命名(或编号)并可直接对应于TN。为计算有效范围的候选库，可获得此有效范围中TN的所有出现中的候选库的交集。所得到的交集可代表可指配给此有效范围内的TN的所有可能的库。
在本发明示范性实施例中，TN可由输入/输出(I/O)读或ALU指令来规定，TN可由I/O写或ALU指令利用。图3描述了表300，其说明了基于图1的示范性系统在规定-使用表中TN的所有可能的使用。例如，如图3所示，此表的右下单元指示TN是否由ALU操作利用，然后TN可驻留在GPR A/B、SRAM/DRAM传送入的任何库中。在将规定-使用表的行与列相交后，TN的非空候选库的所有可能的组合可如下：TN肯定在SRAM传送入中；TN可能在SRAM传送入或DRAM传送入中；TN肯定在SRAM传送出中；TN肯定在DRAM传送出中；或TN可能在GPR A或GPR B中。
当将规定-使用表的行与列相交时，可识别出TN的候选库可能是空的情况。例如，单元(I/O、规定)与单元(I/O、使用)的相交可得到空的结果。如本文所指出的，空的结果可能指没有候选库可用。通常，可存在三种不同的可导致空结果的冲突。如本文所指出的，“规定冲突”可在TN由I/O读和ALU操作规定时存在；“使用冲突”可在TN由I/O写和ALU操作所使用时存在；以及“规定-使用冲突”可在TN由I/O读规定并由I/O写使用时存在。
在本发明示范性实施例中，为解决库冲突，可把冲突的TN(有效范围)分成最小的无冲突部分，然后可增加移动以把值传递通过非冲突的部分。图4描述了流程图400，其说明了用于解决库冲突的示范性方法。在框401中，可构建规定-使用图(DUG)。图5描述了示范性DUG 500。如在图5中所看到的，每个节点501可代表引用TN的指令。边缘502a-502d(d->u)可表示指令d中的TN的规定由指令u在用。本领域的普通技术人员会明白，在DUG 500中可存在循环，如TN1＝TN1+1。
在框402中，可找出DUG中的所有冲突传送边缘。基于上述三种冲突，冲突传送边缘可出现在DUG中。在本发明的示范性实施例中，冲突传送边缘可以是DUG中的边缘，其两端满足一个或多个以下条件：1)传送边缘的尾部是是I/O规定并且相同传送边缘的首部是I/O使用；或2)传送边缘的尾部是I/O规定并且相同传送边缘的首部的前导之一是ALU规定；或3)传送边缘的首部是I/O使用且相同传送边缘的尾部的后续之一是ALU使用。在框402中通过扫描DUG的所有边缘可找出所有冲突传送边缘。
图5中的示例显示了规定-使用图500，其中TN1的候选库集合是空的。在图5中，指令“TN1＜-SRAM”把值从SRAM装入TN1中。边缘(b，f)可以是冲突传送边缘，因为它满足以上所列的第二种条件，即尾部b是I/O规定且f的前导c是ALU规定。
在框403中，可对DUG进行分区。在本发明的示范性实施例中，为了划分DUG，可拆分所有冲突传送边缘，以获得w个子图：R1，R2，...，Rw。
一旦获得子图，那么在框404中便可对每个子图中的TN进行重命名。图6描述了子图600、601，它们可通过把图5中的冲突边缘(b，f)拆分开来创建。如图6所示，可把两个子图的每个中的TN1重命名为TNm和TNn。
在框405中，可在每个子图之间增加移动。在本发明的示范性实施例中，为在每个子图之间增加移动，针对已被拆分的每个边缘(d，u)，假设d中的TN被重命名为TNm而u中的TN被重命名为TNn。因此，如本领域中具有普通技术的人员将会理解的那样，可能需要在规定-使用边缘上插入移动“TNn＝TNm”。在本发明的示范性实施例中，在控制流程图(CFG)中可插入移动以拆分指令d和指令u之间的TN的有效范围。例如，使用BB(i)来表示含有指令i的基本框(BB)。为使所插入移动的动态成本最小，由执行频率加权的从BB(d)到BB(u)的路径的最小割集可表示放置移动的最佳位置。CFG中的临界边缘可以是其首部具有多个前导并且其尾部具有多个后续的边缘。CFG中所有的临界边缘可通过在RA之前在每个边缘上放置空的基本框来分开。最小割集可基于通过删除CFG中的循环而构造的定向非循环图(DAG)来计算。注意，此DAG可由从BB(d)到BB(u)的除了环的后部边缘(如果有的话)之外的所有BB和边缘构成。对于单入口单出口的DAG(其中入口是BB(d)而出口是BB(u))，可从入口到出口计算最小割集，并在最小割集的BB中插入移动。
图7a针对上述示例描述了示范性DAG 700。从b到f的最小割集可以是{d}。可将移动TNn＝TNm插入到基本框d中，如图7b所示。一旦已插入所有的移动，便可识别出所有TN的候选库(即有效范围)并且它们是非空的。给每个TN指配了以下示范性集合中的一个：S_Xfer_In_Set＝{TN肯定在SRAM传送入中}；SD_Xfer_In_Set＝{TN可能在SRAM传送入中或在DRAM传送入中}；S_Xfer_Out_Set＝{TN肯定在SRAM传送出中}；D_Xfer_Out_Set＝{TN肯定在DRAM传送出中}；以及GPR_Set＝{TN可能在GRA A或GPR B中}。
在框406中，可分配集合内的寄存器。在本发明的示范性实施例中，基于寄存器分配的图着色可单独用于以上每个TN集合中。由于以上列出了两个源操作数选择规则，因此对以下情况可进行特别处理。
当对于S_Xfer_In_Set和SD_Xfer_In_Set执行RA时，例如可能需要遵循SRAM或DRAM传送入不可用作A和B操作数二者的规则。
为遵循这种规则，在本发明的示范性实施例中可针对每个BB构造符号寄存器冲突图(SRCG)。如本领域的普通技术人员所理解的，SRCG可类似于DUG。然而，在SRCG中节点可以是传送入集合中的TN。如果两个节点均是相同指令的源操作数的话，边缘可连接两个节点。随后可把SRCG中所有边缘拆分。为拆分这些边缘，可选择具有最高度的节点(即具有最大数量的相邻节点)并可插入移动指令以便把它移动到新的TN中(随后可计算这些新TN的候选库并将它们放入相应的TN集合中)。节点的使用可在冲突点上采用此基本框中的新TN被重命名。在本发明的示范性实施例中，这可等同于从SRCG移除节点和关联的边缘。这种过程可一直持续到拆分了所有的边缘为止。随后可应用RA。
当对于GPR_Set执行RA时，可能需要遵照指令的两个源操作数不能同时驻留在GPRA库或B库中的规则。
在本发明示范性实施例中，可存在不同的方法来着色GPR_Set中的寄存器。例如，在本发明的一个实施例中，可构造具有是GPR_Set中的TN的节点的SRCG。如本领域的普通技术人员所理解的，在这种实施例中，RA问题可等同于例如通过把节点分成两部分：A和B而使SRCG可着2色。每个部分随后可分别采用来自GPRA库和GPRB库的寄存器来着色。图可着2色的必要和充分条件是图不具有任何奇数长度循环。因此，可拆分SRCG中所有的奇数长度循环(如果存在的话)。此拆分可通过如上所述增加移动拆分奇数长度循环的边缘来进行。
图8描述了可用于本发明示范性实施例中的系统的几个部件的计算机和/或通信系统的示范性实施例。图8描述了可用于本发明示范性实施例中的系统的几个计算设备的计算机800的示范性实施例。计算机800可包括但不限于：如任何计算机设备或通信设备，例如包括个人计算机(PC)、工作站、移动设备、电话、手持PC、个人数字助理(PDA)、瘦客户机、胖客户机、网络设施、因特网浏览器、寻呼机或报警设备、电视机、交互式电视机、接收器、调谐器、高清晰(HD)电视机、HD接收器、视频点播(VOD)系统、服务器或其他设备。
在示范性实施例中，计算机800可包括中央处理单元(CPU)或处理器804，其可耦合到总线802上。处理器804例如可经由总线802访问主存储器806。计算机800可耦合到输入/输出(I/O)子系统，如网络接口卡(NIC)822或调制解调器824上以便访问网络826。计算机800还可直接经由例如总线802或主存储器806耦合到辅助存储器808。辅助存储器808可包括例如磁盘存储单元810或其他存储介质。示范性磁盘存储单元810可包括但不限于磁存储装置，如硬盘、光存储设备如一次写多次读(WORM)驱动或光盘(CD)或磁光设备。辅助存储器808的另一种类型可包括可拆卸盘存储设备812，其可用于与如CD-ROM或软盘的可拆卸存储介质814结合。通常，盘存储单元810可存储用于操作计算机系统的应用程序，通常称为操作系统。盘存储单元810还可存储数据库文件(未示出)。计算机800可经由总线802与I/O子系统和盘存储单元810交互。总线802还耦合到用于输出的显示器820和输入设备，比如但不限于键盘818和鼠标或其他点击/选择设备816。
本说明书所陈述和讨论的实施例只用于让本领域的那些技术人员学会发明人发明和运用本发明所教的各种方法。本说明书中没有任何内容被认为是限制本发明的范围。所提供的全部示例是代表性的而不具有限制意义。在不背离本发明的情况下，如本领域的技术人员所理解的那样，根据以上示教可对上述本发明实施例进行修改或变化。因此应当明白本发明可以其它不同于这里具体描述的方式来实现。