可在www.sciencedirect.com在线获取理论计算机科学电子笔记279（1）（2011）3-17www.elsevier.com/locate/entcsCOSTA价值分析中非线性运算的处理迭戈·阿隆索a 普里阿里纳斯a Samir GenaimaaDSIC，马德里康普顿斯大学（UCM），西班牙摘要在不同的程序点上推断程序变量（值）之间的精确关系对于终止和资源使用分析是必不可少的。在这两种情况下，这些信息都被用来合成排名函数，这些函数暗示程序的终止和限制其循环的迭代次数。为了效率，通常将值分析基于非析取抽象域，例如多面体、八角形等。虽然这些域是高效的，并且能够为广泛的一类程序推断复杂的关系，但它们通常不足以对非线性和位算术运算的结果进行建模。通过使用更复杂的抽象域，可以精确地对这些操作进行性能开销。在本文中，我们报告的价值分析的COSTA是基于将非线性操作的析取性质编码到（抽象）程序本身的想法，而不是使用更复杂的抽象域。我们的实验表明，COSTA是能够证明终止和推断界限的资源消耗的程序，不能处理之前。关键词：资源使用分析，价值分析，非线性运算，位算术运算1引言命令式语言的终止和资源使用分析受到了相当大的关注[3，22，20，8，19，13，14]。大多数这些分析依赖于值（或大小）分析组件，其推断在不同程序点处的程序变量的值（或相应数据结构的大小）之间的关系。然后，该信息用于限制程序循环的迭代次数。因此，价值分析的精度直接影响（终止）程序的类别，相应的工具能够证明终止或推断其资源消耗的上下界。此外，在资源消耗的情况下，它还影响推断边界的质量（即，有多紧）。通常，为了效率，在价值分析中使用的底层抽象域基于线性约束的合取，例如，多面体[10]，八角形[18]等。虽然在实践中，这些抽象域足够精确，可以限制许多程序的循环，但当所考虑的程序1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.0024D. Alonso等人理论计算机科学电子笔记279（1）（2011）3涉及非线性算术运算（乘法、除法、位算术等）。这是因为这些操作的语义不能仅用线性约束的合取来精确建模。为了克服这个限制，可以使用支持非线性约束的抽象域，但是，这些域通常会带来显著的性能开销。另一种选择是使用析取抽象域，即，线性约束的析取（合取）。这允许将相应的非线性操作的行为分成几个相互排斥的情况，使得每一个可以仅使用线性约束的合取这种替代方案也会带来性能开销，因为这种析取抽象域的操作通常更昂贵。在本文中，我们开发了一个值分析，处理非线性算术运算使用析取（合取）线性约束。然而，与[21]类似，我们不是直接使用析取抽象域，而是直接在（抽象）程序中编码非线性运算的析取性质。这允许使用非析取域，如多面体、八角形等，并且仍然受益于析取信息，以便为具有非线性算术运算的程序推断更精确的关系。我们已经实现了我们的分析在COSTA，成本和终止分析Java字节码的原型。前-对文献中典型例子的实验表明，来处理以前无法处理的非线性运算程序。本文的其余部分组织如下：第2节简要介绍了我们开发分析的中间语言（Java字节码程序自动翻译为这种语言）;第3节介绍了我们用于处理非线性算术运算的技术;第4节描述了我们的价值分析的不同组成部分;第5节介绍了使用COSTA的初步实验评估;最后，我们在第6节结束。2一种简单的命令式中间语言我们对一个简单的基于规则的命令式语言[1]进行了分析，它在本质上与字节码的其他表示类似[23，16]。为了简单起见，我们考虑[1]中提出的语言的一个子集，它只处理整数上的方法和算术运算在实现中，我们处理完整的顺序Java字节码。基于规则的程序P由一组过程组成。一个过程p有k个输入向量ntsx<$=x1， .. . ，x，k和m输出矩阵ntsy′=y1， . ，ym由一个或多个保护规则定义。规则遵循以下语法：规则：：=p（x<$，y<$）<$g，b1， .. . ，bng：：=true|e1ope2|g1和g2b：：= x：=e|x：=e−e|x：=e+e|q（x<$，y<$）x：= ee|x：= e / e|x：= eremx：= e ⊗e|x：= ee|x：= ede|x：= eaee：：= x|n操作：：=>|<| ≥| =|=D. Alonso等人理论计算机科学电子笔记279（1）（2011）35intm（intpublicintfindDuplicate（ intfindDuplicate）{int int sum =1;int = 0;如果（b> 1）{而 （y x）{m（mx，bx，mrx）←y：=1，z：=0，m1（nx，b，y，z n，nrn）.m1（nx，b，y， zn，nrn）←m2（nx，b，y， zn，ny，zn）←y ≥x。m2（nx，b，y， zn，ny2，z2n）←y x， z1：=z +1， 1，Ⓧ1 y1：=y b，m2（nx，b，y1，z1n，ny2，z2n）.返回 z;}m2（nx，b，y，z n，ny1，z1n），r：=z 1.Fig. 1. Java程序及其中间表示。 方法m计算[log b（x）]|.其中，p（x<$，y<$）是规则的头;g是规则的边，它规定了规则适用的条件; b1，. b在规则的主体中;n是整数;x和y是一个值，而dq（x<$，y<$）是一个由y值调用的参数。 算术运算f和rem分别指整数除法和余数。 它们具有字节码指令idiv和irem的语义[17]。运算、、a和d分别指按位AND、按位OR、左移和右移。它们具有字节码指令iand、ior、ishl和ishr的语义[17]。我们忽略了这些指令的过度行为，支持它们是留给未来的工作。这种语言的主要特点是：（1）递归是唯一的迭代机制，（2）警卫是唯一的形式的条件，（3）没有操作堆栈，（4）规则可能有多个输出参数，这对我们的转换是有用的。从Java字节码程序到基于规则的程序的转换分两步进行。 首先，建立控制流图（CFG）。其次，为CFG中的每个基本块定义一个过程，并通过将其元素视为额外的局部变量来简化操作数堆栈。基于规则的程序的执行模仿标准字节码[17]。过程中的多个输出参数来自于将循环提取到单独的过程中（参见例2.1）。为了简单起见，我们假设程序中的每个规则都是以静态单赋值（SSA）形式给出的[5]。示例2.1图1描述了Java代码（左）和我们运行示例的相应中间表示（右）。请注意，我们的分析是从字节码开始的，这里显示的Java代码只是为了清楚起见。过程m由一个规则定义，它接收x和b作为输入，并返回r作为输出，即，r对应于Java方法的返回值。规则m对应于Java方法的前两条指令，它将局部变量y和z赋值，然后将控制传递给m1。过程m1对应于if语句，由两个互斥规则定义。第一个在b≤ 1时应用，并在输出变量r中返回z的值。当b> 1时应用第二个方法，它调用过程m2（循环），从m2退出时返回6D. Alonso等人理论计算机科学电子笔记279（1）（2011）3m（mx，bx，mrx）←{y=1}，{z=0}，m1（nx，b，y，zn，nrn）.m1（nx，b，y，zn，nrn）←m2（nx，b，y，zn，ny，zn）←{y≥x}。m2（nx，b，y，zn，ny2，z2n）←{yx}，<{z1=z+1}，{b≤1}，{r = z}。m1（nx，b，y，zn，nrn）←{b>1}，m2（nx，b，y，zn，ny1，z1n），{r = z 1}。Ⓧ1 {y1=T}，m2（nx，b，y1，z1n，ny2，z2n）.图二. 图1的程序的抽象编译输出变量r中z1的值。注意z1是指退出过程m2（循环）时z的值，它是由SSA转换生成的。过程m2对应于while循环，由两个互斥规则定义。第一个是当循环条件被评估为false时应用的，第二个是当它被评估为true时应用的。注意m2有两个输出变量，它们对应于退出循环时y和z的值3激励的例子证明图1的程序终止，或者推断其资源消耗的下限和上限（例如，执行步骤的数量），需要限制其循环可以进行的迭代次数。 限制数量-循环的迭代次数通常通过从程序中找到函数f来状态到良基域，使得如果s和SJ是对应于两个连续迭代的两个状态，则f（s）>f（SJ）。传统上，这个函数被称为ranking function[11]。注意，对于终止，足以证明存在这样的函数，而推断资源消耗的界限需要综合这样的排序函数。对于图1的程序，如果程序stat是由t_x，b，y，z_x_y_x，b，y，z_y_x，b，y，z_y_ 此外，该函数可以进一步细化为f（x，b，y，z）=log2（nat（x-y）+1），为了推断循环资源消耗的界限，该函数更准确。在本文中，我们遵循[1]中使用的分析方法，该方法将值分析分为几个步骤：（1）抽象编译[15]步骤，生成程序的抽象版本，用抽象描述替换每条指令（例如，（2）一个定点计算步骤，计算程序的抽象语义;（3）在最后，我们使用点1的抽象程序和点2的抽象语义在图1的程序上应用第一步，得到抽象程序D. Alonso等人理论计算机科学电子笔记279（1）（2011）37∗∗∗图2。可以观察到，线性算术指令由其对应的抽象版本精确地描述。例如，z1：=z +1更新z1以保存z + 1的值，及其对应的抽象版本{z1 = z + 1}是一个表示法，它声明z1的值等于z加1的值。然而，在非线性算术指令的情况下，抽象描述经常丢失有价值的信息。 这是指令y1：=y b的情况，在图1和图2中均用“1”注释。虽然指令更新日期为y1至保持y的值，它的抽象描述{y1=T}指出y1可以取任何值 这里T被解释为任何整数值。 这使得不可能限制循环的迭代次数，因为在抽象程序中函数f（x，b，y，z）=nat（x−y）d oes不会在每次chtwo召唤迭代中减少。在不知道y和b的值的情况下，约束{y1=T}为：实际上，当只允许线性约束的合取时，对y 1：=y b的最佳描述。然而，在图1的程序中，保证y的值为正，b的值大于1。 使用此上下文信息，y 1：= y b的抽象可以改进为{y 1≥2y}，这又允许对排名函数f（x，b，y，z）=nat（x-y）及其精化f（x，b，y，z）=log2（nat（x-y）+1）进行合成。 这表明，当只允许线性约束的合取时，抽象编译可以从上下文信息中受益。然而，抽象编译的本质是只使用语法信息，显然上下文信息并不总是通过对程序的语法分析来获得。当抽象非线性算术指令时，解决精度损失的一种方法是允许使用线性约束的析取。例如，指令y1：=y b可以被抽象为1···n，其中每个i是描述可能场景的线性约束的合取。例如，在一个示例中，我们可以有<$j={y≥1，b≥2，y1≥2<$b}，以便处理y≥1和b≥2的情况。然后，在定点计算过程中，当上下文可用时，将自动选择适当的fixpointi然而，出于效率的原因，我们将我们的价值分析限制为仅使用线性约束的合取为了避免使用析取约束，类似于[21]，我们遵循将析取信息编码到（抽象）程序本身中的方法。例如，m2的第二个规则可以抽象为：m2（x，b，y，z，y，y），z2）←op（a，b，c）←{a=0，c=0}.op（a，b，c）←{a=1，c=b}.{y>|X|， q=0，r=x}。2博士−y}。Xop（x，y，q，r）<${−x>−y>1，0q≤− ， y−y > 1，− ≤q<0，0≤r<博士op（x，y，q，r）←{2博士2Xx> y> 1，0y>1，≤q<0，−y y >1，则x/y是小于或等于x的正数，并且xremy是小于的非负数。y. 当输入值在每次迭代中至少减少一半时，该规则对于合成对数排序函数也是必不可少的请注意，我们忽略了x = MIN VALUE和y= −1的特殊情况，因为这是一种过流行为。乘法。 辅助抽象过程op_abstract定义如下：10D. Alonso等人理论计算机科学电子笔记279（1）（2011）3←o pao（x，y，a，）.←o pao（x，y，，o）.⊗⊕op（x，y，y）op（x，y，a）opao（x，y，a，o）←{x=0， a=0， o=y}. opao（x，y，a，o）←{x=−1， a=y，o=−1}. opao（x，y，a，o）←{x=y，a=x，o=x}.opao（x，y，a，o）<${x>y>0，0≤a≤y，o≥x}.opao（x，y，a，o）<${x>0， y<−1，0≤a≤x，y≤o≤−1}。opao（x，y，a，o）←{x 0，0 <|S|<2，z≥ 2x}。55¢op（x，s，z）←{x<0，0 <|S|<2，z≤ 2x}。5¢op（x，s，z）←{x > 0，|S|≥2，z≥x}。5¢x<0，|S| ≥ 2，z≤x}。op（x，y，z）←{x=0， z=0}.op（x，y，z）←{x=1， z=y}.∗op（x，y，z）←{x=−1， z=−y}.∗op（<$x，y<$，<$z<$）<${x≥2， y≥2， z≥2<$x，z≥2<$y}.∗op（<$x，y<$，<$z<$）<${x≤−2， y≥2， z≤2<$x，z≤−2<$y}。∗op（<$x，y<$，<$z<$）<$<${x≤−2， y≤−2， z≥−2<$x，z≥−2<$y}。∗∗我们省略了那些可以通过交换参数x和y.在这个抽象中，我们区分了x = 0（恒定性）、x= ±1（相等性）和|X|> 1且|y|> 1（进展）。注意，例如，后置条件z≥2x对于为图2中的循环找到对数排序函数是必不可少的。例如，如果我们使用较弱但合理的后置条件z> x，则不可能合成这样的排名函数。按位的和。辅助抽象规则OP和op⊕ 被定义为《奥普法》条款如下：由于这些操作是可交换的，我们省略了通过交换输入参数可导出的规则前两个规则描述了x = 0和x= −1的情况，即，所有位分别为0或1的向量。第三条规则处理x = y的情况。其余的规则是基于xy的结果比x或y的1位数少，而xy的结果比x或y的1位数多。左右移动 虽然Java字节码中的移位操作接受任何整数值作为移位操作数，但移位位置的数量仅由五个最小有效位确定，即，它是一个介于0和2 5− 1之间的值（对于long类型它由六个最低有效位确定）。对于左移操作a，辅助抽象过程op<$定义如下：⊗D. Alonso等人理论计算机科学电子笔记279（1）（2011）311¢Q我op<$（nx，sn，nzn）←{x=0，z=0}.op<$（x，s<$，z<$）<${x=−1，z=−1}.op<$（nx，sn，nzn）←{s=0，z=x}.op（x，s，z）←{¢op（x，s，z）←{x > 0，0<|S|<2，x > z，x≥ 2 z，z≥0}。55¢op（x，s，z）←{x<−1，0 <|S|<2，x − 1 ≤ 2 z，z<0}。5¢op（x，s，z）←{x > 0，|S| ≥ 2，0 ≤z≤x}¢x<0，|S|≥ 2，x≤z≤ −51}}。当移位操作数s满足0≤0时，上述规则提供了一个精确的后置条件。|S|<25岁。在最后两个抽象规则中，后置条件分别是z ≥ x和z ≤ x，因为我们无法观察到s的前五位的值，|≥ 2 5。|≥ 2 5. 类似地，对于右移操作d，辅助抽象规则op为定义如下：请注意，当程序包括几个用于相同操作的非线性指令时，为它们生成不同的辅助抽象过程可能会很有用，例如，op1，op2等。这主要是在调用∗ ∗这些指令的上下文是不相交的，因此将它们的辅助抽象过程避免了合并调用上下文，这通常会导致精度损失。此外，不影响程序终止的非线性算术指令可以像以前一样被抽象，即，到{x=T}，从而避免了不必要的辅助抽象过程引起的性能开销这些指令可以使用依赖性分析来识别，类似于[4]中所做的识别程序变量的方法。4.2不动点算法算法1使用[7]风格的自顶向下策略实现价值分析 它接收一个抽象程序P α和一组初始前置条件E作为输入，并计算P中每个过程的前置和后置条件（分别存储在表PRE和POST中）。前条件PRE[q（x<$）]的含义是，当调用q时，条件成立;后条件POST[q（x<$，y<$）]的含义是，当退出q时，条件成立。过程修复将事件队列Q定位到Q1（L2），将表PRE和POST的元素定位到false（L4和L5），通过为每个元素调用ADD_PRE（L6）来处理初始先决条件E，这又将相应的事件添加到Q，然后在while循环中处理Q的事件，直到没有更多的事件可用。在每次迭代中，从Q中删除事件q（过程名称）（L8），并按如下方式处理：检索q的当前前置条件f（L9），评估q（L11），所有的后置条件都被联合成一个元素δ（使用底层抽象域的最小上界H），最后通过调用ADDpOST将δ作为q的后置条件添加。请注意，对ADDpOST的调用可能会向.规则的评估（过程）在评估期间）w.r.t.一个前置条件处理规则体B中的每个bα12D. Alonso等人理论计算机科学电子笔记279（1）（2011）3我我我我我算法1定点算法1：程序固定点（Pα，E）2：Q=0;3：对所有q（x<$，y<$）∈P，4：PRE[q（x<$）]=false;5：POST[q（x<$，y<$）]=false;6：对所有的p（x<$），p∈E都加pRE（p（x<$），p）;7：而Q. 不需要8：q= Q。return（）;9：q=PRE[q（x<$）];10：δ=false;11：对所有q（x<$，y<$）<$Bα∈Pα做δ=δHEVALUATE（q（x<$，y<$）<$Bα，β）;12：ADDpOST（q（x<$，y<$），δ）;13：函数EVALUATE（q（x<$，y<$）<$Bα，B α）14：对于所有bα∈Bα，15：如果bα），则16：加上pRE（qJ（w<$），q<$w<$. （c）;17：=HPOST[qJ（w<$，z<$）];18：否则，n=nHbα;19：返回"x“”y“”。（c）20：procancerADDprRE（q（x<$），q）21：q=PRE[q（x<$）];22：如果是|那么23：PRE[q（x<$）]=nH;24：Q. return（i）;25：procancelADDpOST（q（x<$，y<$），q）26：δ=POST[q（x<$，y<$）];27：如果δ|那么28：POST[q（x<$，y<$）]=δH;29：对于所有p∈P，30：如果p调用q，则Q。return（p）;如下：如果bα是一个调用qJ（w<$，z<$），那么它通过调用ADD_p_RE（L16）来注册相应的前置条件，并将q的当前后置条件添加到（L17）;否则，bα是一个约束，它简单地将其添加到（L18）。过程ADD_p_RE为q添加一个新的前置条件，如果它不隐含当前的前置条件，并将相应的事件添加到Q。过程ADDpOST为q添加一个新的后置条件（如果它不隐含当前后置条件），并为所有调用q的过程添加事件，因为它们可能必须重新分析。请注意，这两个过程都使用底层抽象域的最小上界H，以便将新的前置或后置条件与当前条件连接起来还要注意的是，由于我们使用具有无限上升链的抽象域，在实践中，这些过程包含了一个加宽运算符，以确保终止。D. Alonso等人理论计算机科学电子笔记279（1）（2011）313∗∗1n我我我n=PRE[q（x<$）]ngφ（b1）···例4.1再次考虑图2的抽象程序，其中m2的第二个抽象规则被替换为m2（nx，b，y，zn，ny2，z2n）←{1， y≥ 2}，1}，以及POST[op_（b，y_（b，y_1））]={y_1≥2_y}。4.3包围循环在本节中，我们描述如何使用抽象程序以及前置和后置条件来绑定程序简单地说，对于每个抽象规则p（x<$，y<$）<$gα，bα， . ，bα∈Pα，我们生成一组跃迁.. i∈[1， .. . ，n]，bα=q（w<$，z<$），np（x）→q（w），好吧我α α α其中x是w。是f在变量x上的投影; φ（b α）= b α，如果b α是一个约束;和φ（bα）=POST[bα]，如果bα是一个调用。然后，所有转换的集合我我我例如，传递给[2]的工具，该工具进而推断用于对应的循环。例4.2使用例4.1的抽象规则和前置条件和后置条件，我们生成转换关系m2（其中n={z≥ 0，y≥ 1，b≥ 2，xy，z1 =z+ 1，y1≥ 2<$y}。然后，[2]的求解器推断预期的排名函数，如第3节所述。5实验评价我们已经在COSTA[3]的上下文中实现了第4节中描述的价值分析的原型。我们已经进行了一些实验，从文献中使用非线性和位算术运算的典型例子。基准点可在www.example.com上获得http://costa.ls.fi.upm.es/papers/bytecode2011。不幸的是，这个实现不能通过COSTA的web接口进行测试，因为它还没有集成到主分支中COSTA通过新的价值分析，能够证明所有基准的终止。请注意，如果没有这种价值分析，COSTA将无法处理这些基准测试。我们还使用其他Java字节码终止分析器分析了基准测试。[22]第23话无法证明任何一个人的存在1使用在线版本http://julia.scienze.univr.it/14D. Alonso等人理论计算机科学电子笔记279（1）（2011）3⊗这些基准。AProVE2 [12]不能证明具有位算术运算的程序的终止，但可以处理具有非线性算术运算的程序，例如乘法和整数除法，除了图1的程序，它不能在5分钟的时间限制内完成证明。在下文中，我们解释了我们对一些基准的分析结果例5.1我们从[9]中借用的一个例子开始：虚空int（ x）{while（x>0）x= X &x−1;}和（x，x）←和1（x，x）。 且1（nxn，n x）←{x≤0}。和1（x，x）←{x>0}，{y=x− 1}，op（x，y，x1），和1（n×1n，n）。右边的代码是Java方法的相应中间表示的抽象编译 为了限制迭代次数，在while循环中，重要的是推断x的值在每次循环中减小。当单独考虑指令x=x x−1时，这不能保证&，因为例如，当x=0时，它不会减少。我们的分析推断前置条件PRE[op⊗（x，y）]={y=x−1，x> 0}，即，上下文x>0是可用的。能够在调用操作符时，这反过来又使得推断后置条件成为可能POST[操作⊗（<$x，y<$，<$x1<$）]={y=x−1， x>0，0≤x1≤x−1}。你说出这个消息-我们可以生成跃迁和1（x）→和1（x1），{x>0，0≤x1≤x−1}为此，我们设计了排序函数f（x）=nat（x）。例5.2下一个例子实现了计算两个自然数的最大公约数的欧几里德算法。它取自Java字节码终止竞争数据库3：intgcd（int本发明公开了一种复合材料，int（b）int tmp;while（b> 0 a> 0）{tmp= b;b = a % b ; a= tmp;}返回 a;}gcd（a，b，r）←gcd1（a，b，r）. gcd1（a，b，a）<${a≤0}.gcd1（a，b，a）<${b≤0}. gcd1（a，b，r）←{a >0，b > 0}，{tmp=b}，oprem（a，b，b1），{a1=tmp}，gcd1（a1，b1，r）。cOSTA在2010年7月的竞赛中未能证明该程序的终止，主要是因为它在抽象b=a % b时忽略了调用上下文，因此无法推断b减少。我们的分析推导出了预条件PRE[oprem（a，b）]={a>0， b>0}，从而使我们有可能推导出p_（op rem（a，b））={ a >0，b>0}。2使用在线版本http://aprove.informatik.rwth-aachen.de/3http://termcomp.uibk.ac.atD. Alonso等人理论计算机科学电子笔记279（1）（2011）3152我条件POST[oprem（a，b，b1 ）]={a>0， b>0， b>b1}。 使用该信息，我们生成转换{gcd1（a，b1）→gcd1（a1，b2），{a>0， b>0， b>b1}}，对于该转换，我们生成排序函数f（a，b1）=nat（b）。例5.3下一个例子取自java.lang. java类的toString（inti，int radix）方法。 它用于在任何数字基数中写入数字。为了简单起见，我们删除了不检查终止的代码，并使用我们的分析推断出的先决条件注释了循环//{i<=0，2<=基数}而（i） <= −radix）{i = i / r a d i x ;}p（i，radix i，r adixi）←{i>−radix}. p（n，radixn，n）←{i≤ −radix}，o p/（i，radix，i1），p（i1，radix，i）.由于预条件PRE[op/（i，radix，i1）]={2≤radix， i≤−radix}，我们的分析推断出预条件POST[op/（i，radix，i1）]={2≤radix，i≤−radix，i≤i1<0}。 使用这个后置条件，我们生成转换p<（ F或此转换我们将排序函数f（nat（−i）+1）合成为log2（nat（−i）+1）。例5.4下一个例子是toUnsignedString（inti，int shift）方法中的一个循环的变体，它用于以二进制、八进制或十六进制形式写入一个数字：//{1<=移位<=4}而 （我 >0个 ）的第一个字符。联系我们 s h i f t;}p（i，shifti，shifti）←{i≤0}.p（i，shifti，shift i）←{i >0}，op<$（ni，shiftn i，ni1ni），p（ni1，shiftni，ni1）.由于预条件PRE[op<$i，shift<$i] ={i >0，1≤shift≤4}，我们的分析推出了预条件POST[op<$i，shift<$i，shift1<$i]={i>0，1≤shift≤4，i≥ 2<$i1，i1≥ 0}.使用这个postcontidion，我们生成转换证明了p（ni，shiftn）→p（ni1，shiftn），{i>0，1≤shift≤4， i≥2ni1，i1≥0} n的秩函数f（ni，shiftn）=10g2（nat（i）+1）.6结论在本文中，我们已经描述了我们如何处理非线性算术指令的价值分析的COSTA。众所周知，当底层抽象域只允许使用线性约束的结合时，处理这样的操作是有问题的。众所周知，使用析取抽象域是解决这个问题的一种可能的方法，但代价是性能开销。在本文中，我们不使用析取抽象域，而是将非线性算术指令的析取性质编码到抽象程序本身中。这种编码，当与价值分析相结合时，16D. Alonso等人理论计算机科学电子笔记279（1）（2011）3非析取抽象域（例如多面体或八角形）使得可以根据到达对应于编码的代码的上下文来动态地选择最佳抽象。我们的实验表明，COSTA现在能够证明终止和推断约束的资源消耗的程序，它不能处理之前。在未来的工作中，我们计划提高分析器的可扩展性，支持算术运算中的超浮点运算，并支持浮点运算。注意，考虑到Parma多面体库[6]的最新发展，支持过流和过点算法相对简单。确认这项工作的部分资金来自欧盟委员会的信息通信技术计划，未来和新兴技术（FET），ICT-231620HATS项目，西班牙科学和信息部（MICINN）的TIN-2008-05624DOVES项目，HI 2008 -0153（Acci'onIntegrada）项目，UCM-BSCH-GR58/08-910502ResearchGroup 和 马 德 里 地 区 政 府 的 S2009TIC-1465PROMETIDOS项目。迭戈阿隆索是部分支持UCM博士奖学金计划。引用[1] E. Albert，P. Arenas，M. Codish，S. Genaim，G. Puebla和D. 扎纳迪尼 Java字节码的终止性分析在Gilles Barthe 和 Frank de Boer ， 编 辑 ， IFIPInternational Conference on Formal Methods for OpenObject-based Distributed Systems（FMOODSSpringer-Verlag，柏林[2] E. Albert，P.Arenas，S.Genaim和G.普埃布拉静态成本分析中的封闭式上限Journal of Automated Reasoning，46（2）：161[3] E. Albert，P. Arenas，S. Genaim，G. Puebla和D. 扎纳迪尼 COSTA：Java字节码开销和终止分析器的设计与实现。在第六届组件和对象的形式化方法国际研讨会（FMCOSpringer，2007年。[4] E. Albert， P. Arenas， S. Genaim ， G. Puebla和 D.扎 纳 迪 尼 Java字 节 码 开 销 分 析 中 无 用 变 量 的 去 除ACMSymposium on Applied Computing（SAC）- Software Verification Track（SV 08），第368北京：人民出版社[5] A. W. 阿佩尔 SSA是函数式编程。 SIGPLAN Notices，33（4）：17[6] R. 巴尼亚拉山口M. Hill和E.再见 帕尔马多面体图书馆：走向一套完整的数字抽象的分析和验证的硬件和软件系统。Quaderno457，Dipartime ntodiMatematica，Uni versi t'adiParma，Ital y，2006. 可以在 www.example.com 上 http://www.cs.unipr 。 it/Publications/.还 公 布 为 arXiv ：cs.MS/0612085，可从http://arxiv.org/。[7] 迈克尔·科迪什有效目标导向的逻辑程序自下而上评价。J. Log.程序. ，38（3）：355[8] B. 库 克 A. Podelski 和 A. 雷 巴 琴 科 系 统 代 码 的 终 止 性 证 明 。 在 Proc. ACM SIGPLAN Conference onProgramming Language Design and Implementation（P
我的内容管理
展开
