基于堆栈的代码优化的类型系统

理论计算机科学电子笔记190（2007）103-119www.elsevier.com/locate/entcs优化基于堆栈的代码的类型系统Ando Saabas和Tarmo Uustalu1塔林理工大学控制论研究所，爱沙尼亚塔林，Akadeemiatee 21，EE-12618摘要我们给出了一个统一的类型系统的帐户的一些优化和底层分析字节码类堆栈为基础的低级语言，包括分析可靠性证明和最强的分析（主类型推断）算法。具体来说，我们处理死存储指令，加载弹出对，复制加载指令，存储加载对。加载-弹出对和存储-加载对消除优化建立在双向分析之上，有助于正确消除跨越基本块边界的指令对因此，不需要关于输入代码的假设（它不需要是高级源程序的编译形式，堆栈在基本块边界不需要是空的，甚至不需要在分析之前检查它的安全性）。可靠性证明和最强分析算法是简单和统一的。关键词：基于堆栈的低级语言，数据流分析，优化，类型系统，认证，双向分析，优化可靠性1介绍流行的Java编译器，如Sun另一方面，提前优化仍然很重要，特别是在移动设备的环境中，即时编译器不如桌面或服务器上的强大[4]并且分布式二进制文件的大小应该尽可能小直接优化字节码解决了高级或中级程序优化中不存在的挑战。可以概述以下原因• 表达式和语句不明确。在一个简单的方法中，许多优化都需要从指令重构表达式树1电子邮件：{ando| tarmo}@ cs.ioc.ee1571-0661 © 2007由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2007.02.063104A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103• 相关指令不一定彼此相邻。 一个值可以放在堆栈上，一些其他的指令执行，然后只有这个值使用和弹出。 这意味着相关指令，例如那些把一个值放在堆栈上，那些使用它的值可以相距任意远。 需要在分析过程中找到它们之间的联系• 一个表达式可以跨越几个不同的基本块。Java虚拟机规范在控制流连接处不要求零堆栈深度，因此在基本块中使用的表达式可以在其他基本块中部分计算。在过程内优化领域所做的大多数工作都采用了只优化基本块内代码的方法[7，9，19，13]。这大概有两个主要原因。首先，跨基本块边界分析字节码比只分析基本块内部的代码要微妙得多。 其次，在编译代码中，跨越基本块的表达式很少（尽管它们确实出现，例如， Java的？表达式）。 一些著名的字节码优化器，如Soot[17]，使用一种方法，首先将类文件转换为三地址中间表示，使用标准技术进行优化，然后转换回字节码。在本文中，我们给出了统一的形式声明性描述，可靠性证明和（完整版）算法的一些优化和他们的底层分析一个简单的，字节码一样的堆栈为基础的低级（非结构化）语言。 我们用于此目的的工具是具有transforma的类型系统，作用成分。这结合了几条工作线，在下面的相关工作部分进行了审查。本文针对死存储、加载-弹出对、重复加载和存储-加载对等典型的堆栈代码优化情况进行了分析和优化。 它们被设计用于处理一般代码，即， 他们不对它的形式做任何假设。代码不需要是高级程序的编译版本。此外，分析和优化不是以任何方式“内部基本块”。相反，它们跨越基本块边界工作，并且不要求堆栈在这些边界处为空。我们表明，优化修改跨基本块边界的指令对需要双向分析，因为信息必须在分析过程中向前和向后传播。 令人高兴的是，事实证明，这种普遍性并没有带来对于特定行为良好形式的代码或编译代码的任何重大开销类型系统方法有几个好处。分析和优化的类型系统化描述的一个突出特点是，它们提供了一种区分，即什么是有效分析（系统规则）的声明性描述，以及如何计算最强的分析（主要类型推断）。 基于关系方法，它们还可以很好地说明和显示优化的合理性。此外，分析类型派生（类型注释）可以用作携带证明的代码中的优化证书[12]类似的场景，这是正式方法相对于非正式数学方法的优势。A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103105∈∈∈∈}∈→{∈ P×|∀∈ ∧∈ ⊃{∈|∈}∈本文的结构如下。在本节的其余部分，我们将确定本文的对象语言。第2节专门介绍死代码消除，分为两个阶段，死存储消除，然后是加载弹出对消除。在本节中，我们还介绍了用于数据流分析和优化的一般类型系统方法，专门用于非结构化低级语言，以及如何在这种方法中陈述和证明可靠性。我们还证明，加载弹出对消除一般的代码必须是双向的，并表明这种分析实际上是一个相当温和的推广更习惯的单向性分析。在第3节中，我们对外挂-荷载组合重复同样的方案。第四节对相关工作进行了评述，第五节对本文的结论进行了总结。由于篇幅的原因，我们只给出了最强的分析算法在完整版的文件。1.1客体语言我们的研究对象是一个简单的基于操作数栈的低级语言。语言语法的构建块是标签lLabel= dfN（自然数）和指令instrInstr。我们假设有一组可数的程序变量（寄存器）xVar。语言的指令由语法instr：：= load x|存储x|推送n|添加|......这是什么？ |流行|DUP|后藤|gotoF l一段代码c代码是一组有限的带标签的指令，即，一组标签和指令对，其中没有标签可以标记两个不同的指令：Code = dfcfin（LabelInstr）l，instr，instr J。（l，instr）c（l，instrJ）cinstr=instrJ.换句话说，一段代码是从标签到指令的部分功能一段代码的域是对部分函数的支持：dom（c）= dflLabel instr。（l，instr）c. 如果l为dom（c），我们将c l写为l在c中标记的唯一指令。该语言的小步（归约）语义是根据状态给出的，这些状态是pc值（标签），堆栈状态和存储的三元组：State=dfLabel×Stack×Store。 堆栈状态是整数和布尔值的列表：zs∈Stack=df （Z+B） 存储是变量到整数的映射：存储= df变量Z.代码段的标准小步操作语义通过索引单步归约关系→ ∈Code→ P（State×State）给出，定义如下：图1中的规则。相关的多步归约关系→E1被定义为它的自反传递闭包。2死代码消除标准的死代码消除优化从程序中删除那些不影响程序结束时活动变量值的语句。在高级程序或中间（基于表达式的低级）代码中，优化在活变量分析之后执行是微不足道的，通常涉及106A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103（l，storex）∈cn∈ Zstore（l，loadx）∈ cloadc<$（l，n：：zs，σ）→（l+ 1，zs，σ[x<$→n]）c <$（l，zs，σ）→（l+ 1，σ（x）：：zs，σ）（l，pushn）∈ cpush（l，add）∈cn0，n1∈ Z加c<$（l，zs，σ）→（l+1，n：：zs，σ）c<$（l，n0：：n1：：zs，σ）→（l+1，n0+n1：：zs，σ）（l，pop）∈cpop（l，dup）∈cdupc<$（l，z：：zs，σ）→（l+1，zs，σ）c<$（l，z：：zs，σ）→（l+1，z：：z：：zs，σ）（l，gotom）∈cgotoc<$（l，zs，σ）→（m，zs，σ）（l，gotoFm）∈cgotoFtt（l，gotoFm）∈cgotoF<$c<$（l，tt：：zs，σ）→（l+ 1，zs，σ） c<$（l，tt：：zs，σ）→（m，zs，σ）Fig. 1.小步语义规则删除赋值后立即死亡的变量。在基于堆栈的代码中，表达式不是显式的（相关指令也不一定相邻），删除死代码并不那么简单。例如，程序x：=z+y可以编译成0，加载z 1 ， 加载 y 2 ，添加3、店铺x四，如果分析表明x是死的，那么在中间代码中，赋值 x可以删除。然而，在基于堆栈的代码中，不仅第3行上的存储指令，而且第0-2行也应该被删除。将基于堆栈的代码优化与中间语言中的优化分开的另一个问题是语句和表达式可以跨越几个基本块（或者，换句话说，基本块不一定进入空堆栈或从空堆栈退出）。这种代码的一个简单示例是以下基于堆栈的低级别等效代码ifbthenx：=zelsey：=z，其中z仅加载一次，并且在两个分支中，仅应用store指令0，loadz1，loadb2，gotoF5 3，storex 4，goto 6 5，storey 6，如果活变量分析显示变量x是死的，则不能简单地移除第3行的存储指令，因为如果采用真分支，则变量x的未赋值将在退出分支后留在栈上。 第0行上的加载指令也不能被删除，因为当它被死存储使用时，它也被假分支中的活存储使用。 在这种情况下，如果没有移动指令，最好的办法是用弹出命令替换指令3我们分两个阶段来消除死代码。在第一阶段（我们称之为死存储消除），所有死存储，添加和条件跳转指令都被替换为弹出指令（以便优化不会在任何标签处改变堆栈高度）基于标准活变量分析的模拟。在第二阶段中，如果可能的话，消除具有相应的先前加载/推入指令的弹出指令，并且注意保持栈高度A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103107≤≤►►∈∈→→联系我们联系我们∈∗→∈在这种转变之后。这两种分析都是完全通用的，不对字节码的形式做任何假设，并且可以跨越基本的块边界。2.1死悬挂物消除我们基于堆栈的语言的活变量分析类似于表达式语言的活变量分析，除了堆栈也被考虑在内。这意味着除了变量可能是活的或肯定是死的之外，堆栈位置也可能是活的或肯定是死的。例如，如果我们知道在执行storex指令之后，变量x立即死亡，那么我们也知道在执行之前栈顶是死的，这意味着无论栈顶持有什么值，它都不会影响活动变量的值。我们描述的分析和优化的类型系统。类型语言和子类型化形式化了分析的底层偏序集，而类型化定义了给定代码段的有效分析（独立于确定特定算法以找到满足某些给定条件的最强分析）。对于实时变量分析，代码类型CodeType是将标签类型分配给每个标签：CodeType=df（Label LabelType）。标签类型τLabelType是一对堆栈和存储类型或特殊类型对于“任何状态”：LabelType = df（StackType StoreType）+。堆栈类型esStackType和存储类型dStoreType分别是列表。对位置类型为“可能存在”和“肯定死亡”的变量的赋值：StackType = df LocType，StoreType = df Var LocType，LocType = df L，D。我们将用简写形式l表示（l）。子类型和类型规则如图2所示。在本文的所有类型系统中，子类型判断表示第一个标签类型是第二个标签类型的子类型（即， 更强）。 同样，子类型判断拉吉表示第一个代码类型是另一个的子类型类型判断<$（l，instr）表示标记指令（l，instr）允许类型<$，即，该分析是对该特定标记指令的有效分析（独立于其可能出现的任何可能的代码上下文）。键入判断是指代码c键入了n，即，这是对C作为整体的有效分析（忽略比特）（l，instrJ）和<$c，j;它们与优化通过分析得出结论）。我们特定分析的类型规则只允许变量或堆栈位置在有效代码类型中的标签l处标记为“死”，如果不存在从l到标签l j的路径，否则必须标记为栈顶的一个典型的有用用法是将其存储在后继标签处标记为“live”的变量栈顶和栈顶下一个位置可用于加法操作，前提是栈顶在后继标签处标记为pop使用的栈顶肯定是死的，因为它的值会丢失，并且不会删除任何位置的值。对于loadx，x的类型取决于它的类型，108A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103≤e≤e'es≤es'd（x）≤d'（x）es≤es'd≤d'L≤D e ≤e[] ≤[]e：：es ≤e'：：es'd≤d'es，d≤es'，d'τ≤sLa bé l. l≤≤l≤（L：es，d[x<$→D]）（es，d）=1+1d（x）=Lstore（，storex）<$→（，store x）l≤（es，d[x<$→d（x）（e：es，d）=l+1（，loadx）<$→（，loadx）1负载n≤（D：es，d）（es，d）=1+1d（x）=DΣ►(Æ,storex)‹→(Æ,pop)布里尔（英、西、d）（e：es，d）=101+ 1推Σ►(Æ,pushn)‹→(Æ,pushn)存储2l≤（L：：L：：es，d）（L：：es，d）=101+ 1Σ►(Æ,add)‹→(Æ,add)加入1l≤（D：：D：：es，d）（D：：es，d）=101+ 1Σ►(Æ,add)‹→(Æ,pop)加入2n≤（D：es，d）（es，d）=101+ 1Σ►(Æ,pop)‹→(Æ,pop)popl≤（（e0e1）：：es，d）（e0：：e1：：es，d）=m1+ 1Σ►(Æ,dup)‹→(Æ,dup)DUPl≤m/=100+1 l≤（L：：es，d）（es，d）=l+1mΣ►(Æ,gotoFm)‹→(Æ,gotoFm)gotoF1n≤（D：：es，d）（es，d）=101+ 1Σ►(Æ,gotoFÆ +1)‹→(Æ,pop)gotoF2=Σ►(Æ,instr)‹→(Æ,instr)非跳跃=Σ►(Æ,gotoFm)‹→(Æ,gotoFm)gotoFn∈dom（c）.Σ►(Æ,cl)‹→(Æ,c'l)Σ►c‹→c'代码图二、活变量分析和死悬挂物排除的类型系统栈顶在后继标签处的类型：如果x在后继标签处已经是活的，则它保持活的，否则如果栈顶是活的（因此需要），则x也变为活的。分析（类型推断）算法找到最弱的有效代码类型，比给定的强，使用给定的作为迭代反向传播的初始值（这对应于高级语言的最弱预类型计算）。 通常，给定的代码类型将堆栈类型设置为空，并将出口标签（域外部的后续标签）处的存储设置为“all live”。在其他地方，标签类型具有默认值类型系统还有一个转换组件，用于在有效代码类型的指导下，将给定片段转换为优化的变体。 判断<$c <$→cJ表示，基于有效的分析，c可以被优化为cJ。可以优化的指令（那些将堆栈高度降低 1)有两个规则。如果x在后置类型中被标记为“死”（即，在指令的后继标签处）。 加法指令可以如果栈顶在posttype中是“死”的，则可以进行优化。 如果跳转目标是下一个标签，则可以优化gotoF指令（因为此时没有真正的需要在栈顶使用布尔条件请注意，虽然我们还没有详细说明它们，但对加载和推送指令的优化也可以添加到类型系统中。 也就是说，如果在如果一个加载指令的栈顶是“死”的，很明显，该值不是 在任何正向路径上使用，因此放在堆栈上的具体值并不重要（只有正确的堆栈高度才重要）。 因此，可以用将正确类型的某个值放在堆栈上的最便宜的指令来替换该指令，例如，按0。为了说明分析不需要相关说明，A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103109∗我们将程序y：=x;x：=w+ 1表示为一段代码，其中赋值y：=x已移动到中间（指令3-4）。在这个例子中，我们假设变量y是活的，变量x在最后是死的的计划。分析得出以下结果。ΣÆl,cÆl,cJÆ[][y<$→D，x<$→L] 0，按 10，按 1[D][y<$→D，x<$→L]1、负载w1、负载w[D，D][y<$→D，x<$→L] 2，加2，弹出[D][y<$→D，x<$→L] 3，负载x3，负载x[L，D][y<$→D，x<$→D]4、店铺y4、店铺y[D][y<$→L，x<$→D]5，storex 5，pop[][y<$→L，x<$→D] 六六优化用pop指令替换了storex和add指令（因为在这两种情况下变量x分别是栈顶在后继者的类型中是死的）。这使堆栈保持平衡。我们的下一个分析（2.2小节）将表明，第2行和第5行的pop指令可以与第0行和第1行的指令一起删除，因为在这些转换之后堆栈的使用也将保持一致。使用关于状态的标签类型索引相似关系，可以很容易地说优化是合理的，定义如下：[][][]z∈Zz<$∈Zzzzseszsz：：zsL：：esz：：zsz∈Bz∈Bzz[][]zzzseszsz：：zsD：：esz：：zszzzszsz：：zsz：：zs<$x∈Var.d（x）=L<$σ（x）=σ<$（x）联系我们zseszs联系我们（l，zs，σ）<$（es，d）（l，zs<$，σ<$）zszs（l，zs，σ）（l，zs，σ）我们可以看到，如果两个状态在标记为“live”的位置上一致，则它们通过适当的标签类型（堆栈和存储类型）相关联。 如果堆栈高度和堆栈元素的值类型一致，则它们是相关的。从一对相关的状态中还原一段原始代码及其优化形式，这种关系。我们得到了下面的可靠性定理。定理2.1（消除死悬挂物的合理性）如果ωc<$→cJ，则：(i) 如果（l，zs，σ）<$$>（l<$，zs <$，σ<$），— 对任意（lJ，zsJ，σJ）使得cj （lJ，z sJ，σJ）和dcj（l，z s，σj）→（lJ，zsJ，σJ），— 对于一个y（lJ，zsJ，σJ）使得cj（l，zs，σj）→（lJ，zs J，σJ）存在re（lJ，z sJ，σJ）使得（lJ，z sJ，σJ）<$$>（lJ<$，z sJ<$，σ<$J）且dc<$（l，z s，σ）→（lJ，z sJ，σJ）.(ii) 如果（l，zs，σ）<$$>（l<$，zs <$，σ<$），— 对任意（lJ，zsJ，σJ）使得c<$（l，zs，σ）→<$（lJ，zsJ，σJ） 存在（lJJ （lJ<$，z sJ<$，σ<$J）和dcJ<$（l <$，z s <$，σ<$）→（lJ，z sj，σJ） 。— 对于一个y（lJ，zs J，σJ），使得cj（l，zs，σj）→c（lJ，zsJ，σJ），则re存在（lJ，zs J，σJ）使得（lJ，zsJ，σJ）<$$><$J （lJ<$，z s J<$，σ<$J）和dc<$（l，zs，σ）→（lJ，zsJ，σJ）/→。证据 部分（i）很容易通过检查以下类型/转换规则来检查：110A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103图三. 示例程序标签说明 第（二）部分是从第（一）部分通过归纳得出的，减少的顺序。Q请注意，第（i）部分说的是“保存”，而我们没有说“进展”。对于仅在图2的类型系统中键入的代码，不能保证适当的只有安全的代码才能证明进步。为了保持类型系统的简单性，我们选择省略安全组件，但它可以被集成。 替代地一个 在我们的系统中，在类型推断之前，总是可以检查一段代码的安全性2.2加载-弹出对消除该分析试图找到具有相应加载/推送指令的弹出指令并消除它们。 优化引入了一个微妙的，是目前在所有字节码转换，删除堆栈高度改变跨基本块边界的指令对。这在图3中示出（其中ls节点表示指令2的级别序列）。看看这个例子，似乎可以将loadx指令与pop一起删除。仔细的分析表明，情况并非如此：由于加载y被存储z使用，pop指令不能被删除，因为这样，在采取分支2之后，堆栈将不会平衡。这又意味着负载x不能被移除。 从这个例子中可以看出，单向分析不足以得出这样的结论：明确需要堆栈位置的信息沿着分支3从存储z向后流到加载y，但随后相同的信息沿着路径2向前流，并再次沿着路径1向后流。因此，需要双向分析，其在每个节点处向前和向后传播信息。 我们还看到，我们实际上并不是在处理对，而是一般的指令网。在适当的类型系统中，一个代码类型∈CodeType又是一个标签类型到每个 标 签 的 分 配 ： CodeType=dfLabel→LabelType 。 这 里 ， 标 签 类 型τ∈LabelType是堆栈类型或用于2一个指令序列是一个级别序列，如果这些指令引起的堆栈高度的净变化是0，并且指令不消耗在执行这些指令之前已经存在于堆栈中的任何值。A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103111e≤eJes≤esJl∈Label. 联系我们mnd≤ opte≤e[]≤[]e：：es≤eJ：：esJτ≤≤ΣÆ=mnd:: ΣÆ+1Σ►(l,storex)‹→(l,storex)店mnd：：=+1Σ►(l,loadx)‹→(l,loadx)mnd:: ΣÆ=ΣÆ+1Σ►(l,pushn)‹→(l,push(n)负载1推1opt：：密码=密码+1Σ►(l,loadx)‹→(l,nop)opt::ΣÆ=ΣÆ+1Σ►(l,pushn)‹→(l,nop)负载2推2l=mnd：：mnd：：esmnd：：es=+1（l，add）<$→（l，add）加入1l=opt：：opt：：esopt：：es=00+10 0（l，add）<$→（l，nop）加入2ΣÆ=mnd:: ΣÆ+1Σ► (l,pop)‹→(l,pop)pop1ΣÆ=opt::ΣÆ+1Σ► (l,pop)‹→(l,nop)流行音乐2ΣÆ=mnd::esmnd：：mnd：：es=m+1m（l，dup）<$→（l，dup）双1ΣÆ=e1：：esopt：：e1：：es=00+10 0（l，dup）<$→（l，nop）双2ΣÆ=ΣmgotoΣ►(l,gotom)‹→(l,gotom)ΣÆ=mnd::eses=mes=1000+ 1Σ► (l,gotoFm)‹→(l,gotoFm)gotoFΣÆ=∗∗=ΣÆ+1loadΣ►(l,loadx)‹→(l,nop)Push=Push=Push+1pushPush（l，pushn）<$→（l，nop）n∈dom（c）.Σ►(l,cÆ)‹→(l,cJÆ)codeΣ►c‹→cJ图四、消除加载-弹出对的类型系统州”。堆栈类型es∈StackType是位置类型“mandatory”和“optional”的列表图4中给出了类型化和子类型化规则。 类型规则规定，如果在某个标签上，堆栈元素被标记为“mandatory”，则在其生存期的所有其他标签上，该特定元素也被认为是“mandatory”。 因此，类型规则解释了哪些优化是可接受的。存储指令的规则规定，指令总是需要堆栈上的“强制”元素，因此它的前身必须明确地在堆栈顶部留下一个值。将元素放入堆栈的指令“不关心”：如果需要一个元素，它们可以推送一个值（posttype中堆栈上的mnd元素），否则可以省略该指令（posttype中堆栈上的opt元素）。 的 这同样适用于pop：如果一个元素被明确地留在堆栈上，则pop指令不能删除，否则可以删除。如上所述，分析（类型推导）算法是双向的。虽然双向分析似乎比单向分析更复杂，但已经表明双向问题本质上并不比单向问题复杂[6]。算法背后的直觉如下。应该给出某些标签上明确需要的类型（通常，代码出口标签上的类型被设置为空栈，也可能是入口标签上的类型）。 所有其他类型都被初始化为默认类型“任何状态”。然后，算法计算22112A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103比给定类型更强的代码的最弱有效类型。在每个标签上，信息都是从所有的继任者和前辈那里收集的。约束从给定的类型以及存储和条件跳转指令开始，这些指令要求在堆栈上为它们提供一个值（即，mnd元素必须是在堆栈类型的顶部）。其他从堆栈中产生或消费值的指令最初可以被假设为产生或消费“无用”值（在类型系统中由opt表示）。 键入从不同方向到达的信息，一个程序点可以根据图1中给出的子类型关系来表示四、这保证了，如果一个指令明确需要堆栈上的一个值，这个信息会传播到它的所有前导。类似地，如果一条指令肯定必须在堆栈上产生一个值（因为一些后续指令可能需要它），则将该信息传播到其后继者。查看图3中的示例，其中我们将控制流图的后置类型初始化为空堆栈，storez的前置类型需要堆栈顶部的mnd元素。这意味着loady的posttype必须在栈顶有mnd。该信息传播到pop指令，并从那里传播到loadx指令。 因此，分析表明，可以删除。另一方面，如果存储z不存在，则两个加载指令的后标签和弹出指令的前标签将保持它们的初始值。opt栈顶类型，并可以删除这三条指令在下面的示例中，在左列中给出了与图3 它得到一个类型，表明没有优化是可能的。在右列中，我们考虑一段最小差异的代码，其中storez指令已被pop替换。这里的分析表明，弹出和相应的加载指令都可以删除。ΣÆl,cÆl,cJÆ[] 0，loadb0，loadb[mnd]1，gotoF 9 1，gotoF 9 []2，loady2，loady[mnd]3，loadbJ3，loadbJ[mnd，mnd] 4，gotoF 7 4，gotoF 7 [mnd]5，storez5，storez[] 6，goto 11 6，goto 11 [mnd]7，pop7，pop[] 8，goto 11 8，goto 11 [] 9，loadx 9，loadx[mnd]10，转到 7 10，转到 7[]11， 11，ΣÆl,cÆl,cJÆ[] 0，loadb0，loadb[mnd]1，gotoF 9 1，gotoF 9 []2，loady2，nop[选择] 3，loadbJ3，loadbJ[mnd，opt] 4，gotoF 7 4，gotoF 7 [opt]5，pop5，nop[] 6，goto 11 6，goto 11 [opt]7，pop7，nop[] 8，goto 11 8，goto 11 [] 9，loadx 9，nop[opt]10，转到 7 10，转到 7[]11，11，用于建立优化可靠性的状态的类型索引相似关系定义如下：[][][]zseszsz：：zsmnd：：esz：：zszseszsz：：zsopt：：eszszseszs（l，zs，σ）es（l，zs，σ）（l，zs，σ）es（l，[]，σ）规则指出，如果两个状态在第一个状态中的可选堆栈位置（在第二个状态中必须省略）可靠性陈述与定理2.1相同，证明也是类似的。这同样适用于下一节中的以下两个优化A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103113−∈{}∈3存储/加载+消除在这一节中，我们将讨论一种使用更广泛的字节码优化-冗余存储/加载计算。这种优化是基于这样的观察，即如果在存储之后将相同的变量重新加载到相同的堆栈位置（并且在此期间变量没有重新定义），那么，如果将来没有使用该变量，则可以消除存储和加载指令。类似地，如果存在存储之后跟随有n个加载，则存储和加载可以由n个1 dup指令替换。 注意，对于这些优化， 存储器和负载不必彼此相邻，可以是中间指令，只要指令之后堆栈高度保持不变，并且顶部以下的值不会被它们消耗我们分两个阶段来实现这种优化。首先，一个简单的正向复制传播分析确定是否可以用dup指令替换某些加载指令。在第二阶段，存储/加载对被检测和变换。3.1重复负荷消除此分析是一个简单的复制传播分析，它试图确定在加载x指令之前，x的值是否已经在堆栈顶部。 如果是这种情况，则可以用dup指令替换loadx指令。这是一个单向的、前瞻性的分析。在类型系统中，标签类型是堆栈类型或一个特殊类型. 堆栈类型esStackType也是位置类型的列表，这次是xVar的元素（表示位置肯定是变量x的副本）和一个特殊类型子类型和类型规则如图5所示。 类型规则规定，堆栈位置可以标记为标签l的变量，如果在所有到该标签的路径上，该变量被放在堆栈的该位置，并且以后不会被修改。换句话说，在标签l处，堆栈中相应位置的值必须等于变量的值。如果堆栈类型在某个位置保存NAC元素，则意味着该位置可能不是副本（例如，因为在某种程度上，l，数字被推到该位置）。因此，加载的类型规则反映了在指令之后，堆栈顶部的值和相应变量的值必须相等。存储x显式地杀死堆栈中的所有变量x，因为堆栈中的值和变量的新值不再能保证一致。 如果变量x在loadx指令之前位于堆栈顶部，则可以进行优化。在这种情况下，可以使用dup替换负载，如下例所示：114A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103eseses[客户端]x：：ese≤eJes≤esJl∈Label. 联系我们x≤nace ≤e[] ≤[]e：：es ≤eJ：：esJ≤τ≤ΣÆ=e::esreplace（x，nac，es）≤nac+1Σ►(l,storex)‹→(l,storex)店x：：x≤x+1我的天l/=x：：es（l，loadx）<$→（l，loadx）负载1x：：x≤x+1l=x：：es负载2nac：：push≤push+1ΣÆ=e0：：e1：：esnac：：es≤± 1添加Σ►(l,pushn)‹→(l,pushn)ΣÆ=e::eses≤100Σ► (l,pop)‹→(l,pop)Σ►(l,add)‹→(l,add)波波ΣÆ=e::ese：：e：：es≤ε+1dup（l，dup）<$→（l，dup）DUP中文（简体）ΣÆ=e：：eses≤100+1es≤μmgotoFΣ► (l,gotom)‹→(l,goton) Σ► (l,gotoFm)‹→(l,gotoFn)ΣÆ=∅instrΣ►(l,instr)‹→(l,instr)n∈dom（c）.Σ►(l,cÆ)‹→(l,cJÆ)codeΣ►c‹→cJ图五、消除重复负荷的类型系统ΣÆ（l，c）（l，cj）[]0，加载x0，加载x[x]1、推11，按1[nac，x]2，存储y2，存储y[x]3，load x3，dup[] 四四这种优化不仅可以通过跟踪堆栈中变量的副本来改进，而且还可以通过跟踪变量的副本来改进。一个位置类型就是一组变量（给定位置肯定是这些变量的副本;空集将表示该位置可能不是任何东西的拷贝）。 然后，即使有来自不同变量的连续加载，也可以引入dup，只要这两个变量实际上是彼此的副本用于建立优化可靠性的状态的标签型索引相似关系定义如下：公司简介zsσzszsσzs[]σ[]σnac：：esz：：zsσ（x）：：zs<$σσ（x）：：zs（l，zs，σ）(Note没有任何国家是处于这种关系中的）。3.2存储-负载对消除存储-加载对分析试图找到存储指令，然后是到相同堆栈位置的加载指令，并引用相同的变量（之前发生对相同变量的任何新存储）。如果以后不使用此变量，则可以删除这两条指令。 由于未来可能的用途如果一个变量的值需要一个活变量分析，我们采取的方法是只删除加载指令，但保留存储指令，并在它前面加上一个dup，如下面的例子所示：z：：zsA. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103115∅∅{[] ≤[]es≤es'e：：es≤e：：es'es≤es'x：：es≤es'τ ≤τLa bé l. l≤≤l=mnd：：eses=1+1<$me mber（x，es）store（，storex）<$→（，store x）l=esmnd：：es =1+ 1l=mnd：：esx：：es=1+1<$me mber（x，es）store_n（n，store_x）<$→（n，dup;store_x）x：esmnd：：es =1+ 1Σ►(Æ,loadx)‹→(Æ,loadx)负载1Σ►(Æ,loadx)‹→(Æ,nop)负载2mnd：：rl=rl+1Σ►(Æ,pushn)‹→(Æ,pushn)推l=mnd：：mnd：：esl+1=mnd：：esΣ►(Æ,add)‹→(Æ,add)添加l=mnd：：mnd：：mnd：：es =l+1弹出式Σ►(Æ,pop)‹→(Æ,pop)l=Σ►(Æ,dup)‹→(Æ,dup)l=mnd：：eses =0.1+ 1es =mgoto gotoFΣ►(Æ,gotom)‹→(Æ,gotom)1=1+1非跳跃Σ►(Æ,instr)‹→(Æ,instr)Σ►(Æ,gotoFm)‹→(Æ,gotoFm)l===Σ►(Æ,gotoFm)‹→(Æ,gotoFm)gotoFn∈dom（c）.Σ►(Æ,cl)‹→(Æ,c'l)Σ►c‹→c'代码图六、存储-负载对消除的类型系统0，存储x0，dup;storex1，load x1，nop 2，.2、...这种方法的好处是可以省略对x未来使用的检查。如果结果证明不需要该变量，则死代码消除优化将在稍后删除dup和store指令由于这种优化操作指令对，因此需要进行双向分析，就像load-pop对的情况一样与前面的分析类似，标签类型也是堆栈类型或“无状态”的特殊类型：LabelType=dfStackType+.堆栈类型是位置类型的列表，这些位置类型是Var的元素x（要插入到优化代码中以在堆栈中保留变量x子类型和类型规则如图6所示。 打字规则说，如果一个标签有某种栈类型，那么每次在执行中到达这个标签时，堆栈的大小将是堆栈中mnd元素的数量。此外，如果在某个标签上堆栈类型包含Var元素，这意味着，如果代码是根据类型规则优化的，则在优化代码中的该标签处，堆栈将在这些位置对应于原始代码的位置例如，一段代码可以按以下方式键入ΣÆl，cl，cJ[]0，按 10，按1 [mnd]1，storex 1，dup;storex[x]2、推 12，按 1[mnd，x]3、存储y3、存储y[x]4，负载x4，nop[mnd]5、店铺z5、店铺z[z值]六六(Note这是当标签16的类型被初始化为T1时分析算法将导出的主要类型。也可以使用[]来标记el612116A. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103∅eseses[客户端]∼∅如果标签6的类型被初始化，这也是算法将传递的 至[]。）分析算法的工作原理如下。应该给出一些标签的最低可接受类型（通常是程序的入口点的类型，即，标签0被设置为[ ]，并且还可选地设置退出标签的类型）。 其余标签初始化为默认类型 . 然后算法尝试以计算每个标签的实际和潜在堆叠高度。如前所述，类型中的mnd元素表示实际元素;类型中的变量表示优化后存在的潜在元素。对于store和load，标签的后继者和前导者的类型用于计算本地标签类型。来自不同方向的类型通过由子类型关系确定的非确定性联合操作（[x]和[y]都大于[x，y]和[y，x]，所以它们没有唯一的最小上界，只有最小上界。）因此，如果在某个传入或传出路径上，潜在的附加堆栈高度实际上不可行，则从堆栈中删除任何临时的附加位置为了简化表示，转换不执行任何重新标记的指示。相反，两个指令（dup和store）共享一个标签。 事实上，适当的重新标记是没有问题的：任何指令标签和跳转目标都应该增加其类型中变量名的数量。 为了简化规则，我们没有这样做建立优化合理性的标签型索引相似性关系定义如下：公司简介zsσzszsσzs[]σ[]σmnd：：esz：：zsσx：：es σ（x）：：zs（l，zs，σ）（同样，没有两个国家处于这种关系中。） 现在，如果第二个状态在其堆栈组件中有适当的附加位置，与存储组件（附加位置复制变量）相一致，则两个状态是相关的。4相关工作相关的工作分为两类：基于堆栈的低级语言的优化工作和类型系统的数据流分析和优化工作，包括数据流分析理论的必要成分基于栈的底层代码正如在介绍中提到的，一个比较知名的字节码转换工具是Soot [17]。Soot的字节码优化方法是将字节码转换为3地址的中间代码，使用标准技术优化中间代码，然后将代码转换回字节码。来回转换会给字节码带来一些不确定性，比如冗余，z：：zszsA. Saabas，T.Uustalu/理论计算机科学电子笔记190（2007）103117dant存储/加载计算。这可以通过将中间代码转换为聚合形式来解决，使用一些窥视孔优化技术并使用标准树遍历技术将其转换为字节码，或者通过将中间代码转换为字节码的流线型形式并对其基本块执行存储加载优化[18]。当然，Soot方法的好处是，对中间语言的优化是例行执行的。缺点是不同表示之间的多次转换使得执行的优化不透明，并且代码可能会丢失以前存在的一些属性