技术领域

本发明涉及现代处理器代码编译优化方法， 尤其涉及基于模调度实现循 环指令调度的编译方法及编译器装置。

背景技术

在现代计算机系统中， 通过编译器各种优化方法来挖掘处理器指令级 并 行性， 是提高处理器性能的有效手段。 软件流水是编译器中一种常见的优化 方法， 它通过在循环级别进行指令调度来挖掘指令级 并行性， 以提高处理器 的性能。

软件流水的基本思想是通过重叠执行不同循环 体指令来挖掘指令级并行 性。 编译器以 C/C++/Java等高级语言源程序作为输入， 从高级语言源程序中 提取循环相关的代码作为调度对象， 首先为这些循环建立控制流图 （CFG, Control-Flow Graph )和数据依赖图 （DDG, Data-Dependence Graph ) , 然后 将处理器中指令的延时和资源占用情况进行抽 象， 得到整个循环的控制依赖 约束、 数据依赖约束和资源约束。 基于模调度的这些约束条件， 软件流水使 用自顶向下、 自底向上或者双向调度方法， 对循环中的指令进行调度， 使其 重组成为新的循环。 重组之后的循环包括入口代码 ( rologue ) 、 核心代码 ( kernel ) 以及排空代码（ epilogue ) 三部分； 其中入口代码和出口代码都是 为了保持程序语义的正确性设置的， 而核心代码则是循环的主体部分。 在重 组之后的循环中， 循环核心的指令数目基本上和原来的循环保持 一致， 但是 指令顺序发生了变化， 尤其是相邻指令之间的依赖数量大大降低， 从而减小 指令之间由于依赖关系而导致的指令延时， 并进一步减小程序运行时间。

目前已有的软件流水技术一般釆用 "表调度" 等启发式策略， 在循环重 组过程中需要始终遵循所有的控制依赖约束、 数据依赖约束和系统资源约束。 若调度过程发生违反约束的冲突， 则调度过程可能会失败， 从而导致重组循 环的性能降低。 随着现代处理器中指令发射宽度的增加和指令 类型的增多， 以上这种由 于约束条件冲突引起的指令调度过程失败情况 也越来越常见。 调度过程的失 败一方面可能导致完全无法挖掘指令级并行性 ， 另一方面也可能引发循环执 行时间较长和寄存器压力较大等问题， 从而导致应用程序的性能较低。

因此， 有效地解决现有技术中由于约束条件冲突引起 的软件流水调度失 败问题， 从而提高循环重组之后的代码性能， 对提高处理器性能乃至整个计 算机系统性能都有着重要作用。

发明内容

本发明所要解决的技术问题是提供一种基于模 调度实现循环指令调度的 编译方法及装置， 能够有效地避免由于模调度约束条件冲突引起 的指令调度 失败。

为了解决上述技术问题， 本发明提供了一种基于模调度实现循环指令调 度的编译方法， 包括由编译器执行的下列步骤：

读入并解析源程序， 获取控制流图信息；

建立循环体结构的数据依赖约束和资源依赖约 束；

在对循环体结构执行模调度过程中， 若检测到指令调度结果会发生数据 依赖冲突和 /或资源冲突， 则根据符合相应约束的回溯模型解决数据依赖 冲突 和 /或资源冲突。

可选的， 读入并解析源程序， 获取控制流图信息的步骤包括：

读入高级语言源程序， 并通过控制流分析技术对高级语言的前端进行 解 析， 获取基本块， 并获取表述基本块的程序结构的控制流图信息 。

可选的 ,针对循环体结构建立数据依赖约束和资源依� �约束的步骤包括： 根据控制流图信息建立所述数据依赖约束， 根据目标处理器的资源信息 建立资源依赖约束。

可选的， 在对循环体结构执行模调度过程中， 若检测到指令调度结果会 发生数据依赖冲突和 /或资源冲突， 则根据符合相应约束的回溯模型解决所述 数据依赖冲突和 /或资源冲突的步骤包括： 根据预先对处理器执行可执行程序时釆用典型 输入数据收集的剖视信息 指导对循环指令的模调度；

针对循环体中每一条需要调度指令当前节点的 调度结果进行数据依赖冲 突的检测和 /或资源冲突的检测；

若检测到调度结果会发生数据依赖冲突和 /或资源冲突， 则相应地使用符 合数据依赖约束的回溯模型和 /或符合资源约束的回溯模型消除数据依赖冲 突和 /或资源冲突。

可选的，

