用于从代码语句生成SIMD代码的方法和系统

摘要

本发明涉及一种用于从代码语句生成SIMD代码的方法和系统。从包括非同构代码语句的代码语句生成SIMD代码。接收代码语句，每个代码语句具有采用相应操作符顺序的一个或多个操作符，并且每个操作符具有类型和关联的操作数。所接收的代码语句中的至少两个代码语句在不同操作符顺序位置中具有相同类型的操作符。在每个所述代码语句中，针对相同类型的操作符标识第一操作符顺序位置。对于每个所述代码语句，针对操作符顺序位置在所述第一操作符顺序位置之前的操作符及其关联的操作数生成代码。至少基于所标识的第一操作符顺序位置、对应的操作符类型以及与所标识的操作符顺序位置处的操作符类型关联的操作数，生成SIMD代码。

说明书

技术领域

本公开一般地涉及用于代码生成的软件开发工具，更具体地说，涉及 编译代码以便在针对单指令多数据(SIMD)执行配置的机器上执行。

背景技术

SIMD配置的计算机包括多个处理元件，它们同时针对多个数据点执 行相同的操作。SIMD处理元件通常用于同时对多组数值进行相加或相乘， 以便实现多媒体编码和呈现以及科学应用。在没有编译器支持的情况下使 用SIMD指令实现算法可能需要用户知道有关数据对齐、体系架构特定指 令集和SIMD寄存器大小的限制。编译器可以允许用户通过从用户的标量 代码生成支持SIMD的代码，利用SIMD处理元件的速度。

发明内容

本公开的各实施例公开一种用于从包括非同构代码语句的代码语句生 成SIMD代码的方法、计算机程序产品和系统。一个或多个处理器接收多 个代码语句，每个代码语句具有采用相应操作符顺序的一个或多个操作符。 每个操作符具有类型和关联的操作数。所述多个代码语句中的至少两个代 码语句在不同操作符顺序位置中具有相同类型的操作符。所述一个或多个 处理器在所述至少两个代码语句的每一个中，针对所述相同类型的操作符 标识第一操作符顺序位置。对于所述至少两个代码语句的每一个，所述一 个或多个处理器针对操作符顺序位置在所述第一操作符顺序位置之前的操 作符及其关联的操作数生成代码。所述一个或多个处理器至少基于所标识 的第一操作符顺序位置、对应的操作符类型，以及与所标识的操作符顺序 位置处的操作符类型关联的操作数，生成SIMD代码。

附图说明

从以下将结合附图阅读的对本发明的示例性实施例的详细说明，本发 明的特性和优点将变得显而易见。附图的各种特性不按比例，因为各图是 为了清晰起见，促进所属技术领域的技术人员结合详细说明理解本发明。 在附图中：

图1示出显示根据本公开的一个实施例的标量代码语句的数据并行表 示和标量代码语句的数据并行机会的示例性包；

图2示出根据本公开的一个实施例的SIMD优化编译器环境的功能框 图；

图3是示出根据本公开的一个实施例的有序选择准备例程的操作的流 程图；

图4是根据本公开的一个实施例的示例性包的示意图；

图5a和5b是示出根据本公开的一个实施例的选择例程的操作的流程 图；

图6-14示出根据本公开的一个实施例的用于从数据并行机会中选择 操作符匹配以便优化的包的示例性处理；

图15示出根据本公开的一个实施例的SIMD优化编译器环境的计算 设备的组件的框图。

具体实施方式

在计算中，代码的基本块是程序中具有仅一个入口点和仅一个出口点 的代码部分。编译器通常将程序分解为其基本块，作为生成编译代码的第 一步。生成支持SIMD的代码的典型编译器从标量代码的基本块中的“同 构”代码模式生成支持SIMD的代码。当代码的基本块中的多个代码语句 或同构代码语句全部按照相同顺序在多个代码语句中包含相同操作符(例 如乘法)，并且将操作符应用于存储器相邻操作数时，存在同构代码模式。 某些编译器可以通过剥离和展开循环，将循环中的代码主体分解为基本块， 作为一种用于在展开的循环主体中标识同构代码语句的方式。这些同构代 码语句可以表示数据并行机会，以便编译器使用SIMD指令进行优化。

本公开的各实施例可以允许编译器扩展数据并行机会以便进行SIMD 优化。各种实施例可以有利地优化来自非同构代码语句以及同构代码语句 的代码，以便生成SIMD指令。本公开的各实施例可以使用标量代码的数 据并行表示(以下称为“包(pack)”)，以便生成支持SIMD的代码。 不同于仅打包来自同构标量代码的代码语句的典型编译器，本公开的某些 实施例可以打包同构和非同构语句两者的数据并行表示。

图1示出显示根据本公开的一个实施例的同构和非同构标量代码语句 110的数据并行表示以及标量代码语句110的数据并行机会190的示例性 包180。如下面详细描述的那样，包创建器210从标量代码语句110创建 包180和数据并行机会190。

在一个实施例中，每个标量代码语句110a-110d可以在包180中表示 为语句阵列，例如行A-行D。语句阵列中的操作符可以具有操作符在阵 列中的位置顺序。在一个实施例中，每个语句阵列可以是语句树的后序表 示，其中语句阵列的较低指数在左侧，并且较高指数的右侧。每个语句阵 列可以由包180中的行(例如行A到行D)表示，并且是有序的以便维护 标量代码语句在基本块中的原始顺序。例如，行A表示标量代码语句110a， 行B表示标量代码语句110b等。如图所示，包180是标量代码语句110a- 110d的语句树的示例性后序表示。在此示例性实施例中，所有操作数位于 其对应的操作符的左边。其它实施例可以将操作数定位在其操作符左边之 外的位置，甚至定位在包180外部的位置，只要可以针对包180中的每个 操作符确定操作数位置即可。某些实施例可以在包180中包括信息，该信 息指示操作数数据类型、操作数位置，以及每个语句阵列和每个语句阵列 中的每个操作符的已处理指示符。在针对语句阵列和操作符生成编译代码 之后，这些语句阵列和操作符被视为已处理。

