用于执行自稳定编译的系统和方法

用于执行自稳定编译的系统和方法
1.相关申请的交叉引用
2.本技术要求于2020年12月11日提交的印度专利申请号202041054066的优先权。
技术领域
3.本公开整体涉及计算机系统中的编译器基础结构，并且具体地涉及用于执行自稳定编译的系统和方法。


背景技术：

4.主流编译器在给定输入程序上执行大量优化遍。优化可指变换计算机程序以提供优点如提高的执行速度、减小的程序大小、减少的功率消耗、增强的安全性、降低的空间利用等。典型地，优化可涉及检查和变换的多个交替阶段。在检查阶段，可读出各种程序抽象，诸如程序的中间表示(ir)、程序分析的结果等，以发现优化该程序的机会。随后，通过在程序的中间表示诸如抽象语法树(ast)、三地址代码等上调用适当的写入器来在变换阶段中变换该程序。
5.在变换程序时，通过各种分析生成的程序抽象诸如指向图、常量图等可能与该程序的所修改的状态不一致。这阻止了下游变换的正确应用，直至经由增量更新或经由无效且完成的重新计算稳定相关抽象为止。因此，除非采取明确步骤来确保程序抽象总是反映该程序在被访问时的正确状态，否则无法确保下游优化的检查阶段的正确性，这又会对最优性且甚至优化的正确性产生负面影响。
6.一般来讲，现有编译器框架不执行这种抽象的自动稳定。因此，优化写入器具有识别(i)要稳定与程序抽象相关联的什么数据结构、(ii)要在哪里稳定数据结构和(iii)如何执行实际稳定的附加负担。此外，添加新的分析成为挑战，因为现有优化可能对其产生影响。此外，在用于并行语言的编译器的情况下，这些挑战变得更困难，其中在代码的一个部分中进行的变换可能保证一些看似未连接的部分的程序抽象的稳定，这是因为这两个部分之间存在并发性关系。
7.响应于串行程序的编译器中的程序变换，已经针对实现特定程序抽象的自动稳定进行了各种尝试。然而，这些努力存在不同缺点。例如，carle和pollock[1989]、以及reps等人[1983]要求程序抽象必须表达为语言构造的上下文相关属性，这非常有限制性。carroll和polychronopoulos[2003]不处理并行程序的遍依赖性和编译器。blume等人[1995]、brewster和abdelrahman[2001]仅处理一小组程序抽象，并且因此是不够的。
[0008]
此外，还存在了一些与数据流分析的增量更新相关的出版物。arzt和bodden[2014]已经提供实现基于ide-/ifds的数据流分析的增量更新的方法。ryder[1983]基于allen/cocke间隔分析[allen和cocke 1976]来讨论了用于前向和后向数据流问题的两种强大的增量更新算法，sreedhar等人[1996]公开了为基于消除的数据流分析执行增量更新的方法。carroll和ryder[1987，1988]已经给出一些用于基于间隔对数据流问题的增量更新和基于消除的分析的重要方法。由于在并行程序诸如openmp程序中存在任务间边(或通
信边)，因此在这种程序的控制和数据流表示中存在大量不适当区域(不可缩减子图)，从而使任何形式的结构数据流分析在该图上不可行[muchnick 1998]，其他出版物包括marlowe和ryder[1989]的著作和来自由pollock和coffa[1989]给出的用于数据流分析的迭代版本的两阶段增量更新算法，然而，在这些出版物中，遍写入器需要提供附加信息以确保它们的数据流分析的增量更新。[0008]鉴于数据流分析的重要性，已经有众多出版物都已经提供针对增量更新及其并行性的分析特定方法。例如，在c程序的上下文中，yur等人[1997]已经提供用于副作用分析的增量更新机制。chen等人[2015]已经提供针对java程序的基于包含的点分析的增量更新。类似地，liu等人[2019]已经提供指针分析的增量且并行的版本。然而，这些和其他出版物本质上是不通用的。因此，不存在解决上文讨论的挑战并保证通用自稳定(尤其是在并行程序的上下文中)的编译器设计或具体实施。相比之下，所公开的方法向现有和未来迭代数据流分析(idfa)的写入器完全地隐藏了并行语义的具体实施和自稳定的增量模式。


技术实现要素：