根据预先对处理器执行可执行程序时釆用典型 输入数据收集的剖视信息 指导对循环指令的模调度的步骤包括：

根据剖视信息中的值剖视信息识别循环体结构 ， 并初始化数据依赖约束 和资源约束； 根据剖视信息中的路径剖视信息指导从控制依 赖到数据依赖的 转换过程；

在假定启动间距条件下， 釆用摆动模调度算法选择对当前指令的调度位 置， 并设置相应的调度优先级；

若检测到所述调度结果会发生所述数据依赖冲 突和 /或所述资源冲突， 则 相应地使用符合所述数据依赖约束的回溯模型 和 /或符合所述资源约束的回 溯模型消除所述数据依赖冲突和 /或所述资源冲突的步骤包括：

若检测选择的当前指令的调度位置会产生数据 依赖冲突， 则依据符合数 据依赖约束的回溯模型中的回溯节点选择目标 和约束条件选取部分指令节点 作为回溯节点， 取消对回溯节点选择的调度位置， 并更新回溯节点的调度优 先级； 若检测选择的当前指令的调度位置会产生资源 冲突， 则依据符合资源 约束的回溯模型中的回溯节点选择目标和约束 条件选取部分指令节点作为回 溯节点， 取消所有与该回溯节点发生资源冲突的节点， 并更新回溯节点的调 度优先级。

可选的， 该方法还包括： 重组循环体结构， 编译生成可执行程序， 包括： 根据剖释信息分析模调度收益，若判断模调度 收益能保证调度结果有效， 则根据调度优先级将相应指令调度到选择的调 度位置上， 并依据产生的循环 入口代码和循环出口代码重组所述循环体结构 ，将源程序编译成可执行程序。

为了解决上述技术问题， 本发明提供了一种基于模调度实现循环指令调 度的编译器装置， 其特征在于， 包括依次连接的控制流信息获取模块、 约束 建立模块以及模调度执行模块， 其中：

控制流信息获取模块设置为： 通过读入并解析源程序获取基本块， 并获 取表述基本块的程序结构的控制流图信息；

约束建立模块设置为： 根据控制流图信息和目标处理器的资源信息建 立 循环体结构的数据依赖约束和资源约束； 模调度执行模块设置为： 在对循环体结构执行模调度过程中， 若检测到 指令调度结果会发生数据依赖冲突和 /或资源冲突， 则根据符合相应约束的回 溯模型解决数据依赖冲突和 /或资源冲突。

可选的， 该编译器装置还包括与模调度执行模块连接的 剖视信息收集模 块， 其中：

剖视信息收集模块设置为： 在处理器执行可执行程序时根据典型输入数 据收集并向模调度执行模块反馈剖视信息， 其中包括值剖视信息和路径剖视 信息；

模调度执行模块设置为： 根据值剖视信息识别循环体结构， 并初始化模 调度对应的数据依赖约束和资源约束， 根据路径剖视信息指导从控制依赖到 数据依赖的转换； 在假定启动间距的条件下进行指令调度位置的 选择， 并设 置相应的调度优先级；若检测到所选择的指令 调度位置会发生数据依赖冲突， 则使用符合数据依赖约束的回溯模型消除数据 依赖冲突； 若检测到所选择的 指令调度位置会发生资源冲突， 则使用符合所述资源约束的回溯模型消除资 源冲突。

可选的，

模调度执行模块是设置为： 若检测到调度位置会产生数据依赖冲突， 则 依据符合数据依赖约束的回溯模型中的回溯节 点选择目标和约束条件选取部 分指令节点作为回溯节点， 取消对回溯节点选择的调度位置， 并更新回溯节 点的调度优先级； 若检测到调度位置会产生资源冲突， 则依据符合资源约束 的回溯模型中的回溯节点选择目标和约束条件 选取部分指令节点作为回溯节 点， 取消所有与回溯节点发生资源冲突的节点， 并更新回溯节点的调度优先 级。

可选的， 该编译器装置还包括与模调度执行模块连接的 循环结构重组模 块， 其中：

模调度执行模块还设置为： 根据值剖视信息分析模调度收益， 若判断模 调度收益保证调度结果有效， 则根据调度优先级将相应指令调度到选择的调 度位置上；

循环结构重组模块设置为： 依据模调度执行模块执行的模调度结果产生 循环入口代码和循环出口代码 , 重组循环体结构 , 将源程序编译成可执行程 序。