在一个实施例中，包180可以包括非线性化地址表达式以及线性化地 址表达式作为操作数。例如，位于包180中的(行A,列1)处的操作数“R[1]” (例如表示阵列中的地址)是示例性非线性化地址表达式。可以在代码生 成期间对非线性化地址表达式进行解析。各种实施例可以创建包，以便包 中的每个语句阵列与其相邻语句阵列具有数据并行机会。某些实施例可以 将包的大小限制为仅包括足够的语句阵列，以便使用每个语句阵列中的一 个操作数填充SIMD寄存器。

数据并行机会190表示包180中进行SIMD优化的机会，并且可以将 这些机会表示为包180中的操作符位置，以下称为“操作符匹配”。数据 并行机会190中的每组操作符匹配190a-190e表示来自包180中的一个或 多个语句阵列的相同操作符的位置。每组操作符匹配190a-190e可以包括 来自包180中的每个语句阵列的最多一个操作符匹配。数据并行机会190 中的一组示例性操作符匹配190a将包180位置(行A,列3)的乘法操作符与 包180位置(行B,列3)、(行C,列3)和(行D,列3)的乘法操作符相匹配， 作为可以优化为一个SIMD指令的一组潜在标量指令操作符。某些实施例 可以在包180中嵌入数据并行机会。

各种编译器实施例可以将数据并行机会190中的匹配操作符190a- 190e的全部或子集优化为SIMD指令，或者不优化任何匹配操作符。有关 从数据并行机会190中选择哪些匹配操作符以便优化为SIMD指令的考虑 可以包括但不限于操作数数据类型、架构SIMD寄存器大小、原始标量代 码的顺序保留，以及收集和分散SIMD寄存器的操作符的操作数的成本。 各种编译器实施例可以生成代码，该代码将数据并行机会190优化为单个 SIMD指令、多个SIMD指令、SIMD和标量指令的组合，或者标量指令 序列。

图2示出根据本公开的一个实施例的SIMD优化编译器环境299的功 能框图。SIMD优化编译器环境299包括计算设备222。计算设备222表 示计算设备、系统或环境，其包括编译器200以及标量代码语句110、包 180、数据并行机会190、窗口290和生成的SIMD代码指令295的存储， 它们全部例如可以存储在有形存储设备上，该有形存储设备例如包括有形 存储设备(多个)1530(图15)或可移动有形存储设备(多个)1570(图 15)。

计算设备222可以是膝上型计算机、笔记本计算机、个人计算机(PC)、 台式计算机、平板计算机、瘦客户机，或者能够执行本公开实施例的所需 功能的任何其它电子设备或计算系统。计算设备222可以包括内部和外部 硬件组件，如针对图15进一步详细示出和描述的那样。在本公开的其它各 种实施例中，计算设备222可以表示使用集群计算机和组件充当单个无缝 资源池的计算系统。一般而言，计算设备222表示能够执行根据本公开的 一个实施例的机器可读程序指令的任何可编程电子设备或可编程电子设备 组合。

在计算设备222中，编译器200可以包括包创建器210、初始化例程 220、有序选择准备例程230、选择例程240以及代码生成例程250。在一 个实施例中，编译器200访问标量代码语句110，创建包180、数据并行机 会190和窗口290，并且生成支持SIMD的代码295。编译器200的一个 实施例可以基于编译器参数生成支持SIMD的代码295，这些编译器参数 标识可以针对其启用生成的代码的SIMD体系架构。计算设备222可以被 配置有SIMD处理元件1545(图15)，并且其它实施例可以针对计算设 备222的SIMD体系架构生成支持SIMD的代码。

在一个实施例中，包创建器210可以将编译器200编译的计算机程序 分解为基本块，并且分析基本块以便标识可以表示SIMD优化机会的标量 代码语句。包创建器210可以从程序的标量代理语句中的同构语句和非同 构语句中标识所有可能的SIMD优化机会。包创建器210可以标识SIMD 优化机会而不考虑操作数存储位置。例如，标识的数据并行机会190可以 包括以下操作符：这些操作符的关联操作数在存储器中不相邻或非存储器 相邻。包创建器210的各种实施例最初可以忽略操作数的位置，并且收集 所有功能上可能的SIMD优化机会。包创建器210随后可以考虑存储位置， 从最初可能的SIMD优化机会中确定优先级。包创建器210可以创建包 180，包180表示被分析代码的基本块中具有SIMD优化机会的所有标识 的标量代码语句。包创建器210还可以创建被标识为潜在SIMD优化机会 的数据并行机会190，它们将操作符定位在包180中表示的标量代码语句 中。可以将创建的包180的位置和数据并行机会190传递到初始化例程 220。

在一个实施例中，初始化例程220接收包180和数据并行机会190， 创建窗口290，并且初始化下面描述的各种指针和值，这些指针和值用于 在数据并行机会190中选择哪些操作符匹配以便优化。参考图4，初始化 例程220可以初始化指向包180中的每个语句阵列的指针，例如语句指针 Spa-SPd和操作数指针OPa-OPd，并且指示包180中的所有语句阵列和 操作符均未由编译器200处理。某些实施例可以初始化扫描指针以便指向 包180中的第一语句阵列。

