多线程程序的死代码消除优化方法

埃及数学学会埃及数学学会www.etms-eg.orgwww.elsevier.com/locate/joemsJournal of the Egyptian Mathematical Society（2012）20，28原创文章基于死代码消除的多线程程序Mohamed A. 扎瓦维开罗大学理学院数学系，吉萨12316，埃及2012年2月2日在线发布摘要本文提出了一种新的用指针结构优化多头程序的方法。该方法在认证代码（证明携带代码）领域有应用，其中需要对每个优化的正确性进行证明或证明。这里的优化是指死代码消除。为了优化多线程程序，本文提出了一种新的并行结构，如连接叉结构，并行循环，有条件地产生线程的操作语义。本文还提出了一种新的多线程程序的指针分析系统。对该类型系统进行了扩展，得到了一个新的多线程程序活变量分析类型系统。对活变量型系统进行了扩展，建立了本文提出的第三种新型系统，该系统对死代码消除进行了优化。上面提到的正义在我们的方法中采取类型派生的形式2011年埃及数学学会。制作和主办：Elsevier B.V.在CC BY-NC-ND许可下开放访问。1. 介绍当今的主流编程方法之一是多线程。使用多线程在很多方面都很有用，电子邮件地址：maelzawawy@cu.edu.eg1110- 256 X？ 2011埃及数学学会。制作和主办：ElsevierB.V.在CC BY-NC-ND许可下开放访问。同行评审由埃及数学学会负责。doi：10.1016/j.joems.2011.12.011(a) 隐藏由某些命令引起的挂起，（b）使构建大型软件系统更容易，（c）改进程序的执行，特别是在多处理器上执行的程序，以及（d）构建高级用户界面。多线程程序中线程之间的潜在交互使编译和程序分析过程复杂化。此外，这种相互作用也使得扩展顺序程序的程序分析技术的范围以覆盖多线程程序变得困难。典型的优化多线程程序是通过数据流分析以算法的形式实现的.这包括将给定的程序转换成一个控制流程图，这是一个方便的形式，算法来操纵。对于某些应用程序（如认证代码），制作和主办：Elsevier基于死代码消除的多线程程序29将每个程序优化与优化正确性的证明或证明相关联。对于这些情况，程序分析的算法方法不是一个好的选择，因为它不适用于程序的语法结构，因此不反映转换过程。此外，所需的调整必须相对简单，因为它在可信计算基础内进行检查类型系统是程序分析的算法方法的一个方便的替代品，当一个正义是必要的。在类型系统方法中，程序的分析和优化由程序的语法结构指导。类型系统的推理规则相对简单，在这种情况下采取类型派生形式的正义也是如此。类型系统对于程序分析的充分性已经在[3，12，22]指针分析是最重要的程序分析之一，它计算描述不同程序点上指针内容的信息。指针分析多线程程序的应用程序的结果，程序分析和编译器优化所需的信息，如活变量分析和死代码消除，分别。活变量分析为每个程序点找到变量集，这些变量的值在程序的其余部分中有用。活变量分析的结果对于死代码消除的优化是必要的，死代码消除在程序结束时本文提出了一种新的指针结构优化多线程程序的方法.所提出的方法的范围足够广泛，包括认证（携带证明）的代码应用程序，其中需要进行优化。类型系统是新方法的基本工具，它考虑了结构化并行构造，如join-fork构造、并行循环和条件派生线程。在我们的方法中，正义采取类型推导的形式。更准确地说，本文提出了一个类型系统的多线程程序的线程敏感指针分析。本文还用一个类型系统来处理多线程程序的活变量分析，该类型系统是指针分析类型系统的扩展。扩展的形式是另一个组件被添加到指向类型。死代码消除多线程程序，然后实现使用类型系统，这又是一个扩展的类型系统的活变量分析。这一次，扩展采用了转换组件的形式，它被添加到类型系统的推理规则中，用于活变量分析。为了证明这三个类型系统的可靠性，本文提出了一种新的并行结构1.1. 动机图1给出了本文所述工作的一个激励性示例。考虑图中左侧的程序。假设在程序结束时，我们对x和y的值感兴趣。我们注意到，第8行中的是一个死代码，因为变量x在第9行中被修改，然后我们才使用变量在第8行中得到的值。第2行中的赋值间接修改了y，在对y在第2行中得到的值进行任何有用的使用之前，在par所以第二行是死代码。图1一个激励性的例子。par命令有两个线程，可以以任何顺序执行。如果第一个线程首先执行，那么第4行和第5行中的赋值就变成了死代码。如果第二个线程首先执行，那么第5行和第6行中的赋值将成为死代码。因此，par命令中的死代码只是第5行中的赋值。本文提出了一种技术，发现和删除这样的死代码在并行结构化程序与指针结构。该技术的输出是类似于图1右侧的程序。除了join-fork构造（PAR），本文还考虑了其他并行构造，如条件派生线程和并行循环。对于每一个这样的程序优化，我们的技术都为优化的正确性提供了一个证明。证明采用类型派生的形式1.2. 贡献本文的贡献如下：1. 一个简单而强大的操作语义为多线程程序与指针结构.2. 一种用于多线程程序指针分析的新型类型系统。据我们所知，这是第一次尝试使用类型系统进行多线程程序的指针分析。3. 一种新型的多线程程序活变量分析系统。4. 一个用于多线程程序死代码消除优化的原始类型系统。1.3. 组织本文的其余部分组织如下。我们所研究的语言第3节和第4节分别介绍了我们提出的对指针敏感的类型系统和第五节介绍了进行程序优化的类型系统。相关工作在第6节中讨论。2.编程语言本节介绍我们使用的编程语言（图2）及其构造的操作语义。该语言是简单的while语言[8]，富含指针操作和结构化并行构造的命令。30M.A. 扎瓦维2.：¼1>2！否则：bc¼ trueS：c中止1/4。图2编程语言。并行构造包括联接分叉构造、并行循环和条件派生线程。par（join-fork）构造在开始par构造，然后等待直到完成。对于} 2 f^;_g;sb1}b2tc！如果sb1tc¼！或sb2tc ¼！;sbtc}sbtc否则：在par构造结束时执行所有这些操作。从语义上讲，par构造可以近似地表示为线程是在任意空间中顺序执行的我们的语义（转换关系）的推理规则定义如下：trary order.我们语言中包含的并行循环结构是par-for。此构造并行执行静态未知数量的线程，每个线程都具有是的，是的！x：¼e：c，中止setc-！x：¼e：c，c½ x#setc]同样的代码（循环体）。因此，par-for的语义可以使用par构造的语义来表达。包含条件派生线程的构造是par-if。这个构造并行执行它的n个并发线程。thread（bi，Si）的执行仅在bi为真时才包括Si定义我们编程语言的构造（包括并行构造）的意义的一种方法是通过cxz0z：e：c，状态ωx：¼e：c，状态cbxcbr地址ωx：1/4e：c，abort x：1/4y：c，c1/2x#y0]cyz0x：z：c，c0x：¼ωy：c，c0操作语义学这相当于定义了[状态之间的]转换关系，定义如下。定义11. Addrs={x0Varx2Var}和Val¼Z[Addrs：电子邮件地址x：¼ωy：c，中止跳过：c，cS1：c，c00S2：c00，状态S1;S2：c，状态S1：c，中止S1;S2：c，中止2. 一个状态要么是中止要么是映射c2C=VarfVal。算术和布尔表达式的语义定义与通常一样，只是不允许在指针上进行算术和布尔运算。公司简介 sxtc¼x0sxtc¼cxstruetc¼truesbtc ¼！if b thenSt elseSf：c，中止sbtc¼false Sf：c，stateif b then St else Sf：c，statesbtc¼falsewhile b do St：c，csbtc¼true St：c，stateif b then St else Sf：c，状态s b t c ¼！while b doSt：c，abortsfalse tc ¼falsesωxtc¼。cyifcxy0;sbtc¼trueS：c，c00whilebdoSt：c00，statewhile b do St：c，statest，se1e tc ¼。se1tcse2tcifse1tc;se2tc2Z;while b doSt：c，abort！否则：sAtc：如果sAtc2f为真，则为假g;！否则：8><！如果se1tc¼！ 或se2tc¼！;● 连接叉：parf fS1g;. . . fSngg：c，c0yparffS1gg;. . . ;fSngg：c，abortzt存在置换h：{1，. ，n} fi {1，. ，n}，并且n+1个状态c=c1，. . . ，Cn+1=c0，使得对于每个se1¼e2tc ¼如果se1tc¼se2tc-，则为true！;：false否则：基于死代码消除的多线程程序3112setc6setc否则：16i6n，Sh（i）：cifi+1.‡存在m使得16m6n，一对一映射b：{1，. ，m} f {1，. . ，n}，以及m +1个状态c =c1，Se6etc¼。！如果se1tc R Z或se2tcR Z;... ，cm+1=中止，使得对于每16i6m，Sb（i）：cifi+1。1232M.A. 扎瓦维pðÞ6;---ð ¼ Þpð ¼ ωÞ22 2NðÞ一个！二号！pð-Þ● 并发生成的线程：parf fifb 1 thenS 1 elseskipg;. . . ;fifbnthenSnelseskipgg：c，c0S：pts[pts0！pts0par-forfSg：pts！PTS0par-为par-iffb1;S1;. . . ;bn;Sng：c，c0St：pts！ pt s0Sf：pts！pts0ifpparffif b1then S1else skipg;. ;fif bn then Sn else跳过gg：c，中止ifbthenStelseSf：pts！PTS0par-if fundb1; S1;. ;bn; Sng：c，中止● 并行循环：S t：pts！ pts whlwhileb do S t：pts！ pts分016分1 S：1分！患者2 点26点02点n次n次S：0分！患者0联系我们z}|fflfflffl ffl ffl fflffl ffl{ zffl fflffl fflfflfflffl ffl}| fflfflffl ffl ffl ffl ffl ffl{129n：parffSg;. . . ;fSgg：c，c0par-对于fSg：c，c03. 指针分析9n：parffSg;. ;fSgg：c，abortpar-forfSg：c，中止表达式的判断具有e：pts fIA的形式。的在引理1中形式化的该判断的预期含义是，A是e在pts类型的状态中可以评估到的地址的集合。一个陈述的判断具有S：ptsfipts0 的 形 式。这个判断简单地保证，如果S在pts类型的状态下执行，并且执行ter-在这一节中，我们提出了一种新的技术，结构化并行程序的指针分析，其中共享指针可以同时更新。我们的技术操纵重要的并行结构，联合叉结构，并行循环，并有条件地产生线程。所提出的技术具有结构简单的组合类型系统的形式。因此，分析的结果是以类型的形式分配给由类型派生批准的表达式和语句。因此，一个类型被分配给语句（程序）的每个程序点。这种赋值类型为程序中的每个变量指定了可能进入变量的地址的保守近似值。指向类型PTS的集合和关系C·PTS定义如下：定义21. PTS={pt s地址：变量2地址}。def2. ptspt s0（）8 x 2Var·pt s x pt s0 x。minates处于状态c0，则c0具有类型pt s0。通常，程序S的指针分析是通过对作为前类型的底类型（将变量映射到）的后类型推导来实现的。与赋值命令安全了对于join-fork命令par的规则（parp），一种可能性是线程Si的执行在任何其他线程的执行开始之前开始。另一种可能性是在所有其他线程的执行结束之后开始执行。当然，在这两者之间还有许多其他的可能性。因此，线Si的分析必须考虑所有这些可能性。这反映在Si的pre-type和par命令的post-type类似的解释阐明了规则（par ifp）和（par forp）。我们注意到，类型不变式需要键入while语句。同样，为了实现对PAR然而，获得这些结果需要分析第一个线程的结果。因此，在规则（parp）中存在一种循环。类似的情况也存在于rules（par ifp）中p3. c}分defX2和（par-for）。这些问题可以使用固定点来处理（）108Var·cx 2 Addrs）cx 2 ptsx.算法该算法的收敛性是有保证的，因为我们的类型系统的规则是单调的，指针分析的类型系统的推理规则如下：n：pts！ ; x：pts！ ptsptsptspts1e2：pts！ ;e：pts！ 答：px：¼e：pts！分半x#A]x：¼&y：pts！我&的天啊！pts8z02ptsy：x：¼z：pts！患者0：px：¼ωy：pts！PTS08z02分x：z：¼e：分！pts0ω：¼pPTS是一个完全格。引理11. 假设e：pts fIA和c`pts。那么sebc2地址意味着s ebc2 A.2. 分6分0（）（6c. c`pts）c`pt s0）.证据第一项是显而易见的。从左到右的方向（2）容易。另一个方向证明如下。假设y0pts（x）。则状态{（x，y0），（t，0）}tVar{x}}是pts类型，因此是pt s0类型，这意味着y0pts0（x）。 因此pts（x）cpts0（x）。 因为x是任意的，所以pts6pt s0。 Hωx：¼e：pts！PTs000S i：pts[[j- i pts j！ ptsiparpparffS1g;. ; fS ngg：pts！ [i分iS：pts pts00S：pts00pts0S;S：pts！0分以下定理1.（合理性）假设S：pts，S：c [c]，c`pts。 那么c0`pts0。证据证明是在类型导子上用结构归纳法进行的。我们展示了一些案例。12–parrf fifb1thenS1elseski pg;. ;fifbnthenSnelseskipgg：pts！pts0parifppar-iff <$b1;S1<$;. . . ;bn;Sng：pts！患者0c0=c[x'sebc]。因此，根据前面的引理c`pts表示c0`pt s0。基于死代码消除的多线程程序332.Σ22Lð- ÞðÞLðÞ6.Σ12.命令的执行。规则ω：<$4处理这种情况\;.删除post类型。规则ω：¼处理的情况是，\;这意味着c0`pt s0=[pts.x：1/4e：1/2 s;1/0s ！0;l0个ωx：1/4e：1/2 s;l0[fxgym！0;l0个.ΣLω ¼ω ¼L– （\：=p）的情况：在这种情况下，存在z2Var，使得 c（x） =z0和z：=e：c[c0.因为c`pts，z0pt s（x），因此通过假设z：=e：ptsfipts0。因此，根据（：=p）的可靠性，c0`pts0。– （parp）的情况：在这种情况下，存在一个置换h：{1，.. . ，n} fi {1，. . ，n}和n +1个状态c =c1，. . ，Cn+1=c0，使得对于每16i6n，Sh（i）：cii+1。c1`pts也意味着c1` pts [[jn h（1）pts j。 因此，通过归纳假设c2`ptsh（1）。 这意味着c2`pts [[jn h（2）pts j。再次通过归纳假设，我们得到c3`ptsh（2）。因此，通过对n 的简单归纳，我们可以表明，分析是一种向后的分析，并提供了对以下c ` l定义的深入了解。假设我们有我们感兴趣的变量集l在执行语句S结束时的值和S的指针分析结果（以S：ptsfipts0的形式）。活变量分析采用预类型推导的形式，其计算集合l，使得S：（pts，l）fi（pts0，l0）。我们用于活变量分析的类型系统的推理规则如下。x：¼e：pts！pts0xRl0：¼ln+1个h（n）JJ– （par-forp）的情况：在这种情况下，存在n，使得n次x：¼e：pts！患者0x2l0x：ve：pt s;l0nfxg[F Ve！0;l0个：1/4升parfzfSg;。}。|.fflffl;ffl fflfffl fflSffl fflfflg{g:c,c0. 通过归纳假设，我们价格：1美元&有S：pts[pt s0fipt s0. 通过（parp），我们得出结论，n次x：1/2&y：2/3;l0nfxgym！ 样品½x#fy0g];l0gskip：skipts; l！ð pts；l ÞparfzfSg;。}。|.fflffl;ffl fflfffl fflSffl fflfflg{g:pts,pt s0. 所以，x：¼ωy：pts！ pt s0xRl0。 l（parp），c0`pts0。Hx：1/2ωy：1/2 s;1/0[fygg！ 振幅0;l0Hz：1/4ω1x：¼ωy：pts！pts0x2l0x：1/2ωy：1/0;l0个：¼ωl004. 活变量分析ωx：¼e：pts！ ptsptsx\l¼ ;.ω：1/4升在本节中，我们将展示一个类型系统来执行live-vari-00结构化并行指针程序的表分析ωx：¼e：pts！ pts pt sx\l-;.ω：1/4升结构。我们从定义活变量开始：定义3ωx：¼e：pt s;l0[F Ve[fxg！0;l0个Si：pts[[j- i pt s j ; l i！ ptsi;l0[[j- i ljparf fS1g;.. . ;fSngg：;[ili！[iptsi;l0pts2拉帕尔– 如果使用变量，则该变量是有用的●作为一元操作的操作数\。parffifb1thenS1elseskipg;. ;fifbnthenSnelseskipgg：pt s;l！ pts0;l0如果我把...如果fb1;S1;... ;bn;Sng：pt s;l！0;l0个●在对一个变量的赋值中，该变量在S：不好 意 思 ！样本0;l0[ll转让，或●在if语句或while语句的保护对fSg：不，不 ！pts0;l000 00 0– 一个变量是活在一个程序点，如果有一个计算路径，从该程序点，在此期间的变量，S1：不好 意 思 ！我的天 啊 ！第0行;第1行;第2行：第1行 ！0;l0个在被修改之前，它是有用的。定义4. 活动类型的集合由L表示，并且等于pts× PeggyVar. 活动类型的第二个组件称为St;Sf：;L！0;l0个ifbthenStelse Sf：pts;l[FVb！0;l0个l/4l0[FV]b=10秒 ！我在做什么，而你在 做 什 么 ！pts;l0ðifÞ带电元件 子类型关系为 定义为：def01;l01 ðpts2;l2Þðpts2;l2Þ6ðpts02;l02ÞðcsqlÞ（pts，l）6（pts0，l0）（）pts6pts0andlsl0.S：01分;101分 ！最大值02;l02活变量分析是一种向后分析。对于每个程序点，这种分析指定了在该点可能存在的变量集（根据上面的定义）。我们的活变量分析的类型系统是作为前一节中指针分析的类型系统的丰富而获得的。因此，可以说这里给出的类型系统是上面给出的类型系统的严格扩展。这是因为指针分析的结果对于提高活变量分析的精度是必要的。这也给了一个直观的解释定义的活类型以上命题S的判断具有形式S：（pts，l）fl（pts0，l0）。该判断的直觉是，在l 0中执行S的后状态处存在活变量意味着在l中执行该执行的前状态处存在活变量。直觉与活变量对于命令 *x：=e，我们有两个规则，即：和：。在这两种情况下，从post-type包括将x添加到post-type。这是因为根据定义3，x在任何exe的前状态都是活L1这个语句修改的变量在执行结束时不可能是活的（pts（x）l0=）。在这种情况下，不需要添加任何其他变量，L2是这样一种可能性，即由该语句修改的变量是实时（pts（x））（1）执行结束时。 在这种情况下，有可能根据定义3有用地使用e的自由变量。因此，e的自由变量被添加到post类型中。这对所有赋值命令的规则给出了直观的解释。上一节中给出的规则（parp）的直觉有助于理解..c0=cpts1134M.A. 扎瓦维--2.Σ212n[l]2121}0l2.布里尔{\ f n 黑 体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}{\fnMicrosoft YaHei\fs20\2cHFFFFFF\b0}（c）类型推导具有以下形式：1. c}lpts（）18x 2l：cnx 102Addrs）cnx102ptscnx 102 ptscnx102：2L.l并行结构的规则（parl）、（par ifl）和（par forl）。为了证明活变量分析的类型系统的可靠性，我们引入了必要的定义，结果(b) 类 型 派 生 的 形 式 为 ： ¼l 。 在 这 种 情 况 下 ， e ：ptsfIA，pts0=pts[x′A]，c0=c[x′sebc]，l=（l0n{x}）[F V（e）。 因此，通过引理3it，不难看出c0}l0pts0。.Σ1定义5def为 每 z02pts（y）， 我们 有 x：=z：pts=0，c（y） =z0，且x：=z：cfic0。 我们有z0pts（y），因为y2l和c`lpts。因此，由。：1/4升，我们2. c~c0defx20有x：=z：（pts，l0）fi（pt s0，l0）。现在c`lpts金额l（）d8efl：cxx：003. C~c0（）c}pts;c0}pts和c~c0。到c}l0pt s。因此，我们得到c}l0分 根据pts;l.：1/4升。.l第六章.表达式c`l表示当存在处于该状态（计算点）的变量并且不包括在l中时的情况。状态c具有类型（pts，l），用c`（pts，l）表示，如果c`lpts且c`l。利用e上的结构归纳证明了以下引理和b.（d）类型推导具有以下形式：1/4 ω2。在这种情况下，为每z02pts（y），我们有 x：=z：pts0，c（y） =z0，x：=z：cfic0，和l=（l0n{x}）[{y，z<$z02pts（y）}. 我们有z2pts（y），因为c`lpts和Y2湖因此，通过：1/4，我们有x：=z：（pts，（l0{x}））{z}）fi（pts0，l0）。C`pts意味c}l0nfxg [fzgpt s. 故，以德为本。：1升，我们得到c0}l0pt s0..Σ引理2. 假设c和 c0是状态 ，（五） 类型派生具有以下形式ω：1/4l. 在这l和l02PVar. 然后1. 如果l为l0且c~lc0，则c~l0c0。2. 如果l=10[FV（e）且c~c0，则sebc=sebc0且c~0c0。对于每个z02pts（x），我们有z：=e：ptsfipts0，c（x） =z0，且z：=e：cfic0。 我们有z0pts（x），因为x2l和c`lpts。因此，由。：1/4升，我们ll有z：=e：（pts，l0）fi（pt s0，l0），因为pt s（x）\l0=;。3. 如果l=10[FV（b）且c=10c0，则sbbc=sbbc0且c=10c0。下面的引理由引理1得出。现在c`lpts等于c}l0pt s。因此我们得到c0pts0，因为z：=e：（pts，l0）fi（pts0，l0），的健全性。：1/4升。1 .一、l引理3. 假设c`lpts，FV（e）cl，e：ptsfIA。然后s e t c 2地址！ s e t c 2 A：(f) 类型派生具有以下形式ω：1/42。 在这对于每个z02pts（x），我们有z：=e：ptsfipts0，c（x） =z0，z=e：c0，l=l0[F V（e）[{x}。我们有z2pts（x），因为c`lpts和x2l。因此由.：¼l我们有x：=z：（pts，（l0n{z}）[证据 考虑状态c0，其中c0=kx。 ifx2F V（e）thenc（x）else0. 不难看出，sebc=sebc0和c0`pts。现在通过引理1，sebc02Addrs蕴涵sebc02A，从而完成了证明. H定理2000F V（e））fi（pt s0，l0）.c`lpts意味c}将0nfzgag[FV]e转换为s。 因此，通过：1/4的可靠性，我们得到c0}0pt s0。(g) 类型派生的形式为（parl）。在这种情况下存在置换h：{1，. . ，n} fi {1，. . ，n}和n+1个状态c=c1，. . ，Cn+1=c0，使得对于每1 6i 6 n，Sh（i）：cii+1。 c1`lpts也意味着c1}lh1pts[[j- h 1 pts s j. 因此，通过归纳1. pts;l6分;lc：cl分cl0分。2. 假设S：（pts，l）fiP（pts0，l0）和S：c[c0. 那就去吧假设c2}l0[[jhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh. 这隐含c2}l.在这种情况下，基于死代码消除的多线程程序35}}}z}|你知道吗？-（(a)类型派生具有以下形式 ：1/4升 .Σz}|你知道吗？2019年12月pts表示c0l0pts0：3. 假设S：（pts，l）fiP（pts0，l0）和S：c[c0. 那么c`l表示c0`l0。 这保证了如果位于c0的变量集包含在l0 中，则位于c的变量集包含在l中。证明1. 假设C`LPT S。 这意味着cl0pts，因为l0cl。最后一个事实意味着cl0pt s0，因为pts6pts0。2. 证明是通过归纳的结构类型deriva-第我们展示了一些案例。1 .在这种情况下，pts0=pts[x′A]和c0=c[x′sebc]。因此c}l0pts意味着c0}l0pts s0，因为xRl0。pts[[j- h] 2 pts s j. 再一次根据归纳假设我们得到c3}l0[[j- h <$2 <$l j pt s h <$2 <$l. 因此，通过对n的简单归纳，我们可以证明c0<$cn<$1}l0[[j- h <$n<$l j pt s h <$n <$l]，这意味着c 0 } l 0 pt s 0 <$4 [ j pts j。(h) 类型派生的形式为（par-forl）：n次如果存在n使得parffSgi。. . ;fSgg：c，c0.通过 感应 假设我们有 S：（分pts0，l）fif（pts0，ll0）。通过（parl）我们得出结论，n次parffSg;. . . ;fSgg：pt s;l！我是说，我是 说， 因此，通过（parl）的可靠性，我们得到c0}l0pt s0。3. 证明也是在类型导式的结构上用归纳法H36M.A. 扎瓦维ωω2012. 在这种情况下，6z02pts（x），我们有z：=e：ptsx：&1：2：3：4：5：6：7：8：9：10我的天啊！x：¼y2ω ωω.Σ. ¼Σ. ¼Σ. ¼Σ. ：图3算法优化-并行.以下推论的证明由定理2得出。推论1. 假设S：c[c0和S：（pts，l） fi（pts0，l0）. 则c`（pts，l）蕴涵c0`（pt s0，l0）。定理3. 设S：（pts，l）fi（pt s0，l0），S：c[c0，c ~（pts，l）c*，且S在c* 处不中止. 则存在状态c0使得S：cω！ c0和c0~l0≤ s0;l0≤c0。证据证明是通过归纳型导子的结构。我们展示了一些案例：1. 类型派生具有以下形式之一。：1/4升的螺旋桨。：1/4升。这里给出的类型系统具有如下形式的判断：S：（pts，l）fi（pts0，l0）WS0。直觉是，S0优化S对死代码消除（可能是程序校正）。正如前面在许多场合所提到的，这种判断的推导为优化提供了一个合理的解释。过程判断的形式表明，本节中介绍的类型系统是建立在活变量分析的类型系统之上的。图3概述了一个算法，并行优化，总结了优化过程。该算法的第一步是指针分析，它用指针信息标注输入程序的点在我们的类型系统中，这一步采用S的post类型派生的形式 对于指针分析，使用底部指向类型^={x';x2Var}是前类型。其次，算法取c0<$cω 1/2x #setcω]。.l.l通过以下方式细化在第一步中获得的指针信息：使用类型组件注释指针类型，2. 类型派生具有以下形式 ：¼ ω1 或 ：1/4 ω2。在这在6z02pts（y）的情况下，我们有x：=z：ptfipts0，c（y） =z0，并且变量使用我们的类型系统进行活变量分析，x：=z：cfic0. 我们设c0<$c ω<$x#cω<$z<$]。：1/4ωl.l这是通过集合l0的S的预类型推导来完成的，一组变量，其值在表达式结束时与我们3. 类型推导 拥有 形式：¼ω1和fipt s0，c（x） =z0，z：=e：cfic0。我们让c0<$cω½z#setcω]作为岗位类型。最后，迄今为止获得的信息在第三步中，通过使用类型系统，本节中提出的死代码消除应用将该算法应用 到图1左侧的程序中。 14. 类型派生的形式为（par）。在这种情况下存在置换h：{1，. ，n}fi{1，. ，n}和n+ 1状态c=c1，. . . ，Cn+1=c0，使得对于每16i6n，Sh（i）：cii+1。我们将c*称为c*1。我们有c1~pt s;[ilicω1。因此在同一个图的右边的程序的结果当然。这个应用程序的细节是一个简单的练习。我们的死代码消除类型系统的推理规则如下：Sh（1）：c*1fic*2andc2~tsh;l0[[jlj这意味x：¼e：pts！患者0xR10：ex：1/4e：1/2;l00 0 ！我 不知道你在说什么！翻斗车1c2~n [[j- h <$2] n] p t s j ; l h <$2 <$p c ω 2. 因此，关于n00的证明所需的。 H5. 死代码消除本节介绍一个用于消除死代码的类型系统。给定一个程序和一组变量，这些变量的值在程序结束时与我们有关，程序中可能有一些代码对这些变量的值没有影响。这种代码被称为死代码。这里介绍的类型系统目的是优化结构化并行程序的指针x：¼e： pts！ 患者x 2 l：e你知道吗？我 不知道你在说什么！x：¼e2xRl：&ex：1/2&y：1/2 s;1/0s ！我 的天啊！翻斗车1skip：pt s;l！你 好！skipx2l0. ：¼e通过消除死代码构建。以类型派生的形式，类型系统将每个优化与优化的可靠性的证明相关联。优化程序可能会导致纠正它，即。阻止它中止ing. 当然，如果删除的死代码是x：¼ωy：pts！pts0xRl0ex：1/2ωy：1/2 s; 1/0[fygg！我不知道，我不知道！翻斗车1x：¼ωy：pts！pts0x2l0：¼ωe堕胎的唯一原因x：1/2ωy：1/ 2pts;2/3 pts; 3/4 pts; 4/5 pts; 5/6 pts; 6/7 pts; 7/8 pts; 8/9pts; 9/10pts; 10/1我不知道你在说什么！x：1/4ωy。2Σ在这种情况下，pt s0=pts[x′A]和c0=c[x′sebc]。我们基于死代码消除的多线程程序371eeeeeeωω联系我们1 122ωx：¼e：pts！pts0ptsx\l¼ ;ωx：1/4e：1/2 s; l0[fxgym！我不知道，我不知道！skip.ω：¼e包括其范围从顺序程序扩展到多线程程序的技术。在上面提到的第一类中，00ωx：¼e：pts！ ptspt sx\l- ;.ω：¼e研究方向分析同步电机的目的是ωx：¼e：pt s; l0[fxg[F Ve！我不知道，我不知道！ωx：1/4eSi：pts[[j-ip tsj;li ！ ptsi;l0[[j-ilj我parffS1g;. . . ;fSngg：pt s;[il i！ [ipt si;l0parffS01g;. . . ;fS0ngg如果b1则S1，否则pg;. . ;fifbnthenSnelseski pgg：pt s;l！pts0;l01拉帕尔[28，32]这是一个很好的解释，将动作与程序段的执行分开。 分析的结果可以被编译器用来方便地添加join-fork结构。多线程计算的一个问题是死锁，它是由于多个线程等待获取资源而引起的.研究人员已经开发了各种死锁检测技术[9，30，31]。 当一段记忆，！parffifb1thenS01elseski pg;. . . ;fifbnthenS0nelseskipggpar-iff <$b1;S1<$;. .. ;bn;Sng：pt s;l！pts0;l0，！par-iffb1;S01;.. . ;bn;S0ngpar-if两个线程访问一个位置（其中一个线程在该位置写入）而不同步称为数据竞争。这一类别的研究方向集中在数据竞争检测[15]。多线程程序的分析-S：不好 意 思 ！ pts0;l0[lS0对fSg：不，不 ！我不知道你在说什么！par-对于fS0gpar-为在存在弱内存一致性模型的情况下，S1：不好 意 思 ！ 你说0 0;l00！S01 S2：00分;100分 ！我不知道你在说什么！S02S1;S2：不好 意 思 ！我不知道你在说什么！S01;S02阿塞克河包含在一个线程中的写语句被其他线程以相同的顺序观察。然而，这种模型简化了硬件层面的一些问题这个方向的工作学生：不好意思，我不 去 ！我不知道你在说什么！S0t Sf：不好意思;l！我不知道你在说什么！S0fifbthenStelseSf：pts;l[FVb！我不知道，我不知道！如果b那么S0telsegS0fðifÞ类似于[5]，旨在克服使用简单一致性存储器模型的缺点。在上述第二类中，l/410[F V V]b=1 0 0 0 0; 我不知道！S0t而b做St：;l！我不知道，我不知道！whilebdoS0tðwhlÞ研究方向。一个这样的方向是使用对线程不敏感的分析技术来分析多线程亲，01;l01 我的天啊！S0分2秒;l2分6秒0分2秒;l02秒eS：不 好 意 思 ！我不知道你在说什么！S0在优化程序时，重要的是要保证，如果(a)原始程序和优化程序以类似的状态执行，并且（b）原始程序在一个状态（而不是中止）结束，则（a）优化程序也不中止事实上，这是由以下定理保证的。定理4. （声音）假设的S：（pts，l）fil（pts0，l0）WS0和c~（pts，l）c*. 然后克[18，24]。尽管对带宽不敏感的技术不是很精确，但某些应用程序可以承受。其技术扩展到涵盖多线程程序的程序分析的示例是代码运动[11]，常量传播[14]，具有复制入和复制出内存语义的多线程程序的数据流[10，17]，以及并发静态单赋值形式[13]。上面提到的几乎所有工作的问题是，它不适用于指针程序。更确切地说，对于某些工作，只有当我们有输入指针程序的指针分析结果时，应用程序才是可能本文提出的优化多线程程序的技术具有比上述优化技术更简单和更可靠的优点，1. 如果S：c[c0]，则存在状态c0使得在指针分析的存在下工作ωS0：C！ c0和c0~00c0.0ωω[医]前列腺素6.2. 指针分析2. 如果S：cω！c0且S在c处不中止，则存在a状态C0ω使得S：c[c0和c0~最大值0;最大值0。顺序程序的指针分析已经被广泛研究了几十年[7]。一种将工作分类的方法是这个定理的证明是通过归纳法的结构的类型推导，它顺利地从定理3。更确切地说，定理3在S0=S时使用. 当S0=skip时，我们取1中的c0¼cω。 我们注意到，定理