上述软件流水模调度方法及装置， 通过建立的数据依赖约束回溯模型和 资源约束回溯模型分别解决指令调度过程中的 数据依赖冲突和资源冲突， 并 通过使用可执行程序执行中的剖视信息指导指 令调度，并最终完成循环重组； 由此， 可避免循环体中相邻指令的数据相关， 减小生成代码的执行时间， 从 而有效地挖掘指令级并行性， 提高处理器系统乃至计算机系统性能。 附图概述

图 1 是本发明的基于模调度实现循环指令调度的编 译方法实施例流程 图；

图 2是图 1中对循环指令的模调度过程实施例流程图；

图 3是本发明用于实现循环指令调度建立回溯模� �实施例流程图； 图 4是本发明的基于模调度实现循环指令调度的� �译器装置实施例结构 框图。 本发明的较佳实施方式 下面结合附图和优选实施例对本发明的实施方 式进行详细地描述。 以下 例举的实施例仅用于说明和解释本发明，而不 构成对本发明技术方案的限制。

如图 1所示， 是本发明提供的基于模调度实现循环指令调度 的编译方法 实施例， 其流程包括如下步骤：

110: 在处理器执行可执行程序时， 编译器根据典型输入数据收集剖视信 息；

剖视信息表示的是目标可执行程序在给定典型 输入条件下执行的状态， 包括值剖视信息和路径剖视信息， 其中， 值剖视信息主要包括部分变量的典 型值， 尤其是循环边界典型值， 可用于计算软件流水模调度所能带来的收益， 从而决定是否要放弃当前指令节点的调度结果 ； 路径剖视信息主要包括控制 依赖发生的频率， 用于指导控制依赖到数据依赖的转换过程。

120: 编译器读入并解析源程序， 获取控制流图信息；

编译器读入高级语言源程序， 并通过控制流分析技术对高级语言的前端 进行解析， 获取基本块（指没有分支的一串顺序执行的指 令） ， 并获取表述 基本块程序结构的控制流图信息。

130: 建立数据依赖约束和资源依赖约束；

编译器根据控制流图信息中所表述的指令间数 据依赖信息建立循环体结 构的数据依赖图， 用于描述循环体中的数据依赖关系； 根据处理器的资源信 息建立对处理器资源约束的描述， 具体表示为资源使用表或者有限状态自动 机。

140: 根据剖视信息指导针对循环的模调度过程， 在调度过程中检测指令 调度结果出现的数据依赖冲突和 /或资源冲突， 并釆用符合相应约束的回溯模 型来消解冲突；

基于模调度方法， 在假定启动间距（Π, Initiation Internal )的条件下对循 环指令进行调度， 根据剖视信息中的循环边界典型值， 判断是否需要继续进 行当前循环的指令调度， 并通过计算软件流水模调度带来的收益， 判断是否 取消当前节点的调度结果； 根据路径剖视信息中的控制依赖发生的频率来 指 导从控制依赖到数据依赖的转换过程。 对于循环体中每一条需要调度的指令， 均针对其调度的结果进行数据依 赖冲突检测和资源冲突检测， 并消除检测出的相应冲突， 包括：

若检测到要调度指令的当前节点会发生数据依 赖冲突， 则使用符合数据 依赖约束条件的回溯模型消除冲突， 即取消当前节点的部分前驱和 /或后继节 点指令， 削弱当前节点的数据依赖约束以完成对其的指 令调度， 并重新设置 被取消节点的调度优先级。

若检测到要调度指令的当前节点会发生了资源 冲突， 则使用符合资源约 束条件的回溯模型消除冲突， 即取消与当前节点发生资源冲突的部分节点指 令， 削弱当前节点的资源约束以完成对其的指令调 度， 并重新设置被取消节 点的调度优先级。

150: 重组循环体， 编译生成可执行程序。

在上述方法是实例中， 步骤 140所表述的编译器对循环指令的模调度过 程实施例的流程如图 2所示， 包括如下步骤：

141 : 根据剖视信息识别循环体结构， 并初始化对应的模调度约束； 编译器根据剖视信息对目标循环结构进行识别 和解析， 并初始化该循环 结构对应的模调度约束， 主要包括数据依赖约束和资源约束。

142:在假定启动间距条件下，釆用摆动模调度� �法选择指令的调度位置， 并设置相应的调度优先级；

对寄存器压力敏感的循环体指令进行调度， 其过程釆用 "先假设启动间 距后调度" 的模调度思想， 即在假定启动间距条件下， 釆用摆动模调度算法 进行指令调度位置的选择。