编译器200可以使用初始化例程220创建的窗口290，以便包括数据 并行机会190中要优化为SIMD指令的选定操作符匹配。在处理包180和 生成编译代码期间，可以重复填充和清空窗口290。窗口290的结构可以 包括但不限于阵列、一组阵列、链接列表、一组链接列表以及简单列表。 一个窗口290可以服务于包180。

在一个实施例中，有序选择准备例程230最初从初始化例程220接收 控制，并且接收创建的空窗口290、创建的包180、初始化的扫描指针、初 始化的语句阵列指针，以及标记为未被处理的所有语句阵列和操作符。有 序选择准备例程230可以准备其它指针，初始化窗口290，并且设置包180 搜索限制以便为下面更详细描述的选择例程240做准备。

有序选择准备例程230可以确定可在包180的何处开始选择要优化为 SIMD代码指令的数据并行机会，并且设置适当的指针。有序选择准备例 程230还可以设置搜索限制，从而确定可以在包180中的何处结束选择要 优化为SIMD指令的数据并行机会。搜索限制可以由将用于生成的SIMD 指令的SIMD寄存器的大小确定。SIMD寄存器大小确定可以优化为一个 SIMD指令的最大数量的操作数，并且因此确定要搜索的最大数量的语句 阵列。例如，如果将四个操作数放入SIMD寄存器中，则搜索限制可以是 四个语句阵列，从而允许优化每个语句阵列中的一个操作数。某些实施例 可能不限制要搜索的语句阵列数量，但可能反而限制选择用于优化的操作 符数量，从而允许将非相邻语句阵列中的操作数优化为一个SIMD指令。 有序选择准备例程230可以使用包180中要优化的操作符位置来初始化窗 口290。在各种实施例中，可以在以下情况下执行有序选择准备例程230： 每次包创建器210创建新包时，在生成每个SIMD指令之后，以及每当选 择例程240(将在下面参考图5a和5b更详细描述)中止包180的搜索时。 有序选择准备例程230还可以确定何时已处理包180中的所有操作符。

在一个实施例中，有序选择准备例程230可以接收新创建的包180， 包180包括以下各项：全部标记为未完全处理(以下为“活动”)的多个 语句阵列；语句指针Spa–SPd(图4)，每个指向其相应的语句阵列的开 始；每个语句阵列中标记为尚未处理(NYP)的每个操作符；以及初始化 后的扫描指针，其指向包180中的第一语句阵列。

有序选择准备例程230可以备选地接收包180，包180已经被搜索至 少一次并且包括多个语句阵列，每个适当地标记为完全处理(以下为“非 活动”)或活动。语句指针Spa、SPb、SPc、SPd各自指向其相应的语句 阵列。操作符指针OPa、OPb、OPc、OPd各自指向其相应的语句阵列中 的操作符，该操作符标记为已处理或尚未处理(NYP)。扫描指针可以指 向包180中的第一语句阵列(在生成SIMD指令之后)，或者可以指向包 180中的多个语句阵列的任何一个的开始(每当选择例程240中止包180 的搜索时)。当向有序选择准备例程230输入时，窗口290可以为空。

图3是示出根据本公开的一个实施例的有序选择准备例程230的操作 的流程图。有序选择准备例程230可以在305判定是否需要初始化在输入 时接收的扫描指针，该扫描指针由初始化例程220或选择例程240(下面 参考图5a和5b描述)设置。在一个实施例中，在输入时指向包180中的 第一语句阵列的扫描指针可以指示需要初始化扫描指针。对于需要初始化 的扫描指针，有序选择准备例程230可以在310定位包180中标记为活动 的第一(或最低指数)语句阵列，例如图4中的行A。当包180中的所有 语句阵列均标记为非活动(如在315判定的那样)时，包180中的所有操 作符均被处理，并且已针对包180表示的所有标量代码语句110生成代码。 如果包180中的至少一个语句阵列标记为活动(如在315判定的那样)， 则有序选择准备例程230可以在320设置扫描指针以便指向包180中标记 为活动的最低指数语句阵列，例如图4中的行A。对于如图4中所示的新 创建的包180，可以始终初始化示例性扫描指针以便指向第一语句阵列。 在设置扫描指针之后，因为可能不需要初始化(在中止搜索包180之后) (如在305判定的那样)，或者因为在320完成初始化，有序选择准备例 程230可以在330针对包180中的每个语句阵列设置操作符指针OPa、 OPb、OPc、OPd，以便指向每个相应的语句阵列中标记为尚未处理(NYP) 的最低指数操作符。对于如图4中所示的新创建的包180，示例性操作符 指针OPa、OPb、OPc、OPd指向其相应的语句阵列中的最低指数操作符， 因为如图4中所示的新创建的包180中的所有操作符均标记为NYP。有序 选择准备例程230可以在336确定要优化的操作符。要优化的操作符可以 是扫描指针指向的语句阵列中标记为NYP的最低指数操作符。在如图4 中所示的示例性新创建的包180中，要优化的操作符是数据并行机会190 中的位置(SPa,列3)或简称为“(a,3)”处的乘法操作符。有序选择准备 例程230可以在340将要优化的操作符的位置添加到290，如图4中所示。 有序选择准备例程230可以在350确定与添加到窗口290的操作符关联的 操作数的数据类型的大小，并且可以在360使用大小设置搜索限制。搜索 限制可以通过限制搜索的包180语句阵列的数量，最小化搜索时间。有序 选择准备例程230然后可以将控制传递到选择例程240。

