83《理论计算机科学电子札记》65卷第2期（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html17页通过比较检查克拉拉·哈拉米略县计算机科学美国匹兹堡查塔姆学院拉吉夫·古普塔部美国亚利桑那大学图森分校计算机科学系玛丽·卢·苏·阿·部计算机科学匹兹堡大学匹兹堡，美国摘要我们提出了一种新的技术，称为比较检查，帮助优化程序编写者调试优化器的测试，对于给定的输入，程序的语义不改变的应用程序的优化。我们已经成功地将比较检查应用于一大类程序转换，这些程序转换改变了（1）中间代码语句计算值的相对顺序，(2)中间代码语句的形式;（3）使用代码复制的控制流结构。我们概述了导致比较检查自动化的关键步骤。然后描述了比较检查在测试给定程序输入的高级循环变换、低级代码优化和全局寄存器分配的实现中1介绍随着编译器越来越多地依赖优化来实现高性能，调试优化代码的技术继续动摇。调试优化代码的问题是双重的，因为优化程序中的错误可能源于源程序或由优化器引入。因此，必须开发工具来帮助应用程序进行优化调试c2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。哈拉米略、古普塔、索法84生成未优化的程序。代码和优化器编写者调试优化器。在本文中，我们专注于为优化器作家开发的工具。特别是，我们提出了一种新的技术，称为比较检查，帮助优化器的作家调试优化器测试，对于给定的输入，程序的语义不改变的应用程序的优化。比较检查器，如图1所示，对于给定的输入，自动orches-executing源程序的未优化和优化版本的执行，并比较它们的语义行为。未优化或优化程序相对于源程序的语义行为的特征在于由未优化或优化程序中的源级语句针对所有可能的输入计算的输出和值。因此，通过检查（1）在两个程序中执行相同的路径，（2）对应的源级别分配计算相同的值和引用（即，读、写）对应的位置，以及（3）输出相同。在两个版本中，对给定输入的输出和由源级赋值语句和分支谓词计算的值进行了比较。此外，对于通过数组和指针进行的赋值，要进行检查以确保赋值的地址彼此对应。除了那些在优化代码中没有计算的死值之外，所有与源代码级变量相同的值都比较不成功比较成功Fig. 1. 比较检查系统。如果语义行为与源程序相同且正确，则优化后的程序可以以高置信度运行。另一方面，如果语义行为不同，比较检查器将显示导致不同的语句以及应用于这些语句的优化。我们的检查方法允许系统定位最早的点，其中未优化和优化的程序在它们的语义行为上相对于源程序不同。例如，检查器检测执行期间的最早点，此时对应的源级别语句实例应该但不计算相同的值。因此，检查器可以检测到优化不正确的语句，并随后计算出不正确的值。优化器编写器可以使用此信息来定位优化程序中的错误代码，并确定是什么转换生成了错误代码。生成优化的程序。比较检查器执行未优化和优化的程序，并对给定的输入进行比较。使用有关语句和与失败检查相关的优化的信息来定位优化程序中的错误。哈拉米略、古普塔、索法85源程序来源Source程序程序程序代码生成器代码生成器UOPT检查OPT1检查OPT2检查OPT3图二. 分阶段比较检查。比较检查的应用可以分几个阶段进行例如，如图2所示，优化任务可以分为三个阶段：高级转换、低级优化和全局寄存器分配。在每个比较检查步骤中，比较一对程序版本，以确定给定的优化阶段是否保留程序的语义。如果比较检查失败，这种方法会将优化器编写者的注意力集中到包含错误的部分。 如果我们简单地比较未优化和完全优化的程序，并且比较检查失败，那么优化器编写者必须将优化器的所有三个部分都视为可能的错误源。本文的其余部分组织如下。在第2节中，我们描述了处理循环转换以及低级代码优化的比较检查方案。在第3节中，我们提出了我们的比较检查方案的全局寄存器分配的概述。在第4节中，我们给出了一些实验结果。我们将我们的方法与第5节中的相关工作进行了比较，并在第6节中进行了总结。2循环转换和代码优化我们的方法处理使用一大类代码优化的代码优化，其特点是在他们的程序代码上的效应如下。变换可以改变中间代码语句计算值的相对顺序（例如，基于部分冗余和部分死代码消除的代码移动），中间代码语句的形式（例如，常数传播和重新关联），以及使用代码复制的控制流结构（例如，函数内联和循环变换循环变换循环变换低级优化低级优化全局寄存器分配哈拉米略、古普塔、索法86循环展开）。为了使比较检查自动化，我们必须（1）确定两个程序计算的哪些值需要相互比较，（2）确定在程序执行中执行比较的位置，以及（3）执行比较。为完成这些任务，利用了以下三个信息来源：(1) 地图。为了比较在未优化和优化程序中计算的值，我们需要确定应该计算相同值的相应语句实例。如果未优化程序中的语句实例和优化程序中的语句实例计算的值应该相同，并且后者是通过应用某些优化从前者导出的，则可以说这两个实例是对应的我们的映射将未优化程序中的语句实例与优化程序中的相应语句实例相 在[8]中，我们开发了一种映射技术来识别相应的语句实例，并描述如何生成支持经典优化和循环转换优化的映射。(2) 注释。映射用于为未优化和优化的程序自动生成注释，该注释引导COM检查器比较相应的值和地址。当到达具有注释的任一程序版本中的程序点时，比较检查器执行与该点处的注释相关联的动作。注释标识程序点，在这些程序点处应执行比较检查或其他活动以启用检查。引入断点来提取值并激活与未优化和优化程序中的程序点相关联的(3) 价值池。由于要比较的值在未优化和优化的代码中并不总是以相同的顺序计算，因此一种机制保存了早期计算的值。这些值保存在值池中，并在不再需要时删除。注释用于指示值是否应该保存在值池中或从值池中丢弃比较校验算法未优化程序的执行驱动优化程序的检查和执行。因此，执行从未优化的代码开始，并继续执行，直到到达断点使用未优化代码中的未优化代码中具有比较检查注释的程序点处的断点指示应检查由某语句计算的值。此外，默认情况下，未优化代码中没有关联注释的程序点处的断点指示应检查最近执行的语句计算的值。如果要检查某个值，则优化程序将一直执行，直到计算出相应的值（如比较所示哈拉米略、古普塔、索法87检查注释），此时对两个值执行检查。在优化程序的执行过程中，\early”（即，尚未计算未优化代码中的对应值）被保存在值池中。如果遇到延迟比较检查注释，指示在当前点不能执行对由未优化程序计算的值的检查，则保存该值以供将来检查。检查器继续交替执行未优化的程序和优化的程序。注释还指示为将来检查而保存的值何时可以以及何时可以从值池中删除值不检查由优化删除的语句实例计算的值比较检查的吸引人的特征之一是它不报告假阳性。这是因为它依赖于精确的动态信息。可以通过运行未优化和优化的程序版本并比较它们的输出来测试优化器。然而，在一个给定的运行，一个典型的程序预计将计算许多最终被丢弃的中间结果。因此，虽然比较检查将在计算这些中间结果时检测到错误，但未优化和优化的程序输出的简单比较将无法检测到相同的错误。例在图3（a）中，示出了未优化的程序和优化的程序版本以及注释。为了便于理解，所示的源代码级语句很简单。应用了以下优化。常量传播--如S20、S30和S110所示，传播S1中的常量1。复制传播-复制S6中的复制M，如S70所示 S100。死代码消除- S1和S6是死后，常数和复制传播。循环不变代码移动- S5被移出双嵌套循环。S10移出内环。部分冗余消除- S9与S8部分冗余。部分死码消除-S10被移出外环。假设所有显示的语句都是源代码级别的语句，并且循环只执行一次迭代。断点用圆圈表示。断点被放置在未优化和优化代码中与注释相关联的程序点以及未优化代码中应执行比较检查的程序点处注：注：哈拉米略、古普塔、索法8838未优化优化未优化代码优化的代码代码跟踪代码跟踪S1 A = 11S2 T1 = A3S3 T1=T1+AS4 T2 = 168S5 M = X * XS6 B = M10S7 IF（B >T2）删除S102S24S55S37S49S711S1检查S2 S2保存S5检查S3S3检查S4S46检查S5与S5检查S7S6S7S2'2S5'4S39S7'删除S10FT10 11S8 C = T2 + X12保存S9S9' C = T2 + XS813检查S8S8保存S8S9S8'1314S9 C = T2 + XS10 D = B + T116S11 T2 = T2 + A17S12 IF（T2 100）19延迟S10不1518S11S1220F检查S9与S8'，S9'删除S8 '，S9'检查S11不检查S1214S1015F不S13 IF（T1 100）2122S13F不勾选S13删除S5FCheckable S102326S14 E = D * 2删除S102725S10' D = M + T1S14' E = D * 228检查S10检查S14S1427S14'28(a) 注释的未优化和优化代码（b）检查跟踪图三. 比较检查方案示例。在虚线框中播放），我们现在描述检查器在该示例中的操作。图3（b）中的轨迹说明了检查器在未优化和优化程序执行之间的切换。跟踪包括执行的语句以及处理注释的断点（圈出）。箭头指示程序之间的切换。注释Check S with S'指示现在是时候将未优化代码中的语句S计算的值与优化代码中的语句S'计算的对应值进行比较。如果注释在优化代码中紧跟着语句S'放置，则注释的with S'部分将被省略。注释Save用于将计算值保存在值池中，而注释Delete用于从值池中丢弃值，因为已经执行了涉及该值的所有检查。一对Delay和Checkable注释由未优化的代码串联使用。Delay注释表示此时无法检查值，因为优化的代码可能还没有计算出该值，而Checkable注释表示现在应该可以检查该值。未优化的程序开始执行S1，并继续执行而不检查S1，因为它已从优化程序中删除。在S2执行之后，到达断点1，并且在S2处计算的值可以在该点处被检查，并且因此优化的程序执行直到检查S2被处理，这发生在断点2处。由S2计算的值16S1117S1219S13212326S1124S10'2524哈拉米略、古普塔、索法89S20比 较了未优化的程序恢复执行，并且S3处的循环迭代开始。在S3执行之后，到达断点3并且优化程序执行直到检查S3被处理。由于必须使用由S50计算的值执行多个比较，因此当到达断点4时，注释SaveS50处理后，由S50计算出的值 存储在值存储器中。优化的代码继续执行，直到断点5，此时处理注释CheckS3。由S3和S30计算的值比较了然后执行S4并检查其值。 S5然后执行并断点8遇到了优化后的程序将一直执行，直到计算出的值byS5可以进行比较，由注释CheckS5与S50表示 在断点9处。保存在值池中的S5的值用于检查。程序继续以类似的方式执行。3全局寄存器分配在本节中，开发了一个寄存器分配检查器，它可以检测寄存器分配器实现中的错误并确定错误的可能原因。该检查器保存不同种类的信息，并利用一组不同的注释来跟踪有关分配给寄存器的变量的信息，并验证在整个优化程序执行过程中使用这些变量的预期值。当不正确地实现寄存器分配技术时，不正确的行为可能包括：使用错误的寄存器，现场注册，从寄存器中逐出一个值但不将其保存以备将来使用，未能从内存加载值，以及使 用陈旧的值。当在寄存器中计算变量的值时，在优化程序中使用变量的旧值，但是优化程序使用存储器中的旧值而不是使用寄存器中的变量的值。寄存器分配检查器可以确定寄存器分配器何时显示这些类型的行为。考虑图4中未优化的C程序片段及其优化版本。假设未优化的程序是正确的，并且寄存器分配被打开，寄存器分配器将变量x、y、z和a分别分配给优化程序中的寄存器r3、r1、r4和r5，并将寄存器r1中的y的值复制到寄存器r2。假设优化后的程序返回错误的输出。使用检查器，在未优化代码的第3行和优化代码的第7行处，在未优化和优化程序的内部行为中检测到差异。检查器指出y在未优化和优化的程序中使用的值不同，并指出r1的使用与y的使用不一致。哈拉米略、古普塔、索法90未优化代码优化的代码1)x = 2 * y...2)z = x +5...3)a = y + y1) 负载r1，y2) 载荷3) mul r3，r1，r2...4) 移动r1，r25)载荷r1，6)添加r4，r3，r17) 添加r5，r1，r18) 存储r5，a在优化程序执行期间较早从R1逐出。检查器还指示y的期望值在寄存器r2中，因此应该使用r2而不是r1。然后，优化器编写器可以使用此信息来调试寄存器分配的实现见图4。 寄存器分配检查的程序示例。寄存器分配检查方案类似于比较检查方案，因为在未优化和优化程序中计算的值都被检查，但是寄存器分配检查方案还比较在两个程序中使用的变量的值，并且跟踪关于在整个优化程序执行期间分配给寄存器的变量的信息。该跟踪信息包括在优化程序的执行的每个程序点(1) 变量值的当前位置(2) 其内存位置保存陈旧值的变量，(3) 寄存器中的值已被逐出的变量，以及(4) 当前分配给寄存器的变量。为了实现这些任务，再次利用映射和注释。比较检查器的映射被扩展到包括未优化和优化中间程序中变量使用之间的对应关系。这些映射是在应用寄存器分配之前生成的，因为两个程序版本之间的对应关系不会因寄存器分配的应用而改变。映射只捕获寄存器分配的影响，而不是其他优化，因为检查是在寄存器分配之前对程序执行的，而在寄存器分配之后对程序执行的。然而，未优化的程序可以包括被假定为正确的其他优化的应用。在应用寄存器分配并由编译器生成代码之后，映射用于自动生成哈拉米略、古普塔、索法91优化的程序，它引导寄存器分配检查器比较相应的值和地址，并跟踪有关变量的信息，这些变量在整个程序执行过程中被分配给寄存器。当达到优化代码中的目标程序点时，与该点处的注释相关联的动作由寄存器分配检查器执行。一个高层次的寄存器分配检查器算法的概念概述，rithm是在图5。该算法类似于比较检查器的算法。断点用于从未优化和优化的程序中提取值以及激活注释。注释指导寄存器分配检查器的操作。然而，由于分配给优化代码中的变量的值是被跟踪和检查的值，所以优化程序的执行驱动未优化程序的检查和执行。因此，执行从优化的代码开始，并继续执行，直到到达断点。 取决于注释，检查器可以跟踪分配给寄存器的变量、逐出的变量和陈旧的变量，和/或确定是否应该在优化代码的当前执行点检查计算或使用的值。当一个值应该被检查时，未优化的程序执行，直到到达相应的执行点，此时对两个值执行检查。检查器继续交替执行未优化和优化的程序。如果比较的值不同，则检查器通知用户不同的可能原因。此外，当值被跟踪时，检查器通知用户任何不一致（例如，加载陈旧值、将非预期值存储到存储器位置等）。一旦检测到变量的值的不一致性，则不一致性通过值的使用传播做执行优化的程序并在断点处处理注释，如果检查注释，则执行未优化的程序，直到达到执行比较检查如果出现错误，则报告错误和错误原因如果注册分配注释或加载注释或存储注释或注册移动注释，则更新寄存器/变量信息验证加载或存储的值是否为预期值，通知用户任何不一致之处endif当优化后的程序尚未执行完毕时图五. 寄存器分配检查器算法。哈拉米略、古普塔、索法92未优化代码优化的代码注释S1）x = 2 *y...S2）z = x +5...S3）a = y +S1’) load r1,yS2’) load r2,2S3’) mul...S4’) move检查y，r1检查/寄存器分配x，r3寄存器移动r1、r2S5’) load负载r1S6'）加上r4、r3、r1检查...S7’) add r5,r1,r1S8’) store检查/寄存器分配z，r4检查y，r1检查/寄存器分配a，r5检查/存储a，r5注释与比较检查技术类似，代码注释指导检查未优化和优化代码中的值。代码注释也用于跟踪变量的值。注释（1）标识应执行比较检查的程序点，以及（2）指示在优化代码中应跟踪和检查变量/寄存器的哪些值。需要五种类型的注释来实现寄存器分配检查策略。在图6中的示例中，说明了与图4中给出的相同的未优化和优化的代码示例，注释显示在虚线框中。(1) 检查v; r注释。 检查V; R注释与优化代码中的程序点P相关联，以指示要执行对寄存器R中变量V的值的检查。 寄存器分配检查器将执行未优化的程序，直到达到等效程序点p。要比较的相应值是优化代码中的v。例如，在图6中，检查注释与状态S10相关联 在优化的代码中，使得将优化的代码中的R1的值与未优化的代码中的Y的值进行比较。检查注释用于检查寄存器加载、存储、使用和赋值。见图6。 注释示例。(2) Registerassign[v;]r注释。寄存器关联注释与优化代码中的程序点相关联，以指示寄存器r的跟踪信息应当被更新。寄存器分配检查器记录先前分配给r的变量被逐出。如果指定了v，则寄存器分配检查器更新其信息以指示r保存变量v，v当前存储在r中，v的存储器位置保存陈旧值，并且当前在寄存器中的v的任何其他值被驱逐。例如，在图6中，一个记录器关联注释与状态S30关联 使得变量x用寄存器r3跟踪，哈拉米略、古普塔、索法93优化代码(3) [v;]r注释。 lload注释与优化代码中的lload指令相关联，并且用于跟踪寄存器r的加载信息。寄存器分配检查器记录先前分配给r的变量被逐出。如果指定了v，则寄存器分配检查器记录r保持变量v，v当前存储在r中，并且当前在寄存器中的v的任何其他值使用跟踪信息，检查器检查所加载的值是否陈旧，并且如果是，则记录该信息，通知用户v的陈旧值，并且如果v的期望值存在，则通知用户v的期望值例 如 ，在图6中，一个load注释与状态S10相关联 在优化的CODE中，TRACK和CHECK寄存器R1中的信息。(4) Store v; r注解。存储注释与优化代码中的存储指令相关联，以跟踪寄存器的存储信息。R.使用跟踪信息，检查器检查r是否不保持v的期望值，并且如果是，则通知用户r不保持v的期望值，并且如果v的当前位置存在，则通知用户v的当前位置。此外，寄存器分配检查器记录v的存储器位置保存当前值。例如，在图6中，存储注释与状态S80相关联。(5) 恢复器移动r; r0注释。寄存器移动注释与优化代码中的移动指令相关联，以跟踪寄存器r0中的信息。 寄存器所有位置缓存器将属于寄存器r的信息复制为属于寄存器r0的信息。例如，在图6中，一个移动注释与状态S40相关联 以跟踪寄存器R2中的信息。组合注释当Check注释与Store注释相关联时，检查器检查存储在优化程序中的程序点处的变量的存储器位置中的寄存器中的值是否匹配未优化程序中的等效程序点处的变量的值。如果值不匹配，则如果寄存器当前保存变量，则检查器通知用户为什么优化代码中的值不正确。值过期、未初始化或错误（可能是因为正确的值被逐出，现在寄存器包含将被存储的错误值）。如果寄存器当前没有保存变量，则检查器通知用户（1）变量的期望值是否驻留在另一个寄存器中，（2）变量的最后位置，以及（3）在指令中提供了错误的寄存器或地址，期望值被较早地驱逐并且未被保存，或者存储器值已经具有期望值（由于较早的存储）。与“加载”注释关联的“检查”注释以类似的方式处理。当检查注释与配准分配注释相关联时，哈拉米略、古普塔、索法94未优化代码优化的代码注释1S1’) load r1,yS2’) load r2,231)x = 2 * y254S3’) mul...S4’) move检查y，r1检查/寄存器分配x，r3寄存器移动r1、r26S5’) load负载r172)z = x + 59S6'）加上r4、r3、r1检查8...3)a = y + y11131012检查/寄存器分配z，r4检查y，r1检查/寄存器分配a，r5检查/存储a，r5检验器验证在优化代码中的程序点处分配给寄存器的值与在未优化代码中的等效程序点处的变量的值相匹配。如果操作数不正确，则检查器将已经通知用户具有意外值的用法。否则，会生成错误代码。注释放置注释被放置在优化的程序中，如下所示。使用映射，Check=Register分配注释被放置在优化代码中的每个变量分配上，并且Check注释被放置在优化代码中的每个变量使用上。接下来，在存储到寄存器的优化代码中的每个指令处，放置寄存器分配注释，除了在检查=寄存器分配注释已经放置的程序点处。在优化代码中将变量加载到寄存器中的每条指令处，放置Check=Load注释。在优化代码中的所有其他加载指令处，加载注释被放置。类似地，在存储到变量的存储器位置的优化代码中的每个指令处，放置Check=Store注释。在优化代码中的所有其他存储指令处，放置Store注释。最后，在优化代码中的每个移动指令处，放置寄存器移动注释。见图7。 寄存器分配检查器示例。例考虑图7中带注释的未优化和优化的程序段，它们说明了图4中给出的相同的未优化和优化代码示例。断点用圆圈表示。注释以虚线框显示。优化后的程序从S10开始执行，并到达断点1.检查器根据注释哈拉米略、古普塔、索法95加载到寄存器R1中的值应当与未优化代码中的Y值在未优化代码中的等效程序点处进行比较。因此，未优化的程序执行直到到达断点2，此时检查器将未优化的程序中的y的值与优化的代码中的r1的值进行比较。如果两个值相同，检查器将根据Load注释确定应该跟踪有关y和r1的信息。检查器记录r1现在持有y的值，并且y当前存储在r1中。如果y存储在任何其他寄存器中，则检查器记录y从这些其他寄存器中被逐出。此外，如果加载的值是陈旧的，检查器会通知用户陈旧的值和变量的预期值的位置（如果存在）。优化后的程序继续执行，并到达断点3。检查器通过记录r2中的最新变量现在被逐出来处理Load注释。优化和未优化的程序以类似的方式继续执行。请注意，当到达断点6时，检查器将处理Register move注释，并记录r2保存y的值，y存储在r2中。在断点7处，检查器处理Load注释并记录y从r1中被逐出。在断点10处，检查器通过执行未优化的程序来处理Check注释，直到到达断点11，此时将未优化的代码中的y的值与r1进行比较。值为dier，检查器通知用户y已从r1中删除，优化代码中y的预期值在r2中。4实施和实验实现了OP优化代码的编译检查器COP，包括指令映射、注释放置和检查。LCC[7]被用作应用程序的编译器，并被扩展为包括一组优化，即循环不变代码运动，死代码消除，部分冗余消除，寄存器分配，复制传播以及常数传播和折叠。平均而言，优化的lcc生成的优化代码执行速度比未优化的代码快16%。当程序被优化时，映射被生成。除了生成目标代码之外，lcc还被扩展为确定未优化和优化代码之间的映射、断点信息以及从映射派生的注释。发出断点信息和注释的代码通过库例程集成在lcc中。因此，应用程序的编译和优化产生用于未优化程序和优化程序的目标代码以及辅助代码。les包含断点信息和注释，优化和优化的程序。这些辅助词是由检验员使用的哈拉米略、古普塔、索法96去2854700：01：4300：08.3600：01：3800：08.5301：41.3402：18.82源长度（线）未优化代码注释优化的代码注释程序（中央处理器）（中央处理器）（中央处理器）（中央处理器）警察（回应(CPU)时表1执行时间（分：秒）。WC338时间00：00：26时间00：02：1600：00：1800：01.86时间00：30：29时间00：53.33yacc5900：01.10时间00：06：3800：00.9800：05.8401：06.9501：34.331m88ksim17939时间00：29：62三点零八分十五秒时间00：24.92三点零七分三十九秒四十一：十五点九二四十八分五十九点二十九秒1压缩143800：00.2000：02.9100：00：1700：02.89时间00：52.0901：22.821李691601：00.2505：42.3900：55.1505：32.32九十九：五十一点一七一百二十三：三十七点六七1Ijpeg27848时间00：22.5302：35.2200：20.7202：33.98三十八：三十二点四十五五十七：三十点七四使用Spec95基准测试输入集每当计算源级别赋值或谓词的值时，以及每当计算数组和指针地址时，都会生成断点还生成断点以保存用于结构的动态分配存储的基地址malloc（）、free（）等）。数组地址和指针地址的比较实际上是通过比较它们的o集与检查器收集的最接近的基址来进行的浮点数的比较允许不精确的相等。也就是说，允许两个旋转点数相差一定的小Δ [10]。断点使用快速断点实现[9]。实验进行了评估COP的实用性。主要关注的问题是比较检查计划的效用和费用。COP被发现是非常有用的，在实际调试优化器实现这项工作。在优化的实现以及映射和注释中很容易检测和定位错误当检测到两个值之间的比较不成功时，COP指示哪个源级别语句计算了值、应用于该语句的优化以及未优化和优化的汇编代码中的哪些语句计算了值。在成本方面，未优化和优化程序的速度下降以及比较检查器的速度是令人感兴趣的。COP在两个程序的执行过程中执行对y的检查。值和地址比较都被执行。在实验中，COP在HP 712/100上运行，未优化和优化的程序在单独的CPU 5上运行工作站，而不是在同一个处理器上运行所有三个在第3节。消息通过10 Mb网络上的套接字传递。 缓冲器用于减少执行程序和检查器之间发送的消息数。一些整数规格95基准以及一些较小的测试程序被用作测试用例。表1显示了未优化和优化程序的CPU执行时间，包括注释和不包括注释。平均而言，注释使未优化程序的执行速度减慢了8倍，优化程序的执行速度减慢了9倍。优化的程序体验1哈拉米略、古普塔、索法97比未优化的程序更大的开销，因为更多的注释被添加到优化的程序中。表1还显示了COP的CPU和响应时间。COP的性能在很大程度上取决于程序运行的长度.就CPU和响应时间而言，比较检查需要几分钟到几小时。如果比较检查是在线执行的（即，非交互式）。检查器的性能被发现是由处理平台和网络速度的限制。更快的处理器和100 Mb网络将大大降低这些时间。事实上，当COP在333 MHz Pentium Pro处理器上执行时，就CPU时间而言，性能平均快6倍。无法访问更快的网络。在实验期间测量池大小，并且池大小相当小。如果不比较地址，则池大小包含的每个程序的值都小于40。如果比较地址，则池大小包含的值小于19005相关工作没有太多的工作集中在开发工具来帮助调试优化器。Bug nd [1]是为了帮助调试优化器而开发的，它可以精确地指出哪些函数会产生错误的代码。该工具还通过将每个函数编译为最高级别的正确优化来帮助应用程序编写人员。为了完成这些任务，必须将函数放在单独的le中。Boyd和Whalley[2]开发了vpoiso工具来识别优化过程中导致执行输出不正确的第一次转换。 开发了图形优化查看器xvpodb，允许用户在每次应用转换之前和之后查看生成的指令的状态。但是，如果优化器编写者无法断定优化代码中的哪些特定指令产生了不正确的结果，那么使用xvpodb将是乏味的。最近的工作[3，4]静态地比较了编译过程前后程序的中间形式，这项工作象征性地评估程序的中间形式，并检查符号评估是否等价。虽然这种方法验证了所有可能的程序输入的程序转换，但它也检测不一定是错误的假警报。相比之下，比较检查不检测假警报，但其仅针对在其上运行未优化和优化程序版本的输入来测试程序的翻译。调试优化器的另一种方法是简单地使用调试优化代码的工具，让用户推断错误是在源代码中还是在优化器中。 这种方法不仅使任务用户更加困难;此外，即使是最新的调试优化代码的工作也不能完全报告变量的预期值，哈拉米略、古普塔、索法98未优化的程序[11，5，6]。6结论在本文中，我们提出了比较检查，一种技术，旨在帮助优化程序的作者调试他们的优化程序，通过测试的unoptimized和优化版本的程序具有相同的语义方面的程序输入。比较检查技术使用映射和注释来指导检查。映射是在执行优化时确定的，因此需要优化器编写器扩展优化实现以包括映射。注释及其放置是根据映射自动确定的。在检查过程中，如果两个版本的语义不同，检查器可以查明最早的差异发生在哪里以及涉及的优化比较检查的方法不同于传统的调试方法，即用户查询调试器。检查器的工作没有任何用户查询。 它也不同于验证方法，对于给定的输入，检查器使用精确的动态信息来比较语义行为。验证技术适用于任何输入，但会产生误报。检查器不会产生误报。引用[1] J.M. 卡 伦 和 达 内 尔 ， P.A. Bug nd ： A Tool for Debugging OptimizingDebugger. Sigplan Notices，25（1）：17{22，1990年1月[2] 博伊德，M.R.和Whalley，D. B.优化错误的隔离和分析。在ProceedingsACM SIGPLAN'93 Conf. on Programming Languages Design and Implementation中，第26页{35，1993年6月[3] Necula、G.翻译验证的优化编译器。在Proceedings ACM SIGPLAN'99 Conf.on Programming Languages Design and Implementation中，第83页{94}，2000年6月[4] Pneuli，A.，Rodeh，Y.， Shtrichman，O.， Siegel，M. 在Proceedings11 th International Conference on Computer Aided Veri cation，LNCS 1633，Springer-Verlag，第455-469页，1999中。[5] 吴湖，加-地优化代码的交互式源代码级编译。 博士论文，伊利诺伊大学香槟分校，2000年。[6] Dhamdhere，D. M.和Sankaranarayanan，K. V.优化程序中的动态货币确定。ACM Transactions on Programming Languages and Systems，20（6）：1111{1130，November 1998.[7] 弗雷泽角和Hanson，D. 一个可重定向的C语言：设计与实现。 本杰明/卡明斯，1995年。哈拉米略、古普塔、索法99[8] 哈拉米略角古普塔河，巴西-地因此，M. L.捕获代码改进转换的效果。在并行架构和编译技术国际会议的会议记录中，第118页，1998年10月。[9] Kessler，P.快速断点：设计与实现。在Proceedings ACM SIGPLAN'90 Conf.on Programming Languages Design and Implementation 中 ， 第 78 页 {84 ，1990}。[10] 索西奇河和Abramson，D. A.守卫：一个相对的守卫。Software Practice andExperience，27（2）：185{206，February 1997.[11] 吴，L.，米拉尼河帕蒂尔·H Olsen，B.，和Hwu，W. W.一个新的全局优化 代 码 框 架 。 在 Proceedings ACM SIGPLAN'99 Conf. on ProgrammingLanguages Design and Implementation，第181页{191，1999}中。
我的内容管理
展开