143: 检测选择的调度位置是否会产生冲突， 是则执行步骤 144, 否则执 行步骤 145;

将选择的调度位置作为调度结果分别进行数据 依赖冲突检测和资源冲突 检测。

数据依赖冲突是指所选择的调度位置无法满足 循环指令内部的数据依赖 关系， 其检测方法基于表示当前循环数据依赖关系的 数据依赖图 （DDG ) 。 当前指令的调度位置必须满足两个条件： 1 )对于数据依赖图中该指令所对应 节点的所有前驱节点， 所选择的调度位置必须使得当前节点开始执行 的时刻 晚于所有前驱节点完成执行的时刻； 2 )对于数据依赖图中该指令所对应节点 的所有后继节点， 所选择的调度位置必须使得当前节点完成执行 的时刻早于 所有后继节点开始执行的时刻。 若当前节点的调度位置无法满足上述两个条 件的任意一个条件， 则可以判定发生了的数据依赖冲突。

资源依赖冲突是指由于处理器中运算单元、 访存单元等硬件资源的有限 性， 造成当前节点在所选择的位置中无法获得有效 资源的情况， 其检测方法 依赖于处理器资源约束的表示形式。 对于资源向量表（ Resource-Reservation Table, 参考 Alfred V.Aho的著作 Compilers: Principles, Techniques, & Tools. Second EMon)) ) 的资源约束描述形式， 若调度位置所对应资源向量表项中 的资源可用数量为 0 , 则可以判定发生了资源冲突。对于有限状态自 动机（参 考 DM Lavery ¥j论 ^ iModulo Scheduling for Control-intensive General-purpose Programs)) ) 的资源约束描述形式， 若调度位置使得自动机无法转移到下一 个有效状态， 则可以判定发生了资源冲突。

144: 针对检测出的数据依赖冲突釆用数据依赖约束 回溯模型消除， 针对 检测出的资源冲突釆用资源约束回溯模型消除 ；

上述针对数据依赖冲突和 /或资源冲突， 根据当前指令节点相应的依赖约 束条件从以下三个方面进行处理， 其流程可参见图 3 , 包括：

1441 : 根据依赖约束的特点判断对当前指令节点是否 需要进行回溯；

1442: 根据回溯节点选择目标和约束条件选取部分指 令节点作为回溯节 点， 取消对回溯节点的调度结果；

回溯节点的选择， 是提高用回溯模型消除相应冲突有效性的关键 。

在数据依赖约束回溯模型中， 将 "回溯节点尽量少" 、 "调度窗口尽量 大" 作为回溯节点选择目标， 将 "回溯节点被取消后仍然可调度" 、 "回溯 过程不引起颠簸" 等作为约束条件， 来选择回溯节点， 取消对这些回溯节点 的调度结果， 即取消选择的调度位置。

在资源约束回溯模型中， 将 "取消节点尽量少" 、 "回溯节点所占用的 关键资源尽量少" 或者 "引起的资源冲突最少" 作为回溯节点选择目标； 将

"回溯过程不引起颠簸" 、 "回溯过程不增加寄存器压力" 作为约束条件， 来选择回溯节点， 并取消所有与回溯节点发生资源冲突的节点。

1443: 更新回溯节点的调度优先级。

选择好回溯节点后， 重新设置回溯节点的调度优先级。

145-149: 根据剖释信息分析模调度收益， 若判断该模调度收益能保证调 度结果有效， 则根据调度优先级将相应指令调度到选择的调 度位置上， 并产 生循环入口代码和循环出口代码； 否则报告模调度失败， 重新执行步骤 142, 从选择指令的调度位置开始重新进行模调度。

根据剖释信息分析模调度收益， 其中包括分析是否减弱了寄存器压力。 当顺利地完成了所有指令的调度后， 输出重组后的循环， 并生成相应循 环入口代码和出口代码。

本发明针对上述方法实施例， 相应地还提供了基于模调度实现循环指令 调度的编译器装置实施例， 其结构如图 4所示， 包括依次连接的控制流信息 获取模块、 约束建立模块以及模调度执行模块， 其中：

控制流信息获取模块， 设置为： 于读入并解析源程序， 获取控制流图信 息；

约束建立模块， 设置为： 根据控制流图信息和目标处理器的资源信息建 立数据依赖约束和资源约束；

模调度执行模块， 设置为： 在执行模调度过程中针对检测指令调度结果 发生的数据依赖冲突和 /或资源冲突， 根据符合相应约束的回溯模型解决。