返回到图2，选择例程240从有序选择准备例程230接收控制，并且 接收初始化后的扫描指针、其中所有语句阵列和操作符指示它们是否以被 处理的包180、指向每个语句阵列中的最低指数NYP操作符的初始化后的 操作符指针、初始化后的扫描限制，以及使用要优化为SIMD指令的操作 符的位置初始化的窗口290。选择例程240搜索包180，以便针对在窗口 290中初始化的操作符从数据并行机会190中获得操作符匹配，并且将选 定操作符匹配位置添加到窗口290，以便由代码生成例程250用于针对选 定操作符匹配生成优化后的SIMD指令。

选择例程240的某些实施例可以仅从数据并行机会190中选择操作符 匹配以便添加到窗口290以进行优化，这些操作符匹配的操作符位置语句 阵列指数大于有序选择准备例程230在窗口290中初始化的操作符位置的 语句阵列指数，从而生成以下代码：该代码维护在包180中表示的原始标 量代码语句110的操作顺序或操作符优先顺序。在以下情况下将完成选择 例程240：当窗口290包括足够的匹配操作符以便使用其操作数填充SIMD 寄存器时，当在窗口290中初始化的操作符在数据并行机会190中的所有 操作符匹配(例如190a(图4))均被处理时，当搜索整个包180时，以 及当达到有序选择准备例程230设置的搜索限制时(即使选定数据并行机 会的操作数可能未完全填充SIMD寄存器)。每当针对在窗口290中初始 化的操作符，从数据并行机会190中选择操作符匹配将导致生成不维护在 包180中表示的原始标量代码语句110的操作顺序的指令时，选择例程240 可以中止选择搜索而不生成任何代码。

图5a和5b是示出根据本公开的一个实施例的选择例程240的操作的 流程图。选择例程240可以在505判定针对其位置最近添加到窗口290的 操作符，是否在数据并行机会190中存在操作符匹配。如果在数据并行机 会190中存在匹配操作符，例如190a(图4)(如在505判定的那样)， 则选择例程240可以在510从数据并行机会190中选择以下操作符匹配： 该操作符匹配的语句阵列指数大于其位置最近添加到窗口290的操作符的 语句阵列指数，但该操作符匹配的语句阵列指数小于剩余数据并行机会 190的语句阵列指数。例如，在图4中，最近添加到窗口290的操作符位 置是(a,3)；满足上面选择准则的操作符匹配位置是(b,3)。如果选定操作符 匹配在有序选择准备例程230设置的扫描限制内(如在515判定的那样)， 并且选定操作符匹配表示的操作符是其语句阵列中的最低指数NYP操作 符(如在517判定的那样)，则选择例程240可以在520将选定操作符匹 配的操作符位置添加到窗口290。在一个实施例中，选择例程240可以通 过将选定操作符匹配位置与相应语句阵列“x”的操作符指针(OPx)相比 较，确定选定操作符匹配是语句阵列中的最低指数NYP操作符。其位置 等于操作符指针(OPx)指向的位置的选定操作符匹配可以被确定为语句 阵列中的最低指数NYP操作符。在图4中，示例性选定操作符匹配位置(b, 3)等于OPb指向的位置。

如果选定操作符匹配不是语句阵列中的最低指数NYP操作符(如在 517判定的那样)，则选择例程240可以判定选定操作符匹配是否已被处 理，或者处理选定操作符匹配是否可以导致生成不维护在包180中表示的 原始标量代码语句110的操作顺序的代码。在一个实施例中，选择例程240 可以再次通过比较选定操作符匹配位置与语句阵列“x”的操作数指针 (OPx)做出判定。对于其列指数小于操作数指针(OPx)的列指数的选 定操作符匹配位置，选定操作符匹配可能已经在先前搜索中处理。在一个 实施例中，选择例程240可以在包180的任何一次选择搜索期间，仅选择 数据并行机会190的子集以便在SIMD指令中优化，从而绕过其它机会直 到后续选择搜索。其列指数大于操作数指针(OPx)的列指数的选定操作 符匹配位置可以生成不维护包180表示的原始标量代码语句110的操作顺 序的代码，并且可以导致选择例程240中止选择扫描。

如果选定操作符匹配已被处理(如在519判定的那样)，则选择例程 240可以在525判定数据并行机会190中是否存在其它操作符匹配。如果 数据并行机会190中存在其它操作符匹配(如在525判定的那样)，则可 以在530从数据并行机会190中选择新操作符匹配，并且继续选择搜索。 新选择的操作符匹配(在530选择)可以表示数据并行机会190中的下一 个操作符匹配，该操作符匹配的语句阵列指数大于在519判定已经处理的 操作符匹配的语句阵列指数，但小于剩余数据并行机会190的语句阵列指 数。

对于不是语句阵列中的最低指数NYP操作符(如在517判定的那样)， 并且尚未处理(如在519判定的那样)的选定操作符匹配，选择例程240 可以中止选择搜索，以便防止生成可能不维护在包180中表示的原始标量 代码110的操作顺序的代码。选择例程240可以在532从窗口290中删除 所有操作符位置，并且设置扫描指针以便指向操作符匹配的语句阵列，从 而导致中止选择搜索。执行可以继续，其中有序选择准备例程230重新初 始化指针和值，以便进行包180的新选择搜索。

在520将选定操作符匹配的操作符位置添加到窗口290之后，选择例 程240可以在535判定是否已向窗口290添加足够的操作符匹配以便使用 其操作数填充架构SIMD寄存器。当其位置在窗口290中的匹配操作符的 操作数未填充SIMD寄存器(如在535判定的那样)时，并且当数据并行 机会190中存在其它操作符匹配(如在537判定的那样)时，选择例程240 可以在510选择另一个数据并行机会190，并且继续选择搜索。