[0009]
公开了一种用于程序的自动自稳定编译的计算机实现的方法。该方法包括接收输入程序。使用多个分析操作来生成该输入程序的多个抽象，其中该多个抽象中的每个抽象表示与在编译时的程序状态相关联的信息。接下来，该方法包括对根据一个或多个预定基本变换表达的该多个抽象中的一个抽象执行一个或多个优化操作。该预定基本变换捕获与所修改的程序状态相关联的信息。在稳定模式下由稳定器使用由该一组预定基本变换捕获的信息来稳定该多个抽象中的一个或多个抽象。该稳定包括使用所捕获的信息来更新该一个或多个抽象以维持该抽象与所修改的程序状态的一致性。
[0010]
在各种实施方案中，预定基本变换包括添加、删除或修改该程序的语法部分。在一些实施方案中，该稳定模式是懒惰无效稳定模式、懒惰更新稳定模式、急切更新稳定模式、急切无效稳定模式中的一者或它们的任何组合。在各种实施方案中，该一个或多个抽象表示与串行或并行程序相关联的信息。在一些实施方案中，该多个抽象包括中间表示、控制流图和抽象语法树。在一些实施方案中，该多个抽象包括迭代数据流分析，并且其中使用自动懒惰更新稳定模式来稳定该迭代数据流分析。在一些实施方案中，该方法包括响应于执行新的优化操作而稳定该一个或多个抽象，其中该稳定包括更新该一个或多个抽象以维持该抽象与所修改的程序状态的一致性。
[0011]
根据另一个实施方案，公开了一种用于执行程序的自动自稳定编译的系统。该系统包括分析部件，该分析部件被配置为接收输入程序并执行该输入程序的多个分析操作以生成多个抽象，其中该多个抽象中的每个抽象表示与在编译时的程序状态相关联的信息。该系统包括优化部件，该优化部件被配置为通过基于一组预定基本变换修改与该抽象相关联的该程序状态来对该多个抽象中的一个抽象执行一个或多个优化操作，该组预定基本变换捕获与所修改的程序状态相关联的信息。该系统还包括稳定器，该稳定器被配置为使用由该一组预定基本变换捕获的该信息来稳定该多个抽象中的一个或多个抽象，其中该稳定包括使用所捕获的信息来更新该一个或多个抽象以维持该抽象与所修改的程序状态的一致性。
[0012]
在各种实施方案中，该分析部件包括预处理单元、词法分析单元、语法分析单元和
语义分析单元。在一些实施方案中，该稳定器被配置为在稳定模式下操作，其中该稳定模式是懒惰无效稳定模式、懒惰更新稳定模式、急切更新稳定模式、急切无效稳定模式或它们的任何组合中的一者。在一些实施方案中，该优化部件包括一个或多个抽象读出器和一个或多个抽象写入器。该一个或多个抽象读出器被配置为读出该一个或多个抽象，并且该一个或多个抽象写入器被配置为修改该一个或多个抽象。
[0013]
本文中描述了这个和其他方面。
附图说明
[0014]
当结合附图考虑时，本发明具有将从本发明的以下详细描述和所附权利要求中更加显而易见的其他优点和特征，在附图中：
[0015]
图1示出了根据本主题的一个实施方案的用于程序的自动自稳定编译的方法的流程图。
[0016]
图2示出了根据本主题的一个实施方案的用于执行程序的自动自稳定编译的系统的框图。
[0017]
图3示出了根据本主题的一个实施方案的编译过程的框图。
[0018]
图4示出了根据本主题的一个实施方案的优化过程的框图。
[0019]
图5示出了根据本主题的一个实施方案的每个代码优化过程的交替的检查阶段和变换阶段的流程图。
[0020]
图6示出了根据本主题的一个实施方案的在由检查阶段调用的抽象获取器期间执行的步骤的流程图。
[0021]
图7示出了根据本主题的一个实施方案的在由变换阶段调用的基本变换期间执行的步骤的流程图。
[0022]
图8示出了根据本主题的一个实施方案的由抽象的稳定器执行的步骤的流程图。
[0023]
图9示出了根据本主题的一个实施方案的用于阶段稳定器处理节点添加对阶段信息的影响的流程图。
[0024]
图10示出了根据本主题的一个实施方案的用于阶段稳定器处理节点移除对阶段信息的影响的流程图。
[0025]
图11示出了根据本主题的一个实施方案的idfa稳定的流程图。
[0026]
图12a至图12b示出了根据本主题的一个实施方案的idfa稳定器的第一遍的流程图。
[0027]
图13示出了根据本主题的一个实施方案的idfa稳定器的第二遍的流程图。
[0028]
图14示出了根据本主题的一个实施方案的用于移除并行程序的屏障的客户端优化遍。
[0029]
图15示出了根据本主题的一个示例的描绘在各种稳定模式下idfa稳定时间的加速的图表。
[0030]
图16示出了描绘根据本主题的一个示例的在各种自稳定模式下节省存储器占用(最大驻留集大小)的图表。
具体实施方式
[0031]
虽然已经参考某些实施方案公开了本发明，但是本领域的技术人员将理解的是，在不脱离本发明的范围的情况下，可以进行各种改变并且等效物可以取代。另外，在不脱离本发明的范围的情况下，可以进行许多修改以使具体情况或材料适应本发明的教导。
[0032]
贯穿本说明书和权利要求书，除非上下文另有明确指示，否则以下术语采用与本文明确相关的含义。“一个(a)”、“一种(an)”和“所述(the)”的含义包括复数指代物。“在
……
中(in)”的含义包括“在
……
中(in)”和“在
……
上(on)”。参考附图，贯穿这些视图中的相同的数字表示相同的部分。另外，除非另外说明或与本文中的公开内容不一致，否则对单数的引用包括对复数的引用。
[0033]
本主题描述了用于串行和并行编程应用的计算机程序的自稳定编译的方法和系统。根据本主题，自稳定编译涉及响应于因编译器内的不同优化造成的程序改变而更新编译器内的内部程序分析相关信息。
[0034]
根据本主题的各种实施方案，图1中示出了用于程序的自动自稳定编译的方法的流程图。方法100可包括在框102处接收输入程序。在框104处，可使用多个分析操作来生成输入程序的多个抽象。多个抽象中的每个抽象可表示与当前程序状态相关联的一些信息。在一些实施方案中，多个抽象可包括中间表示、控制流图、抽象语法树、具体语法树等。
[0035]
接下来，在框106处，可通过基于一组预定基本变换修改与抽象相关联的程序状态来对多个抽象中的一个抽象执行一系列优化操作。可使用存在于多个抽象中的一个或多个抽象中的信息来执行优化操作。在各种实施方案中，优化操作可包括对抽象的检查和变换。每个变换可涉及程序或抽象状态的修改。在各种实施方案中，预定基本变换可包括添加、删除或修改输入程序的语法部分。
[0036]
在框108处，可在稳定模式下使用由该一组预定基本变换捕获的信息来稳定多个抽象中的一个或多个抽象。稳定可包括更新一个或多个抽象以维持抽象与所修改的程序状态的一致性。在各种实施方案中，步骤104、106和108可在所接收的输入程序的编译期间执行多次。在一些实施方案中，稳定模式是懒惰无效稳定模式、急切更新稳定模式、急切无效稳定模式和懒惰更新稳定模式中的一者。在各种实施方案中，该方法可包括稳定并行程序的一个或多个抽象。在各种实施方案中，该方法还可包括响应于添加新的优化通过更新一个或多个抽象以维持抽象与所修改的程序状态的一致性来自动稳定一个或多个抽象。
[0037]
根据本主题的各种实施方案，图2中示出了用于执行程序的自动自稳定编译的系统200的框图。系统200可主要包括存储器单元202、处理单元204和编译器单元206。编译器单元206可包括分析部件208，该分析部件被配置为接收输入程序并执行输入程序的多个分析操作以生成多个抽象。每个抽象表示与在编译时的程序状态相关联的信息。编译器单元206还可包括优化部件210，该优化部件被配置为通过基于一组预定基本变换修改与抽象相关联的程序状态以修改该程序状态来对多个抽象中的一个抽象执行一个或多个优化操作。该一组预定基本变换捕获与所修改的程序状态相关联的信息。此外，编译器单元还可包括稳定器212，该稳定器被配置为使用由一组预定基本变换捕获的信息通过更新多个抽象中的一个或多个抽象以维持抽象与所修改的程序状态的一致性来稳定该一个或多个抽象。在各种实施方案中，稳定器212可被配置为在稳定模式下操作，该稳定模式可以是懒惰无效稳定模式、懒惰更新稳定模式、急切更新稳定模式、急切无效稳定模式和它们的任何组合中的
一者。
[0038]
图3中示出了编译过程的框图。编译过程300可包括输入程序302的交替的分析和优化阶段。在各种实施方案中，输入程序302可以是并行程序，或者另选地是串行程序。如前所讨论，编译器单元206可包括分析部件208和优化部件210。在各种实施方案中，分析部件208和优化部件210可以是编译器的前端或后端或两者的一部分。在一些实施方案中，分析部件208可包括预处理单元304、词法分析单元306、语法分析单元308和语义分析单元310。优化部件210可包括代码优化312和代码生成314。单元304至314可对一个或多个抽象316进行读写。
[0039]
预处理单元304可被配置为扩展输入程序中的各种宏和头文件。词法分析单元306可被配置为将源代码文本分解成称为词法标记的小片的序列，诸如关键字、运算符、文字、标识符等。语法分析单元308还可被配置为通过解析标记序列来识别输入程序中的语法结构。在一些实施方案中，语法分析可生成抽象316，诸如解析树，其以树结构表示程序。
[0040]
语义分析单元310可被配置为通过执行操作如类型检查、对象绑定、拒绝不正确程序或发出警告来生成新的抽象或修改现有抽象316。代码优化单元312可被配置为执行程序的机器相关和机器独立优化。所变换的程序可由代码生成单元314转变成输出语言，诸如汇编语言、字节代码或机器代码。
[0041]
根据本主题的另一个实施方案，图4中示出了自稳定编译的框图。每个优化遍可包括程序抽象的交替的检查和变换阶段。在检查阶段中，可读出各种程序抽象，诸如中间程序表示和程序分析结果，以识别程序中的改进的机会。在各种实施方案中，程序抽象316可以是指向图、控制流图、三地址代码等。
[0042]
抽象读出器402(或中间表示读出器)可被配置为将一个或多个抽象316读出到存储器诸如硬盘或随机存取存储器(图中未示出)中。抽象获取器404可被配置为查询底层抽象316的内部状态。抽象写入器406(或中间表示写入器)可被配置为对一个或多个抽象或中间表示316执行变换。可基于多个预定基本变换408和宏变换410来执行变换。在各种实施方案中，多个预定基本变换408可包括一个或多个基本操作，诸如添加、移除或修改抽象。每个变换可在内部表达为一个或多个基本变换的序列。例如，基本变换可包括在抽象诸如控制流图抽象中添加或移除节点或控制流边。抽象的变换可涉及程序的状态的修改。
[0043]
一个或多个基本变换408可被传送到每个抽象316的一个或多个稳定器212。在各种实施方案中，每个抽象316可与稳定器212相关联。一个或多个稳定器212可被配置为使用由更早使用的基本变换捕获的信息来稳定一个或多个抽象。在各种实施方案中，默认通用稳定器可用作所有程序抽象的基类，其使用固定抽象特定基本操作集来稳定任何程序抽象。
[0044]
在各种实施方案中，抽象写入器406可仅经由基本变换被调用。每个程序抽象316的抽象获取器404可仅经由一组专用稳定器212访问对应抽象的内部状态，这确保了抽象的每个可观察状态与程序的中间表示的当前状态一致。
[0045]
在各种实施方案中，每个具体程序抽象类可继承程序抽象的抽象基类(basepa)。基类可包括自稳定所必需的一个或多个常用方法和数据结构。稳定过程可由每个有效程序抽象的抽象获取器响应于变换而触发。在各种实施方案中，可维护程序抽象的全局集(allabstractions)，并且在可在每个程序抽象对象a的构造期间隐式调用的基类程序抽象
(basepa)的构造器中，可将a的引用添加到allabstractions。
[0046]
在基础抽象的构造器中，可初始化在抽象本地的一个或多个数据结构。一个或多个数据结构可存储在基本变换期间添加的边、移除的边、添加的节点和移除的节点的信息。该数据结构可能是抽象的自稳定所需的。basepa的构造器的示例可给出为：
[0047]
global.allabstractions.add(this)；
[0048]
addededges＝new...；removededges＝new...；addednodes＝new...；
[0049]
ꢀꢀꢀꢀ
removednodes＝new...；}
[0050]
在各种实施方案中，响应于由优化操作执行的修改对程序抽象的稳定可通过直接修改程序抽象的内部表示来完成。另选地，并且更优选地，程序抽象可在内部执行稳定，即，可向程序抽象告知已对程序执行的确切修改。
[0051]
在各种实施方案中，预定基本变换可用作优化与程序抽象之间的缺失链接。预定基本变换可经由一个或多个基本操作捕获所有程序修改。在每个基本变换中，可收集关于节点、控制流边、调用边和任务间边的添加/删除的信息。所收集的信息可被发送到存在于集allabstractions中的每个程序抽象对象。
[0052]
根据本主题的各种实施方案，图5中示出了代码优化过程的交替的检查阶段和变换阶段的流程图。如所讨论，代码优化过程312可包括检查阶段502和变换阶段504的交替阶段。在检查阶段，可调用一个或多个抽象获取器404-1、404-2、
……
404-n。该方法可涉及在框506处使用所检查的抽象来确定该程序是否可受益于优化。如果执行优化，则可在变换阶段504中调用一个或多个基本变换408。
[0053]
根据本主题的一个实施方案，在图6中示出了在检查阶段502期间由抽象获取器404执行的步骤的流程图。对于来自抽象的域的元素f，抽象获取器404可在框602处检查相关联的抽象是否被初始化。如果抽象未初始化，则可执行所需的分析操作，并且随后可返回元素f的值。分析初始化操作可由分析部件208执行，如先前所述。另选地，如果抽象获取器404确定抽象被初始化，则在框604处，抽象获取器404可确定抽象是否稳定。如果确定抽象已经稳定，则还可返回f的当前值而无需进一步计算。如果抽象已被初始化并且抽象不稳定，则在框606处，抽象获取器404可检查抽象是否在稳定中。如果抽象经历稳定，则可返回元素f的保守值。在各种实施方案中，抽象获取器404可被配置为忽略不稳定抽象的值。如果稳定未开始，则在框608处，抽象获取器404可调用抽象稳定器212，以执行稳定，并且然后返回f的值。
[0054]
根据本主题的一个实施方案，图7中示出了通过基本变换过程在变换阶段期间执行的步骤的流程图。如图所示，在基本变换408中执行的步骤可包括在框702处收集要被移除或添加的边以用于移除抽象中的旧的节点。在框704处，可稳定阶段抽象以对旧的节点的移除建模。接下来，在框706处，可用新的节点替换旧的节点。该方法还涉及在框708处收集在添加新的节点时添加或移除的边。在框710处，可稳定阶段抽象以反映新的节点的添加。在框712处，可通过将受影响的边和节点发送到可被标记为不稳定的抽象的稳定器来处理每个抽象。
[0055]
根据本主题的一个实施方案，图8中示出了由抽象稳定器a执行的步骤的流程图。为了稳定任何程序抽象，可调用稳定器212来执行步骤序列。当请求稳定时，稳定器212可基于抽象特定方法和存储关于添加的边、移除的边、添加的节点和移除的节点的信息的内部
集来监督自稳定过程。在各种实施方案中，稳定器212可处理边移除操作、边添加操作、节点移除操作和节点添加操作对抽象的影响。稳定器212还可任选地执行共同预处理和共同后处理操作。
[0056]
如图6所示，在608处，如果抽象尚未稳定，则可调用抽象稳定器212。在框802处，所调用的抽象稳定器212可将抽象a标记为在稳定中。在框804处，稳定器212可执行对抽象a的共同预处理。可在框806和808处处理每个所捕获的移除边和所捕获的添加边。可分别在框810和812处处理每个所捕获的删除节点和添加节点。在各种实施方案中，可以任何次序执行在806至812处的步骤。接着，可在框814处针对抽象a执行共同后处理。在各种实施方案中，共同预处理和后处理步骤可任选地用于指定可能是稳定所需的程序抽象特定初始化和清理任务。基类basepa可提供预处理和后处理步骤的默认(空)具体实施。可在框816处清除捕获的节点和边的所有集，并且可在框818处将抽象a标记为稳定的。
[0057]
在各种实施方案中，多个抽象316可包括阶段分析(或并发分析)。在阶段分析中，如果已被添加到程序的节点n不在内部含有在线程间的任何全局同步操作，诸如屏障，则可重新使用n的cfg邻域的阶段信息以稳定n及其子节点的阶段信息。也可类似地执行节点移除。当添加或移除的节点可含有屏障时，该屏障可改变阶段信息(全局地)。因此，可从开始重新计算阶段信息(通过从分析部件208调用其初始化操作)。需注意，如果阶段稳定引起任何任务间边的添加/移除，则可将那些边捕获在添加边/移除边集中。
[0058]
根据本主题的一个实施方案，图9中示出了用于由阶段稳定器处理节点添加对阶段信息的影响的流程图。在框902处，阶段稳定器可获得添加节点。阶段稳定器可检查节点是否含有屏障。如果节点含有屏障，则在框904处，阶段稳定器可重新计算阶段抽象和任务间边。如果节点不含有屏障，则在框906处，可从添加节点的邻域获得阶段信息。在框908处，可将阶段信息复制到节点n及其嵌套节点。如果节点n是或含有flush节点，则在框910处，可将任务间边添加到涉及节点n。
[0059]
类似地，根据本主题的一个实施方案，图10中示出了用于由阶段稳定器处理节点移除对阶段信息的影响的流程图。该方法可包括在框1002处获得移除节点。如果节点含有屏障，则在框1004处，阶段稳定器可重新计算阶段抽象和任务间边。如果节点不含有屏障，则在框1006处，阶段稳定器可通过清除节点n的阶段信息来处理每个嵌套节点。在框1008处，如果节点n是或含有flush节点，则阶段稳定器可移除涉及节点n的任务间边。
[0060]
在各种实施方案中，程序抽象316可包括迭代数据流分析(idfa)的结果。所公开的方法提供了可用于实例化任何idfa(例如，指向分析)而无需任何附加代码就能实现自稳定的通用模板。为了实现自稳定，可维护节点的内部集(种子)，从该内部集开始，作为程序变换的结果，流图可能需要更新。在前向(或后向)分析的情况下，在方法(节点移除/添加和边移除/添加)中用因其前导子(或后继子)的改变而需要重新计算in(或out)流图的那些节点填充种子集。可无需重写共同预处理的默认(空)具体实施，并且可重写共同后处理以调用将种子作为自变量的自稳定过程。
[0061]
根据本主题的一个实施方案，图11中示出了idfa稳定器的流程图。该方法可包括在框1102处获得工作列表中的种子节点。该方法可在框1104处检查工作列表是否为空。如果在框1104处工作列表不为空，则可在框1106从工作列表中选择第一节点。可在框1108处保存节点的scc id。可在框1110处运行具有自变量scc-id的第一遍。接下来，该方法可涉及
在框1112处检查工作列表是否具有来自scc-id的节点。如果在框1112处工作列表具有来自scc-id的节点，则在框1114处可从工作列表中选择scc-id的第一节点。可在框1116处运行具有自变量scc-id的第二遍。
[0062]
根据本主题的一个实施方案，在图12a至图12b中示出了框1110中的idfa稳定器的第一遍的流程图。在框1202处，可清除集经处理节点和欠近似节点。可在框1204处处理scc id为scc-id的每个节点n，然后可在框1206将欠近似节点中的所有元素添加到工作列表。如果在框1208处工作列表具有scc id为scc-id的节点，则在框1204处的处理可涉及从工作列表中选择scc id为scc-id的第一节点n。可在框1210处清除集有效前导子。可在框1212处将scc id非scc-id的n的或存在于经处理节点中的所有前导子添加到集有效前导子。在框1214处，可使用有效前导子来计算节点n的流事实。如果节点n的流事实改变，则可在框1216将其后继子添加到工作列表。如果集有效前导子含有n的所有前导子，则可在框1218处从集欠近似节点中移除节点n，并且将其添加到集经处理节点。如果集有效前导子不含有n的所有前导子，则可在框1220处将节点n添加到集欠近似节点以及集经处理节点。
[0063]
根据本主题的一个实施方案，图13中示出了对于工作列表中scc id为scc-id的每个节点，idfa稳定器的第二遍的流程图。该方法可涉及在框1302处从工作列表中移除scc id为scc-id的第一节点n。在框1304处，可使用节点n的所有前导子来计算该节点n的流事实。如果节点n的流事实已经改变，则可在框1306处将其后继子添加到工作列表。
[0064]
实施例
[0065]
实施例1：稳定模式评估
[0066]
在程序修改中稳定程序抽象的时间和方式是重要的，并且用于执行稳定的两个选择可能是急切对懒惰和无效对更新。
[0067]
基于这两个维度，评估了用于任何程序抽象的以下四种稳定模式：(i)急切-无效(eginv)，(ii)急切-更新(egupd)，以及(iii)懒惰-无效(lzinv)，(iv)懒惰-更新(lzupd)。然后比较这四种稳定模式。
[0068]
急切对懒惰：在急切模式的情况下，对于每个程序抽象(比如a)，涉及k个基本变换的优化将导致其稳定器的k个调用(比如i1、i2、
……
、ik)。可能存在在调用l
……
ij(1≤i《j≤k)之间未读出a的情况。在这种情况下，稳定器的调用ii、i
i+1
、
……
、i
j-1
是冗余的。相比之下，懒惰-稳定避免了这种冗余。
[0069]
无效对更新：虽然更新模式看起来比无效模式有效得多，但实际上其性能的差异取决于若干因素，诸如程序修改的次数、相关联的递增更新的复杂性等。此外，设计用于某些程序抽象的更新模式是非常有挑战性的任务。为了解决这种问题，自稳定编译器可支持(懒惰)稳定的无效以及更新模式。
[0070]
需注意，尽管通常lzupd在执行方面似乎是最有效的稳定模式，但eginv稳定模式最接近于在常规的编译器的情况下通常由编译器写入器写入的自定义代码，尤其是在缺少相关程序抽象的增量更新的任何概念的情况下。
[0071]
实施例2：优化过程：用于openmp程序的屏障移除器
[0072]
编译器写入器使用自稳定方法来有效地设计或实现新的优化，而不必写入任何附加代码来稳定程序抽象。为了说明使用所公开的编译方法的益处，使用了减少openmp c程序中的冗余屏障的所涉及的优化遍。
[0073]
如图14中的框图所示，屏障移除器方法执行以下步骤。该方法包括在框1402处移除冗余屏障(在并行区域内)。该移除不违反跨语句的在语句之间的任何数据依赖性。剩余的两个步骤有助于提高每个功能内的屏障移除器的机会。在框1404处扩展和合并并行区域，同时可能尽可能将它们的范围扩展到它们的封闭功能的调用点。这有助于为所得的并行区域内带来更多屏障(包括隐式屏障)，从而为屏障移除创造新的机会。接下来，在框1406处，该方法包括将单态调用内联，该单态调用的目标函数是(i)非递归的，并且(ii)含有至少一个屏障。重复这三个步骤，直到固定点(无变化)为止。这三个步骤涉及许多交错的检查和变换阶段，这又引起对各种程序抽象(诸如阶段信息、指向信息、超级图(涉及cfg、调用图和任务间边)、ast等)的许多交错访问(读出和写入)。
[0074]
与在传统的编译器的上下文中设计或实现该方法的情况相反，在自稳定编译的上下文中实现该方法仅需要实现上述三个优化步骤，并且无需显式代码来稳定相关程序抽象。此外，优化写入器甚至不必指定需要稳定什么程序抽象。因此，即使在所涉及的优化的上下文中，优化写入器仍不清楚如需要稳定哪些抽象、在何处要调用稳定代码和如何稳定抽象中的每个抽象的问题。
[0075]
实施例3a：在编译时间方面的性能评价
[0076]
稳定的懒惰模式的性能评价通过在实施例2中讨论的优化的上下文中研究与编译时间相关的参数来进行。
[0077]
公开了描述在运行屏障移除方法时自稳定的懒惰模式对上述基准程序的编译时间的影响的评估。供参考，在表1中，列7至10示出了在执行屏障移除时在eginv和lzupd模式的自稳定的上下文中在自稳定上花费的时间(以秒计)和总编译时间。如先前所讨论，eginv可以说是实现自稳定的最简单(且自然)的方式。
[0078]
表1：基准特性
[0079][0080]
[0081]
缩写：#loc＝代码行的数目，#leaf＝超级图(抽象)中的叶节点的数目，#pc＝静态并行构造的数目，#barr＝静态屏障的数目(隐式+显式)，并且#ph＝静态阶段的数目。stb时间和总时间分别是指编译器编译基准(使用eginv和lzupd模式)所花费的稳定时间和总时间。存储器是指运行barrelem(具有eginv和lzupd稳定模式)的最大附加存储器占用。具有在时间和存储器方面的最大节省的数据条目以粗体示出。
[0082]
egupd、lzinv和lzupd的影响在idia稳定时间的加速方面通过示出它们相对于eginv的相对加速来示出(参见图15)；表1(第7列和第8列)中示出了eginv和lzupd的稳定时间的原始编号以供参考。如所预期，在所有情况中，lzupd模式带来最小稳定成本；因此，其产生相对于eginv的最大加速，其中加速在稳定数据流分析所花费的时间内在6.9x至77.lx之间变化(几何平均值＝18.82x)。使用特定稳定模式的增益取决于多个稳定模式特定因素，例如(i)稳定触发的次数、(ii)在稳定期间重新处理程序节点的次数、(iii)每次稳定处理每一程序节点带来的成本等。
[0083]
lzupd对eginv：在idfa稳定时间中加速的情况下(图15)，因lzupd而观察到的增益跨所有基准在6.9x与77.lx之间变化。如上所述，实际增益取决于多个因素。例如，对于quake，观察到了idfa稳定时间的最大加速(77lx)，这是由于与eginv相比，在quake中lzupd仅对一小部分(0.03％，数据未显示)的节点重新处理这一事实。类似地，在stencil(6.9x)、ep(7.5x)和histo(7.75x)的lzupd模式下观察到的相对较低的加速(即使仍然相当显著)可归因于以下事实：在所有这三个基准中，每一失效在eginv模式下重新处理的节点的数目在所考虑的基准中是最少的(数据未示出)。
[0084]
lzupd对egupd：从图15中清楚的是，尽管egupd模式始终比eginv表现得更好，但是与lzupd相比，它表现得显著更差。这是因为与lzupd相比，egupd处理显著更高数目的节点。
[0085]
lzupd对lzinv：如图15所示，在idfa稳定时间的上下文中，对于除sp之外的所有情况，lzupd比lzinv表现更好(几何平均值3.30x更好)。sp给出了有趣情况，其示出如果所处理的节点的数目非常高，则重新运行完整分析而不是递增地执行更新是有益的。然而，实际稳定时间之间的差异非常小(《0.25s)。
[0086]
lzinv对egupd：如所预期，lzinv和egupd之间的性能比较由于在两种模式之间划分的懒惰对急切和更新对无效操作所致的益处和损失而导致未能做出的判断。总体上，lzinv胜过egupd达窄界限(几何平均值加速＝1.2x)。
[0087]
总之，在所有四种稳定模式下，lzupd模式带来稳定时间的最大益处。这又导致总编译时间的显著改进，其中跨所有基准(参见表1中的第9列和第10列，用于原始编号)，加速(与eginv相比)在1.08x至10.4x(几何平均值＝4.09x)之间变化。还可看出，在大多数基准中，lzupd不仅降低了稳定的费用，而且还降低了剩余编译时间((第9列至第7列)对(第10列至第8列))，这是由于存储器使用的显著降低(参见第11列和第12列)而产生的潜在益处(在高速缓存、垃圾收集等中)所导致的。
[0088]
实施例3b：在存储器消耗方面的性能评价
[0089]
在实施例2中讨论的优化的上下文中，通过研究与存储器消耗相关的参数来执行所提出的懒惰稳定模式的性能评估。
[0090]
表1(列11和12)示出了在运行来自实施例2的屏障移除方法时就最大驻留大小而言的最大附加存储器占用(以mb为单位)。值通过在具有和没有优化过程的编译期间取峰值
存储器要求的差异来获得。所示的值借助于/usr/bin/时间gnu效用(版本：1.7)计算。图16示出了与eginv模式相比，egupd、lzinv和lzupd模式在存储器占用中的百分比节省。所有这三种稳定模式就存储器要求而言比eginv模式执行得更好(或者或多或少相当)。与eginv模式相比，egupd、lzinv和lzupd模式的存储器消耗的几何平均值改善分别为37.01％、42.54％和53.86％。如上所述，懒惰选项和更新选项都使在数据流分析的稳定期间应用不同的传递函数的次数最小化，即，这一主张通过以下观察来证实：对于大多数基准(除ep、clomp和stencil之外)，与eginv模式相比，lzupd要求最少量的存储器，并且tpacf的最大百分比节省为94.89％。
[0091]
ep和stencil中的表观差异主要是测量工具的精度的问题，其中当绝对值之间的差异小时(几十mb)，难以依赖于增益。需注意，该工具在绘制峰值存储器要求的广图片方面仍有效。在clomp中，在使用java剖析器jvisual vm分析程序时，lzupd和lzinv的峰值存储器使用略高于(约2％)eginv的峰值存储器使用，并且这种异常似乎与底层gc的行为有关，特别是与何时调用gc(影响峰值存储器使用)有关。
[0092]
总之，与朴素eginv方案相比，所提出的懒惰稳定模式带来显著的存储器节省。这又可提高存储器流量和总体性能增益。
[0093]
为了凭经验验证编译器的和指向分析的设计/具体实施的正确性，检验了在稳定的每个模式下的每个基准的指向图。所有四个模式的最终指向图的状态逐字匹配。对于每个基准，检验出所生成的优化代码(i)跨自稳定的四种模式无差别，并且(ii)产生与未优化代码的输出相同的输出。
[0094]
实施例4：自稳定对手动稳定
[0095]
通过比较执行自稳定与执行手动稳定所需的编码努力，执行用于评估所公开的自稳定编译方法对写入不同的编译器遍的影响的经验研究。该研究在来自实施例2的屏障移除优化的各种组成部分的上下文中执行。
[0096]
使用了估计执行手动稳定可能需要的附加编码努力的简单方案。通过进行屏障移除的具体实施以及各种程序抽象还有基本变换来剖析自稳定编译器。通过在每个基准程序上运行该剖析的编译器，获得以下内容：(i)用于屏障移除的改变点(或基本变换可能发生的程序点)集，以及(ii)可能受屏障移除影响的程序抽象集。使用了该数据来估计在添加了新的抽象和新的优化时可能需要克服问题的手动编码努力。
[0097]
实施例4a：在哪里调用稳定？
[0098]
在表2中，列举了在屏障移除的主要组成部分中发现的改变点的数目。
[0099]
表2：在研究中在基准上运行屏障移除时在该屏障移除的组成部分内获得的改变点的最大数目
[0100]
barrelem的组成部分loc#cp并行构造扩大167572功能内联46315冗余屏障删除3132驱动器101总计246190
[0101]
缩写：loc＝代码行的数目；#cp＝改变点的数目
[0102]
在不存在所公开的方法的情况下，编译器写入器将必须在屏障移除中正确地标识这90个改变点(即，平均来讲，几乎每28行代码1个)，并且插入代码来确保受影响的程序抽象的稳定。在每个改变点处，编译器写入器需要处理受影响的程序抽象的稳定，而不管所选择的稳定模式如何。理想地，如果cl与a相关，则需要响应于在改变点cl处的变换来稳定程序抽象a。如果在cl处执行的变换之后读出a，并且其间没有遇到其他改变点，则认为cl是a的相关改变点。因此，使用相关改变点集作为改变点集的更紧密近似，在此之后，可能必须将a稳定。
[0103]
表3列出了受屏障移除影响的每个程序抽象的相关改变点的数目；该数据也是通过剖析自稳定编译器获得的(上文讨论的剖析细节)。
[0104]
表3：通过屏障移除读出的程序抽象
[0105]
程序抽象mode|stb|#a-cp指向点lzupd31612控制流图lzupd61957调用图lzupd1849阶段分析eginv13640任务间边eginv7015符号/类型表lzupd7832标签查找表lzupd47732
[0106]
缩写：mode＝稳定模式；stb＝稳定代码的loc；#a-cp＝在从中读出抽象之后的屏障移除的上下文中的相关改变点的数目。
[0107]
表3示出了在没有所公开的方法的情况下，存在需要调用该稳定代码的大量位置。例如，需要在57个位置执行cfg稳定，并且在49个位置执行调用图，这可能导致麻烦且易于出错的代码。此外，在向编译器添加任何新的程序抽象时，编译器写入器将必须再访先前存在的优化的所有改变点(例如，用于屏障移除的90个改变点)以检查该改变点是否可能必须稳定新添加的程序抽象。相比之下，在存在所公开的方法的情况下，所有上述任务是自动的，即，编译器写入器不需要花费精力来识别稳定的位置，因为写入器不需要添加附加代码作为优化的一部分就能稳定程序抽象。
[0108]
实施例4b：稳定什么？
[0109]
在手动分析屏障移除的代码时，发现存在由屏障移除使用和/或影响的七个程序抽象。这些列在表3中。列4中的非零数字示出编译器写入器实际上需要在执行屏障移除期间调用用于七个程序抽象中的每个程序抽象的稳定代码。因此，在手动稳定的情况下，在写入屏障移除时，编译器写入器需要从过多的可用程序抽象中标识这七个程序抽象，这是一个艰巨任务。此外，在添加任何新的程序抽象a时，编译器写入器需要手动地重新分析屏障移除以检查其对a的影响。相比之下，在存在所公开的方法的情况下，这些任务是自动的，即，编译器写入器无需费力就能标识可能受优化遍影响的程序抽象(现有的或新的)。
[0110]
实施例4c：如何稳定？
[0111]
对于程序抽象的手动稳定，编译器写入器从四种稳定模式中的任一种稳定模式或它们的组合中进行选择，如先前所讨论。在需要通过屏障移除来稳定的七个程序抽象中，阶段分析和任务间边已从yconan导出，yconan是由zhang和dusterwald[2007,2008]提供的并
发性分析。不清楚yconan是否存在支持稳定的更新模式的直接方法。通过检查自稳定编译器的代码，估计了稳定所有七个程序抽象所需的手动代码的量，如表3所示。在添加新的程序抽象时，编译器写入器将需要手动地写入附加代码以用于其稳定。相比之下，在所公开的方法的上下文中，对于迭代数据流分析的情况，诸如指向分析(具有用于手动稳定的316个代码行)或任何新的基于idfa的程序抽象，编译器写入器将不必写入任何稳定代码。因此，与传统的编译器相反，在所公开的方法中写入优化或基于idfa的分析要容易得多，因为编译器写入器不必担心稳定。
[0112]
所公开的方法提供了一种优化方法，以使各种现有程序抽象与所修改的程序一致。该评估还示出了所公开的方法使得易于编写优化和程序分析遍(具有执行稳定所需的最少代码)。此外，懒惰更新和懒惰无效稳定选择带来高效的编译器。所公开的方法不仅为现有优化或程序抽象而且为所有未来的优化或程序抽象提供有保证的自稳定。该方法提供了显式步骤以确保程序抽象总是反映程序在被访问时的正确状态，这又确保下游优化的检查阶段的正确性，并且因此确保所生成的输出程序的正确性。
[0113]
尽管详细描述包含许多细节，但是这些细节不应被解释为限制本发明的范围，而仅作为说明本发明的不同示例和方面。应当理解，本发明的范围包括本文未讨论的其他实施方案。在不脱离如本文描述的本发明的精神和范围的情况下，可在本文公开的本发明的系统和方法的布置、操作和细节中做出将对本领域技术人员显而易见的各种其他修改、改变和变化。

