带类型恢复的编译器源源翻译技术.pdf

计算机研究与发展I S S N1 0 0 0 1 2 3 9 C N1 卜1 7 7 7 T P J o u r n a lo fC o m p u t e rR e s e a r c ha n dD e v e l o p m e n t4 7 7 1 1 4 5 1 1 5 5 2 0 1 0 带类型恢复的编译器源源翻译技术 米伟1 2李玉祥1陈莉1冯晓兵1张兆庆1 1 中国科学院计算技术研究所系统结构重点实验室北京 1 0 0 1 9 0 2 中国科学院研究生院北京 1 0 0 0 4 9 m i w e i i c t a e c n AS o u r c e t o S o u r c eT r a n s l a t i o nM e t h o dw i t hT y p eR e s t o r a t i o ni naC o m p i l e r M iW e i l L iY u x i a n 9 1 C h e nL i l F e n gX i a o b i n 9 1 a n dZ h a n gZ h a o q i n 9 1 1 K e yL a b o r a t o r yo fC o m p u t e rS y s t e ma n dA r c h i t e c t u r e I n s t i t u t i o no fC o m p u t i n gT e c h n o l o g y C h i n e s eA c a d e m yo f S c i e n c e s B e i j i n g1 0 0 1 9 0 2 G r a d u a t eU n i v e r s i t yo fC h i n e s eA c a d e m yo fS c i e n c e s B e i j i n g1 0 0 0 4 9 A b s t r a c tS o u r c e t o s o u r c et r a n s l a t i o ni sa ni m p o r t a n tw a yt Om a k ea n a l y s i sa n do p t i m i z a t i o ni na c o m p i l e rr e t a r g e t a b l e I ti sw i d e l yu s e dt Os u p p o r tv a r i o u sp a r a l l e lp r o g r a m m i n gl a n g u a g ee x t e n s i o n s a n dp l a t f o r mi n d e p e n d e n to p t i m i z a t i o n s a n di tc a nh e l pp r o g r a m m e r st Ov a l i d a t et h ep r o g r a m c o r r e c t n e s sa n dt ot u n et h ep e r f o r m a n c e I nt h em u l t i c o r ea n dm a n y c o r et i m e s u s e r sarem o r e e a g e r l yd e m a n d e dt og e ti n v o l v e d i n p r o g r a ma n a l y s i s a n do p t i m i z a t i o n S o u r c e t o s o u r c ec o d e g e n e r a t i o n w h i c hi sp l a t f o r mi n d e p e n d e n ta n du s e rf r i e n d l y i si n c r e a s i n g l yw e l c o m e d S o u r c e t o s o u r c ei se a s yt oi m p l e m e n ti nas i m p l ec o m p i l e r b u td i f f i c u l tt Oi m p l e m e n ti nac o m p i l e rw i t hc o m p l e x p r o g r a ma n a l y s i sa n da g g r e s s i v eo p t i m i z a t i o n s T h e r e f o r ef e wp r o d u c t i o nq u a l i t yc o m p i l e r sp r o v i d e d r o b u s ts o u r c e t o s o u r c et r a n s l a t i o n I ti Sf o u n dt h a tt r a n s f o r m a t i o np r o d u c e db yo p t i m i z a t i o ni st h e l e a d i n gc auseo ft h ed i f f i c u l t y T h ep r o b l e m sarea n a l y z e di nt h es o u r c e t o s o u r c et r a n s l a t i o nb a s e do n al o to fe r r o rc a s e s a n dat r a n s l a t i o nt e c h n i q u ew i t ht y p er e s t o r a t i o ni sp r o v i d e dt os o l v et h ep r o b l e m T h e nt h ea u t h o r si m p l e m e n tt h et e c h n i q u ei nt h eO p e n 6 4c o m p i l e r e v a l u a t ei tv i as u p e r t e s ta n d s p e c 2 0 0 0b e n c h m a r k sa n dp r o v et h a ti tg r e a t l yi m p r o v e st h er o b u s t n e s so ft h es o u r c e t o s o u r c e t r a n s l a t i o n T h em e t h o di nt h ep a p e ri si n t e g r a t e di nt h es o u r c e t o s o u r c et r a n s l a t o rm o d u l ea n d s e p a r a t e df r o mv a r i o u so p t i m i z a t i o n s S Oi ti se a s yt Ob eu s e di no t h e rc o m p i l e r s K e y w o r d s c o m p i l e r s o u r c e t o s o u r c e r e t a r g e t a b l e i n t e r m e d i a t e r e p r e s e n t a t i o n t y p e i n c o n s i s t e n c y t y p er e s t o r a t i o n 摘要源源翻译是使编译器的分析和优化可重定向的一种重要方式 它被广泛用来支持并行语言扩展 或者各种体系结构无关的优化 并且可以帮助程序员进行正确性或者性能的调试 在多核 众核时代 程 序分析和优化倾向于让用户更多地参与 这种平台无关而且用户友好的代码生成方式也越来越受到欢 迎 在简单的编译器中添加源源翻译的支持很容易 但在实现了复杂的程序分析和激进的优化的编译器 中 却很少有编译器提供健壮的源源翻译支持 优化对程序结构的改变是造成翻译困难的首要原因 结 合大量出错实例对优化给源源翻译带来的困难进行分析 提出了一套基于类型恢复的翻译技术 并在 O p e n 6 4 编译器中实现了这种方法 通过s u p e r t e s t 和s p e c 2 0 0 0 测试集的测试 验证了这种方法对源源 收稿日期 2 0 0 9 0 2 1 1 修回日期 2 0 0 9 0 90 2 基金项目 自然科学基金重点项目 6 0 6 3 3 0 4 0 国家 九七三 重点基础研究发展计划基金项目 2 0 0 5 C B 3 2 1 6 0 0 万方数据 计算机研究与发展2 0 1 0 4 7 7 翻译的健壮性有很大改善 该方法的实现模块集成在源源翻译器内 与编译器各种分析优化模块独立 所以该方法容易移植到其他编译器中 关键词编译器 源源翻译 可重定向 中间表示 类型不一致 类型恢复 中图法分类号T P 3 1 4 现代优化编译器一般是先将源码转换为中间表 示 在中间表示上作大量程序分析 机器无关优化变 换 最后生成目标码 源源翻译器是一种很有用的编 译基础设施 它实现将中间表示转换为语义等价并 可进行再编译的高级语言源码 源源翻译器用途很 广 首先它可以帮助编译器实现平台无关分析和优 化的重定向 例如用来实现平台无关的自动并行化 S I M D 优化以及循环优化等高层程序优化 尤其目 前针对多核平台的程序并行化 并行编程模型以及 并行语言扩展的研究十分迫切 一个试验性的语言 模型或者语言扩展要被大家接受需要得到各种平台 上的用户的支持 源源翻译作为一个可重定向工具 可以显著扩大研究的适用范围和影响力 第二 用户 可以利用源源输出的结果进行程序调试 也可以在 源源翻译输出的优化代码基础之上进行手工优化 用户面对的编译结果是高级语言而不是汇编代码 这极大改善了用户配合编译器进行程序功能和性能 调试的体验 因此国内外很多研究者都迫切希望能 有既包含完善分析和优化的基础设施 又带有很好 的健壮性和可维护性的源源翻译器的编泽平台作为 他们的研究平台 源源翻译面临2 大主要困难 一是编译器中包 含大量优化 优化会改变中间表示上表达式的类型 或者改变表达式的变量或者操作符等 这些变化可 能使翻译过程中表达式的类型与表达式的其他部分 所期望的类型不一致 下面称作类型不一致问题 导致直接翻译发生错误 这里的翻译错误可能是翻 译结果再次编译时不符合语法规范 也可能是翻译 结果再次编译的执行结果不符合原来程序的语义 二是高级语言信息转换成中间表示过程中会有一部 分信息丢失 这个问题主要出现在处理C 和 F 9 0 F 9 5 语言的时候 以C 面向对象的特征为 例 面向对象是比面向过程更高一级的抽象 而通常 用于常规优化的中间表示的抽象级别与面向过程程 序语言大致相当 在C 被翻译成中间表示时 抽 象层次下降的过程可以看作是用面向过程的语言实 现面向对象特征的过程 而抽象层次一旦下降之后 除非花很大的代价保存相关的信息 否则翻译阶段 要从中间表示上逆向恢复那砦面向对象的特征十分 复杂 退而求其次 我们采用把C 翻译成C 和把 F 9 0 F 9 5 翻译成F 7 7 的方法 虽然在翻译代码可读 性方面不算理想 但这个方法在很大程度上解决了 C F 9 0 F 9 5 语言翻译的功能问题 本文重点讨 论的是如何解决第1 个困难 对第2 个困难的进一 步改善是下一步的T 作 源源翻译通常会按照中间表示的样子一对一地 进行翻译 我们下面也经常把这种翻译方式称为直 接翻译 对于比较简单的编译器 直接翻泽的方式不 会造成问题 但是对于比较复杂尤其是像g c c 1 J 或 者O p e n 6 4 2 这样有大量优化的编译器 直接翻译就 会有很多问题 目前g c c 没有提供源源翻译的支持 而O p e n 6 4 的源源翻译 主要包括U p c c 编译器 3 和 O p e n u h 编译器t 4 所做的工作 基于直接翻译的框 架做了大量就事论事 c a s eb yc a s e 的修复工作 但 因为没有解决造成直接翻译困难的根本问题 所以 翻译结果存在大量的错误以至于经常不能够顺利地 再编译 而且翻译模块的代码变得非常复杂且难以 维护 本文首先检查中间表示上不同类型节点的翻译 情况 分析了哪些类型的节点的翻译可能会导致翻 译错误 在上面分析的基础上 本文总结了什么是导 致类型信息不一致的原因 在哪里可以找到可靠的 类型信息来源 然后提出了类型信息恢复方法并且 在编译器中作了实现 最后通过大量的测试以及与 前人工作的对比说明采用类型恢复方法后的源源翻 译器的健壮性有了很大的改善 由于解决了类型不 一致这个根本问题 翻译过程的实现以及维护都变 得简单 所以本文的方法很容易移植 我们的源源1 具能够支持C C 和F 7 7 以及 F 9 0 程序的源源翻译 由于是涉及类型信息不一致 问题 而F 7 7 和F 9 0 是强类型语言 所以问题比较 小 因此本文主要以C 和C 程序的源源输出作 为讨论对象 1 类型不一致问题的分析 编译器中优化种类很多 通常优化只要不使汇 万方数据 米伟等 带类型恢复的编译器源源翻译技术 编代码对应的执行结果发生改变就认为该优化是正 确的 但正确的优化却可能导致直接翻译产生错误 我们通过分析发现 优化不能保证源源翻译结果正 确的原因来自于汇编语言与高级语言之间的差别 汇编语言的操作数的类型只能是一些基本类型即整 型和浮点等 而高级语言的表达式的类型既有简单 类型也有数组 结构或者指针等复合类型 这些复合 类型还会互相嵌套组合构成更加复杂的类型 汇编 代码的语义由基本类型运算的结果决定 只要优化 前后结果不变就说明汇编代码生成正确 而翻译代 码的表达式的语义由构成表达式的每一个子表达式 的类型以及操作符共同决定 只有类型和操作符组 合起来的含义跟翻译之前的程序一致 并且每一个 表达式的形式都符合语言的规范 这才能说明翻译 正确 优化对中间表示的修改总会试图保持汇编代 码的执行结果不变 但优化对中间表示上表达式形 式的改变可能使得表达式类型 尤其是复合类型 与 翻译所期望的类型不一致 从而导致翻译结果错误 这就是优化给直接翻译带来的类型不一致问题 第1 1 节中会给出2 个实例来具体说明类型不一致 问题 1 1 中间表示上涉及类型不一致问题的节点类型 类型不一致问题是由于优化改变了中间表示而 引起的 但并不是所有的中间表示发生变化都会产 生这个问题 我们对大量翻译出错现象的分析发现 只有涉及访存操作的中间表示发生变化会导致类型 不一致问题 而算术运算类型和控制流类型节点的 变化则不会导致这个问题 通过下面的分析把问题 焦点集中在访存操作上 这给类型恢复方法的讨论 带来了很大的方便 访存操作由基地址表达式 偏移表达式和访问 对象的类型组成 它的任务是寻址和取数 寻址由基 地址和偏移2 个要素决定 取数则由访问对象类型 的长度决定 对翻译而言 偏移表达式的计算由基地 址表达式的类型和偏移表达式两者决定 即优化无 论是改变了基地址表达式的类型 还是改变了偏移 表达式 直接把中间表示翻译成代码都可能造成错 误 下面用图1 和图2 两个例子来分别说明这2 种 情况 我们采用抽象语法树结构作为中间表示 并采 用了单独的符号表 因为语法树上每类节点的含义 比较直观所以不另作解释 图1 中 拷贝传播优化 c o p yp r o p a g a t i o n 会用 指针变量q 代替变量P 因为q 和p 实际上指向的 i n t p l 0 0 1 i J5 i m q 9 2 P5 i 力 a i n t j j i m g g i d 4 a r r a y r e f 4B a r r a y r e f 乏4B 圉i int c 凸 i n t 1 0 0 g f 小 j e F i g 1 T h et y p ec h a n g e so ft h eb a s ea d d r e s s e x p r e s s i o n a P r o g r a ms o u r c ec o d e b I Rb e f o r e o p t i m i z a t i o n c I Ra f t e ro p t i m i z a t i o n d W r o n g t r a n s l a t i o nc o d e a n d e C o r r e c tt r a n s l a t i o nc o d e 图l基址表达式的类型发生变化 a 程序源代码 b 优化前的程序中间表示 c 优化后的程序中间表 示 d 错误的翻译后代码 e 正确的翻译后代码 s t r u c t s t r u a X i m d i n t 口 i n t c s t r u c tyb 1 0 0 i n t i p 一6 f c 二 a s t r u tY s t r u c t X i n t d i n t 口 i n t c s t r e e t Y b f l 0 0 1 乍 i n t f5 p f 1 1 c 8 一 C V T i a t c h a r 8 p f l e F i g 2 O f f s e te x p r e s s i o nc h a n g e s a P r o g r a ms o u r c e c o d e b I Rb e f o r eo p t i m i z a t i o n C I Ra f t e r o p t i m i z a t i o n d W r o n gt r a n s l a t i o nc o d e a n d j C o r r e c tt r a n s l a t i o nc o d e 图2 偏移表达式发生改变 a 程序源代码 b 优化 前的程序中间表示 c 优化后的程序中间表示 d 错误的翻译后代码 e 正确的翻译后代码 是相同的地址 所以优化不会对将要生成的汇编代 码的执行结果造成影响 而在直接翻译后的代码中 围 小臼 万方数据 计算机研究与发展2 0 1 0 4 7 7 优化前的二维数组p E i 3 E j 3 优化后变成了q E i E j 3 而q 是指向整型的指针 可以看作一维数组 在翻 译后的代码中直接用q 作为二维数组访问的基地址 表达式显然是错误的 再编译会造成语法错误 图1 中的例子是因为基地址表达式的类型发生 了改变而导致的翻译错误 而图2 中的例子则是由 于偏移表达式发生了变化导致的错误 图2 中指针 P 相对结构体中数组b 之间的偏移是4B 隔着i n t 口 结构体类型y 中c 相对于它所在结构体的首地 址的偏移是4B 这两者之和刚好等于结构体类型y 的大小8B 所以结构体折叠优化 s t r u c t u r e f o l d i n g 用于增强依赖分析 会把P 与声一6 之间的 偏移以及b E i 3 与b E i 3 f 之间的偏移都折叠到原表 达式中间的数组中去 使原来数组的下标由i 变成 i 1 得到图2 c 的形式 注意这时目标地址相对于 基地址表达式P 的偏移的值与原来没有变化 仍然 是 H 一1 8 8 标注在a r r a y r e f 节点旁边是数组元 素的大小即类型y 的大小 所以对汇编代码生成而 言优化是正确的 但在翻译的结果图2 d 中 P 的 类型指向的是类型X 翻译的结果显然是错误的 此 外 图2 b 中的访存表达式的中间表示涉及结构 体 数组和指针类型的组合 这些复合类型可以任意 地嵌套组合构造成任意复杂的访存表达式 而优化 对表达式任意一处的改变都可能带来不一致的问 题 这给翻译带来了困难 算术运算类型节点的翻译则不会造成类型不一 致问题 这是因为 1 绝大多数编译器的中间表示上的计算操作 都是 加减乘除 与或非 取整 等简单的算术或者逻 辑运算 只涉及整型或者浮点等基本类型 涉及的指 针类型也会被转换成对应长度的整型 不会涉及数 组 结构体以及指针这样的复合类型 C 和C 对 于算术操作操作数的基本类型的规定比中间表示还 要宽松 例如C 和C 语言允许整型和浮点操作 数之间的运算 允许不同长度的整型之间的运算等 而中间表示上不允许这样 中间表示上遇到这些情 况必须进行类型提升 所以对中间表示的算术操作 进行直接翻译就可以保证翻译的结果不违反语法正 确性 2 中间表示上的这些基本类型的算术操作基 本上可以直接对应到相应类型的汇编指令 而我们 在作源源翻译时可以认为编译器产生的汇编指令序 列是正确的 所以对算术操作的翻译只要在操作符 以及操作数的类型上与中间表示保持一致 就可以 保证翻译的结果在语义上正确 C a l l 节点 控制流节 点以及其他特殊节点在优化时也可能发生变化 但 因为只是语句顺序发生改变 不涉及类型不一致问 题 所以不会造成翻译上的困难 综上所述 类型不一致问题主要集中在访存操作 上 类型不一致问题可以被归结为 在中间表示上由 优化造成的 访存操作的基地址表达式的类型与翻译 时偏移表达式的形式所期望的类型不一致的问题 2 类型信息恢复方法 类型不一致问题是由优化使访存操作的基地址 表达式的类型与偏移表达式所期望的类型不一致造 成 一种很容易想到的解决方法是把访存操作全部 线性化成基地址加偏移地址的形式 偏移地址由地 址计算线性表达式构成 然后按这种形式进行翻 译 这样能避免类型不一致问题 但是这种方法一方 面会影响翻译结果再编译的优化效果 另一方面也 会明显降低翻译结果的可读性 所以这不是一种好 的翻译方式 文献 4 5 的翻译方式采用了折中的方 法 他们根据自己的少量目标程序拟定一些判定规 则 规则判定不存在类型不一致问题的地方就直接 翻译 存在类型不一致问题的地方就采用线性化的 翻译 但这些规则很大程度上是就一些特定情形 c a s eb yc a s e 进行特殊处理 并不具有通用性 因 为优化的多样性以及嵌套访存操作的复杂性 这种 方法只是对一少部分例子在有限的优化之下能够得 到正确的翻译结果 而且用于特殊处理的代码都有 产生作用的特殊场景 大量的这种特殊处理的代码 极大增加了代码的复杂度 会使翻译的维护变得越 来越困难 我们的目标是使翻译适应更多的程序及各种优 化 并且保证翻译输出有较高的质量 即保持中间表 示上的数组 结构体和指针访问等结构 我们注意到 中间表示上保存着编译器进行汇编代码生成时必需 的信息 假设编译器汇编代码生成是正确的 那么这 部分信息始终是可靠的 这部分信息主要包括数组 访问元素的大小 数组的各维维展大小 结构体访问 的结构体信息和域访问信息 访存操作的基本类型 等 其中访存操作的基本类型指访存操作以什么类 型从内存中取数 它只能是整型 浮点等基本类型 我们希望利用这部分信息结合中间表示的含义作类 型恢复 对于访存操作而言即恢复出与偏移表达式 一致的基地址表达式的类型 万方数据 米 伟等 带类型恢复的编译器源源翻译技术 1 1 4 9 2 1 带类型恢复的翻译技术概述 如图3 中所示 我们在翻译模块之前增加了一 遍类型恢复处理 类型恢复相当于对翻译之前的中 间表示进行一次预处理 从中闻表示上恢复得到满 足一致性要求的类型 这样翻译模块使用恢复的类 型在必要的时候插入强制类型转换 以此避免产生 类型不一致问题 虽然我们可能对很多优化是否会 造成类型不一致问题不确定 也不知道未来会有什 么样的优化会加入编译器中 通过类型恢复处理可 以屏蔽之前所有分析和优化造成的不一致 使翻译 模块有简单统一的处理方式 A r c h i t e c t u r eI n d e p e n d e n t A n a l y m sa n d0 p t l m l z a t i o n A r c h i t e c t u r e D e p e n d e n tA n a l y s i s a n dO p t i m i z a t i o n A s s e m b l yC o d e T y p eR e s t o r a t i o n 妙 S o u r c e t o S o u r c e T r a n s l a t i o n 妙 T r a n s l a t e d S o u r c ec o d e F i g 3 T r a n s l a t i o nf r a m e w o r k 图3 源源翻译框架 2 2 类型恢复方法概述 为了便于说明 我们首先对访存操作进行一个 简单分类 访存操作的操作数有的又被用于其他访 存操作的基地址 我们把这类访存操作称为中间访 存 有的访存操作则被用于算术运算 赋值或者作为 函数的实参 把这类访存称为根节点访存 因为根节 点访存在抽象语法树上位置比较靠上 而中间访存 作为根节点访存的基地址位置比较靠下 类型恢复 会从根节点访存开始 恢复每一层访存操作的基地 址表达式的类型 所以类型恢复在抽象语法树上是 一个自上而下的过程 根据第1 1 节的分析 算术运 算操作 赋值操作和函数的形参类型都是可靠的 所以我们可以由这些操作的类型信息推知根节点访 存操作的操作数的类型 这是我们作类型恢复的基 础 我们根据根节点访存的操作数的类型和根节点 访存上保留的用于汇编代码生成的信息 可以反推 访存操作基地址表达式的类型 这样得到的类型一 定是满足类型 致性原则的 如果根节点访存的基 地址表达式是中间访存操作 那么上面的类型恢复 可以递归进行 直到访存操作的基地址是算术表达 式或者是变量为止 类型恢复产生的结果是每一层 访存表达式的基地址都会被标注上恢复的类型 它 表达了从根节点访存到当前层的中间访存这一系列 嵌套访存操作对当前访存操作的基地址表达式类型 的要求 标注的类型将在翻译阶段用到 2 3 类型恢复规则 访存操作每一层节点的具体类型恢复方法跟这 一层的操作类型是紧密联系的 图4 中给出了常见 的访存节点的类型恢复规则 主要涉及t L 和 t 这3 个类型变量 F i g 4T y p er e s t o r a t i o nf o r m u l a 图4 类型恢复规则 下面我们解释这3 个类型变量的含义 E 是当 前节点的父亲节点传入的类型 它反映了上一级节 点的翻译对当前节点的类型要求 而L 则反映了 当前节点对下一级节点的类型要求 它将作为下一 级节点的丁mL 表示当前访存操作的基地址类 型 它与T i 可能一致也可能不一致 引入T 的目 的是为了使翻译阶段知道只有当t 与互 不一致 时才存在类型不一致问题 减少翻译阶段插入的强 制类型转换 类型恢复规则的含义是比较直观的 对于 i n d i r e c t r e f 节点构造的T 叫 是指针类型 对于 c o m p o n e n t r e d 节点构造的T o 是结构体类型 对 于 a r r a y r e d 节点构造的L 是指针或者指向数组 的指针类型 下面以图1 c 为例具体说明 a r r a y r e d 节点的类型恢复规则 图1 中 a r r a y r e d 的父 亲节点是i n t 类型的加法运算 所以T i 是i n t 类型 表示翻译后的数组表达式必须是i n t 类型才能进行 i n t 类型的加法运算 瓦表示加法操作节点对 a r r a y r e d 节点的类型要求 t 则表示数组元素的类型 万方数据 1 1 5 0 计算机研究与发展2 0 1 0 4 7 7 因为只有类型的大小是汇编代码生成的必需信息 a r r a y r e D 节点上不会保留数组元素类型而只会保 留类型的大小 所以需要根据类型的大小构造 T e 在图1 中 a r r a y r e d 的元素大小是4B 图1 c 中我们把它标记在 a r r a y r e d 节点上了 对应 图4 a r r a y r e d 中的e l e m s i z e 4B 刚好与T i 的类型 i n t 大小一致 所以T 就可以设为i n t 类型 这样 可以减少T e 与T i 不一致的情况 而如果e l e m s i z e 与T i 的大小不一致 就需要构造一个大小为 e l e m s i z e 的类型作为T 按图4 中 a r r a y r e d 的 规则会构造数组类型c h a r e l e m s i z e 3 最后根据规 则得到T 0 的类型是 i n t 1 0 0 3 表示数组的基地 址表达式必须是 i n t E l O O 类型才能与数组表达 式一致 我们可以从图1 e 中看到正确的翻译结果 中使用了恢复得到的类型 i n t E l O O 从上面的例子中可以看出规则的设计思想 实 际上的规则比图4 列出的要复杂 因为规则需要考 虑怎样才能使翻译插入的强制类型转换最少 怎样 才能最接近源代码的表示形式 比如我们会尝试把 线性化了的结构体访问的翻译形式恢复成普通结构 体访问形式 图4 的规则中我们略去了那些考虑 只 列出最核心的部分 c o m p o n e n t r e d 表示对结构体的访问 结构体 的类型信息T 可以从符号表中直接获得 而被访问 的域的类型信息可以从 获得的被访问的域的类型就是 c o m p o n e n t r e d 翻译后的表达式的类型t T o 等于L 表示 结构体基地址表达式的类型必须是t 类型 v a t e x p r 表示的是具体的变量 它是抽象语 法树的叶子节点 所以它只有正 没有L 变量的 类型信息T 可以从符号表中取得 变量表达式的 类型t 碘就是T 一a d d r e x p r 表示取地址操作 对应于c c 中的取地址符 由于它的唯一 孩子节点是叶子节点 我们把 k i d o g e tm a r k e dt y p eT e 口 Lf r o mn o d e 一 k i d o c o m p a r ei ft h et y p ei sc o m p a t i b l e l r e s C o m p a r e t y p e c o m p a t i b l e T 坤r T i i f r e s F A L S E i n s e r tt y p ec o n v e r s i o nt ot h em a r k e d t y p eL I n s e r t t y p e c o n v e r s i o n T i n f o r t h ei t hd i m e n s i o no ft h ea r r a y k i d i o u t p u t T r a n s l a t e n o d e j k i d i o u t p u t T r a n s l a t e c o m p o n e n t r e f t r e en o d e n o d e t r a n s l a t es t r u c t u r er e f e r e n c ee x p r e s s i o n T r 口n s Z 口 g 以o d e k i d o g e tm a r k e dt y p eT c l p r 瓦f r o mn o d e 一 k i d o c o m p a r ei ft h et y p ei sc o m p a t i b l e r e s C o m p a r e t y p e c o m p a t i b l e Z e q T i i f r e s F A L S E i n s e r tt y p ec o n v e r s i o nt ot h em a r k e d t y p eT i l I I n s e r t t y p e c o n v e r s i o n T o u t p u t 簧t r a n s l a t et h ef i e l d i nt h es t r u c t u r e t T r a n s l a t e n o d e k i d l O t h e rT r a n s l a t ef u n c t i o n s i 翻译算法中主要有C o m p a r e t y p e c o m p a t i b l e 和I n s e r t t y p e c o n v e r s i o n 这2 个函数需要关注 函 数C o r n p a r e t y p e c o m p a t i b l e 比较T 与T i 两个 类型对翻译而言是否等价 从而决定是否需要插入 强制类型转换 一般情况下只有T 与T i 完全相 同时才能匹配 但可以有如下例外 虽然指针类型 T 与数组类型T 2 不相同 假设指针类型T 指向 的元素类型是瓦 数组类型T 2 的数组元素类型是 丁4 只要T 3 和L 完全相同就可以认为T 与疋是 匹配的 例如可以认为指针类型i n t p 1 0 0 与数 组类型i n tp s o 1 0 0 3 是匹配的 加上这个例外之 后 翻译后的代码可以减少大量强制类型转换 函数 I n s e r t t y p e c o n v e r s i o n 负责在输出中插入强制类 型转换 由于c c 语言不允许数组或者结构体 类型的强制类型转换 所以需要把简单的强制类型 转换 t y p e 变成比较复杂的形式 t y p e 为 了减少对代码可读性的影响 我们引入C V T 宏 用 C V T t y p e 来插入强制类型转换 2 5 例子分析 第2 3 节已经叙述过图1 的例子 现在来看图 2 的例子在本文的翻译方式下怎样得到正确的翻译 结果 对图2 的例子首先进行类型恢复处理 a r r a y r e d 的父亲节点是整型计算节点 所以 a r r a y r e d 的T i 是i n t 类型 又因为瓦的类型i n t 的大小是4 个字节 而 a r r a y r e d 的数组访问元素的大小是8 个字节 所以 a r r a y r e d 的T e 是 c h a r 8 类型 而L 是 c h a r 8 类型 所以基地址表达式P 的 T i 是 c h a r 8 P 因为是 v a r e x p r 类型的节点 所以P 的t 是P 在符号表中的类型 s t r u c tX P 是叶子节点所以类型恢复过程结束 在翻译阶段 由 于P 的T i 和T e 不一致 而且 a r r a y r e d 节点的 T i 和T e 也不一致 所以翻译P 之后以及翻译 a r r a yr e D 之后都需要按照瓦的类型插入强制类型 万方数据 计算机研究与发展2 0 1 0 4 7 7 转换 得到对图2 的例子正确的翻译结果为C V T i n t c h a r 8 3 痧r i 1 2 6 翻译代码质量分析 从翻译算法可以看出 翻译的结果保留了中间 表示上数组 指针和结构体等高级语言的形式 这有 助于提高翻译后代码的可读性并有利于后端编译器 的分析和优化 但另一方面为了维护类型一致性的 需要 翻译生成的代码中插入了一些强制类型转换 但插入的强制类型转换大部分是不同指针类型之间 的转换 这样的类型转换只会影响再编译时编译器 对翻译代码的理解 不会导致生成多余的指令 所以 不会影响翻译代码再编译后的执行效率 虽然强制 类型转换会使翻译结果的可读性受到一定影响 但 我们通过实现较为宽松的类型比较策略减少了很多 强制类型转换 削弱了类型转换带来的负面影响 3 实验评价 因为O p e n 6 4 是一个有丰富分析和优化的编译 平台 有很多并行语言扩展和平台无关优化方面的 研究基于O p e n 6 4 编译器 所以本文的工作基于 O p e n 6 4 实现 我们选用的是p a t h s c a l e 2 2 编译器 p a t h s c a l e 编译器是O p e n 6 4 编译器的一个商业版本 的分支 在工作的前一阶段中我们继承了U p c c 3 1 和 O p e n u h H j 的已有基础 在此之上进行改进 前后花 费了大约8 个人月的时间才使大部分s p e c 2 0 0 0 通 过了0 2 选项 一小部分通过了0 3 选项 而且代码 变得更加复杂而且脆弱 进一步的工作很难继续 这 个过程也使我们积累了大量翻译错误的实例 我们 在此基础上分析总结了翻译错误发生的根本原因之 后 采用本文的类型恢复方法对翻译框架进行了重 新设计 然后只花费了4 个人月的时间就通过了 s p e c 2 0 0 0 的全部0 2 0 3 0 3 I P A 选项 实验分4 个部分 首先我们对源源翻译的正确 性进行测试 因为提高源源翻译的健壮性是本文工 作的中心 第2 部分我们把翻译结果再编译生成的 代码的性能与直接编译生成代码的性能进行比较 说明经过源源翻译后的代码性能没有下降 第3 部 分我们测试了类型恢复和翻译这两个阶段所占编译 时间 发现在打开优化选项之下类型恢复和翻译所 占时间很少 最后通过源源翻译把我们在A M D O p t e r o n 平台上实现的动态数据重组优化很容易地 移植到A l p h a 和龙芯平台 使一些例子得到了显著 的加速 以此示例源源翻译的作用 我们把源源翻译的代码生成方式称为两遍编译 的代码生成方式 即第1 遍编译得到翻译后的代码 再经过第2 遍编译生成可执行码 与之对应的是直 接编译的代码生成方式 如果两遍编译后的代码执 行结果与直接编译后的代码执行结果相同 就说明 翻译代码正确 我们一般认为选用的第2 遍编译的 编译器是可靠的 为了尽可能保证第2 遍编译的可 靠性 我们在正确性测试中第2 遍编译采用0 0 选 项 我们采用了包括过程间优化选项 I P A 在内的 各级优化选项测试了s u p e r t e s t 5 和s p e c 2 0 0 0 测试 包 因为本文只关注C 和C 的翻译问题 所以这 里只列出C 和C 的测试情况 测试集包括 s u p e r t e s t 中除带异常处理代码的C 例子之外的 所有测试例子 s p e c 2 0 0 0 测试集中所有C 和C 的测试程序 表1 中列出了测试环境 表2 给出了测 试结果 T a b l elC o r r e c t n e s sV a l i d a t i o nE n v i r o n m e n to fS o u r c et o S o u r c e s r c 2 s r cf o rs h o r t 表l 正确性测试环境 T h eF i r s tC o m p i l a t i o nT h eS e c o n dC o m p i l a t i o n T e s t i n gP l a t f o r m P a t h s c 赳e 2 2 p a t I s c a l e 2 2 0 0o p t i o n A M D O p t e r o n2 6G P a t h s c a l e 2 2 g c c 3 4 5 0 0o p t i o nA l p h aE V 6 76 0 0 M T a b l e2C o r r e c t n e s sT e s tR e s u l t 表2 正确性测试结果 T h e Firs 誉 S pe c2 0 0 0 i n t Scpec2000 f pCompilationoptions p r o g r t 盖嚣 n 1 2p r o g r a m s 4c a m s U p c c 和O p e n u h 的源源模块不支持C 以及 过程间优化 打开过程间优化后的源源翻译需要增 加一些特殊处理 所以我们在O p t e r o n 平台上测试 了0 3 选项下s p e c 2 0 0 0 中的C 程序 没有例子能够 通过 U p c c 仅在0 2 选项下能够通过它自带的用C 改写后的N P B 2 3 测试集中的6 个例子和s p l a s h 2 测试集中的2 个例子 这使得U p c c 虽然有很多目 标实验平台 但除x 8 6 x 8 6 6 4 i t a n i u m 之外的众多平 台上只能够执行有限几个例子 为了验证源源翻译输出的代码质量 图5 中对 直接编译和使用两遍编译得到的可执行码的性能进 行了对比 测试结果显示两遍编译的代码质量与一 遍编译几乎没有什么差别 由于维护类型一致性而 引入的强制类型转换对代码性能的影响很小 表3 给出了图5 性能测试的测试环境 万方数据 米伟等 带类型恢复的编译器源源翻译技术 1 1 5 3 T a b l e3T h eC o n f i g u r a t i o no ft h eT e s t si nF i g 5 表3F i g 5 中测试的测试配置 F i g 5 P e r f o r m a n c ec o m p a r i s o nb e t w e e nd i r e c tc o m p i l a t i o n a n dt w i c ec o m p i l a t i o n 图5 直接编译与两遍编译的性能比较 我们测试了类型恢复阶段和翻译阶段在第1 遍 编译中所占编译时间的比重 图6 中的结果是 s p e c 2 0 0 0 所有C 和C 程序测试结果的平均值 在总的编译时间中 0 0 选项下类型恢复时间占 2 5 翻译时间占2 5 4 在0 2 选项下类型恢复 时间占0 6 1 翻译时间占5 8 4 而在0 3 选项 下类型恢复时间仅占0 3 5 翻译时间占3 5 8 可见翻译阶段的编译时间所占比例在0 0 选项下比 较明显 在其他选项下比较小 而类型恢复的编译时 间所占比例在每一种选项下都很小 我们在p a t h s c a l e 2 2 中新添加了动态数据重 组优化 6 这项优化对s p e c 2 0 0 0 中a r t 和e q u a k e 两 个例子在O p t e r o n 平台上取得了很好的加速比 我们采用源源输出的方式把这项优化移植到A l p h a 处理器和龙芯上 图7 给出了测试结果 通过源源 翻译再编译 程序在A l p h a 和龙芯2 F 平台上同样 获得了显著的加速 通过源源编译支持我们很容易 地实现了平台无关优化的移植 表4 列出了数据重 组优化测试的测试环境 F i g 6 C o m p i l a t i o nt i m ed i s t r i b u t i