当选择搜索完成时，因为针对其位置最近添加到窗口290的操作符， 数据并行机会190中不存在其它操作符匹配(如可以在505、525和537 判定的那样)，窗口290包括足够的匹配操作符以便使用其操作数填充 SIMD寄存器(如在535判定的那样)，或者存在于数据并行机会190中 的操作符匹配在有序选择准备例程230中定义的搜索限制之外(如在515 判定的那样)，选择例程240可以在540将包180中包括在窗口290中的 所有操作符位置标记为已处理。对于属于其相应的语句阵列中要处理的最 后操作符的任何操作符(如在545判定的那样)，选择例程240可以在546 将相应的语句阵列标记为“完全处理”或“非活动”。选择例程240可以 在550例如将窗口290的位置传递到代码生成例程250，以便针对其位置 在窗口290中的操作符生成SIMD指令。选择例程240可以在560清空窗 口290，并且设置扫描指针以便指向包180中的最低指数语句阵列。执行 可以继续，其中有序选择准备例程230重新初始化指针和值，以便进行包 180的新选择搜索。

返回到图2，代码生成例程250从选择例程240接收控制，以便针对 窗口290中的选定操作符匹配生成支持SIMD的代码。在窗口290中表示 的所有操作符都相似，但它们来自不同的标量代码语句。从中选择操作符 匹配的标量代码语句可以是同构和非同构的。当生成支持SIMD的代码时， 代码生成例程250可以定位与每个选定操作符关联的操作数。由先前计算 产生的操作数可以存储在临时变量中。临时变量可以是与对应的选定操作 符关联的操作数。代码生成例程250针对包180接收的第一窗口290可以 表示具有关联的操作数的操作符，这些关联的操作数位于存储器中或者是 立即操作数。在针对同一包180接收的后续窗口290中，这些操作符的关 联操作数可以是由接收的先前窗口290的计算产生的临时变量。代码生成 例程250可以将SIMD指令的结果存储在临时变量中，并且可以将临时变 量的符号指数与其操作符位置在窗口290中的每个操作符关联。如果临时 变量例如是向量，则代码生成例程250可以另外将该向量的特定通道与特 定操作符关联。对于仅包含一个操作符位置的窗口290，代码生成例程250 可以生成标量指令，或者可以生成仅使用SIMD寄存器的一个通道的 SIMD指令。在一个实施例中，包创建器210可以在包180中指示代码生 成例程250应该如何在没有选定任何数据并行机会190的情况下针对操作 符生成指令。

代码生成例程250可以针对操作数执行分析以便确定最有效的操作数 收集。代码生成例程250可以判定选定匹配操作符的操作数是否全部位于 存储器的连续块中，并且如果这样，则例如可以生成向量指令以便加载操 作数。当操作数需要重新排序时，可以由置换指令执行操作数的加载。对 于非连续操作数存储位置，代码生成例程250可以将操作数逐个加载到标 量指令中，并且例如生成置换或移动指令以便将这些操作数定位在SIMD 寄存器的适当通道中。在另一个实施例中，可以使用固有指令，例如IBM 的Power Systems平台上固有的vec_insert。可以在其它体系架构平台上使 用类似的固有指令。在加载所有操作数之后，代码生成例程250可以生成 应用窗口290中的操作符的SIMD指令，并且例如将结果放在临时变量中。 CONV操作符可以生成打包和解包指令，如通常用于使用SIMD指令优化 CONV操作那样。代码生成例程250可以减少通过执行副本传播通道生成 的语句的最终数量。

图6-14示出根据本公开的一个实施例的用于从数据并行机会190中选 择操作符匹配以便优化的包180的示例性处理。所述描述是示例性的而不 是限制性的。

图6示出由包创建器210(图2)创建并且由初始化例程220初始化的 新包180，并且示出针对新包180初始化的所有语句指针SPa、SPb、SPc、 SPd、指示它们为活动的所有语句阵列，以及包180中标记为NYP的所有 操作符。有序选择准备例程230已设置扫描指针以便指向包180中的最低 指数语句阵列，初始化操作符指针OPa、OPb、OPc、OPd以便指向每个 相应的语句阵列的最低指数操作符，并且初始化窗口290以便包括扫描指 针指向的语句阵列中的最低指数NYP操作符的操作符位置，在该实例中 为行A中的列3处的乘法操作符。语句阵列中的操作符将在以下通过其(行, 列)位置(例如(a,3))引用。在该实例中，与操作符关联的操作数数据类型 确定有关要搜索的语句阵列数量的限制。该实例还假设包180(包括阵列 R、S和X)中的所有操作数是长度为四的整数数据类型，并且SIMD寄 存器的长度为十六字节。将四个示例性操作数放入每个示例性SIMD寄存 器中，从而将搜索的示例性语句阵列数量限制为四。在该实例中，当在行 A处开始搜索时，选择例程240可以全部搜索行A–行D表示的所有语句。

有序选择准备例程230初始化到窗口290中的位置(a,3)处的示例性乘 法操作符可以与数据并行机会190中的一组操作符匹配190a中的位置(b, 3)、(c,3)和(d,3)处的乘法操作符相匹配。选择例程240从所述一组操作符 匹配190a中选择实际操作符匹配以便优化。选择例程240确定位置(a,3) 处的操作符在数据并行机会190中具有操作符匹配(b,3)，并且行B在搜索 限制内。因为操作符位置(b,3)是行B中的最低指数NYP操作符，即，操 作符指针OPb指向位置(b,3)，所以选择例程240将操作符位置(b,3)添加 到窗口290。选择例程240然后确定数据并行机会190中存在另一个操作 符匹配(c,3)。因为语句阵列行C也在搜索限制内，并且操作符指针OPc 指向操作符位置(c,3)，所以选择例程240将操作符位置(c,3)添加到窗口 290。选择例程240可以针对数据并行机会190中的操作符匹配(d,3)重复 该过程。窗口290现在针对相同操作符(在该实例中，为乘法操作符“*”) 包括四个操作符位置，每个操作符位置具有相同数据类型(例如，长度为 四的整数)的操作数。现在将窗口290发送到代码生成例程250，以便针 对位于包180中的(a,3)、(b,3)、(c,3)、(d,3)处的乘法操作符生成SIMD 指令。来自窗口290的操作符现在可以在包180中全部标记为已处理。