技术特征：
1.一种用于程序的自动自稳定编译的计算机实现的方法，所述方法包括：由处理器(204)接收输入程序；由所述处理器(204)使用多个分析操作来生成所述输入程序的多个抽象，其中所述多个抽象中的每个抽象表示与在编译时的程序状态相关联的信息；由所述处理器(204)通过基于一组预定基本变换修改与所述抽象相关联的所述程序状态来对所述多个抽象中的一个抽象执行一个或多个优化操作(408)，其中所述一组预定基本变换捕获与所修改的程序状态相关联的信息；以及由稳定器(408)在稳定模式下使用由所述一组预定基本变换(212)捕获的所述信息来稳定所述多个抽象中的一个或多个抽象，其中所述稳定包括使用所捕获的信息来更新所述一个或多个抽象以维持所述抽象与所修改的程序状态的一致性。2.根据权利要求1所述的方法，其中所述预定基本变换(408)包括添加、删除或修改所述程序的语法部分。3.根据权利要求1所述的方法，其中所述稳定模式是懒惰无效稳定模式、懒惰更新稳定模式、急切更新稳定模式、急切无效稳定模式或它们的任何组合中的一者。4.根据权利要求1所述的方法，其中所述一个或多个抽象表示与串行或并行程序相关联的信息。5.根据权利要求1所述的方法，其中所述多个抽象包括中间表示、控制流图和抽象语法树。6.根据权利要求1所述的方法，所述方法包括响应于执行新的优化操作而稳定所述一个或多个抽象，其中所述稳定包括更新所述一个或多个抽象以维持所述抽象与所修改的程序状态的一致性。7.根据权利要求1所述的方法，其中所述多个抽象包括迭代数据流分析，并且其中使用自动懒惰更新稳定模式来稳定所述迭代数据流分析。8.一种用于执行程序的自动自稳定编译的系统，所述系统包括：分析部件(208)，所述分析部件被配置为接收输入程序并执行所述输入程序的多个分析操作以生成多个抽象，其中所述多个抽象中的每个抽象表示与在编译时的程序状态相关联的信息；优化部件(210)，所述优化部件被配置为通过基于一组预定基本变换修改与所述抽象相关联的所述程序状态来对所述多个抽象中的一个抽象执行一个或多个优化操作(408)，其中所述一组预定基本变换捕获与所修改的程序状态相关联的信息；以及稳定器(212)，所述稳定器被配置为使用由所述一组预定基本变换(408)捕获的所述信息来稳定所述多个抽象中的一个或多个抽象，其中所述稳定包括使用所捕获的信息来更新所述一个或多个抽象以维持所述抽象与所修改的程序状态的一致性。9.根据权利要求8所述的系统，其中所述分析部件(208)包括预处理单元(304)、词法分析单元(306)、语法分析单元(308)和语义分析单元(310)。10.根据权利要求8所述的系统，其中所述稳定器(212)被配置为在稳定模式下操作，其中所述稳定模式是懒惰无效稳定模式、懒惰更新稳定模式、急切更新稳定模式、急切无效稳定模式或它们的任何组合中的一者。11.根据权利要求8所述的系统，其中所述优化部件包括一个或多个抽象读出器(402)
和一个或多个抽象写入器(406)，并且其中所述一个或多个抽象读出器(402)被配置为读出所述一个或多个抽象，并且所述一个或多个抽象写入器(406)被配置为修改所述一个或多个抽象。

技术总结
本发明公开了用于程序的自动自稳定编译的系统和方法。该方法包括由分析部件(208)接收输入程序并使用多个分析操作来生成该输入程序的多个抽象。该多个抽象中的每个抽象表示程序状态。优化部件(210)基于一组预定基本变换(408)来对该多个抽象(316)中的一个抽象执行优化操作以修改该程序状态。稳定部件(212)在稳定模式下使用由该一组预定基本变换捕获的信息来执行对该多个抽象(316)中的一个或多个抽象的稳定。该稳定包括更新该一个或多个抽象(316)以维持该抽象与该程序状态的一致性。象(316)以维持该抽象与该程序状态的一致性。象(316)以维持该抽象与该程序状态的一致性。


技术研发人员：K
受保护的技术使用者：印度理工学院马德拉斯分校
技术研发日：2021.11.26
技术公布日：2023/8/14