对IA-64结构特性优化代码的二进制翻译技术研究

论文摘要

二进制翻译技术是解决软件移植问题的重要手段，为不同的指令集体系结构（ISA）间转换架起了桥梁，对促进软硬件之间的协调发展有着重要的意义，二进制翻译技术的研究已成为一个热点研究领域并且取得了很多研究成果。目前国内外的大部分二进制翻译系统都是针对源机器为32位机设计和开发的，64位体系结构为二进制翻译技术研究带来了新的挑战。本论文首先对基于IA-64平台的二进制代码翻译理论和实现技术做了充分研究，提出了二进制翻译模型的形式化描述以及描述语言驱动的方法。然后介绍了我们设计并实现的二进制翻译系统ITA及其关键技术。本文结合IA-64的二进制代码特性研究了如何提高静态翻译代码覆盖率的问题，重点讨论了跳转表和switch语句目标地址的恢复方法。最后深入研究了IA-64结构特性优化代码翻译技术：二进制代码中的谓词执行和投机代码消除技术。 本文的主要贡献如下： 1．建立二进制翻译的形式化描述，提出了使用机器描述语言驱动二进制翻译系统实现的方法，并结合可变源和目标的二进制翻译框架，分析了描述语言的应用对二进制翻译系统效率和能力的影响； 2．设计并实现了ITA静态二进制翻译系统，在实现这个系统的过程中，针对IA-64体系结构特性，提出了一些比较实用的技术，包括ELF64文件解码、指令束特性消除、复杂参数识别、语义映射、系统库函数恢复、结构特性优化代码消除等，这些技术的应用保证了ITA二进制翻译系统的正确性和翻译效率。 3．提出了静态恢复跳转表的算法，解决了含有跳转表的IA-64二进制代码的翻译问题。通过ITA翻译系统的有效性和正确性验证，表明该算法可以有效的识别IA-64在不同编译环境下产生的跳转表，恢复跳转目标地址，提高了静态翻译的代码覆盖率。 4．提出了基于谓词分析的谓词代码消除技术，解决了IA-64体系结构中谓词执行特性代码的翻译问题。提出了谓词分析算法，并依据谓词分析的结果实现了指令的反调度、谓词代码消除以及控制流图的优化，这些技术经过验证能显著降低生成代码的结构复杂度，提高了二进制翻译的代码质量。 5．提出并实现了针对IA-64控制投机代码的投机消除算法，解决了投机执行特性给二进制代码翻译以及程序理解带来的问题。该算法将投机代码下沉，消除具有投机形态的指令，并通过恢复代码的验证以及内存二义性消除，从而保证了程序变换前后语义的等价性。经过性能测试，表明该算法可以将带有投机特性的IA-64代码正确翻译到目标机代码，同时有效地提高了翻译生成的代码质量，显著提高了生成代码的执行效率。 ITA二进制翻译系统的正确性和有效性为本文取得的研究成果提供了保证，目前该系统已经通过了800多个C语言程序（约40多万行源代码编译生成的上百万条IA-64指令）

论文目录

• 摘要
• ABSTRACT
• 目录
• 表目录
• 图目录
• 第一章 引言
• 1.1 二进制翻译技术概述
• 1.1.1 静态二进制翻译和动态二进制翻译
• 1.1.2 相关工作
• 1.1.2.1 静态二进制翻译器
• 1.1.2.2 动态二进制翻译器
• 1.1.2.3 二进制代码优化器
• 1.2 IA-64体系结构
• 1.2.1 IA-64体系结构特点
• 1.2.2 IA-64二进制翻译中的难点问题
• 1.3 课题研究的意义
• 1.4 本文贡献
• 1.5 文章组织
• 第二章 相关基本概念与背景知识
• 2.1 相关的基本概念
• 2.1.1 控制流图
• 2.1.2 基本块
• 2.2 数据流分析
• 2.2.1 活跃变量分析
• 2.2.2 使用定义链
• 2.3 ELF64文件格式
• 2.3.1 ELF64文件header
• 2.3.2 ELF64文件中的表
• 2.4 IA-64指令格式
• 2.5 IA-64堆栈结构
• 2.6 动态连接
• 2.7 本章小结
• 第三章 可变源和目标的二进制翻译系统
• 3.1 引言
• 3.2 二进制翻译模型的形式化描述
• 3.3 描述语言
• 3.3.1 描述机器指令的语法
• 3.3.2 状态定义和操作语义描述
• 3.3.3 SSL语言
• 3.3.4 过程抽象语言 PAL
• 3.3.5 应用机器描述文件
• 3.4 应用实例
• 3.4.1 中间表示
• 3.4.2 前端模块
• 3.4.3 后端模块
• 3.4.4 实现效果及分析
• 3.5 本章小结
• 第四章 ITA二进制翻译系统
• 4.1 引言
• 4.2 ITA总体框架
• 4.3 二进制文件解码
• 4.4 解码 IA-64指令
• 4.4.1 指令解码过程
• 4.4.2 基本块的划分及控制流图的构建
• 4.4.3 指令束特性的消除
• 4.5 语义映射
• 4.6 过程抽象分析
• 4.6.1 过程识别
• 4.6.2 参数分析
• 4.6.3 返回值的恢复
• 4.6.4 系统库函数的恢复
• 4.7 优化代码消除
• 4.8 C代码产生器
• 4.9 实验结果及分析
• 4.9.1 代码膨胀率
• 4.9.2 代码执行时间
• 4.10 本章小结
• 第五章 跳转表恢复技术
• 5.1 引言
• 5.2 问题描述
• 5.3 IA-64跳转表特性分析
• 5.3.1 gcc 2.96的跳转表特性分析
• 5.3.2 gcc 3.2.3的跳转表特性分析
• 5.3.3 icc的跳转表特性分析
• 5.3.4 代码分析小结
• 5.4 switch语句目标地址恢复
• 5.4.1 gcc 2.96的switch语句目标地址恢复算法
• 5.4.2 gcc 3.2.3的switch语句目标地址恢复算法
• 5.4.3 icc 8.0的switch语句目标地址恢复算法
• 5.5 相关工作
• 5.6 实验数据
• 5.7 本章小结
• 第六章 IA-64谓词特性的消除
• 6.1 引言
• 6.2 谓词执行及对二进制翻译的影响
• 6.3 简单谓词消除策略
• 6.4 谓词分析
• 6.4.1 谓词关系
• 6.4.2 谓词分析算法
• 6.5 谓词消除技术
• 6.5.1 反调度
• 6.5.2 反谓词
• 6.5.3 控制边简化
• 6.6 相关工作
• 6.7 实现和试验结果
• 6.8 本章小结
• 第七章 IA-64投机代码消除
• 7.1 IA-64控制投机
• 7.1.1 控制投机机制
• 7.1.2 控制投机对二进制翻译的影响
• 7.2 简单处理方法
• 7.3 投机代码消除
• 7.3.1 装入下沉
• 7.3.1.1 分析指令间的关系
• 7.3.1.2 投机域
• 7.3.2 恢复代码验证
• 7.3.2.1 确定路径等价
• 7.3.2.2 验证装入等价
• 7.3.2.3 消除内存二义性
• 7.3.3 投机消除算法
• 7.4 实现及测试结果
• 7.5 相关工作
• 7.6 本章小结
• 第八章 总结和进一步的工作
• 8.1 文章总结
• 8.2 进一步的工作
• 致谢
• 参考文献
• 作者在学期间取得的学术成果