优化编译器中的寄存器约束解耦与整数线性规划

理论计算机科学电子笔记132（2005）131-148www.elsevier.com/locate/entcs论寄存器饱和Sid-Ahmed-Ali Touati法国凡尔赛大学PRiSM实验室摘要在优化编译器中，寄存器分配过程仍然是一个关键阶段，因为它可以减少损害性能的溢出代码。在非循环数据依赖图（DAG）的指令调度阶段，通常会考虑寄存器约束：任何调度都必须最小化寄存器需求。然而，在以前的工作[14]中，我们引入并数学研究了寄存器饱和（RS）概念。 它包括计算所有有效时间表所需的寄存器的确切上限，而不受功能单元约束。RS的目标是将寄存器约束与指令调度解耦。在本文中，我们继续我们的理论工作，我们提出了两个主要结果。 首先，我们给出了一个精确的解决方案与整数线性规划的计算RS的DAG和减少它的问题。我们的整数规划带来了一种新的方式来建模寄存器的约束，使我们能够产生最低数量的约束和变量的文献（到现在为止）。事实上，给定一个有n个节点和m个弧的DAG，我们需要O（n2）个整数变量和O（m+n2）个线性约束，这比文献中模拟寄存器约束的实际大小复杂度要好。其次，我们证明了减少寄存器饱和度的问题是NP-难.我们在本文中的详细实验表明，我们以前的算法[14]几乎是最优的。我们也提供了一个讨论，以论证为什么RS方法应该更好地减少寄存器的要求。关键词：寄存器压力，指令级并行，线性规划，优化编译。1介绍指令级并行（ILP）的引入，使得经典的顺序代码语义寄存器分配技术不再适用。因此，旧的图着色技术应该被重新考虑，以有效地优化编译器的现代体系结构。在文献[5]中，作者指出，在旧寄存器1 电子邮件地址：touati@prism.uvsq.fr1571-0661 © 2005 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.033132S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131分配技术和ILP指令调度。如果一个经典的寄存器分配是早期完成的，引入的假依赖抑制了良好的进一步的ILP提取。然而，这一结论并不阻止任何编译器有效地执行早期寄存器分配，但条件是所使用的分配器应该对调度器敏感，如[12，11，8]所做其他一些研究[13，10，5]声称，最好将指令调度和寄存器分配结合在一个复杂的通道中，论证了单独应用每种方法对另一种方法的然而，只有当应用的第一遍（ILP调度器或寄存器分配器）是“自适应”时，才会出现这种阶段排序问题事实上，如果足够小心，我们仍然可以有效地将寄存器约束与指令调度解耦。在本文中，我们将展示如何在调度之前处理寄存器约束，并解释为什么要这样做在指令调度之前处理寄存器约束的主要原因是我们认为寄存器分配作为一个优化问题比代码调度更重要。这是因为，通常情况下，代码性能对内存访问比细粒度调度（内存间隙）更敏感：缓存未命中可能会阻止处理器实现高动态ILP，即使调度程序在编译时提取了它。即使有人认为溢出代码表现出很高的局部性，因此可能会产生缓存命中，我们也不能在编译时断言它，因为在编译时，存储访问延迟是不可预测的（我们不能保证日期位于何处）。此外，内存请求，即使它们是数据独立的，也表现出高潜在的冲突，因为微架构限制和内存消歧机制（加载/存储队列）的简化以及缓存级别中可能的银行结构[7]。即使存在足够的ILP，即使数据位于缓存中，这些可能的冲突也可能导致严重的性能下降。当然，我们声称溢出代码更具破坏性，这适用于存储器访问延迟与计算延迟相比非常长的体系结构。几乎所有高性能处理器都是如此。如果存储器访问延迟不是关键的，则寄存器饱和概念可能不太有用。在ILP调度之前处理寄存器约束的另一个原因是寄存器约束比资源约束复杂得多。资源约束下的调度是一个性能问题。给定一个数据依赖图（DDG），我们肯定会为任何底层硬件属性找到至少一个有效的调度（极端情况下是顺序调度，即，无ILP）。然而，调度具有有限数量的寄存器的DDG更复杂。我们不能保证至少有一个时间表的存在。S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131133DAG寄存器饱和度降低（修改）DAG寄存器分配调度寄存器饱和计算Fig. 1. 早期注册压力管理在某些情况下，我们必须引入溢出代码，因此我们改变了问题（输入DDG）。此外，如果没有足够的寄存器可用，则调度与寄存器分配的组合传递呈现出重要的缺点。在调度期间，如果没有足够的空闲寄存器存在，我们可能需要插入加载-存储操作。我们不能保证在已经调度的代码中存在这些引入的内存访问的有效发布时间;资源或数据依赖性约束可能会阻止在已经调度的代码中找到有效的发布槽这一事实迫使迭代地应用调度，然后进行溢出，直到找到解决方案。所有上述参数使我们在开始调度过程之前重新考虑处理寄存器压力的新方法，以便调度程序不受寄存器约束，并且不会受到过度序列化的影响。出于这个原因，我们在[14]中提出了寄存器饱和（RS）概念，该概念可以防止DAG为所有有效调度同时生成过多的值。我们的pre-pass分析了DAG（相对于控制流），以推断出所有调度的最大寄存器需求。我们将此限制称为寄存器饱和（RS），因为寄存器需求可以达到此限制，但永远不会超过它。如果RS超过可用寄存器的数量，我们将引入新的弧来减少它，请参见图1。在本文中，我们提供了精确的（最佳的）方法来计算RS和减少它的问题。在我们的RS分析通过后，DAG是免费的寄存器的限制，可以发送到调度器和寄存器分配器。本文的组织结构如下。第二节介绍了我们的DAG和处理器模型，它可以用于大多数现有的ILP结构（超标量，VLIW，EPIC/IA 64）。中给出了通过intLP计算最优RS的第3款.我们的intLP公式通过引入额外的二进制变量来使用逻辑公式（= x，x，y）和max运算符（max（x，y））的线性书写，如之前在[15]中所述。降低RS的最优解134S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131在第4节中提供。我们的大量实验表明，我们的初始算法[14]在第5节中几乎是最优的。在结束之前，我们在第6节中进行了讨论，以论证为什么RS概念是在ILP调度之前处理寄存器约束2DAG和处理器型号在我们的研究中，DAGG=（V，E，δ）表示操作与任何其他串行约束之间的数据依赖性。DAG由它的运算集V、它的边集E={（u，v）/ u，v∈V}和δ定义，使得δ（e）是边缘e的延迟，以处理器时钟周期表示设n为节点数，m为弧数。G的调度σ是一个函数，它为每个操作给出整数执行（发布）时间：σ是有效的<$e=（u，v）∈E，σ（v）−σ（u）≥δ（e）G的所有有效无圈时间表的集合记为<$<$（G）。我们考虑具有多个寄存器类型的目标RISC风格架构，其中T表示寄存器类型的集合（例如，T={int，float}）。DAG的某些语句和某些优先约束具有更多的at-贡品比其他人，这取决于他们是否指的是要存储在寄存器中的值。VR，t是要存储在类型t∈ T的寄存器中的值的集合。我们考虑每个语句u∈V至多写入一个类型t∈ T的寄存器。定义具有不同类型的多个值的语句在我们的模型中被接受，如果它们不定义某个类型的多个值2。ER，t是通过类型t∈T的值的低依赖边的集合。值ut的消费者（阅读者）的集合是：Cons（ut）={v∈V|（u，v）∈ ER，t}中的某些值可能不会在所考虑的DAG中使用为了对这样的退出值建模，我们假设所考虑的DAG包含底部节点这是这些退出值的低依赖性的汇点。此外，还有一个从DAG的任何其他节点到该底部节点的串行弧。 这种虚拟弧的延迟等于源操作的延迟。底部节点始终是DAG的最后一个计划节点。为了考虑静态问题VLIW和EPIC/IA 64处理器，其中硬件流水线步骤对编译器可见（我们考虑动态地2这个模型的限制，对实际的ILP处理器几乎没有影响，允许我们在[15，14]中使用一些图形特征进行形式证明。S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131135不不调度超标量处理器也是如此），我们假设从寄存器读取和定义了两个延迟函数δr和δw，其中ut从t型寄存器的读周期为σ（u）+δr（u），ut向t型寄存器的写周期为σ（u）+δw（u）.例如，在超标量和EPIC/IA 64处理器中，δr和δw等于零。当一个时间表是固定的，我们可以很容易地计算出我们需要多少寄存器的每个寄存器类型t，以建立一个有效的寄存器分配。它是同时存活的t型值的最大数目的标准概念，也等于干涉图中的最大团。回想一下，如果两个变量的生命周期间隔相互干扰，那么这两个变量被称为同时存活，因此它们不能共享同一个寄存器。对于给定固定调度σ的DAGG，类型t的寄存器要求（或寄存器需要）记为RNσ（G）。在定义了DAG和处理器模型之后，下一节将展示如何计算精确的最佳寄存器饱和度（RS）。3计算最佳寄存器饱和度首先如果|VR，t|，类型t的值的总数，小于或等于Rt，类型t的可用寄存器的数量，那么我们可以肯定，任何调度都不能要求超过|VR，t|≤ Rt寄存器。否则，我们必须分析寄存器饱和（RS）。DAGG的寄存器类型t的RS是该DAG的所有有效调度所需的最大寄存器：RSt（G）=maxσ∈N（ G）RNσ（G）我们在[14]中证明了计算这个参数是一个NP完全问题，并提供了一个算法。下面，我们给出了一个精确的intLP的变量和约束的集合，用于计算RSt（G）。我们的intLP配方使用逻辑公式的线性书写（=，，）和max运算符（max（x，y））通过引入额外的二进制变量，如之前在[15]中所述。然而，逻辑运算符和最大运算符的线性写入需要绑定整数变量的域集136S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131不不3.0.1调度变量对于所有的操作u∈V，我们定义一个包含调度时间的整数变量σu≥请注意，这些调度变量并不代表资源约束下的最终调度（将在RS通过后计算但它们仅代表我们的intLP公式的中间变量。第一个线性约束是那些描述优先关系的约束，因此我们将其写入intLP系统：εe=（u，v）∈E，σv−σu≥δ（e）时间复杂度为O（n），时间复杂度为O（m）。为了约束我们变量的域集，我们定义T为最坏的概率最小的时间。 我们选择的T规模很大，例如T=e∈Eδ（e）是合适的最坏总调度时间（无ILP的情况）。然后，我们编写以下约束：σu ∈V，σu ≤T因此，我们对任何u∈V推出：• σu≥σu=LongestPathT o（u）是• σu≤σu= T−LongestPathF rom（u）是根据最差总调度时间T的“尽可能晚”的调度时间。3.0.2注册需求限制干扰图类型t的值ut的生命周期间隔是（给定时间表σ）LT（ut）=]σ+δ（u），max.Σσ+δ（vσ uwvv∈ Cons（ ut）（r ）]也就是说，我们假设在时刻c写入寄存器的值在一步之后可用（生命周期间隔保持开放）。因此，如果一个操作u在时刻c从一个寄存器中读取，而另一个操作v同时在其中写入，则u不会得到v请注意，这是一种选择，而不是对模型的限制我们为each值u定义变量kut≥0t，它计算其终止日期（最后一次读取该值）。这样定义的变量的个数是O（n）。由于我们的可变域是有界的（假设T是有限的），我们知道ku是在d下由我们满足给定的时间来定义的：t∈ T，t∈VR，t：kut≤kut≤kut哪里S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131137u，vtt不u，v• kut=σu+δw（u）是ut的第一个可能的定义日期;• kut=maxv∈Cons（ut）.Σσv+δr（v）是ut的最新可能的死亡日期。我们使用最大运算器的线性列来计算kut，如[15]中所示。我们在intLP系统中写入：乌鲁特 ∈VR，t：kut=maxv∈ Cons（ ut）.Σσv+δr（v）对于所有类型的寄存器，定义所有killing date的总复杂度为O（n2）变量和O（n2）约束。现在，我们可以认为Ht是G对于寄存器类型t的无向干涉图。对于任意两个不同的值ut，vt∈VR，t，我们定义：二进制变量st{0，1}，如果两个生命周期类型t的间隔干扰：t∈T，t耦合ut，vt∈VR，t：⎧如果LTσ（ut）<$LTσ（vt）/=φ，则为<$1tu，v=0.00否则变量的数量st是两个值的组合的数量，.u，v|，即，|, i.e.,|（|V R，t |− 1）/ 2.| − 1)/2.LTσ（ut）<$LTσ（vt）=.φ是指t的一个整数。他把自己的一生都献给了“在”另一个之前，即，LTσ（ut）<$LTσ（vt）∨LTσ（vt）<$LTσ（ut），其中表示区间代数中的“before”关系。那么，我们必须表示以下约束：.st= 1ttttu，v⇐⇒ ¬LTσ(u)≺LTσ(v)∨LTσ(v)≺LTσ(u)其中LTσ（u）<$LTσ（v）i <$ut≤σv+δw（v）。该连续流的等式为kut>σv+δw（v），即，kut−σv−δw（v）−1≥0。由于su，v∈{0，1}，因此每个变量都是经过训练的如下所示：tu，v≥1 ⇐⇒⎧kut−σv−δw（v）−1≥0kvt−σu−δw（u）−1≥0给定三个逻辑表达式（P，Q，S），（PQ）S）。我们通过引入二进制变量（见[15]）来编写这两个具有线性约束的析取，通过计算线性函数的有限下界。 的复杂性时间复杂度为O（n2），时间复杂度为O（n2）。约束SS138S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131u，v不不不干涉图同时存活的t型值的最大数目对应于Ht=（VR，t，Et）中的最大团，其中（ut，vt）∈ Eti是它们在-间隔干扰= 1）。为了简单起见，而不是考虑干扰-对于图本身，我们更倾向于考虑它的补图HJ=（VR，t，EJ）t t其中（ut，vt）∈ EJi，它们的寿命间隔不干扰（st= 0）。然后，t u，v同时存活的类型t的值的最大数目对应于HJ中的最大独立集合。为了编写描述独立集（IS）的约束，我们定义了一个不二元变量xut∈ {0，1}对于每个值u∈VR，t使得xut = 1 iut属于HJ的某个IS。我们在模型中表示以下线性约束条件：<$xut，xvt∈VR，t：su，v=0=<$xut+xvt≤1这个方程意味着，如果两个节点u和v在HJ中连接，那么它们中的一个且只有一个可以属于IS。时间复杂度为O（n）。在O（n2）的情况下，时间复杂度为O（n2因此，时间复杂度为O（n）。3.0.3语域需求类型t的寄存器要求是HJ中的最大IS，即，最大特ut∈VR，txut.因此，类型t的寄存器饱和度计算如下：最大 Σut∈VR，txut在我们的整个intLP中，整数变量的总数是有界的O（|V|2），且子序列的总数目至多为O（m +n2）. 注意，我们的intLP公式可以通过考虑以下因素来优化：• 初始DAG中的边e=（u，v）对于调度约束是冗余的，并且如果lp（u，v）>δ（e）则可以安全地忽略，其中lp（u，v）表示从u到v的最长路径（条件是该弧• 两个值（ut，vt）∈VR，t永远不可能同时存活，对于所有可能的调度，一个值总是在S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131139其他. 如果满足以下两个条件中的任何一个，则属于这种情况：vJ∈Cons（vt）：lp（vJ，u）≥δr（vJ）−δw（u）N∈Cons（ut）：lp（uJ，v）≥δr（uJ）−δw（v）在计算出最优RS之后，下一节将展示如何在它超过极限时减少它。4最佳寄存器饱和降低在寄存器饱和RSt（G）超过类型t的可用寄存器Rt的数量的情况下，则我们必须将额外的串行弧添加到DAGG中以将RSt（G）降低到该限制以下。新增加的弧必须通过照顾关键路径尽可能地节省ILP。我们用E表示我们添加到G以构建新的扩展DAG的额外边的集合，即G=G\E，使得RSt（G）≤Rt。我们要解决下面的形式问题。定义4.1[ReduceRS问题]设G =（V，E，δ）是一个DAG。设Rt和P是两个正整数.是否存在G的扩展DDGG=G\E使得：和RSt（G）≤Rt临界路径（G）≤P定理4.2 ReduceRS问题是NP难的。证据我们证明了ReduceRS问题是从寄存器约束下的调度问题让我们从定义后一个问题开始。 为了证明的清晰起见，我们假设所考虑的寄存器类型t是隐式的（我们在这个证明中的符号中不包括t定义4.3[SRC问题]设G=（V，E，δ）为DAG，R为正整数，P为长度。是否存在一个有效的时间表σ∈N（G）使得：RNσ（G）≤R和总计划时间≤P140S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131JSRC问题在文献[4]中已被证明是NP难的。现在我们证明ReduceRS和SRC问题在计算复杂性方面是等价的。1. ReduceRS= 0.5SRC设G是ReduceRS问题的解。则任意的尽可能快的时间表σ∈N（G）都是SRC的解.2. SRC= CRYPReduceRS设σ是SRC的解，即， RNσ（G）≤ R，总调度时间≤ P。我们通过添加串行弧来构建扩展的DDG G G，以使G的任何时间表的值生命期具有与σ定义的相同的优先关系。<$u，v∈VR/LTσ（u）<$LTσ（v）则我们添加以下弧：• 如果v∈Cons（u），则将来自其他u.J JΣe=（u，v）/u∈Cons（u）−{v}• 否则，将来自所有u的读取器的串行弧.JJΣe=（u，v）/ u∈Cons（u）这些添加的弧的延迟必须根据目标代码来选择。我们有两个案子，(i) 在超标量代码的情况下，语义是顺序的。因此，每个添加的弧的延迟被设置为1;(ii) 在VLIW或EPIC/IA 64的情况下，存在读和写操作集3。因此，对于每个添加的弧e=（uJ，v），延迟被设置为δ（e）=δr（uJ）-δw（v）。实际上，添加的弧和选择的弧强制以下断言：LTσ（u）<$LTσ（v）=<$$>σ∈<$（G）：LTσJ（u）<$LTσJ（v）那么，对于所有根据σ非同时存活的值，G中不存在使它们同时存活的方案σJ它的正式写法是：.<$<$u，v∈VR，LTσ（u）<$Lσ（v），<$σJΣ∈G（G）/ LTσJ（u）<$LTσJ（v）φ3在EPIC/IA 64体系结构上，一个写器和一个读器可以被调度在同一个指令组上，因此写延迟静态地被认为是零。S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131141uu换句话说，我们确保G的任何时间表都将保证优先级G的寿命区间随σ的变化关系。因此，G的任何时间表σJ都不可能需要超过σ的寄存器需要，RS（G）=RNσ（G）≤RSRC问题的解可能在ReduceRS的解中产生回路。我们确信，如果在G中引入任何回路，那么它一定是非正的，因为至少存在有效调度σ∈G（G）. 康-因此，ReduceRS问题的解决方案可以产生循环DDG。稍后我们将看到如何消除这些解决方案。对于G的关键路，引入的序列弧保证至少σ∈N（G）.由于存在这样一个总时间的时间表≤P，则G的关键路不能长于P。Q定理4.2的证明给出了使用整数规划的ReduceRS问题的最优解的直观。它的计算分为两步：(i) 我们首先计算一个有效的时间表σ，使得寄存器需要类型t被最大化并且不超过Rt，而总调度时间是有界的。这个时间表与最后一个时间表不同，在资源限制下计算(ii) 然后，如定理4.2的证明所描述的，我们添加连续弧。这导致扩展的DDG具有最小化关键路径的有界寄存器饱和。为了计算这样一个调度，我们使用前面在第3节中定义的intLP公式，它最大化了寄存器需求。我们保留了第3节中的所有约束和变量，除了那些计算最大独立集现在，我们使用二进制变量xit，如果值ut存储在寄存器i中，则将其设置为1。由于有Rt个可用寄存器，我们最多有|V| × Rt变量。由于Rt是一个常数是我们的问题（目标机器中的寄存器数量），因此这些变量的数量为O（|V|）.intLP系统试图用精确的Rt颜色（可用寄存器的最大数量）来构建干扰图的着色。如果用Rt寄存器找不到解，则在递减Rt（直到1）后求解另一个intLP。如果在达到一个目的时不能找到最终解决办法能够寄存器，则不能降低寄存器饱和，溢出是不可避免的。使用以下约束条件计算变量xit。142S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131uuv• 值ut仅存储在类型t的一个寄存器中：rtt ∈ T， = 1个i=1• 如果两个值相互干扰，则它们不能共享同一个寄存器：t∈T，t对ut，vt∈VR，ttu，v≥1=100.xit +xitΣ≤1，i=1，...，Rt最多有O（V2× Rt）= O（V2）这样的约束.• 目标函数最小化总调度时间：最小化σ2.将a t（|V|2）对第3节的前LP系统的继续训练。如前所述，我们的DAG和处理器模型包括写入和读取对象集。因此，在某些情况下，最佳RS减少可能需要将非正电路引入到原始DAG中。即使这样的非正电路不阻止图被调度，它们仍然违反DAG属性并施加硬调度约束，该硬调度约束在指令调度的后续通道中的资源约束下可能无法满足。我们必须排除这样的最优解，在[15]中。基本上，我们添加最多O（n3）变量和O（m+n3）约束以保证扩展DDG的拓扑排序的存在性。同样，这些约束只需要为VLIW和EPIC码添加，而不需要为超标量码添加。5实验我们对从SpecFP、whetstone、livermore和linpack中提取的一些科学代码进行了广泛的实验由于RS计算和约简的所有问题都是NP困难的，因此获得最优解非常耗时（从几秒到几天）。实验的DAG只是一些循环体（不包括分支）。详细的数值结果和图见[15]。基本上，我们在[14]中提出的所有算法都接近最优。关于RS计算，最大经验误差是一个寄存器（在极少数情况下）。对于RS约简，我们必须探索两个参数：约简的RS和关键路径。我们注意到RS和ILP是最优intLP程序导致的RS约简和ILP损失;我们注意到RS约简和ILP约简了RS。：sS.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131143减少和ILP损失导致我们的物流。然后，我们的实验分为以下几组。(i) 在RS = RS ≠0的情况下，我们的算法成功地最优地减少了RS.那么，ILP损失可以是：(a) ILP= ILP≥100%（占全部结果的72.22%）。我们的算法成功地在最佳减少RS与最佳的ILP损失。(b) ILP ILP不可能！(ii) 在RS > RS ≥1的情况下，我们的算法没有成功地最优地降低RS。那么，ILP损失可以是：(a) ILP = ILP （占所有结果的4.63%）。 我们的算法有子-最佳RS减少，但最佳ILP损失。(b) ILP< ILP无效（小于所有结果的1%）。我们的算法有次优的RS减少与次优的ILP损失。(c) ILP> ILP ≥（占全部结果的3.7%）。我们的算法具有次优的RS减少，但具有超优的ILP损失。这种情况是有趣的- ING：由于我们的算法有次优RS减少，那么它得到额外的寄存器，使他能够利用更多的ILP。(iii) 由于<我们的算法计算了一个有效的RS_n，所以RS_n是不可能的。显然，我们的RS减少算法是非常有效的：在大多数情况下，它以最佳的ILP损失最佳地减少了RS。在大多数情况下，次优ILP损失伴随着最优RS减少，而次优RS减少大多伴随着超优ILP损失。我们得到了次优ILP损失和次优RS减少在不到1%的情况下。6讨论：最小化还是饱和寄存器需求？文献中包含了大量关于最小化对ILP编码敏感的超标量（顺序）码中的寄存器需求的技术[6，8]。其他人更喜欢将ILP调度与寄存器分配结合起来[2，5，9]。所有这些技术都试图最小化寄存器需求。在我们的方法中，我们使用相反的方法：我们最大化寄存器要求，以便最小化添加的弧的数量，如Berson在[1]中所做我们在[14]中提供了与他的方法的比较，以显示我们在工作中修复的局限性。最小化寄存器需求本质上是一种比144S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131因为很多原因使其饱和。 我们在下面解释它们。记录器压力为零给定DAG，如果RS不超过可用寄存器的数量。虽然最小化方法增加了额外的弧，但我们的方法例如，请看图2，其中粗体圆圈是要存储在寄存器中的值，而粗体弧线是当前依赖关系。的初始DAG显然具有等于4的寄存器饱和度：这是因为我们可以调度4个操作{a，b，c，d}以便同时产生4个值如果处理器至少有4个寄存器，则DAG将保持原样，后续调度然而，利用最小化方法，部分（b）中的新DAG被限制为不需要多于2个寄存器4，而不管可用寄存器的数量。可以看出，部分（b）中的DAG比通过RS分析释放的初始DAG更具限制性。我们引入了如果所考虑的DAG的固有数据依赖性在另一ILP调度器上产生限制性寄存器压力（RS超过可用寄存器的数量的情况），则最小化方法比RS减少方法添加更多的弧这是因为我们的方法只引入足够数量的弧，以减少RS低于所考虑的限制。然而，最小化方法试图在可能的最低水平上减少寄存器需求例如，查看图2，假设我们有3个可用的寄存器。部分（c）示出了由RS减少通道产生的新DAG：在这里，RS从4减少到3，并且因此我们具有比部分（b）中产生最小化方法的弧更少的弧。对于前者，最终分配器将根据调度使用1个、2个或3个寄存器;对于后者，我们将仅使用1个或2个寄存器，这更具限制性。因此，RS概念有助于更好地从可用寄存器中获益。当两种方法等价时如果目标处理器是一个超标量乱序，并且其动态调度器是最优的，并且寄存器重命名硬件支持具有无限数量的隐藏寄存器，则两种方法（RS和寄存器需要最小化）应该是等效的。由于用于重命名的隐藏寄存器数量有限，并且运行时调度器不太理想，我们的RS方法可能会产生更好的代码，因为它更好地利用了可用的寄存器。4这里，我们在关键路径约束下最小化寄存器需求S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131145117(a)初始DAG（b）寄存器需求最小（c）RS减少，3个可用寄存器图二. RS减少与最低寄存器要求我们的方法适用于显式读/写对象集我们的DAG和处理器模型允许对寄存器进行显式读写。因此，我们的方法是更通用的比现有的技术，并可以适用于超标量，VLIW和EPIC码。对于后两种情况，在减少RS时必须特别注意：我们必须禁止在所得DAG中出现非正电路。对于全局调度程序，我们的模型假设每个值只有一个可能的定义。这个假设在基本块（BB）内是正确的，即，如果代码不包含分支。在全局控制流程图（CFG）的情况下，静态数据依赖性分析可能会为某些值提供不止一个定义，因为它无法确定采用哪条执行路径。实际上，我们已经在[15]中展示了如何将RS分析扩展到全局非循环CFG（不包括循环）及其与全局指令调度器的交互，该全局指令调度器可以将操作从一个BB移动到另一个BB。但是，我们必须意识到，在全局寄存器分配中，分配的寄存器数量可能优于MAXLIVE，因为可能会插入额外的“移动”操作。我们认为，利用文[3]的理论结果，可以证明最佳差至多是一个额外寄存器。因此，我们仍然可以在全局非循环CFG中使用寄存器饱和概念，额外寄存器。例如，这可以通过将可用寄存器的数量减少R来完成，使得最终寄存器分配不能超过R，即使已经插入了移动操作一17B1C1D1一17B1C1D1D1一BC1146S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131类似工作我们的理论框架是对Berson [1]所做研究的扩展。关于我们的逻辑学[14]和伯森总结如下：• 我们的工作是正式的，所以我们可以证明我们所有的断言。我们能够保证生成的代码是正确的;• 我们在文[14]中指出，Berson的工作包含一些错误和不完整的证明。例如，必须仔细选择节点之间的杀死关系，否则计算的寄存器饱和度将是不正确的。文[ 1 ]中没有涉及到这一重要方面• 我们的工作是VLIW和EPIC码的扩展，具有多种寄存器类型;• 实验结果表明，我们的算法接近最优，而Berson的算法则不是最优的Pinter然而，首先，她的技术只适用于超标量代码，不适用于VLIW和EPIC代码。其次，她的模型没有考虑到多个寄存器类型。第三，也是最后一点，她7结论在本文中，我们继续我们早期的工作寄存器饱和（RS）的概念，以管理寄存器的压力，并避免溢出代码调度和寄存器分配步骤之前。我们认为，寄存器的限制必须考虑到ILP调度之前，但使用RS的概念，而不是由现有的最小化策略。否则，即使存在足够的寄存器，后续ILP调度器也将受到限制。计算DAG的寄存器饱和度是NP完全的。一个intLP精确配方。我们的正式数学模型和[14]中的理论研究使我们能够给出接近最优的算法。在存在分支的情况下，通过插入具有相应的入流弧的入口和出口值，非循环CFG的全局RS被带回到DAG（基本块）中的RS（参见[15]）。如果RS超过可用寄存器的数目，我们必须减少它，同时最大限度地减少关键路径的增加，这是一个NP难问题。提出了一种基于整数规划的最优精确RS约简方法S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131147如果我们假设写O-集（VLIW和EPIC代码），一些最佳解决方案可能需要在原始DAG中插入非正电路。这些循环可防止在存在资源约束的情况下调度扩展DDG。克服这个问题的一个充分必要条件是保证扩张图的拓扑排序的存在性。这是通过向intLP公式添加新的约束来完成的。我们还证明了，我们的初始算法简化RS是非常有效的最佳解决方案相比。一个重要的问题（让未来的工作）是最小的溢出代码插入数据依赖图。现有的研究插入溢出操作，无论是在顺序代码（无论FU的使用），或通过迭代ILP调度后溢出。我们认为这个问题必须在数据依赖图的层次上加以考虑引用[1] David A.伯森细粒度并行架构中寄存器分配和指令调度的统一。博士论文，匹兹堡大学，1996年。[2] Thomas S.更勇敢FRIGG：一种结合寄存器分配和指令调度的新方法。硕士论文，密歇根理工大学，1994年。[3] Dominique de Werra，Christine Eisenbeis，Sylvain Lelait，and Bruno Marmol.循环寄存器分配的图论模型。离散应用数学，93（2-3）：191[4] 克莉丝汀·艾森贝斯，弗朗哥·加斯佩洛尼，乌维·施维格尔肖恩。在多个指令发布处理器中分配寄存器。在IFIP WG 10.3并行体系结构和编译技术工作会议的会议记录中，PACTACM Press，June27[5] S. M. Freudenberger和J.C.拉滕伯格寄存器分配和指令调度的阶段排序。 在代码生成-概念，工具，技术。代码生成国际研讨会会议记录，第146-172页，伦敦，1992年。史普林格出版社[6] R. Govindarajan，H.杨角，澳-地张建民Amaral和G. R.高.最小寄存器指令序列问题：重温DAG的最优代码生成 在第15届国际并行和分布式处理研讨会（IPDPS-01）的会议录中，第26-26页，Los Alamitos，CA，2001年4月23-27日。IEEE计算机协会。[7] 威廉·杰尔比和克里斯托夫·莱姆埃。WBTK：一组新的微基准测试，以探索内存系统性能。在洛斯阿拉莫斯计算机科学研究所（LACSI）研讨会，2002年10月。[8] 约翰·詹森传输触发架构的制造商策略。博士论文，荷兰代尔夫特大学，2001年。[9] D. Kaestner和M.朗根巴赫用线性规划优化代码。计算机科学讲义，1575：122[10] Waleed M.梅莱斯具有溢出和流水线负载的二叉树的持续发布调度SIAM J. Comput. ，30（6）：1921148S.-答：A. Touati/Electronic Notes in Theoretical Computer Science 132（2005）131[11] 辛迪·诺里斯和洛里·L.波洛克一种对存储器敏感的全局寄存器分配器。在IEEE，编辑，Supercomputing 93 Proceedings：Portland，Oregon，第804IEEE计算机学会出版社.[12] 施洛米特湾 品特寄存器分配与指令调度：一种新方法。SIGPLAN Notices，28（6）：248[13] Rau'lS ilver a，JianWa n g，Gu a ng R. 去吧，去吧。 去找一个人。一种用于动态发布处理器的预处理系统指令集。在1997年并行架构和编译技术国际会议（PACT-97）的会议记录中，第78-89页，加利福尼亚州旧金山，1997年11月。IEEE计算机学会出版社.[14] 锡德·艾哈迈德·阿里·图瓦提超标量和VLIW码中的寄存器饱和。在计算机科学中的计算机构造国际会议论文集，讲义。Springer-Verlag，2001年4月。[15] 锡德·艾哈迈德·阿里·图瓦提指令级缓存中的寄存器压力。博士论文，《凡尔赛大学》，法国，2002年6月。请参见ria.fr/INRIA/Projects/a3/touati/thesis。