静态单赋值表单在Java虚拟机代码优化中的应用

理论计算机科学电子札记141（2005）85-102www.elsevier.com/locate/entcs静态单赋值表单Andreas Gal Christian W.ProbstMichael Franz1加州大学信息与计算机科学学院Irvine，CA，92697，USA摘要静态单赋值（SSA）形式经常被用作Java虚拟机代码优化过程中的中间表示。最近，SSA已成功用于字节码验证。然而，在代码消费者处构造SSA是昂贵的。基于SSA的移动代码传输格式已经被证明可以通过将SSA创建转移到代码生产者来消除这种成本。然而，这些新格式与已建立的Java类文件格式不向后兼容。我们提出了一种新的方法来传输SSA信息隐式通过标准Java字节码的结构代码属性。 虽然产生的字节码序列仍然可以直接由传统的虚拟机执行，但我们的新型VM可以推断SSA形式并确认其安全性，几乎没有开销。保留字： 移动代码，验证，优化1 电子邮件：{gal，probst，franz}@ uci.edu本研究部分由美国国家科学基金会（NSF）根据TC-0209163和ITR-0205712拨款以及海军研究办公室（ONR）根据N 00014 -01-1-0854协议资助。美国政府被授权为政府目的复制和分发重印本，尽管上面有任何版权注释。本文所含的观点和结论是作者的观点和结论，不应被解释为必然代表国家科学基金会、海军研究办公室或美国任何其他机构的官方政策或认可（无论是明示还是暗示）。政府的1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.02.04586A. Gal等人/理论计算机科学电子笔记141（2005）851引言Java程序以独立于平台的字节码格式提供。为了执行这样的程序，虚拟机（VM）可以选择简单地逐指令解释字节码指令。与本机机器代码执行相比，这会导致执行性能的显著损失。即时（JIT）编译器用于动态地将可移植字节码转换为本地机器码，该本地机器码由底层物理CPU直接执行，从而消除了解释引起的大部分开销。代码优化是许多动态代码生成系统的重要组成部分由于字节码必须运行在各种可能的目标架构上，代码生产者无法提前应用许多优化。例如，执行积极的公共子表达式消除，虽然可能在具有许多寄存器的RISC架构上受益，但可能会通过增加寄存器压力和引入不必要的内存溢出来严重降低CISC架构（如x86）的性能。因此，优化必须由代码消费者JIT编译器来执行由于字节码是基于堆栈的，因此不太适合执行代码优化。相反，它通常被转换为一种中间表示形式，如静态单分配（SSA）形式[5]。在SSA形式中，变量被分成多个实例，这样每个新的变量实例都只定义一次。在控制流合并点，插入特殊的φ指令来合并变量实例，并将适当的值分配给该变量的新的唯一实例通过这种转换，SSA形式将定义使用信息嵌入到程序表示中。我们最近已经展示了如何使用SSA进行字节码验证[9，10]。为了实现这种方法，重要的是使传入程序的SSA形式有效地可用。 从算法的角度来看，将字节码转换为SSA需要在图中找到支配者[3，12]，并计算迭代的支配边界[2]。 虽然这两个问题在理论上都是线性的[20]，但它们仍然会导致不可忽略的运行时间开销。SafeTSA [1]等方法通过在代码生产者将字节码转换为SSA来避免这种开销。然而，为了发布移动代码，SafeTSA定义了一种新的不兼容的类文件格式。虽然可以通过将基于SSA的表示作为可选注释来避免此类兼容性问题，但该选项会严重增加类文件的大小，因为代码会被有效地表示两次。这也将允许两种格式之间的不一致缺乏兼容的传输格式阻碍了基于SSA的移动代码格式的采用。A. Gal等人/理论计算机科学电子笔记141（2005）8587我们提出了一种新的方法，基于SSA的移动代码表示。而不是引入一个新的和不兼容的字节码格式，我们使用现有的字节码格式和传输SSA信息，通过修改结构代码属性，如局部变量映射和基本块排序。生成的字节码与Java标准完全兼容，可以由传统的Java VM执行。然而，一个特制的VM可以直接推断SSA形式，并在线性时间内验证推导出的基于SSA的表示的正确性。本文的其余部分组织如下：在第2节中，我们简要概述了Java字节码格式。第3节描述了我们用来编码SSA信息的字节码转换过程。第4节讨论支配者信息的编码、解码和验证。相关工作在第5节中讨论。第6节包含我们的结论，并讨论了未来的工作。2 Java字节码JVML指令在两个位置读取和存储中间值：操作数堆栈和局部变量。这些位置的类型是低敏感性的，因为同一个堆栈单元或局部变量可以在程序执行期间保存不同类型的值验证确保位置的使用一致，并且中间值总是使用原始写入的相同类型读回。验证也保证了控制流的安全性，但这是一项相对微不足道的任务。相反，验证数据流是否类型良好则相当复杂。JVM字节码验证器[13，14，23]使用迭代数据流分析和JVML指令的抽象解释器。与JVM不同，用于验证的抽象解释器的堆栈和局部变量存储类型，而不是值。从验证器的角度来看，JVM指令是对类型而不是值执行的操作。JVML验证工作在方法级别。如果每个方法都是可验证的，那么整个程序都是可验证的。在本文的其余部分，我们交替使用程序和方法，并且只考虑不包含子例程构造的JVML子集。在处理Java字节码时，子例程是一个非常复杂的问题[8，11，18，21]，并且已经被证明是一种非常有效的减少代码大小的方法[7]。当前Java版本1.5中的编译器不再生成子例程。我们的原型实现通过将子例程内联到调用方法2的主体中来解决子例程的罕见出现。2我们已经研究了许多字节码应用程序，包括Eclipse框架，dif-88A. Gal等人/理论计算机科学电子笔记141（2005）853静态单一赋值形式传统的JVML字节码不符合SSA格式。值可以写入局部变量或堆栈单元，并且不需要为每个新定义使用新的局部变量或堆栈单元然而，也没有什么可以阻止代码生产者发出Java字节码程序，其中值保存在局部变量中，每个定义都被分配了自己的局部变量。在本节中，我们将描述一个简单的转换，该转换采用常规Java字节码并将其转换为一种形式，该形式允许代码消费者推断SSA形式，即使代码仍然作为纯JVML字节码传输为了确保代码消费者不仅可以提取SSA信息，而且还可以验证使用它是安全的，我们还通过重新排列基本块的顺序来编码支配树信息使用支配者树，我们可以在线性时间和单次扫描中遍历代码和类型检查用途及其3.1静态单一分配表单大多数JVML指令使用堆栈来访问操作数和存储计算值。为了允许代码消费者推断这些指令的静态单一分配形式，我们用局部变量访问指令（如iload和istore）封装它们。例如，表达式a=b+cd负荷1// biload 2// c加载3// d伊穆尔//c * diadd// b + c * d在本例中，b、c和d分别从局部变量1、2和3中读取。将c和d相乘并将结果加到a后，最终值留在堆栈上。在我们丰富的传输格式中，我们使用Shaylor在转换后的代码中，每个指令直接从局部变量读取其参数，并且堆栈在指令之间始终为空Java API和SPEC基准测试。在大约540万条指令中，我们只发现0.24%是在子程序中一个子程序的平均大小是7条指令，它只被调用2次。A. Gal等人/理论计算机科学电子笔记141（2005）8589iload 2//c加载3//d伊穆尔//c * diStore 5//temp = c * d负荷1//biload 5//templateiadd//b + tempiStore 4//a = b + c * d不是通过堆栈传递c++d的临时结果，而是将其分配给一个新的局部变量5，以确保堆栈在imul和iadd之间为空。实际上，我们将基于堆栈的JVML表示转换成SSA形式的基于寄存器的表示。传统的JVM显然会为这两个代码片段计算出相同的结果，尽管由于代码更冗长，完成转换后的片段的操作需要稍微多花一些时间然而，一个有意识的JVM可以很容易地检测到每个局部变量只被赋值一次，从而跳过重命名阶段，直接获得代码的SSA形式通过将程序转换为基于寄存器的格式，许多JVML指令变得过时。JVML指令集可以分为两类指令：核心指令和数据流指令。核心指令对存储在操作数栈上的值进行操作，而诸如dup、dup 2、iload x和istore x的数据流指令仅通过操纵操作数栈的状态以及在操作数栈和变量之间交换值来促进核心指令之间的值的数据流。值由核心指令产生，并可由其他核心指令消耗。在值的生存期内，它可以驻留在操作数堆栈上值可以同时驻留在多个位置。数据流指令既不产生也不消耗值，而只是在堆栈位置和变量之间传输值[9，10]。在转换过程中，代码生成器消除了所有数据流指令，并将其替换为对SSA变量的直接引用。下面的代码片段计算22：iconst_2dupimulistore 1转换后，由iconst 2生成的值存储在局部变量2中。 dup指令被删除，imul指令被转换为直接指向定义其操作数的指令，这是为iconst2新引入的istore 2指令。任何将来对结果的使用都被替换为对局部变量1的直接引用，该局部变量保存乘法的结果：90A. Gal等人/理论计算机科学电子笔记141（2005）85iconst_2istore 2iload 2iload 2imulistore 1在转换之后，除了封装核心指令的加载/存储指令之外，代码不包含任何更多的数据流指令。3.2控制流合并除了单赋值性质外，φ-指令是SSA形式最重要的特征φ指令用于沿着多个输入控制流边缘合并定义JVML没有φ-指令，因此我们需要一种替代的方式来表示它们。添加新指令不是一个选项，因为我们希望保持向后兼容性。相反，我们使用JVM操作数堆栈在控制流合并时在基本块之间传递值φ-操作数在每个基本块的末尾被推送到堆栈上，该基本块以具有多个前导块的基本块为目标，并且每个这样的合并块从堆栈中弹出φ因此，φ-指令l3=φ（l1，l2），它连接局部变量1和2的定义，并将结果留在局部变量3中，表示为：加载1转到L1...加载2转到L1...第一层：iStore 3这种方法适用于常规的控制流边缘，但不能应用于异常处理程序。异常处理程序在调用时自动清除堆栈而是使用临时局部变量将φ操作数从常规代码传递到异常处理程序。为了确保代码消费者可以容易地识别异常边缘的φ操作数，可以触发异常的每个指令都是然后是相应的局部变量加载和存储指令，以准备潜在的异常退出：A. Gal等人/理论计算机科学电子笔记141（2005）8591负荷1iStore 9iload 2iStore 10负荷1iload 2idivistore 3在这里，局部变量9和10被用作临时变量来保存用于保护idiv指令的异常处理程序的φ操作对于传统的JVML，这种表示在解释过程中会产生轻微的运行时开销。优化JIT编译器可能会检测未使用的变量并消除额外的istore指令（死代码消除）。为了评估转换对字节码程序大小的影响，我们使用编码器将670个类从JDK 1.4.2转换为SSA-可推断形式。平均而言，班级人数增加了30%。4支配者信息为了构造程序的SSA表单，代码消费者需要访问支配者信息。这对于SSA形式的JVML字节码的线性时间验证也是需要的虽然存在多种方法来从控制流图中有效地计算支配者树[12，3，4]，但我们的方法使用了这样一个事实，即代码生产者已经拥有支配者树，或者可以很容易地从控制流图中获得它。支配者树然后被用来重新排列基本块，使得代码使用者可以重新构造支配者树，而不是从头开始计算。我们首先描述从基本块的排序中解码支配关系解码过程本质上决定了编码器必须如何排列基本块。然后，第4.2节描述了实际编码基本块的过程，第4.3节显示了原型的一些性能测量，第4.4节介绍了如何验证计算的支配者信息。4.1解码支配者信息解码器仅从它所接收的程序中可用的信息来构造支配者树-编码器所计算的基本块的从接收到的基本块流中解码支配者信息分两个阶段工作首先，构造支配树的初始近似。第二阶段纠正错误和丢失的边缘。为了限制问题空间，出于效率的原因，我们限制了92A. Gal等人/理论计算机科学电子笔记141（2005）85因为在第一阶段中计算的近似可能偏离正确的支配关系。由于直接支配者关系形成一棵树，每个节点只有一个前任，但可能有几个继任者。该性质可用于在第二阶段中当向上移动近似中错误放置的节点时，始终清楚要遵循哪条边相反，当向下移动节点时，第二阶段必须确定选择哪个边-这将需要访问通过这些边可到达的子树。在我们更详细地描述这两个阶段之前，我们注意到一个节点、它的前任和它的直接支配者之间的特殊关系。如果d是n的直接支配者，则n的每个前趋者要么是d，要么被d支配。定理1设G是一个结点为N，边为E <$N × N的图. 让S是G的入口结点，DomN×N是G的直接支配子G中具有通常表示（n1，n2）的节点的关系∈如果n为1，是n 2的直接支配者。dominates：N→ 2 N将一个节点n映射到N 中 所有被n支配的节点。则以下语句是等价物：• （n1，n2）∈DOM• <$n∈N，其中n/=n1，（n，n2）∈E：n∈domains（n1）证据对于节点n1和n2之间的边，我们写n1→n2，对于（可能是空的）路径n1~n2。我们用间接法来证明这两个方向-是的假设存在一个节点n∈N，其中nn1，（n，n2），（n1，n2）∈E但n/∈优于（n1）. 那么既然n1不支配n，存在一条不经过n1的路Sn，并且由于（n，n2）∈E，存在一条从S到n2的不经过n1的路Sn→n2.因此，（n1，n2）/∈DOM. - 是的设n1不是n2的直接支配者，即存在一条不经过n1的路S~n2。假设这条路径的最后一步是边（n，n2）nn2。 由于路径不经过n1，所以n是n2不直接被n1所支配。Q这些事实直接导致了在解码器的第一阶段计算支配者树的近似值的方法（图1）。解码器的输入是基本块的序列解码器自下而上构建支配者树，通过总是在已经插入的节点之上插入节点机顶盒包含当前支配者树中尚未被分配直接支配者的所有节点。每当一个基本A. Gal等人/理论计算机科学电子笔记141（2005）8593decode（）//第一top=0读下一个基本块bbwhile（可用的基本块）domains（bb）={bb}对于所有在top中的节点n∈sucs（bb），将n加到domains（bb），将（bb，n）加到DOM从顶部移除n读下一个基本块bb将n加到domains（bb）上，并将n//第二将所有节点n附加到工作列表中，这些节点具有不是其IDOM的前驱节点，而（工作列表不为空）bb=worklist.removeFirst（）在支配者树中找到bb所有bb重新计算bb和n1之间支配者树中所有节点的支配设置bb将所有节点n附加到工作列表，这些节点由bb支配，并且具有不是其IDOMFig. 1.基本块流的解码算法。第一阶段构造一个近似的支配者树，而第二阶段在支配者树中向上移动节点。我们使用IDOM作为直接支配者的缩写。当读取块N时，解码器确定其控制流后继者。如果置顶包含n的后继者s，则在n和s之间插入支配者边缘，并且从置顶移除s。最后，将n添加到top。由于定理1，s的直接支配子是n或支配n。因此，s被插入低于它的直接支配者，我们在第二阶段只通过向上移动节点来利用它第二阶段跟踪近似中具有不是其直接支配者的控制流前驱的所有节点根据定理1，它们的每一个控制流的前一个必须被它们的直接支配者支配 对于每一个这样的节点n，解码器向上走，近似的支配树，直到它找到一个节点n1，支配所有的n然后，解码器将n1设置为n的直接支配者，并检查n的每个后继s是否仍然满足定理1每个s都有一个不受s的支配者支配的前导者，这个前导者被添加到工作列表中。这是必要的，因为移动n可能会改变s的信息。4.2编码支配者信息编码器负责促进上述解码过程为了确保一个节点在近似中被放置在它的前一个节点之下，它必须被编码在前一个节点之前。根据定理1，这也确保每个节点被放置在其直接支配者之下。为了构造编码，编码器采用控件的子图94A. Gal等人/理论计算机科学电子笔记141（2005）85图二.左图是一个示例程序的组合控制流图和支配者图。实线边是控制流边，虚线边是支配流边.右图显示了实际用于构造编码的子图。encode（）<$n，nJ∈N且（n，nJ）∈E<$（n，nJ）/∈DOM：OUT（n）+ +;IN（nJ）++;通过递增IN（n）和递减OUT（n）对N进行排序，将每个节点n放置在其直接支配者<$n，nJ∈N，其中（n，nJ）∈DOM<$（n，nJ）/∈E：把nJ放在nJJ之前，其中nJJ∈domains（n）<$（nJJ，nJ）∈E图三.在代码生成器中计算基本块编码的算法。 G是一个结点为N，边为E<$N×N的图. DomN×N是G中的直接支配关系，dominates（n）给出被n支配的节点的集合。第一个阶段计算由控制流边连接但不是由控制流边连接的节点的输入和输出边的数量。支配优势使用这些数字，节点被初始排序。第二阶段将所有节点置于其直接支配者之前。最后阶段确保如果在直接支配者和节点之间没有控制流边缘，则节点被进一步移动到前面图作为输入。这个子图恰好包含控制流边（n1，n2），对于这些边，n1不支配n2.图2显示了一个示例程序的控制流图根据输入和输出边的数量，编码器确定基本块的初始编码节点基于较少的传入边和较多的传出边进行排序这种启发式的动机是第一个解码阶段如何将边缘插入近似的支配树。每当找到未处理节点n的直接前驱p时，将支配边（p，n）添加到解码树不是支配边的每个控制流边（n1，n2）将导致近似支配者树中的错误边。我们可以通过首先对n1进行编码来避免这种插入，这样第一个相位中就不会有n2。123468597234685719A. Gal等人/理论计算机科学电子笔记141（2005）8595top. 对于示例程序，这给出了[6、 5、 3、 4、 9、 7、 2、 8、 1]然而，如第4.1节所述，解码器有两个属性，对所选择的编码施加额外的限制首先，由于代码消费者处的解码器只能向上移动节点，因此每个节点必须在其直接支配者之前被编码对于示例程序的初始编码因此，编码器从后向前遍历初始编码，并将节点向前移动，直到它们在其支配者之前被编码对于示例程序，这将导致编码[6、 5、 7、 4、 3、 9、 2、 8、 1]如上所示，在阶段1期间，解码器跟踪尚未解码支配者的节点。当到达入口节点时，所有尚未连接的节点虽然这种方法适用于直接支配者和节点之间有直接边的节点，但必须特别注意不存在这种边的节点。在示例图中，（3，7）是唯一一对通过支配树边而不是通过CFG边连接的节点。为了确保解码器将7放置在其直接支配者3之下，7必须在从其支配者的最短路径上的其控制流前导之前被编码。例如，节点7必须在节点6之前编码这导致最终编码[7、 6、 5、 4、 3、 9、 8、 2、 1]4.3性能这一节展示了示例程序的解码是如何工作的，并报告了我们的原型实现。如上所示，图2中示例程序的编码是[7、 6、 5、 4、 3、 9、 8、 2、 1]图4显示了在解码器的第一阶段（图1）计算的信息可以看出，除了2个支配者边缘之外的所有支配者边缘都已被正确解码第二阶段从工作列表（2， 7， 8）开始，一个不是他们的直接统治者的前任。对于节点2，支配者树中唯一的前趋者是支配所有其他节点的入口节点1，因此不采取任何动作对于节点7，解码器选择节点3，因为它支配节点5和6，7的前身因此，直接支配者7被设置为3，将不正确的边的数量减少到1。 因为7没有96A. Gal等人/理论计算机科学电子笔记141（2005）85节点读CFG萨奇顶部插入边缘72∅6 七、八7（六、七）57645第五、六条（四、五）3 四、六四、六（3、 4）、（3、 6）9389三、（8， 9）123468597见图4。编码的示例程序的解码和计算的支配树的第一近似。实边是计算的支配者树中缺失的边，即没有被正确解码。子节点，则不会向工作列表添加新节点对于下一个节点（8），解码器选择节点1作为直接支配者，因为它支配其前任1，2和6。8的唯一子节点不需要向工作列表添加新节点，因此第二阶段使用正确的支配者树完成。我们已经测量了随机生成的可约和不可约图上的该算法的原型实现的性能图5比较了构建支配树的时间与[12]中算法的实现右边的图显示了在解码步骤的第二阶段中，当节点在近似支配树中向上移动时所需的迭代次数。迭代次数几乎与节点数成线性关系。4.4验证即使有意识的代码消费者识别所有这些代码模式并构造基于SSA的中间表示，它也需要在IR安全地用于代码优化之前验证代码实际上是有效的SSA形式。为此，代码消费者必须验证以下三个属性：• 在SSA形式中，变量只被指定一次• 变量在首次使用之前就被定义了• 变量以类型安全的方式使用A. Gal等人/理论计算机科学电子笔记141（2005）8597Lengauer Tarjan译码器605040302010160014001200100080060040020000 20040060080010001200节点140000200400600800100012001400节点图五.解码阶段的原型实现与Lengauer和Tarjan的支配者算法实现的比较[12]。 左图显示了为一个随机构造的具有x个节点的图构造支配树所需的时间。右图示出了在解码期间执行的迭代次数。由于在将节点放入工作列表中时使用了选择启发式，因此该算法在每次迭代中执行转换。虚线代表平等。测试是在一台2.66Ghz和512MB RAM的Pentium 4上进行的。由于直接对SSA表示执行类型检查，因此基于数据流分析的传统字节码验证已经过时，并且如果发现SSA表示是安全的，则不再执行有趣的是，代码消费者不需要验证φ指令的适当位置虽然放置太少或太多的φ-指令会导致程序无法计算有意义的结果，但只要每个φ-指令都是类型安全的（我们会检查），它们就永远不会导致不安全的代码每个局部变量只被赋值一次是微不足道的。这是程序加载后代码消费者执行的第一个操作传统的JVM使用迭代的数据流分析来验证类型安全和正确的变量初始化.虽然同样的方法可以用来验证代码确实是SSA格式的，但直接以SSA形式执行验证要优雅得多，也更有效[9，10]。为此，我们必须首先从代码中恢复支配者信息，然后以支配者树的顺序遍历代码，以使用相应的定义进行类型检查。解码器不保证结果图是程序的正确支配树。恶意程序可以通过重新排列基本块来构建，使代码消费者相信某些基本块正在支配其他基本块，而实际上并非如此。如果代码消费者盲目地信任基本块排序，那么它就很容易受到这种攻击。幸运的是，我们可以很容易地验证所获得的支配者信息，通过改写的支配者树问题作为一个数据流方程。时间[ms]迭代/转换7098A. Gal等人/理论计算机科学电子笔记141（2005）85DOM（S）={S}⎧ ⎫⎨DOM（n）=⎩p∈preds（n）⎬DOM（p）⎭{n}图六、具有节点N、边E和起始节点的图G的DOM集的数据流方程S.DOM（b）定义为包含支配的每个基本块的集合。B. 代替使用迭代数据流分析，我们根据解码器产生的支配树来初始化每个集合DOM（b如果代码以可解码的基本块序列传输，则数据流方程将在一次迭代中得到满足，确认解码的支配者树。如果在一次迭代后它们不满足，代码消费者会退回到使用类似[3，12]的方法从头开始计算支配者树的标准解决方案。一旦我们恢复了支配者树，我们就以支配者树的顺序遍历代码，并确定每个变量定义的不同类型然后将该类型与相应的用途相匹配。由于变量只被赋值一次，并且我们首先访问控制块，因此定义将在使用它们之前自动出现。如果解码器遇到一个缺失的定义，代码将被拒绝。此外，每个变量，除了由φ-指令定义的变量，有一个唯一的类型，因为它只被分配一次（SSA）。这大大简化了类型检查。在遍历代码时，记录每个定义的类型，对于每次使用，请查阅此表，以验证定义和使用是否具有兼容的类型。正如我们上面讨论的，程序不包含任何更多的数据流指令，如dup。其余的核心指令是自类型的，即。任何消耗的操作数的期望类型唯一的例外是φ指令，其返回类型必须通过对其操作数的类型推断来基于SSA的字节码验证的更详细描述可以在[9，10]中找到。5相关工作在控制流图中寻找支配树是程序分析和转换的基本问题，例如：静态单一赋值表单构造。虽然已经提出了具有不同平均复杂度和最坏情况复杂度的多个算法[15，12，3，4]，但是所有这些算法都在A. Gal等人/理论计算机科学电子笔记141（2005）8599控制流程图上的单相基于这些先前的工作，我们已经分为两个阶段的建设在本文中描述。静态单一分配形式在当前大多数基于JIT的高性能虚拟机中用作中间表示。然而，SSA很少用作传输格式。SafeTSA [1]是一种固有安全的移动代码表示格式，使用SSA作为编码和传输格式。这还有一个额外的好处，即消除了对验证的需要，因为移动代码是以自一致的格式存储的，除了格式良好和类型良好的程序之外，它不能表示任何东西这是以放弃现有的Java类文件格式为代价的，这并不总是可以接受的。我们的方法和Safe-TSA有一个共同点，它们都使代码以SSA形式提供给JIT，这可以用来加速代码生成。使用基于SSA的表示来编译字节码的一个例子是Marmot [6]，这是一个研究高级编程语言实现的研究平台我们工作的主要区别是Marmot，像许多其他类似的框架一样，只关注代码消费者端，而不生成代码生产者端的提示，如程序重新排序。用代码消费者可以检查的证明来注释移动代码是一个很好的探索领域。证明携带代码（PCC）[17，16]通过减轻代码消费者验证代码的负担来解决这个问题相反，代码生产者根据公共安全策略计算验证条件，并证明它对程序是真的此证明与代码一起发送给代码使用者在接收时，代码消费者重新计算验证条件，然后可以检查所附证明是否确实建立了代码生产者所声称的验证条件就像使用SSA作为传输格式一样，随代码一起发送附加的证明信息需要放弃原始的Java字节码格式。分裂验证器方法[22]与PCC非常相似。它用数据流分析的固定点注释JVML，否则在类加载期间由JVM执行对于带注释的类文件，验证被简化为确认注释确实是一个有效的固定点，这可以在接近线性的时间内完成这个想法已经被用于我们的方法中，用于验证计算的支配树。否则，拆分验证器就像PCC一样，需要随代码提供额外的注释。100A. Gal等人/理论计算机科学电子笔记141（2005）856结论和今后的工作我们已经提出了一种新的方法来传输SSA信息在Java字节码通过结构化注释：而不是引入新的字节码指令或添加显式注释，字节码的重新排列和转换，以允许代码消费者推断SSA形式，而实际上不必计算支配树和迭代的优势边界。代码使用者只需运行一些简单的测试，以确保编码的信息有效。代码使用者不仅可以避免执行这些分析，而且还可以使用直接在SSA表示上操作的更有效的类型检查方法。验证不是最差情况下的二次数据流分析，而是在线性时间内运行，并对程序进行单次扫描。所介绍的研究正在进行中。虽然我们已经实现了一个原型编码器和解码器系统，但解码器并没有完全与虚拟机集成，因此我们目前没有报告任何性能数据从以前的工作[9]中，我们知道基于SSA的验证比基于传统数据流分析的验证平均快约15%。不考虑φ指令布局的支配树和迭代支配边界的计算时间，加速比为45%。我们希望在验证时间上实现类似的减少，并且增加的好处是SSA形式可以立即用于JIT编译器，而无需任何额外的计算。就未来的工作而言，我们目前正在对我们的方法对遗留VM的影响进行当代码在遗留VM上执行时，可以预期会有一定的速度减慢。转换最显著的影响是代码大小的增加虽然这对解释有显著的负面影响，但我们预计它对JIT编译的代码的影响有限所提出的结构注释的第二个副作用是每个方法使用的局部变量的数量显著增加与代码大小的增加相比，这似乎是一个很好的代码生成，特别是当动态编译器使用简单的寄存器分配器时。引用[1] Amme，W.，N. Dalton，J. von Ronne和M. Franz，SafeTSA：基于静态单一分配形式的类型安全和可重命名安全的移动代码表示，在：ACM SIGPLAN编程语言设计和实现会议论文集，2001年，pp.137[2] 比 拉 尔 迪 湾 和 K. Pingali ， Algorithms for Computing the Static Single Assignment Form ，Journal of the ACM（JACM）50（2003），pp. 375-425A. Gal等人/理论计算机科学电子笔记141（2005）85101[3] Buchsbaum，A. L.，H. Kaplan，A.罗杰斯和J. R. Westbrook，A new，simpler linear-timedominators algorithm ， ACM Transactions on Programming Languages and Systems20（1998），pp. 公元1265-1296年。[4] 库珀，K. D、T.哈维和K. Kennedy，A Simple，Fast Dominance Algorithm，Software PracticeExperience4（2001）. 1-10。[5] 塞隆河，J. Ferrante，B. K.罗森，M。N. Wegman和F. K. Zadeck，Eccently Computing StaticSingle Assignment Form and the Control Dependence Graph ， ACM Transactions onProgramming Languages and Systems，1991，pp.451-490.[6] 菲 茨 杰 拉 德 ， R.T. B. Knoblock ， E. 鲁 夫 湾 Steensgaard 和 D.Tarditi ， Marmot ： AnOptimizing Compiler for Java，Software-Practice and Experience30（2000 ）， pp.199-232.[7] Freund，S.N.，Java字节码子程序的成本和好处，在：OOPSLA的Java研讨会正式基础会议记录，1998年。[8] Freund，S. N.和J. C. Mitchell，Java字节码子例程和异常的规范和验证，技术报告CS-TN-99-91，斯坦福大学（1999）。[9] Gal，A.，C. W. Probst和M. Franz，Proofng：Eccient SSA-based Java Verification，TechnicalReport 04-10，University of California，Irvine，School of Information and Computer Science（2004）.[10] Gal，A.，C. W. Probst和M. Franz，Integrated Java Bytecode Verification，收录于：第一届面向对象语言抽象解释国际研讨会论文集，2005年。[11] Hagiya，M.和A. Tozawa，关于Java虚拟机子程序数据流分析的一种新方法，在：G。Levi，editor，Static Analysis，5th International Symposium，SAS十七比三十二[12] Lengauer ， T. 和 R. E. Tarjan ， A Fast Algorithm for Finding dominators in a multinationalgraph，Transactions of Programming Languages and Systems（TOPLAS）1（1979），pp. 121-141[13] Leroy ， X. ， Java Bytecode Verification ： Algorithms and Formalizations ， Journal ofAutomated Reasoning30（2003）. 235-269。[14] Lindholm，T.和F.Yellin，[15] Lowry，E.和C.W. 目标代码优化，ACM通信12（1971），pp. 13比22[16] Necula 、 G. C. 的 方 法 ， Proof-carrying code ， in ： Proceedings of the 24th ACM SIGPLANSymposium on Principles of Programming Languages（POPL），Paris，France，1997.[17] Necula、G.C. 和p.Lee，Safe Kernel Extensions Without Run-Time Checking，in：USENIX，nd第二届操作系统设计与实现研讨会论文集（Proceedings（OSDI229-243[18] 奥卡拉汉河 Java字节码子程序的简单、全面的类型系统，在：第26届 ACM SIGPLAN程序设计语言原理研讨会论文集（POPL），圣安东尼奥，得克萨斯州，1999年，页. 70比78[19] Shaylor，N.，A Just-in-Time Quancher for Memory-Constrained Low-Power Devices，in：Proceedings of the 2nd Java Virtual Machine Research and Technology Symposium （JVM-02）（2002）. 119比126[20] Sreedhar，V. C.和G. R. Gao，A Linear Time Algorithm for Placing φ-nodes，in：Proceedings ofnd22 ACM SIGPLAN Symposium on Principles of Programming Languages，旧金山，加利福尼亚州，1995年，pp. 62比73[21] 斯塔塔河和M. Abadi，A Type System for Java Bytecode Subroutines，ACM Transactions on102A. Gal等人/理论计算机科学电子笔记141（2005）85Programming Languages and Systems21（1999）.90-137.A. Gal等人/理论计算机科学电子笔记141（2005）85103[22] SunMicrosystems， JSR-000139连接有限设备配置1.1。http://www.jcp.org/en/jsr/detail? id=139。[23] Yellin，F.，Java中的低级安全性，369-380.