上述编译器装置实施例还包括与模调度执行模 块连接的剖视信息收集模 块， 其中：

剖视信息收集模块， 设置为： 在处理器执行可执行程序时根据典型输入 数据收集并反馈剖视信息， 其中包括值剖视信息和路径剖视信息；

模调度执行模块通过剖视信息收集模块反馈的 剖视信息指导对循环指令 的模调度， 包括在假定启动间距的条件下对循环指令进行 调度， 根据剖视信 息中的循环边界典型值， 指导指令调度的各阶段； 通过计算软件流水模调度 带来的收益， 判断是否取消当前节点的调度结果； 根据路径剖视信息中的控 制依赖发生的频率来指导从控制依赖到数据依 赖的转换过程。

在上述编译器装置实施例中，控制流信息获取 模块读入高级语言源程序， 并通过控制流分析技术对高级语言的前端进行 解析， 获取基本块， 并获取表 述基本块程序结构的控制流图信息；

约束建立模块根据控制流图信息中所表述的指 令间数据依赖信息建立数 据依赖图， 以描述循环体中的数据依赖关系， 其中， 部分数据依赖关系是通 过 IF指令-转换技术从部分控制依赖关系转化而来 ；建立的目标处理器资源约 束具体表示为资源使用记录或者有限状态自动 机；

模调度执行模块根据剖视信息识别循环体结构 ， 并初始化对应的模调度 约束； 在假定启动间距条件下， 釆用摆动模调度算法进行指令调度位置的选 择， 并设置相应的调度优先级； 若检测到选择的指令调度位置会发生数据依 赖冲突， 则使用符合数据依赖约束的回溯模型消除冲突 ； 若检测到选择的指 令调度位置会会发生了资源冲突，则使用符合 资源约束的回溯模型消除冲突。

模调度执行模块在数据依赖约束回溯模型中， 以 "回溯节点尽量少" 、 "调度窗口尽量大" 作为回溯节点选择目标， 以 "回溯节点被取消后仍然可 调度" 、 "回溯过程不引起颠簸" 作为约束条件， 选取部分指令节点作为回 溯节点， 取消对这些回溯节点的调度结果（即取消选择 的调度位置） ， 并重 新设置回溯节点的调度优先级； 在资源约束回溯模型中， 以 "取消节点尽量 少" 、 "回溯节点所占用的关键资源尽量少" 或者 "引起的资源冲突最少" 作为回溯节点选择目标， 以 "回溯过程不引起颠簸" 、 "回溯过程不增加寄 存器压力" 作为约束条件， 取消所有与回溯节点发生资源冲突的节点， 并重 新设置回溯节点的调度优先级。

上述编译器装置实施例还包括与模调度执行模 块连接的循环结构重组模 块， 其中：

模调度执行模块还设置为： 根据所述剖视信息中的值剖视信息分析模调 度收益， 若判断所述模调度收益能保证调度结果有效， 则根据调度优先级将 相应指令调度到选择的调度位置上；

循环结构重组模块， 设置为： 依据模调度执行模块执行的模调度结果产 生循环入口代码和循环出口代码， 重组循环体结构， 将所述源程序编译成可 执行程序。

本领域普通技术人员可以理解上述方法中的 全部或部分步骤可通过程序 来指令相关硬件完成， 所述程序可以存储于计算机可读存储介质中， 如只读 存储器、 磁盘或光盘等。 可选地， 上述实施例的全部或部分步骤也可以使用 一个或多个集成电路来实现， 相应地， 上述实施例中的各模块 /单元可以釆用 硬件的形式实现， 也可以釆用软件功能模块的形式实现。 本发明不限制于任 何特定形式的硬件和软件的结合。

以上所述仅为本发明的优选实施例而已， 并不用于限制本发明， 对于本 领域的技术人员来说， 本发明可以有各种更改和变化。 凡在本发明的精神和 原则之内， 所作的任何修改、 等同替换、 改进等， 均应包含在本发明的保护 范围之内。

工业实用性 上述实施方式通过建立的数据依赖约束回溯模 型和资源约束回溯模型分 别解决指令调度过程中的数据依赖冲突和资源 冲突， 并通过使用可执行程序 执行中的剖视信息指导指令调度， 并最终完成循环重组； 由此， 可避免循环 体中相邻指令的数据相关， 减小生成代码的执行时间， 从而有效地挖掘指令 级并行性， 提高处理器系统乃至计算机系统性能。