图7示出在有序选择准备例程230执行以下操作之后的包180：重新 初始化扫描指针以便指向包180中属于活动的最低指数语句阵列(在该实 例中，该语句阵列仍然是包180中的第一语句阵列)，重新初始化操作符 指针OPa、OPb、OPc、OPd以便指向每个相应的语句阵列的最低指数 NYP操作符(在该实例中，这些操作符更改为先前选择搜索的结果)，并 且初始化窗口290以便包括语句阵列中扫描指针指向的最低指数NYP操 作符的操作符位置。在该实例中，扫描指针仍然指向语句阵列行A，因为 并非语句阵列中的所有操作符均被处理。操作符指针OPa现在指向位置(a, 6)处的乘法操作符，其作为语句阵列中的最低指数NYP操作符，因为语句 阵列行A中的位置(a,3)处的前一个操作符已被处理，如上面参考图6所述。 与操作符(a,6)关联的操作数数据类型可以确定有关要搜索的语句数量的 新限制。因为该实例假设包180中的所有数据类型是长度为四的整数，所 以选择例程240可以全部搜索语句阵列行A–行D。有序选择准备例程230 初始化到窗口290中的位置(a,6)处的示例性乘法操作符与数据并行机会 190中的一组操作符匹配190b中的位置(c,8)和(d,8)处的乘法操作符匹配。 选择例程240确定位置(a,6)处的操作符在数据并行机会190中具有操作符 匹配(c,8)，并且行C在搜索限制内。因为操作符位置(c,8)不是行C中的 最低指数NYP操作符，即，位置(c,8)到语句阵列行C中的列指数大于操 作符指针OPc指向的操作符位置的列指数，所以选择例程240从窗口290 中删除操作符位置(a,6)，中止选择搜索以便防止生成可能不维护原始标量 代码的操作顺序的指令，并且设置扫描指针以指向行C，以便用信号通知 有序选择准备例程230初始化指针从而使下一次搜索在行C上开始。

图8示出在有序选择准备例程230执行以下操作之后的包180：重新 初始化扫描指针以便指向选择例程240用信号通知的语句阵列，如上面参 考图7所述。操作符指针OPa、OPb、OPc和OPd保持不变，因为先前 选择搜索没有处理任何操作符。有序选择准备例程230初始化窗口290以 便包括语句阵列中扫描指针指向的最低指数NYP操作符的操作符位置。 在该实例中，扫描指针指向语句阵列行C，这是中止包180的先前搜索的 语句阵列。操作符指针OPc仍然指向位置(c,6)处的加法操作符，因为在先 前选择搜索中没有处理任何操作符。与操作符(c,6)关联的操作数数据类型 可以确定有关要搜索的语句数量的新限制。因为该实例假设包180中的所 有数据类型是长度为四的整数，所以可以搜索从行C开始的四个语句阵列。 因为示例性包180仅具有四个语句阵列，所以仅语句阵列行C和行D在搜 索限制内。有序选择准备例程230初始化到窗口290中的位置(c,6)处的示 例性加法操作符与数据并行机会190中的一组操作符匹配190c中的位置(b, 6)和(d,6)处的加法操作符相匹配。选择例程240确定位置(c,6)处的操作符 在数据并行机会190中具有操作符匹配(b,6)，但行B不在搜索限制内，并 且因此不能选择以便优化。选择例程240然后确定数据并行机会190中存 在另一个操作符匹配(d,6)，行D在搜索限制内，并且操作符指针OPd指 向操作符位置(d,6)。选择例程240将操作符位置(d,6)添加到窗口290。窗 口290现在针对相同操作符(在该实例中，为加法操作符“+”)包括两 个操作符位置，每个操作符位置具有相同数据类型(例如，长度为四的整 数)的操作数。将窗口290(尽管不完整)发送到代码生成例程250，以便 针对位于包180中的(c,6)和(d,6)处的加法操作符生成SIMD指令。来自窗 口290的操作符现在可以在包180中全部标记为已处理。

图9示出在有序选择准备例程230执行以下操作之后的包180：重新 初始化扫描指针以便指向包180中属于活动的最低指数语句阵列(在该实 例中，该语句阵列是包180中的第一语句阵列)，重新初始化操作符指针 OPa、OPb、OPc、OPd以便指向每个相应的语句阵列的最低指数NYP操 作符(在该实例中，仅其中某些操作符更改为先前选择搜索的结果)，并 且初始化窗口290以便包括语句阵列中扫描指针指向的最低指数NYP操 作符的操作符位置。在该实例中，扫描指针指向语句阵列行A，因为并非 语句阵列中的所有操作符均被处理。操作符指针OPa仍然指向位置(a,6) 处的乘法操作符，因为该操作符在先前搜索中未被处理。与操作符(a,6)关 联的操作数数据类型可以确定有关要搜索的语句数量的新限制。因为该实 例假设包180中的所有数据类型是长度为四的整数，并且在语句阵列行A 处开始搜索，所以选择例程240可以全部搜索语句阵列行A–行D。有序 选择准备例程230初始化到窗口290中的位置(a,6)处的示例性乘法操作符 与数据并行机会190中的一组操作符匹配190b中的位置(c,8)和(d,8)处的 乘法操作符相匹配。选择例程240确定位置(a,6)处的操作符在数据并行机 会190中具有操作符匹配(c,8)，并且行C在搜索限制内。因为操作符指针 OPC现在指向位置(c,8)处的乘法操作符，其作为行C中的最低指数NYP 操作符，因为语句阵列行C中的先前操作符已被处理，所以选择例程240 将操作符位置(c,8)添加到窗口290。选择例程240然后确定数据并行机会 190b中存在另一个操作符匹配(d,8)。因为语句阵列行D也在搜索限制内， 并且操作符指针OPd指向操作符位置(d,8)，所以选择例程240将操作符 位置(d,8)添加到窗口290。窗口290现在针对相同操作符(在该实例中， 为乘法操作符“*”)包括三个操作符位置，每个操作符位置具有相同数据 类型(例如，长度为四的整数)的操作数。将窗口290发送到代码生成例 程250，以便针对位于包180中的(a,6)、(c,8)和(d,8)处的乘法操作符生成 SIMD指令。来自窗口290的操作符现在可以在包180中全部标记为已处 理。

