分簇VLIW处理器上统一的指令调度和寄存器分配方法

摘要

本发明公开了一种分簇VLIW处理器上统一的指令调度和寄存器分配方法，指令调度器将程序中所有基本块按照相反后序进行调度，并将每个基本块中的指令按照优先级调度；即，每次选取可调度指令中优先级最高的指令，给它分配簇及簇上的功能部件，并且使用寄存器分配器给该指令的虚拟寄存器分配物理寄存器。本发明具有可最大程度地减少程序的基本块中指令执行时间、有效降低寄存器压力等优点。

说明书

技术领域

本发明主要涉及到处理器的编译优化技术领域，特指一种适用于分簇VLIW处理器的指令 调度和寄存器分配方法。

背景技术

随着各种应用程序对DSP(数字信号处理器)的性能要求不断提高，当前的高端DSP通 常采用VLIW体系结构来挖掘指令级并行性，从而提高DSP处理器的性能。VLIW处理器由多 个功能部件组成，其中每个功能部件可以执行多种指令。所有的功能部件共享一个寄存器文 件。在每个时钟周期，多个指令可以在多个功能部件上并行执行。然而，单个寄存器文件极 大地阻碍了VLIW处理器的可扩展性，在增加功能部件数目的同时想要保持或加速时钟频率， 对于单个簇的体系结构来说是不可能的。分簇VLIW体系结构通过将单个簇的体系结构划分为 多个较小的簇来获得更高的性能和较低的功耗，每个簇有自己的功能部件和本地寄存器文件， 簇间由通信网络进行通信。

指令调度和寄存器分配是编译器优化的两个重要问题，对程序的执行时间有很大影响。 传统方法将寄存器分配和指令调度分两个阶段执行，从而会导致阶段顺序问题，使得编译代 码不够优化。若寄存器分配在指令调度前执行，同一个寄存器可能被分配给不同的变量，导 致伪依赖关系，因此降低代码的指令级并行性。若指令调度在寄存器分配之前执行，增加的 指令级并行性可能极大地增加寄存器压力，导致寄存器溢出。

分簇VLIW处理器使得指令调度和寄存器分配更具挑战性。首先，指令调度需要将指令分 配到不同的簇，不当的分配会导致不必要的簇间通信，从而增加基本块的执行时间。第二， 簇间的指令分配对不同簇上的寄存器压力有很大影响。不当的分配机制可能导致各簇的寄存 器压力不均匀而增加寄存器溢出。第三，当变量被从一个簇传递到其它簇的时候，会动态地 产生的新的活跃区间，并且需要其它簇上的多个寄存器来保存同一个变量的副本。第四，一 个变量的精确的活跃区间取决于它的第一个定义和最后一个使用的相关指令在何时被调度， 而无法由传统的针对静态代码的活跃区间分析来决定。

发明内容

本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种可最 大程度地减少程序的基本块中指令执行时间、有效降低寄存器压力的分簇VLIW处理器上统一 的指令调度和寄存器分配方法。

为解决上述技术问题，本发明采用以下技术方案：

一种分簇VLIW处理器上统一的指令调度和寄存器分配方法，指令调度器将程序中所有基 本块按照相反后序进行调度，并将每个基本块中的指令按照优先级调度；即，每次选取可调 度指令中优先级最高的指令，给它分配簇及簇上的功能部件，并且使用寄存器分配器给该指 令的虚拟寄存器分配物理寄存器。

作为本发明的进一步改进：所述寄存器分配器为一个递增寄存器分配器，所述递增寄存 器分配器根据指令调度器的调度情况给每条指令依次分配物理寄存器。

作为本发明的进一步改进：所述指令优先级在调度前根据指令间延迟和处理器资源限制 来确定，并且在调度过程中根据寄存器压力来动态更新。

作为本发明的进一步改进：所述簇的选择取决于指令在各簇上可能的调度时间及寄存器 压力。

作为本发明的进一步改进：在指令调度和寄存器分配过程中，对程序的控制流图中的变 量进行生命周期分析；首先根据控制流图，对变量进行静态的生命周期分析；然后在调度过 程中，所述递增寄存器分配器根据部分调度信息动态地分析变量的生命周期；即，根据已有 的部分调度，进一步对变量的生命周期进行动态的分析。

作为本发明的进一步改进：对于有n个变量的程序，静态生命周期分析的时间复杂度在 最坏情况下为O(n⁴)，在通常情况下为O(n)或O(n²)；动态生命周期分析的时间复杂度为 O(|B|*n)，其中|B|为控制流图中的基本块数目。

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

