没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记141(2005)69-84www.elsevier.com/locate/entcs验证更多循环优化本杰明·戈德堡阿米尔·普努埃利纽约大学计算机科学系美国纽约摘要翻译验证是一种确保翻译器(如编译器)产生正确结果的技术。由于翻译器本身的完全验证通常是不可行的,翻译验证提倡将验证任务与翻译任务耦合,因此翻译器的每次运行都产生验证条件,如果有效,则证明翻译的正确性。 在以前的工作中,翻译验证方法被用来证明各种编译器优化的正确性的框架,最近的重点是循环转换。然而,其中一些想法是初步的,尚未得到实施。 此外,还有一些常见的循环转换的例子,我们以前的方法无法处理。本文件讨论这些问题。 本文介绍了一种新的循环缩减变换规则REDUCEtions,并且我们推广了我们之前的规则VALIDATE,以便它可以处理更多涉及循环的转换。然后,我们将描述如何在我们的编译器验证工具TVOC中实现所有这些(包括以前的一些理论工作)。保留字:翻译验证,形式化方法,循环优化1引言更高的正确性对于拥有正确的程序是必不可少的。对于关键应用程序,仅仅有源代码的正确性证明是不够的。还必须保证编译器将源代码正确地翻译成目标机器代码。验证现代优化编译器的正确性是一项具有挑战性的任务,因为它们的大小,复杂性以及随时间的演变。1电子邮件:{yinghu,barrett,goldberg,amir}@ cs.nyu.edu1571-0661 © 2005由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2005.02.04470Y. Hu等人理论计算机科学电子笔记141(2005)69翻译验证(TV)[12]是一种技术,用于确保翻译器(如编译器)发出的目标代码是源代码的正确翻译。由于验证整个编译器的困难,即确保它为每个可接受的源程序生成正确的目标代码,翻译验证用于验证编译器的每次运行,比较实际的源代码和目标代码。在以前的工作[14,15]中,引入了证明规则PERMUTE来验证循环重排变换,并引入了证明规则VALIDATE来验证所谓的结构保持变换。然而,我们发现这些规则对于优化编译器执行的某些类型的转换是不足够的。例如,一个重复递增一个变量的循环可以被一个乘法操作所取代。对于这种转换,我们引入了一个新的证明规则REDUCE。此外,我们发现,在一些结构保持的情况下,涉及嵌套循环,规则验证是不成功的。然而,通过稍微推广规则(获得我们称为GEN-VALIDATE的规则),我们也可以处理这些情况TVOC是纽约大学正在实施的一种工具,用于为英特尔开放研究平台(ORC)实现翻译验证[7]。TVOC简单-分段规则但前提是,GEN-VALIDATE,和 还原并检查生成的使用自动定理证明器CVC Lite[1]验证条件。TVOC的最新版本还包括[4]中建议的用于验证重新排序循环优化的思想的具体实现。特别是,TVOC现在使用一个统一的证明规则,用于所有重新排序的循环优化,一个用于确定发生了哪些循环优化的方法(而不是依赖于编译器来获取此信息),以及一种用于优化组合的方法。第二节回顾了为优化编译器的翻译验证提供必要理论基础的转换系统。第3节讨论了编译器验证的相关工作,特别是我们以前在编译器翻译验证方面的工作,包括规则VALIDATE和PERMUTE。第四节介绍了新的证据规则REDUCE。第五节提出了证明规则GEN-VALIDATE,它是VALIDATE的推广.最后,第6节描述了如何在最新版本的TVOC中实现所有这些证明规则。2背景为了讨论程序的形式语义,我们简要地回顾了转换系统TS,它是[ 12 ]中转换系统的一个一个转换系统S=V,O, Θ,ρ,是一个状态机,它包括:Y. Hu等人理论计算机科学电子笔记141(2005)6971表;可观测变量的集合OV;初始条件 Θ,其是关于V的表征系统的初始状态的公式;以及转移关系ρ,关于变量的未引发版本和引发版本的公式,其中引发版本指的是后继状态中的变量的值,而变量的未引发版本指的是它们在前状态中的值。过渡态因此,例如,转移关系可以包括一个比它在旧的(预转换)状态下的值。变量是类型化的,并且TS的状态是变量的类型一致的解释。对于状态s和变量x∈V,我们用s[x]表示s赋予x的值。我们假设每个转移系统都有一个变量pc来描述程序位置计数器。虽然可以为每个语句单独分配一个转换关系,但我们更喜欢使用广义转换关系,描述沿着程序路径从一个基本块到另一个基本块执行几个语句的效果考虑下面的代码:L0:L1:L2:n= 500;return 0;如果(nw)到达L2;......在转移关系中有两个析取,它们的起始位置是L0.第一个描述了L0到L1的路径,即pc=L0∧ nJ=500<$YJ = 0<$NJ≥wj<$PCJ =L1,第二个描述了L0到L2路径,即pc = L0 n j = 500 μ m yJ= 0 nJ0:BJ(i);B(i+1)对于i= 1到N,B(i)≠BJ(N)对于i= 1到N,x:=x+1;=nx:=x+N;Fig. 1. 一个循环减少的例子。其中循环被删除并替换为单个语句。我们称之为循环减少,并提出了一个新的证明规则,还原,以处理这种情况。规则推导如图所示2,其中,符号“0”表示两段代码是等价的。图二. 减少循环的规则推导循环减少是基于为执行循环的结果找到一个封闭形式的表达式这种转换通常可以使用归纳法来验证。规则REDUCE是基于一个归纳的论点,执行B(i)从1到N等价于执行某个封闭形式的块BJ(N)。第一个前提是基本情况。它要求B(1)等价于BJ(1)。第二个前提是归纳的情况,它要求BJ(i)能够对于图1中的代码,B(i)是x:=x+1,并且BJ(i)是x:=x+i。这两个前提可以很容易地建立这个简单的案子规则REDUCE也可以用来表明一个什么都不做的循环可以被删除。图3显示了一个转换,它删除了一个没有循环身体 在这种情况下,B(i)=BJ(i)=Skip。对于i= 1到N,跳过;=跳过;图三. 减少一个空的循环。5规则的一个推广第三节简要介绍了证明规则VALIDATE。RULEVALIDATE可以验证源和目标具有相同循环的许多转换76Y. Hu等人理论计算机科学电子笔记141(2005)69结构然而,仍然有一些情况下,即使循环结构相同,规则验证是不成功的。图4给出了由ORC执行的这种转换的示例。cp1:如果(1≤N),则{CP1:对于i= 1到N,CP2:对于j= 1到M,do= 1CP3:B(i,j);CP4:l1:cp2:CP3:}CP4:如果(1≤M),则{对于i= 1到N,对于j= 1到M,B(i,j);}见图4。一个验证失败的例子。转换在主循环之前添加了两个在该示例中,CP1、CP2、CP3和CP4是源切割点,并且cp1、cp2、cp3和cp4是目标切割点。控制映射将每个目标切割点映射到对应的源切割点。标签11标记不在切割点集中的目标位置现在,考虑一个简单的目标路径从cp1到cp4.该路径从cp1经过l1,然后直接到达cp4,而不进入环路。该目标路径在条件N≥1<$M 1下使能其对应的源路径从环路内的CP1到CP2,在CP2停留N个周期,然后退出到CP4而不进入内环。由于该源路径在其从CP1到CP4的途中穿过CP2N次,因此它不是简单路径。这是规则验证的一个问题:从cp1到cp4的简单路径在源代码中没有对应的简单路径! 因此,对应于从CP1到CP4的简单路径失败。规则VALIDATE对图的转换失败的原因四是它假定目标中的每个简单路径对应于源中的一个或多但是,此转换将源中的非简单路径转换为目标中的简单路径我们可以通过放松对规则验证所使用的截点集的要求来解决这个问题。图5给出了修改后的证明规则GEN-VALIDATE,附录中给出了其正确性的证明。它本质上与[15]中给出的证明规则相同,只是增加了一个新的0项,它明确地允许更自由地选择割点集。临界点Y. Hu等人理论计算机科学电子笔记141(2005)69770. 建立源和目标切割点集CPS和CPT,其中包括所有初始和终端程序位置。 对于两个截点i和j之间的任何简单路径,它的转移关系ρij必须是可计算的。1.建立控制抽象κ:CPT→CPS,使得i是T的初始(终端)位置iκ(i)是初始(终端)位置S。2. 对于CPT中的每个割点i,形成一个只涉及目标变量的不变量i。3. 建立数据抽象α:(PC=κ(pc)<$(p1 → V1 = e1)<$··· n(pn→Vn=en)其断言源和目标在对应的切割点处,并且其向一些非控制源变量Vi∈ VS分 配 目 标 变 量 上的表达式ei,条件是(目标)布尔表达式pi。 要求对于每个初始目标切割点i,θT→α还要求每个可观测源变量V∈ OS 都有一个唯一的对应的可观测目标变量v∈ OT,对每个终端目标割点t,pc=t<$α意味着对所有V∈ OS,V=v.4. 对于每对割点i,j∈CPT,使得存在从i到j的简单路径,我们形成验证条件T_SJ JC ij:(ρ π) →α我的朋友,π∈Paths(κ(i))S其中Paths(κ(i))是从κ(i)开始的所有简单源路径的集合,ρπ是简单源路径π的跃迁关系。5.确定所有生成的验证条件的有效性。图五.广义Gen-VALIDATE集合必须像以前一样包括程序的起始点和终止点,但它们不一定包含每个循环的点。相反,我们要求每个简单路径的转移关系是“可计算的”。这里的“可计算”是指路径是有限的,它的转移关系可以通过数据流分析计算出来,也可以通过证明规则推导出来。 很容易看出,无循环路径保证是可计算的。但也有这样的情况,即只要循环的迭代次数已知,就可以通过展开循环来计算循环为了解决图4的例子,我们可以消除切割点CP2和CP2,如图6所示。现在有几个新的简单路径,以前不存在。其中大多数是无循环的,因此很容易计算。然而,现在存在从CP1到CP4的新的源路径。只有当内部循环从未执行时,此路径才是可能的(否则将到达CP3但这意味着循环体实际上是空的,正如前面所讨论的(请参见78Y. Hu等人理论计算机科学电子笔记141(2005)69图3)、一个空体的循环相当于什么都不做注意,目标中的这种路径是不可行的,因为它需要1≤M和1> M都为真。因此,所有这些路径都是可计算的,并且满足规则GEN-VALIDATE的要求。利用这组新的切割点,验证成功,因为从cp1到cp4的目标路径存在对应的简单源路径。CP1:fori= 1toNdo forj =1toMdoCP3:= 0B(i,j);CP4:cp1:如果(1≤N),则{如果(1≤M),则{fori= 1toNdo forj =1toMdoCP3:B(i,j);}}CP4:见图6。 修改后的切割点示例。6新的实施功能源程序编译器TVOC有效无效见图7。 TVOC的老建筑。IR S是/否是/否CVC精简版验证条件2期1期目标IR T.l档桉源IR SY. Hu等人理论计算机科学电子笔记141(2005)6979TVOC是纽约大学正在开发的翻译验证工具它接受源程序S和目标程序T作为输入。这些都是以WHIRL中间表示形式提供的,这是英特尔的开放研究型计算机(ORC)[ 7 ]等使用的格式TVOC的输出要么是在[4]中,引入了一些尚未在TVOC中完全开发或实施的想法。此后,我们修改了TVOC以实现这些功能以及本文所述的功能。图7显示了TVOC的旧架构。[ 4 ]中讨论了该架构的三个局限性:首先,我们依赖于编译器生成的辅助文件(.l文件)来告诉我们执行了哪些循环转换;其次,循环转换必须在一个步骤中验证,即使转换更自然地建模为几个简单转换的组合;第三,有几个不同的证明规则(和相应的代码)用于验证循环转换。在本节中,我们将讨论TVOC的新架构(如图8所示),并展示我们如何实现这些问题的解决方案。我们还讨论了本文所描述的GEN-VALIDATE源程序编译器TVOC有效无效图8.第八条。TVOC的新架构。是/否验证条件是/否CVC精简版目标IR T源IR S1期S=S1S2Sn=SJS'2期(S',T)80Y. Hu等人理论计算机科学电子笔记141(2005)691. 对于源代码中深度为m的每个嵌套循环,检查相应的目标代码是否有深度为n的嵌套循环。请注意,我们可以匹配源和目标中的循环,因为WHIRL包含注释,指示源中的哪一行号对应于给定的目标行。2. 如果m > n,检查目标是否包含来自源循环体的代码。如果没有,尝试循环减少。否则,尝试循环融合。3. 如果m=n,检查是否有索引乱序。如果是,则发生循环交换。4. 如果m
下载后可阅读完整内容,剩余1页未读,立即下载
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 共轴极紫外投影光刻物镜设计研究
- 基于GIS的通信管线管理系统构建与音视频编解码技术应用
- 单站被动目标跟踪算法:空频域信息下的深度研究与进展
- 构建通信企业工程项目的项目管理成熟度模型:理论与应用
- 基于控制理论的主动队列管理算法与稳定性分析
- 谷歌文件系统下的实用网络编码技术在分布式存储中的应用
- CMOS图像传感器快门特性与运动物体测量研究
- 深孔采矿研究:3D数据库在采场损失与稳定性控制中的应用
- 《洛神赋图》图像研究:明清以来的艺术价值与历史意义
- 故宫藏《洛神赋图》图像研究:明清艺术价值与审美的飞跃
- 分布式视频编码:无反馈通道算法与复杂运动场景优化
- 混沌信号的研究:产生、处理与通信系统应用
- 基于累加器的DSP数据通路内建自测试技术研究
- 跨国媒体对南亚农村社会的影响:以斯里兰卡案例的社会学分析
- 散单元法与CFD结合模拟气力输送研究
- 基于粒化机理的粗糙特征选择算法:海量数据高效处理研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)