注解信息制导的动态二进制翻译及优化.pdf

收稿日期 3 和静态编译器 A 2B4 上实现了注解信息制导的动态二进制编译及优化技术 实验结果表明该三种注解信息较大程度地提高了动态 翻译码的执行效率 关 键 词 动态翻译 动态优化 编译器 注解信息 中图分类号 CD00 文献标识码 543 674 G HI J7 KL L 543 N 4 N J1 54 7 其中 有代表性的系统有 而言 利用 动态二进制翻译器翻译执行的速度大约是直接针对安腾编译 的二进制代码的执行 速 度 的 A B C A 图 给 出 8 在被动态翻译执行的时间分布图中 图 动态翻译执行 8 D 时间分布 D 4 H 6 如图 所示 优化翻译码的执行时间为 IA 普通翻译码 的执行时间为 A 而翻译开销仅为 A 可见对 8 这一类计算密集的程序而言 优化翻译码的效率是动态翻译 执行的关键 本节分析了优化翻译码效率较低的主要原因 并 说明了注解信息如何帮助提高翻译码效率 高级语言信息的缺失 相比较于源程序而言 编译器产生的二进制代码丢失了 大量的信息 主要有 高级语言的结构信息 如函数 循环 分支等相关信息 变量名信息及其作用域信息及高级数 据结构的信息如结构 数组 指针等 变量的修饰信息 如 2 0 J21 14 K 编译时用户直接输入的一些编译选项 信息等等 这些信息的丢失对动态二进制翻译器的翻译效率带来非 常不良的影响 高级语言程序结构上带有一些特殊信息 如函数或循环必定为单入口结构 函数体或循环体的范围信 息等等 没有这些信息 动态二进制翻译器只好作出保守的假 设 如所有翻译码块可能有翻译时不可见的前驱 预先读取的 代码的属性可能是不可读的 函数返回指令未必返回至调用 点等等 缺乏变量名信息及作用域信息使得动态二进制翻 译器无法进行有效的相关性分析 由于无法利用一些修饰 信息及编译选项 动态二进制翻译器失去了进行更积极地优 化来获得更高的性能的机会 利用注解信息可以很好地弥补高级语言信息的缺失 注 解信息可以说明二进制代码中函数体和循环体的范围 这样 动态二进制翻译器可以分析整个函数的代码 得到完整的控 制流图 同时 编译器在静态时分析得到的相关性分析的结果 也可以通过注解信息传递到动态二进制编译器 在体系结构差异时的翻译码质量 编译器在编译源软件时 它针对某一源体系结构生成指 令 如果该体系结构的指令集设计没有考虑动态二进制翻译 实现 这些指令可能比较很难用其他目的体系结构来模拟 尤 其在源体系结构与目的体系结构存在如下差异的情况下 动 小 型 微 型 计 算 机 系 统 L 年 万方数据 态二进制翻译产生的代码往往比较低效 寄存器数目及线 性地址空间大小 运算部件的执行环境及运算模型 内存一致性模型 微体系结构带来的影响等等 如果源体系结构的寄存器比较少 而目的体系结构的寄 存器比较多时 二进制翻译可能带来多余的内存操作 因为在 针对源体系结构编译源代码时 由于寄存器缺乏一些变量可 能被分配到内存里 这样的源代码在翻译成翻译码时 就存在 大量的内存操作 而对目的体系结构直接编译的代码将这些 变量直接分配到寄存器里而避免了这种多余的内存存取操 作 线性地址空间的差异可能会导致在内存操作时需要进行 地址的翻译 这会引入很多不必要的开销 如果运算部件的执行环境及运算模型不同 源指令对源 体系结构的状态更新可能需要用目的体系结构上的好几条指 令来模拟 譬如说 04 011 0 2 1 A2 B 1 01A G 242H0 2 1 之后 编译器还可以利用动态信息进行回馈优化 将二进制代 码试运行 并利用获取的动态信息对二进制代码进行再次优 化 在二进制翻译阶段 注解信息段在二进制文件被装载的同 时被装载 二进制翻译器中的注解信息读取器根据预定义格 式来读取注解信息 并将其组织成易于访问的内部表示结构 期 李剑慧 等 注解信息制导的动态二进制翻译及优化 万方数据 利用这些额外的注解信息 二进制翻译器可以产生更高质量 的翻译代码 从而提高翻译码的执行速度 对注解信息的读取 和利用不影响程序的正确运行 如果我们将源程序在编译时产生的中间表示传给动态二 进制翻译器 那么动态二进制翻译器将相当于该编译器对于 目标体系结构的一个后端 在这种情况下 中间表示完全包含 了源程序的一切关键信息 而不牵涉源体系结构的任何细节 也不存在机器码带来的精确异常的约束 故此 传递中间表示 信息可以得到最为理想的翻译码 然而 将整个中间表示作为 编译的输出会使得执行文件规模过大 失去了二进制代码文 件的意义 注解信息试图用最少量的信息来来解决上节中所 述的大部分问题 通过对这些关键信息的筛选 简化 拼装 我 们可以找到一个有效的表示来承载这些信息 注解信息可以 将源代码的信息以及在编译中分析出来的中间信息合并传递 给动态二进制翻译器 一个好的注解信息格式需要拥有如下 几点特性 格式紧凑 能被快速装载 能表示多种 注解信息 易于扩展 2 0 针对高级中间表示的分析及优化 选择生成目 标机器指令的低级中间表示 678 A8 2 8 0 调度及寄存器分配 最后对指令进行编码生成二进 制代码 注解信息可能在编译的不同阶段来采集 在编译器的 前端在作词法分析和语法分析的时候 它可以收集变量的定 义修饰符 编译选项信息等 在编译器生成中间表示并对其进 行分析时 它可以将分析的结果转换为注解信息进行保存 譬 如说 变量之间的数据相关性信息 有关循环的信息 有关函数 的信息 等等 最后 在生成低级中间表示并对它进行调度和寄 存器分配之后 它可以记录寄存器分配中的寄存器溢出信息 注解信息通常附着在中间表示上 对中间表示的各种优化及 变换需要保证注解信息的正确与完整 输入 附有注解信息的一个函数的中间表示 输出 函数注解信息表 注解信息数据段生成算法 初始化 BC 链表和 C 数组 按地址顺序 对函数中每一块 做 对每一种注解信息 D 做 分析并抽取该基本块的该种注解信息 如果成功 做 将该基本块 加入 C E 区间 否则 若 C D 区间不在 BC 的任一表元中 新增表元于 BC 表示该区间 将该区间的注解信息加入该表元 清空 C D 扫描 BC 的每一表元 若其范围覆盖全函数 尽可能用函数级信息描述廖表元注解信息 用区间级信息描述其他注解信息 否则 用区间级信息描述该表元的注解信息 图F 20 0 2 93 在生成二进制代码的阶段 注解信息生成器生成注解信 息数据段 通常过程式语言编译器以函数为单元生成二进制 小 型 微 型 计 算 机 系 统 GGH 年 万方数据 代码 所以注解信息数据段算法扫描函数的中间表示生成该 函数的注解信息表 所有函数的注解信息表组成注解信息数 据段 在生成函数的注解信息表时 该算法为每一种注解信息 生成尽量大的区间范围 以尽量减少区间的个数 并且 它将具 有相同区间范围的注解信息收集在一起 所以它们可以共用 区间级信息的头部空间 在区间范围以其注解信息收集好之 后 该算法生成符合格式注解信息表 若某一区间与函数范围 相同 则尽量用函数级信息中的特性码位来描述注解信息 对 不能用特征码来描述的注解信息 则用区间级信息来描述 在图 的算法中 我们用 58 给出了第二步中的按需读取注 解信息的算法 在优化翻译阶段 二进制翻译器先确定需要优化翻译的 指令范围 再生成这些指令的中间表示 然后在分析中间表示 的基础上 对翻译码进行优化和调度 一些表示函数范围或循 环范围的注解信息可以在二进制翻译器确定指令范围时使 用 这样可以使得生成的控制流信息更为完全和准确 而在分 析中间表示时 注解信息可以被参考 使分析结果更精确 从而 使得相关的优化及调度的幅度更大 效果更好 输入 被翻译的代码块首地址 输出 读取并利用注解信息制导优化的翻译码 按需读取注解信息算法 0 0 用块首地址 查询注解信息索引 树 如果一个 树节点的对应函数包含 0 0 如果 树节点中1未读取1位为2 0 0 取出当前函数注解信息表的首地址 读取函数级及区间级注解信息 将这些注解信息转化为内部表示 将1未读取1位置为 利用注解信息将代码块进行优化翻译 否则 将代码块进行优化翻译 图 0 按需读取注解信息算法 456 0 A9 9 8 85 8 5 B 6 58 实验结果 我们在英特尔的动态二进制翻译器1 C ADE F 1 C ADEF 和静态编译器1C 8 H 5 1上实现了 注解信息制导的动态二进制翻译及优化的整体框架 来验证 它的有效性 C ADEF 是英特尔开发的商用动态二进制翻译器 系统 它使得原来在 IJ3 体系结构上的应用软件无需移植即 可在安腾目标机上运行 C 8 H 5 是针对英特尔各种 体系结构采用最新编译优化技术的静态编译器 为了验证注 解信息制导的二进制翻译及优化方法的有效性 我们选取了 三种易于实现又比较有效的注解信息 赫兹 一级 尺寸为 3 字节 二级为 A 三级为 3 B 实验结果表明 该三种注解信息有较小的生成及读取时 表 C 三种注解信息的加速比平均值及其综合效果 D 9 C 4E E F G G 8 4 8 83 886 3 48 A BCC DE F CG FBB B 7 4 8 23 45 6 8 H 3 8 3 I BCCC JJ J KLGKE J H84 8 I 2 M 1 M 8 N48 3G 4 3 5 8 03 3 8 0 8 98 6 6 98 8 3 G 66 833 8 G 8 4 8 83 I 886 3 48 8 G 3 BCCJ L I48 O8 68 7 O P5 8 QR JB 8G6 8 86 3 A 7 EED S D 7 EED KTGTL K U48 I N4 3 8 8W8 0 8 BCCC JJ J T 2 8 N H A GJB 3 0 68 6 6 8 7AN BCCJ F M 08 H 2 8 N 3 48 V 3 0 0 8 6 G 98 6 I A 3 A 8 V I2XGBCCJ BCCJ D 3 7 H 3 I Y1YY2 Z 0W H898 8 3 I 8 8 8 BCCB E N 3 98 I M XZ 4 555 3 98 8 8 3 V 8 G6 98 6 3 H M 3 8 03 088 3 6 Y 98 3 N8 4 BCCL I 08 83 I P 7 S8 8 8W 8 8 83 5 4 48 038 48 Y MN 3 P I A P34 M G N 3 N8 4 I 4 8 0 8 8G 53 8 8 EEE B M S H083 8 5 6 M 8 V N 3 8 6 G 48 683 6 N X 8 A GJB 8W8 0 8 5 4 38 6 3 683 86 30 A GJB 3 A 0 G 386 3 3 8 JT 4 0 A V G 4 8 0 8 BCCJ E GBCL L 0 1 CCb G 4 8 0 BL 4 0 A V 4 8 0 8 EEF BTGJF K V 1 10 S8 03 8 8 6 8 0G 8 V 5 8 H 3 I A I2X CJ BCCJ JTGLF T H083 8 5 6 H83 6 8 88 6 8 886 3 48 A BCCK EJ B LJTGLLD F 8986 0 O08 9 9 0 I7 VA2 Z EEE 9 2 68 I 8 8 8 EEE D Q0G45 I 3 3 YV 8 0 YVBCCJ CCDDDTC 7 D BCCJ E Q O I 7 I 0 03 3 3 I 3 BCC KC T KLEG KTT BJ Z O U4 R0 V O0 M X 3G 3A7H 3 0 3 I 886 3 48 A 8 V BCCT BL 23 45 6 7 8 38 8W 8 38 886 3 48 V I G 3 0 3 BCCB J 期c c c李剑慧 等 注解信息制导的动态二进制翻译及优化c c 万方数据 注解信息制导的动态二进制翻译及优化注解信息制导的动态二进制翻译及优化 作者 李剑慧 王昀 黄波 乐永年 刘江宁 叶锦云 LI Jian hui WANG Yun HUANG Bo YUE Yong nian LIU Jiang ning YE Jin yun 作者单位 李剑慧 LI Jian hui 复旦大学 计算机科学与工程系 上海 200433 英特尔 中国软件中心 上海 200241 王昀 黄波 乐永年 刘江宁 叶锦云 WANG Yun HUANG Bo YUE Yong nian LIU Jiang ning YE Jin yun 英特尔 中国软件中心 上海 200241 刊名 小型微型计算机系统 英文刊名 JOURNAL OF CHINESE COMPUTER SYSTEMS 年 卷 期 2007 28 3 参考文献 24条 参考文献 24条 1 Transitive Corp 2 Ebcioglu K Altman E DAISY dynamic compilation for 100 architectural compatibility 1997 3 Baraz L Devor T Etzion O IA 32 execution layer a two phase dynamic translator designed to support IA 32 applications on Itanium r based systems 外文会议 2003 4 Bala V Duesterwald E Banerjia S Transparent dynamic optimization the design and implementation of dynamo 1999 5 Probst M Dynamic binary translation 2002 6 Bruening D Garnett T Amarasinghe S An infrastructure for adaptive dynamic optimization 外文会议 2003 7 Garnett T Dynamic optimization of IA 32 applications under dynamoRIO 2003 8 Zheng C Thompson C PA RISC to IA 64 transparent execution no recompilation 2000 03 9 Chernoff A Herdeg M Hookway R FX 32 a profile directed binary translator 外文期刊 1998 2 10 Dehnert J C Grant B K Banning J P The transmeta code morphing software using speculation recovery and adaptive retranslation to address real life challenges 2003 11 Michael Gschwind Dynamic and transparent binary translation 外文期刊 2000 03 12 Gschwind M Altman E R Precise exception semantics in dynamic compilation 2002 13 Li J H Zhang Q Xu S Huang B Optimizing dynamic binary translation for sIMD instructions 外文会议 2006 14 Kistler T Franz M Continuous program optimization design and evaluation 外文期刊 2001 06 15 Bik D Girkar M Inside the Intel compiler 2003 16 Intel Corporation Intel itanium architecture