图10示出在有序选择准备例程230执行以下操作之后的包180：重新 初始化扫描指针以便指向包180中属于活动的最低指数语句阵列(在该实 例中，该语句阵列仍然是包180中的第一语句阵列)，重新初始化操作符 指针OPa、OPb、OPc、OPd以便指向每个相应的语句阵列的最低指数 NYP操作符(在该实例中，仅其中某些操作符更改为先前选择搜索的结 果)，并且初始化窗口290以便包括语句阵列中扫描指针指向的最低指数 NYP操作符的操作符位置。在该实例中，扫描指针继续指向语句阵列行A， 因为并非语句阵列中的所有操作符均已被处理。操作符指针OPa现在指向 位置(a,7)处的除法操作符，其作为语句阵列中的最低指数NYP操作符， 因为语句阵列行A中的先前操作符已被处理，如上所述。与操作符(a,7) 关联的操作数数据类型可以确定有关要搜索的语句数量的新限制。因为该 实例假设包180中的所有数据类型是长度为四的整数，并且搜索从语句阵 列行A开始，所以选择例程240可以全部搜索行A–行D表示的语句阵 列。有序选择准备例程230初始化到窗口290中的位置(a,7)处的示例性除 法操作符与数据并行机会190中的一组操作符匹配190d中的位置(b,7)、 (c,9)和(d,9)处的除法操作符相匹配。选择例程240确定位置(a,7)处的操作 符在数据并行机会190中具有操作符匹配(b,7)，并且行B在搜索限制内。 因为操作符位置(b,7)不是行B中的最低指数NYP操作符，即，位置(b,7) 到语句阵列行B中的列指数大于操作符指针OPb指向的操作符位置的列 指数，所以选择例程240从窗口290中删除操作符位置(a,7)，中止选择搜 索以便防止生成可能不维护原始标量代码的操作顺序的指令，并且设置扫 描指针以指向行B，以便用信号通知有序选择准备例程230初始化指针从 而使下一次搜索在行B上开始。

图11示出在有序选择准备例程230执行以下操作之后的包180：重新 初始化扫描指针以便指向选择例程240用信号通知的语句阵列，如上面参 考图10所述。操作符指针OPa、OPb、OPc和OPd保持不变，因为先前 选择搜索没有处理任何操作符。有序选择准备例程230初始化窗口290以 便包括语句阵列中扫描指针指向的最低指数NYP操作符的操作符位置。 在该实例中，扫描指针指向语句阵列行B，这是中止包180的先前搜索的 语句阵列。操作符指针OPb仍然指向位置(b,6)处的加法操作符，因为在 先前选择搜索中没有处理任何操作符。与操作符(b,6)关联的操作数数据类 型可以确定有关要搜索的语句数量的新限制。因为该实例假设包180中的 所有数据类型是长度为四的整数，所以可以搜索从行B开始的四个语句阵 列。因为示例性包180仅具有四个语句阵列，所以仅语句阵列行B–行D 在搜索限制内。有序选择准备例程230初始化到窗口290中的位置(b,6) 处的示例性加法操作符与数据并行机会190中的一组操作符匹配190c中的 位置(c,6)和(d,6)处的加法操作符相匹配。选择例程240确定位置(b,6)处 的操作符在数据并行机会190中具有操作符匹配(c,6)，并且行C在搜索限 制内。因为位置(c,6)处的操作符已经处理，所以其位置不是行C中的最低 指数NYP操作符，即，位置(c,6)到语句阵列行C中的列指数小于操作符 指针OPc指向的操作符位置的列指数。选择例程240然后确定数据并行机 会190中存在另一个操作符匹配(d,6)，行D在搜索限制内，但确定在先前 搜索中还处理相似的操作符位置(c,6)、操作符位置(d,6)。窗口290仅包括 一个操作符位置(b,6)，在该实例中为加法操作符“+”。将窗口290(尽 管不完整)发送到代码生成例程250，以便针对位于包180中的(b,6)处的 加法操作符生成SIMD(或标量)指令。来自窗口290的操作符现在可以 在包180中标记为已处理。

图12和13继续示出在有序选择准备例程230执行以下操作之后的包 180：重新初始化扫描指针以便指向包180中属于活动的最低指数语句阵列 (在图13和图14，该语句阵列仍然是包180中的第一语句阵列)，重新 初始化操作符指针OPa、OPb、OPc、OPd以便指向每个相应的语句阵列 的最低指数NYP操作符，并且初始化窗口290以便包括语句阵列中扫描 指针指向的最低指数NYP操作符的操作符位置、操作符位置(a,7)(图12) 和操作符位置(a,9)(图13)。

