领域特定语言用于编译器的数据流分析生成器

理论计算机科学电子笔记164（2006）103-119www.elsevier.com/locate/entcs一种用于生成数据流分析器的贾增2纽约哥伦比亚大学计算机科学系查克·米切尔3微软公司华盛顿州雷德蒙德Stephen A. 爱德华四世纽约哥伦比亚大学计算机科学系摘要数据流分析是一种很好理解的、非常强大的技术，用于在编译过程中分析程序。几乎所有的编译器都使用某种数据流分析作为其优化阶段的一部分。然而，尽管理论上很好理解，但这种分析通常很难编码，因此很难快速试验变体。为了解决这个问题，我们开发了一种特定于领域的语言，Analyzer Generator（AG），它可以为Microsoft的Phoenix编译器框架合成数据流分析阶段。 AG隐藏了使分析模块化所需的繁琐细节，但生成的代码与手工编码的代码一样高效。我们引入的一个关键构造允许IR对象类在不重新编译的情况下进行扩展。三个分析的实验结果表明，AG代码可以是十分之一的等效手写C++代码的大小，而没有损失的性能。我们希望AG能够使开发新的数据流分析变得更加容易。关键词：领域特定语言，数据流分析，动态类扩展，编译器，Phoenix编译器框架1Edwards和他的团队获得了NSF CAREER奖、SRC奖和纽约州NYSTAR计划的支持2电子邮件地址：jia@cs.columbia.edu3电子邮件地址：chuckm@microsoft.com4电子邮件地址：sedwards@cs.columbia.edu1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.10.008104J. Zeng等理论计算机科学电子笔记164（2006）1031引言现代的优化编译器是一种庞大的野兽。例如，GCC 4.0.2的代码超过了100万行。它的重要性很大程度上是由于它的许多特性：完全支持真实世界的语言，一百种或更多的优化算法，以及无数的后端。但其内部结构的API的内在复杂性我们通过提供一种特定于域的语言来解决后一个问题，AG用于实验上，我们表明，在AG中编码的功能等效的分析可以小于十分之一的线的数量，他们的手编码的C++同行，并具有相当的性能。减少描述特定分析所需的代码行数可以减少编码和调试时间。我们希望我们的语言能够快速进行实验，比较各种分析的有效性。最后，通过提供一种简洁的语言，允许分析以模仿标准文本的伪代码表示法进行编码[1]，编译器学生将能够更快地编码和实验这些算法。我们的工作的一个贡献是动态扩展现有类的机制在编写数据流分析时，通常希望在分析的中间表示（IR）中向现有类添加新的字段和方法。然而，这些字段在分析完成后就不需要了，所以我们想丢弃它们。虽然继承使创建新类变得容易，但大多数面向对象语言不允许更改现有的类。主要的区别是，我们希望现有代码从新类生成对象，否则它不会这样做。扩展类的挑战是面向方面编程社区的一个活跃的研究领域[7]，但是他们的解决方案与我们的不同。例如，非常成功的ANOJ [6]语言提供了类型间声明，可以向现有类添加字段和方法像我们的技术一样，这种技术允许在类的主文件之外定义新的类字段和方法，它是一种编译时机制，实际上改变了底层的类表示，需要重新编译原始类和依赖于它的所有内容。在AG中，当添加新字段时，只有扩展类的代码必须重新编译。MultiJava [3]提供了一种机制，能够扩展现有的类而无需重新编译它们，就像我们自己的机制一样，但它们的机制只允许向现有的类添加方法，而不是字段。在AG中，我们提供了一种无缝的机制来为现有的IR类添加注释。在AG代码中，用户可以使用与原始类中的字段相同的简单syn- tax来访问这些添加的字段。添加这些字段不需要重新编译任何使用原始类的代码。我们在微软的Phoenix框架上实现了AGJ. Zeng等理论计算机科学电子笔记164（2006）103105用于构建用于程序分析、优化和测试的编译器和工具。像SUIF系统[13]一样，Phoenix被专门设计为可扩展的，并提供了例如将新字段附加到核心数据类型而无需重新编译核心的能力。不幸的是，在C++中实现这样的工具（Phoenix就是在C++中编写的）在使用这样的工具的代码的复杂性和执行速度方面都有代价在实验中，我们发现执行速度的损失小于4倍，并且可以改进;不幸的是，在C++中使用这种工具的冗长损失似乎是10倍左右。减少这一点是农业的主要优势之一。2相关工作数据流分析的理论已经得到了很好的研究。Kildall [8]是最早提出统一的基于格的全局程序分析框架的人之一。后来，Kam和Ullman [5]提出了迭代方法，并使理论更加具体。Wilhelm [12]指出，数据流分析有许多通用理论，但很少有工具是建立在这些理论之上的，被广泛接受的就更少了。一个很大的原因是缺乏标准的中级程序表示。我们希望Phoenix编译器框架能够解决这个问题，至少对于面向对象的命令式语言来说是这样。缺乏工具的另一个原因是它们的复杂性。因此，我们工作的重点是提供一个简单的语言和工具来编写数据流分析。Tjiang它建立在SUIF[13]通用编译器构造框架之上然而，沙利特并没有引入一种新的语言。它使用C++并提供一些API，很像Phoenix环境，它的重点主要是它的效率，而不是它的简单性。虽然它使分析的实现更加模块化，但它仍然难以使用。一些工具需要明确定义数据流分析中使用的网格例子包括Alt和MartinPAG是众所周知的，并已在工业中使用。AG和PAG之间有很多相似之处：都使用基本块和不变的前置条件检查来提高生成的分析器的速度两者都提供了“set”数据类型。与AG不同，PAG要求用户指定分析过程中使用的格，这提供了更多的优化选择，比如加宽和缩小，并且更容易验证算法一些工具专门处理过程间分析，例如Yi和Harri-son我们只关注程序内的分析，尽管我们的许多想法应该延续到程序间的问题。106J. Zeng等理论计算机科学电子笔记164（2006）1033AG的设计G是一种高级语言，它提供抽象来描述迭代数据流分析。AG编译器将AG程序转换为C++源文件和头文件，然后编译生成动态链接库（DLL）文件。（图1）然后可以将此DLL我们生成的插件扩展了IR对象来收集信息，并调用Phoenix框架的一部分遍历来执行迭代分析。这个遍历函数调用AG程序中定义的计算。我们遵循经典的数据流分析方法。AG程序隐式地遍历程序的控制流程图，并且每次考虑一个基本块。在每个块内，分析操作其组成指令和操作数。因此，我们选择在AG中将块、指令和操作数作为基本对象。很自然，Phoenix已经有了这样的数据类型，但是AG使它们更容易使用，因为我们的语言对它们有更深入的理解AG的主要贡献之一是能够向这些基本数据类型添加属性和计算。这个功能依赖于Phoenix中已经内置的机制，但是由于C++的局限性，使用这样的机制对于代码来说是笨拙和繁琐的。G使它更容易。为了简化计算功能的描述，我们在AG中包含了新的状态，例如foreach和数据流方程，就像在任何编译器文本中找到的那样。我们还介绍了一种集合数据类型，因为在数据流分析过程中收集的数据通常采用集合的形式。AG依赖于Phoenix Traverser类。这是一个迭代的迭代器，并不保证有界性。参见Nielson和Nielson [9]关于保证有界性问题的讨论。4AG语言AG语言是为数据流分析而设计的。它为迭代过程内分析的共同特征提供了抽象。为了用户的方便和适应性，我们选择了类似于C++的语法，并添加了各种新的语句和构造。4.1程序结构图2显示了描述分析仪的典型AG它定义了一个新的命名阶段，用新的字段和方法扩展了许多内置的Phoenix类，以定义要收集的信息，并最终定义了用于数据流分析的传递函数。扩展类定义了一个新的IR类，它使用Phoenix动态可扩展的IR类系统。在扩展类中声明的新字段和方法将作为新的类成员添加。用户可以直接引用它们，J. Zeng等理论计算机科学电子笔记164（2006）103107Phx C++编译器AG翻译DataflowAlgorithm.agDataflowAlgorithm.Phx.cpp/.hAG库文件Phx库文件DataflowAlgorithm.dllFig. 1. AG框架的运作阶段名称{extend classname{外地申报.方法声明.void Init（）{ 个文件夹}.public voidrun（）{Compose（N）{. 个文件夹Meet（P）{. 个文件夹结果（N）{. 个文件夹}}图二、AG程序的结构原始类的成员（我们的编译器识别这些字段，并生成适当的Phoenix代码来访问和调用这些扩展类的成员）。注意，在一个扩展类中声明的方法是“私有的”，也就是说，它们只能应用于相应的扩展对象，或者在同一个扩展类下声明的其他方法中。目前，我们只支持扩展Block、Instr和Opnd类。在每个扩展类中，Init方法的行为（并作为初始化器执行）就在扩展类的构造函数每个阶段都有一个定义返回类型和迭代类型的TransFunc。108J. Zeng等理论计算机科学电子笔记164（2006）103分析仪的安装（向后或向前），更重要的是，分析过程中应用的方程。TransFunc的主体可以定义函数，特别是三个保留函数：Compose，Meet和Result。Compose和Meet函数在编译器对每个块进行迭代时应用。Compose函数使用全局数据定义块内的计算。Meet函数定义块之间执行的计算，即，将数据从前趋程序的出口合并到后继程序的入口Result函数定义在迭代后立即执行的操作。它通常将信息传播到组成块的对象，如指令。其他函数可以在TransFunc中声明;它们可以由三个保留函数调用，也可以相互调用。用户可以在这些方法的主体中嵌入任意C++代码。这样的代码段对AG编译器是透明的，ag编译器只是将它们逐字包含在生成的代码中。4.2公司简介我们从C++中推导出AG我们在附录中给出了它的完整语法;表1提供了一个摘要。下面，我们提供一些关于它的设计细节。Set是一种类似于C++标准库中set的数据类型。它只能应用于保留类，实际上是指一组ID。例如，Map类型类似。在分析过程中，最相关的数据是那些包含每个块的入口和出口点信息的数据，因此我们引入了In和Out数据集作为内置变量。除了两个逻辑运算符之外，表1中的运算符既可以应用于整数，也可以应用于集值变量。使用+、−和 * 运算符生成对位向量执行Or、Minus和And运算的在数据流分析中，经常需要遍历对象的子集，因此我们添加了一个foreach语句来完成此操作。Foreach是一个谓词迭代器，这意味着它遍历集合的成员，并仅对集合中选定的成员执行操作。 用户不必专门声明迭代器，只需声明一个迭代发生的类型的变量和要迭代的集合。 用户还可以指定一个条件，作为一个过滤器和方向（向前/增加或向后/减少）。条件是用where关键字描述的。语法如表1所示。所允许的类型、范围和条件在所附语法表中列出。“where condition“和“direction“参数是可选的这样的foreach语句在C++中被转换为条件for循环，并在Phoenix框架中使用迭代器宏。注意foreach语句，特别是谓词，不是严格必要的（一个额外的if就足够了），但同样可以说CJ. Zeng等理论计算机科学电子笔记164（2006）103109数据类型Set Map int bool void特殊变量输入输出operator s+−=+=−=内置类Opnd Instr Block Expr Func Region特殊方法初始化组成满足结果内置函数DstAliasTable SrcAliasTable Print内置常量向前向后声明阶段标识符（参数列表）{.个文件夹extend classtype{.个文件夹transFunc（direction）{.个文件夹statementslvalue=expression;if（）{.}else{.个文件夹/%arbitrary C++ code%/foreach（type var in range where cond. 方向）{. 个文件夹phoenix-iterator（.）{. }表1AG.总结如果范围是Set，则类型必须与其内容匹配。 否则，如果范围是类，则类型必须与其成员之一匹配。例如，每条指令都包含一个操作数列表，因此我们可以指定Opnd的类型和指令的范围。此外，用户可以指定“数据流dst”的条件Phoenix提供了大量的迭代器宏，这些宏几乎可以在AG中原封不动地使用（参见图3第12行）。唯一的区别是，在C++中，匹配的DstAliasTable是一个保留函数，它接受别名标记x作为参数，并返回一组别名标记为x的目标操作数。类似地，SrcAliasTable返回具有相同别名标记的所有源操作数。5例为了说明AG，我们提出了一个完整的例子：经典的完整的银源如图3所示。该算法计算到达程序中每个基本块《龙书》（Dragon Book）[1]110J. Zeng等理论计算机科学电子笔记164（2006）103变量的操作数是指令中可以分配给变量的操作数。 在PhoenixIR中，每条指令都有源操作数和目的操作数。为了达到定义，我们主要关心的是目的地。整个分析被定义为一个称为ReachingDefs的阶段（图3的第1行）。分析的其余部分由扩展类组成，这些扩展类将字段和计算添加到操作数、指令和基本块的内置数据类型，以及传递函数的描述。5.1扩展类扩展类通过额外的字段来增加现有的数据类型，在这些字段中收集信息和收集信息的过程这类似于在面向对象的语言中扩展基类，但不同之处在于，新的属性实际上是在语言级别上附加到“基类”本身的对象，而不仅仅是在派生类的对象中（我们从ag生成的C++代码实际上使用了 但是用户可以引用新属性，就好像它们已经在原来的班级。考虑Opnd扩展类（第3-20行）。这将为每个操作数添加两个属性，即名为Gen和Kill的操作数集。像往常一样，Gen集合包含在块内定义的操作数，并且在源代码中紧随其后。Init函数用于初始化Gen和Kill字段的值。这两个集合以位向量的形式实现--Gen的声明见图4中的第2-12行Init的主体将目的操作数添加到Gen集合。类似地，内置目的地opnd映射到别名标签表（DstAliasTable）中具有与操作数相同的别名标签的所有其他目的地操作数（即，当两者都修改相同的内存位置时）被添加到Kill集（第12Instr和Block扩展类将Gen和Kill集添加到它们的每个类中，并分别使用来自Opnd和Instr对象的数据填充这些集。图4中的第47-72行请注意，这个函数完全是根据分析器中如何使用这些数据合成的，而不是根据AG源代码中的显式代码合成的在收集块的Gen和Kill集之后，该算法指定了主要分析迭代的一些在传递函数TransFunc的开头，声明迭代向前进行并返回一组Opnd对象。扩展类是基于原始的IR类。图3中的示例显示用户可以引用扩展类中的字段（例如，图3，第10行，图3，第13行： 这两个引用产生了非常不同的C++代码（c.f.图4，第21和23行）。J. Zeng等理论计算机科学电子笔记164（2006）1031111阶段到达定义{23extendclassOpnd {4设置Opnd> Gen;5设置Opnd>Kill;6publicvoidrun（）{8Opnd opnd =this;public voidrun（）{10opnd->Gen += opnd;1112foreach_must_total_alias_of_tag（alias_tag，opnd->AliasTag，AliasInfo）{13opnd->Kill+=String getString（String）;14}15opnd->Kill -= opnd;16}17}18}1920extend class Instr {21设置Opnd> Gen;22设置Opnd>Kill;23publicvoidrun（）{25Instr instr=this;2627foreach（OpnddstOpnd ininstrwhere（oplowdst））{28instr->Gen+= dstOpnd->Gen;29instr->Kill+=dstOpnd->Kill;30}31}32}3334extend class Block {35设置Opnd> Gen;36设置Opnd>Kill;37publicvoidrun（）{39Block block =this;4041foreach（Instr instr in block）{42block->Gen = instr->Gen +（block->Gen- instr->Kill）;43block->Kill=block->Kill+instr->Kill -instr->Gen;44}45}46}4748设置Opnd> TransFunc（Forward）{public void run（N）{50Out = In-N->Kill + N->Gen;51}5253满足（P）{54In += P->Out;55}56}57}图三.一个完整的AG分析：达到定义112J. Zeng等理论计算机科学电子笔记164（2006）1031个类OpndExtensionObject：2publicPhx：：RbagGenTest：：AG：：OpndExtensionObject3.4PHX_DEPENTE_PROPERTY（Phx：：BitVector：：Sparse* ，Gen）;5PHX_DEFINED_VIRTUAL_GET_PROPERTY（Phx：：BitVector：：Sparse*，Gen）const;6PHX_DEFINED_VIRTUAL_SET_PROPERTY（Phx：：BitVector：：Sparse*，Gen）;78Phx：：BitVector：：稀疏* _local_Gen;（9）1011void OpndExtensionObject：：Init（Phx：：FuncUnit *func_unit，12Phx：：BitVector：：Sparse*PHX_ARRAY（dst_alias_table））13{14Phx：：IR：：Opnd *opnd=_this;15if（opnd->IsDef）{this->Gen->SetBit（this->uid）;17foreach_must_total_alias_of_tag（alias_tag，opnd->AliasTag，func_unit->AliasInfo）{18this->Kill->Or（dst_alias_table（alias_tag））;19}20next_must_total_alias_of_tag21this->Kill->ClearBit（this->uid）;22}23}2425void IterateData：：Merge（26Phx：：DataFlow：：Data*dependent_block_data，27Phx：：DataFlow：：Data* affected_block_data，28Phx：：DataFlow：：MergeFlags标志）{IterateData * dep_block_data=PTR_CAST（IterateData *，dependent_block_data）;30Phx：：BitVector：：稀疏*出来= dep_block_data->Out;3132if（标志& Phx：：DataFlow：：MergeFlags：：First）在int getName（）;33else In->Or（Out）;34dep_block_data->Out= Out;35}3637虚空Traverser：：InitData（Phx：：BitVector：：Sparse *PHX_ARRAY（dst_alias_table））38{39foreach_block_in_func（block，funcUnit）{40foreach_instr_in_block（instr，block）{41foreach_blog_dst_opnd（dstopnd，instr）{42OpndExtensionObject*ext_dstopnd =43OpndExtensionObject：：GetExtensionObject（dstopnd）;44ext_dstopnd->Init（funcUnit，dst_alias_table）;45}46下一个_低_dst_opnd;47InstrExtensionObject*ext_instr =48InstExtensionObject：：GetExtensionObject（instr）;49ext_instr->Init（funcUnit->Lifetime）;50}51next_instr_in_block;52块扩展对象*ext_block =53BlockExtensionObject：：GetExtensionObject（block）;54ext_block->Init（funcUnit->Lifetime）;55}56next_block_in_func;57}58}见图4。由AG编译器为到达定义示例5.2传递函数像往常一样，我们假设每个块在控制流程图中有唯一的入口和出口点“In”和“Out”是分别与入口点和出口点相关的两个内置数据集。TransFunc头的定义将“In”和“Out”集的类型声明为保持操作数。这两个集合通常用于传递函数来传递数据。组成和满足是定义传递函数的两个主要函数在这个程序中，他们指定了标准中的两组数据流方程，J. Zeng等理论计算机科学电子笔记164（2006）103113达到定义生活变量Uninitialized变量C++编程语言（手册）791303∗108†AG控制器（手动）645594C++编译器（生成）626519682C++运行时7.3s0.8s†AG运行时间7.4s3.1s13.6s手动编码的实时变量分析使用硬编码字段，这使得它更简单，但代价是远没有那么模块化。†手动编码的未初始化变量分析依赖于Phoenix SSA库，该库未包含在本文档算 这是一个与AG生成的代码非常不同的架构。表2实验结果：AG生成的代码的大小和速度与. 手写的路[1，方程。10.9]：in[Bi]=out[Bj]BjaBiout [Bi]= gen [Bi]（in [Bi] − kill [Bi]）。第一个方程精确而简单地包含在Meet函数中（第59行），该函数计算迭代中前一个块的出口点数据与当前块的入口点数据的乘积In与正在访问的当前块相关，而Out与传递给Meet函数的块P相关。 默认情况下，Meet函数的参数是表示当前块的任意前趋块的基本块。如图4第31-第二个数据流方程包含在Compose函数（第55行）中，该函数计算单个块从入口点到出口点的全局数据转换。声明为Compose函数的参数，变量N默认是块的扩展对象。由于Gen和Kill是已经添加到Block类中的字段（第38和39行），因此它们可以被称为N的成员。5.3标签：Phase and Traverser一个完整的AG程序被翻译成一个C++程序，该程序被编译为一个插件阶段，可以作为Phoenix编译过程的一部分调用。它首先遍历所有扩展对象，然后执行前向并行计算器，该前向并行计算器应用数据流方程来迭代地计算遵循控制流图结构的块，直到In集合收敛于每个块。生成的代码使用Phoenix框架中内置的机制来完成此任务;AG用户不会为此编写代码。114J. Zeng等理论计算机科学电子笔记164（2006）1036实验结果我们在三个分析中测试了AG我们之所以选择这三个例子，是因为Phoenix中已经有了由经验丰富的程序员编写的每一个例子的手写版本。我们比较了前两个示例生成的代码与手动编写的代码的大小和速度，因为它们与我们生成的代码一样，使用了Phoenix中的Traverser类。未初始化变量的手动编写版本使用Phoenix表2显示了我们的结果。 我们计算了这些插件的平均运行时间，通过运行编译器与插件，运行编译器没有插件，并减去这两个运行时间。因此，这些时间有点可疑，因为它们还包括加载和初始化插件本身的时间在每个测试用例中，AG编译器生成的C++代码是AG源代码大小的六倍以上。对AG来说更好的是，达到定义的手动代码甚至比生成的代码还要大。这是因为AG库文件包括常用的代码和默认方法，例如阶段的构造函数手动编写的活动变量代码比为该分析生成的C++代码要小，但这是因为手动编写的代码没有使用（冗长的）Phoenix扩展对象。我们在一台配备2.0 GHz Pentium-M处理器、运行Windows XP的笔记本电脑 上 运 行 生 成 的 Phoenix C++ 代 码 基 准 是 Phoenix Microsoft IntermediateLanguage阅读器，它可以为各种目标生成高级中间表示。它大约有五十万行代码。自动生成的可达性定义分析代码运行速度与MSIL阅读器上手动编写的代码一样快。不幸的是，实时变量分析代码的运行速度只有它的四分之一，但这是有原因的：手动编写的C++版本不使用Phoenix对象扩展功能。相反，它只是在每次遍历块时重新计算所需的数据。因此，这里的速度差异更多地说明了使用扩展对象而不是更暴力的方法的成本。显然，在这个例子中，计算是足够便宜的，所以重复它比保存和稍后恢复它的成本更低。我们为未初始化的变量包括AG代码的运行时，但不给出手动编写的代码的时间，因为它使用完全不同的算法。7结论我们提出了一种特定于领域的语言AG，用于在Microsoft的Phoenix框架中编写数据流分析实验结果表明，手工编写的AG代码可以不到十分之一的等效手工编写的C++的大小与类似的AG代码简单性的一个关键推动因素是其机制-J. Zeng等理论计算机科学电子笔记164（2006）103115扩展现有IR类的机制，这使得扩展现有类而无需重新编译它们成为可能，并允许用户级代码像典型的字段一样轻松地访问这些字段。作为一种小型的、特定于领域的语言，AG有一些弱点。最小化冗长是我们的重点，我们这样做是在损失一些可扩展性的情况下。最明显的是，用户被迫使用迭代分析框架，即使Phoenix有其他的选择，如网格和静态单赋值框架。虽然AG有一些高级类型，如集合和映射，但它的类型系统是有限的，不支持字符串、数组、任意迭代器等。AG目前也仅限于在中级中间表示（MIR）上运行的分析此外，AG程序目前只处理用户定义的变量; MIR中的许多例如，左侧的C状态被拆除，如右侧所示。AG代码当前忽略临时t1。x = y +3;−→t1= y +3;x =t1;与许多领域特定语言一样，调试AG有点问题。虽然我们提供了print语句，但AG没有专用的调试器、IDE或开发环境中的任何其他标准功能。所有这些都可以增加，但不是没有相当数量的工作。AG是作为翻译器构建的，因此理论上大多数弱点都可以通过扩展AG来修复它可以扩展，比如说，描述基于区域的数据流分析，或描述优化。但是很难说AG在什么时候会不再是一种特定领域的语言，而会变成C++。尽管如此，我们相信代码大小减少10倍是合理的，因为使用小型语言会带来额外的挑战。有关凤凰的更多信息，请参阅其官方网站：http://research.microsoft.com/compilers网站。致谢我们要感谢Al Aho对这个项目的启发性讨论和有趣的建议。我们也要感谢整个凤凰集团的善意帮助和支持。引用[1] Alfred V. Aho，Ravi Sethi，and Je Escherey D.厄尔曼原则、技术和工具。Addison-Wesley，1988年。[2] Martin Alt和Florian Martin。使用PAG生成高效的过程间分析器。第二届国际静态分析研讨会论文集（SAS），第33-50页，英国伦敦，1995年史普林格出版社116J. Zeng等理论计算机科学电子笔记164（2006）103[3] 作者声明：Gary T. Leavens，Craig Chambers，and Todd Millstein. MultiJava：Java的模块化开放类和对称多重分派。面向对象编程，系统，语言和应用程序（OOPSLA），第130-145页，明尼阿波利斯，明尼苏达州，2000年[4] 马 修 湾 Dwyer 和 Lori A. 克 拉 克 用 于 构 建 数 据 流 分 析 器 的 灵 活 架 构 。 在 Proceedings of the 18 thInternational Conference on Software Engineering（ICSE），第554-564页[5] John B. Kam和Je Escherey D.厄尔曼全局数据流分析和迭代算法。Journal of the ACM，23（1）：158[6] Gregor Kiczales，Erik Hilsdale，Jim Hugunin，Mik Kersten，Je Escherey Palm和William G.格里斯沃尔德一个概述的ANOW J。计算机科学讲义，2072：327[7] Gregor Kiczales ， John Lamping ， Anurag Menhdhekar ， Chris Maeda ， Cristina Lopes ， Jean-MarcLoingtier ， andJohnIrwi n.一 种 特殊的 程 序 设 计 。InMehmetAksitanddSatoos hiM ats uoka，editors ， Proceedings European Conference on Object-Oriented Programming ， pages 220-242 ，Berlin，Heidelberg，and New York，1997. 史普林格出版社[8] G.基尔达尔全局程序优化的统一方法。在Proceedings of Principles of Programming Languages，第194-206页[9] Hanne Riis Nielson和Flemming Nielson有界不动点迭代在Proceedings of Principles of ProgrammingLanguages（POPL），第71-82页[10] Steven W. K. Tjiang和John L.轩尼诗Sharlit：一个构建优化器的工具。Proceedings ofProgrammingLanguage Design and Implementation（PLDI），第82-93页，纽约，纽约，1992年。[11]G. A. Venkatesh和Charles N.费舍尔Spare：程序分析算法的开发环境。IEEE软件工程学报，18（4）：304[12] 莱因哈德·威廉程序分析-工具制造者的观点。ACM Computing Surveys，28（4es）：177，1996.[13] 作 者 ：Robert S.作 者 ：Christopher S.放 大 图片 作 者 ： Saman P.作 者 ：Steven W. K.放 大 图片 作 者 ：Tjiang，Lih-Wei，Chau-Wen Tseng，Mary W. 莫妮卡·霍尔 Lam，and John L.轩尼诗SUIF：研究并行化和优化编译器的基础设施。ACM SIGPLAN Notices，29（12）：31[14] 李光根和威廉姆斯·卢德韦尔·哈里森三世。过程间程序分析的自动生成和管理。在Proceedings ofPrinciples of Programming Languages（POPL），第246-259页J. Zeng等理论计算机科学电子笔记164（2006）103117公司简介ag相：相位标识符（parameter-listopt）复合语句参数列表：参数参数列表，参数参数：类型标识符字体：基础型可扩充类型设置类型>地图类型，类型>基本类型：其中之一int bool voidextensible-class-type：其中之一别名OpndInstr块区域功能化合物声明：联系我们声明：声明语句声明：变量说明函数定义扩充类定义assignment-expressionopt;if-else-statementforeach-statementphoenix-foreachcontinue;break;returnexpression;118J. Zeng等理论计算机科学电子笔记164（2006）103cpp代码段复合语句J. Zeng等理论计算机科学电子笔记164（2006）103119变量声明：类型变量声明列表;变量声明列表：变量变量声明列表变量：识别器标识符=表达式功能定义：基本函数定义基本功能定义：类型标识符（参数列表选项）复合语句transfer-function-definition：transFunc（direction）类型复合语句计算函数定义：compound-statement（compound-statement）compute-function-name：函数名组成满足结果扩展类定义：扩展类型复合语句assignment-expression：变量或字段赋值运算符表达式变量或字段：变量或字段->标识符标识符120J. Zeng等理论计算机科学电子笔记164（2006）103表达式：数字文字变量或域二元运算符表达式！表达-表达式variable-or-field（variable-listopt）（表达式）变量列表：变量或场变量列表，变量或字段binary-operator：其中之一+ --<>&& || <=>= ！= =-赋值运算符：其中之一=+=--if-else-statement：if（expression）语句if（expression）语句else语句foreach-statement：foreach（type identifierinexpression whereoptdirectionopt）复合语句其中：where表达式方向：其中之一正倒向phoenix-foreach：phoenix-foreach-keyword（parameter-listopt）compound-statementcpp-code-segment：/%C++-program-text%/