1、本发明的分簇VLIW处理器上统一的指令调度和寄存器分配方法，将指令调度和寄存 器分配结合在一个阶段完成，从而避免了传统方法将两者分别执行而带来的阶段顺序问题。

2、本发明的分簇VLIW处理器上统一的指令调度和寄存器分配方法，在计算指令优先级 时不仅考虑指令间延迟，也考虑处理器资源限制，而传统方法不考虑处理器资源限制，因此 本发明的方法所计算的指令优先级更加精确，更能精确反映指令的相对重要性。此外，本发 明在具体应用的调度过程中动态更新指令优先级，可以有效降低寄存器压力。

3、本发明的分簇VLIW处理器上统一的指令调度和寄存器分配方法，在调度指令时，指 令调度器考虑了多个因素：指令的最早调度时间和其后续指令的最早调度时间，以及各簇的 寄存器压力，从而能够更加有效地调度指令。

附图说明

图1是本发明的流程示意图。

具体实施方式

以下将结合说明书附图和具体实施例对本发明做进一步详细说明。

如图1所示，本发明的分簇VLIW处理器上统一的指令调度和寄存器分配方法，为：指令 调度器将程序中所有基本块按照相反后序进行调度，并将每个基本块中的指令按照优先级调 度。每次选取可调度指令中优先级最高的指令，给它分配簇及簇上的功能部件，并且使用递 增寄存器分配器给该指令的虚拟寄存器分配物理寄存器。即，在给每个指令分配簇和功能部 件的同时，给每个指令的虚拟寄存器分配物理寄存器。

在上述过程中，寄存器分配工作由一个递增寄存器分配器实现，它根据指令调度器的调 度情况给每条指令依次分配物理寄存器。

本实施例中，指令优先级可以在调度前根据指令间延迟和处理器资源限制来确定，并且 在调度过程中根据寄存器压力来动态更新。

本实施例中，簇的选择需要考虑指令在各簇上可能的调度时间及寄存器压力。

在上述过程中，本发明进一步对程序的控制流图中的变量进行生命周期分析；在具体应 用时，可以采用传统的递归算法来进行生命周期分析。

在上述过程中根据已有的部分调度，进一步对变量的生命周期进行动态的分析。对于有 n个变量的程序，静态生命周期分析的时间复杂度在最坏情况下为O(n⁴)，在通常情况下为O(n) 或O(n²)。动态生命周期分析的时间复杂度为O(|B|*n)，其中|B|为控制流图中的基本块数目。

由上可知，本发明的关键就在于将指令调度和寄存器分配放在同一阶段完成，其目的是： 最小化所有指令的总体执行时间。对每一个可调度指令，指令调度器在分配簇和功能部件的 同时，调用递增寄存器分配器给该指令分配物理寄存器。递增寄存器分配器还要考虑簇间通 信带来的寄存器之间的数据拷贝问题，在不同簇上用相应的寄存器保存一个变量的多个副本。 递增寄存器分配器根据变量生命周期和当前调度信息来决定分配或释放一个物理寄存器。由 于本发明将指令调度和寄存器分配结合在同一阶段执行，只有当相关的指令被调度时才能决 定变量生命周期的开始和结束。所以，递增寄存器分配器根据部分调度信息动态地分析变量 的生命周期。

因此，本发明将寄存器分配和指令调度集成在同一个阶段来执行，以产生性能优化的编 译代码。

在具体应用过程中，本发明在调度当前优先级最高的可执行指令v_i时，给v_i选择簇取决 于v_i在各簇上可能的最早执行时间或它的直接后续指令v_j的最早执行时间。为v_i选择的簇是 使得v_j可以尽早执行的。若不能评估v_j的执行时间，则为v_i选择一个簇使得v_i可以尽早执行。 此外，各簇的寄存器压力也在考虑范围内，以避免各簇的寄存器压力不均衡而引发不必要的 寄存器溢出。

与传统的图着色寄存器分配方法不同，递增寄存器分配器按照指令调度的顺序给逐条指 令分配寄存器。当调度一条可执行指令v_i时，如果需要另外一条指令v_k产生的结果a并且a 已经被溢出，或者v_k和v_i不在同一个簇上，则需要为a在v_i所在的簇上分配一个寄存器。随 后，为指令v_i的目标寄存器分配一个物理寄存器，如果此时没有空闲的物理寄存器，需要选 择一个物理寄存器的值溢出并将该物理寄存器分配给v_i的目标寄存器。

以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于 本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术 人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。