图14示出可以在已处理所有操作符并且针对包180表示的所有标量代 码语句110生成优化代码之后出现的包180。

所属技术领域的技术人员知道，本发明的各个方面可以实现为系统、 方法或计算机程序产品。因此，本发明的各个方面可以具体实现为以下形 式，即：完全的硬件实施方式、完全的软件实施方式(包括固件、驻留软 件、微代码等)，或硬件和软件方面结合的实施方式，这里可以统称为“电 路”、“模块”或“系统”。此外，本发明的各个方面还可以实现为在一 个或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介质 中包含计算机可读的程序代码。

可以采用一个或多个计算机可读介质的任意组合。计算机可读介质可 以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质 例如可以是—但不限于—电、磁、光、电磁、红外线、或半导体的系统、 装置或器件，或者上述的任意合适的组合。计算机可读存储介质的更具体 的例子(非穷举的列表)包括：具有一个或多个导线的电连接、便携式计 算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦 式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑盘只读存储 器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。 在本文件中，计算机可读存储介质可以是任何包含或存储程序的有形介质， 该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。

计算机可读的信号介质可以包括例如在基带中或者作为载波一部分传 播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号 可以采用多种形式，包括—但不限于—电磁信号、光信号或上述的任意合 适的组合。计算机可读的信号介质可以是计算机可读存储介质以外的任何 计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令 执行系统、装置或者器件使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括 —但不限于—无线、有线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本发明的 各个方面的操作的计算机程序代码，所述程序设计语言包括面向对象的程 序设计语言—诸如Java、Smalltalk、C++等，还包括常规的过程式程序设 计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在 用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包 执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计 算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过 任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户 计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通 过因特网连接)。

上面参照根据本发明实施例的方法、装置(系统)和计算机程序产品 的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框 图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机程序 指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机或其 它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在 通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程 图和/或框图中的一个或多个方框中规定的功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些指令使 得计算机、其它可编程数据处理装置、或其它设备以特定方式工作，从而， 存储在计算机可读介质中的指令就产生出包括实现流程图和/或框图中的 一个或多个方框中规定的功能/动作的指令的制造品(article of  manufacture)。

也可以把计算机程序指令加载到计算机、其它可编程数据处理装置、 或其它设备上，使得在计算机、其它可编程装置或其它设备上执行一系列 操作步骤，以产生计算机实现的过程，从而使得在计算机或其它可编程装 置上执行的指令提供实现流程图和/或框图中的一个或多个方框中规定的 功能/动作的过程。

图15示出根据本发明的一个实施例的图2的SIMD优化环境299的 计算设备222的组件的框图。应该理解，图15仅提供一种实现的例示，并 非暗示对其中可以实现不同实施例的环境的任何限制。可以对所示环境做 出许多修改。

计算设备222可以包括一个或多个处理器1520、一个或多个计算机可 读RAM 1522、一个或多个计算机可读ROM 1524、一个或多个SIMD处 理元件1545、一个或多个有形存储设备1530、设备驱动器1540、读写驱 动器或接口1532，以及网络适配器或接口1536，它们全部通过通信结构 1526互连。通信结构1526可以使用任何体系架构实现，该体系架构被设 计为在处理器(例如微处理器、通信和网络处理器等)、系统存储器、外 围设备和系统中的任何其它硬件组件之间传递数据和/或控制信息。

一个或多个操作系统1528、编译器200、标量代码语句110(图2)、 数据并行机会190(图2)、生成的SIMD指令295(图2)以及窗口290 (图2)存储在一个或多个计算机可读有形存储设备1530上，以便经由一 个或多个相应的RAM 1522(其通常包括高速缓冲存储器)由一个或多个 处理器1520执行。在所示环境中，每个计算机可读有形存储设备1530可 以是内部硬盘驱动器的磁盘存储器件、CD-ROM、DVD、记忆棒、磁带、 磁盘、光盘、半导体存储器件，例如RAM、ROM、EPROM、闪存，或 者可以存储计算机程序和数字信息的任何其它计算机可读有形存储设备。

计算设备222还可以包括读写驱动器或接口1532以便读取和写入一个 或多个便携式计算机可读有形存储设备1570。计算设备222上的编译器 200、标量代码语句110(图2)、数据并行机会190(图2)、生成的SIMD 指令295(图2)以及窗口290(图2)可以存储在一个或多个便携式计算 机可读有形存储设备1570上，经由相应的读写驱动器或接口1532读取， 并且加载到相应的计算机可读有形存储设备1530中。

计算设备222还可以包括网络适配器或接口1536，例如TCP/IP适配 卡或无线通信适配器(例如使用OFDMA技术的4G无线通信适配器)。 可以经由网络(例如，因特网、局域网或其它网络、广域网或无线网络) 和网络适配器或接口1536，将计算设备222上的编译器200从外部计算机 或外部存储器件下载到计算设备。从网络适配器或接口1536，将程序加载 到计算机可读有形存储设备1530中。网络可以包括铜线、光纤、无线传输、 路由器、防火墙、交换机、网关计算机和/或边缘服务器。

计算设备222还可以包括显示屏1550、键盘或小键盘1560，以及计算 机鼠标或触摸板1555。设备驱动器1540与显示屏1550对接以便成像，对 接到键盘或小键盘1560、计算机鼠标或触摸板1555，和/或显示屏1550， 从而对字母数字字符输入和用户选择进行压力传感。设备驱动器1540、读 写驱动器或接口1532，以及网络适配器或接口1536可以包括硬件和软件 (存储在计算机可读有形存储设备1530和/或ROM 1524中)。

附图中的流程图和框图显示了根据本发明的不同实施例的系统、方法 和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程 图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述 模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的 可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功 能可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上 可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的 功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/ 或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬 件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。