动态二进制翻译中基于中间代码的优化研究

论文摘要

如何提高动态二进制翻译系统的性能,是每个动态二进制翻译系统亟需解决的问题之一。基于中间代码层实现多源多目标的动态二进制翻译器,其中间代码层的性能至关重要。一是中间代码自身的效率。中间代码作为动态二进制翻译器中一层,一般以简单为设计的首要原则,每条指令只实现单一功能,导致中间代码膨胀严重,且带来一定程度的冗余信息。二是中间代码的优化机会。由于中间语言的平台无关性,对它进行的优化方法也是独立于平台的,所以可以构筑平台无关的、可重用的优化框架。为了改进中间代码的质量,提高二进制翻译器的性能,本文对二进制翻译中和中间语言相关的优化技术进行了研究。论文的主要工作包括:一、对基本块内的常用优化策略进行研究,针对CrossBit中间语言的组成和特性,提出了适合CrossBit中间语言的SSA形式化算法和冗余指令删除算法,大大减少了代码的膨胀率,使CrossBit系统的性能提升约10%30%。二、借鉴现有链接技术,在CrossBit上实现了路径线性化算法,减少了系统的上下文切换,使CrossBit系统的性能提升约10%30%。三、对动态优化技术进行研究,运用Profile实现热块的识别,并结合运用二级TCache以及VCache,为进一步进行动态优化奠定了基础。四、通过对后端寄存器分配算法的研究和比较,如全局寄存器分配、特殊寄存器分配、图染色法等,提出了适合CrossBit X86后端的基于next-use信息的寄存器分配策略。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 虚拟机技术
• 1.1.2 二进制翻译技术
• 1.1.3 二进制翻译技术研究现状
• 1.1.4 中间语言研究现状
• 1.2 研究目标
• 1.3 全文结构
• 第二章 CROSSBIT 及其中间语言
• 2.1 CROSSBIT 系统概述
• 2.2 CROSSBIT 的中间语言
• 2.2.1 设计思想
• 2.2.2 虚拟寄存器
• 2.2.3 寻址模式
• 2.2.4 访存策略
• 2.2.5 颗粒度
• 2.2.6 中间指令集
• 2.3 CROSSBIT 中间语言应用举例
• 2.4 CROSSBIT 性能评测
• 2.5 本章小结
• 第三章 基于CROSSBIT 中间代码的静态优化
• 3.1 SSA 形式化
• 3.2 冗余指令删除
• 3.2.1 算法描述
• 3.2.2 实验数据
• 3.3 死代码删除
• 3.3.1 算法描述
• 3.3.2 实验数据
• 3.4 本章小结
• 第四章 基于CROSSBIT 中间代码的全局优化
• 4.1 直接跳转（DIRECT BRANCHES）
• 4.1.1 翻译块链接（Translation Linking）
• 4.1.2 路径线性化（Trace Linearization）
• 4.2 条件跳转（CONDITIONAL BRANCHES）
• 4.2.1 回填技术（Back Patching）
• 4.3 间接跳转（INDIRECT BRANCHES）
• 4.3.1 分支预测（Software indirect jump prediction）
• 4.3.2 Pin 的改进
• 4.3.3 HDTrans 的改进
• 4.4 RETURN 语句
• 4.4.1 Return 缓存（Caching）
• 4.4.2 克隆（Cloning）
• 4.5 CROSSBIT 实现
• 4.6 本章小结
• 第五章 基于CROSSBIT 中间代码的动态优化
• 5.1 PROFILE 技术简介
• 5.2 热块识别
• 5.3 循环识别
• 5.4 热路径识别
• 5.5 “二级”TCACHE 的应用
• 5.6 VCACHE 的应用
• 5.6.1 VCache 工作原理
• 5.6.2 Profile 统计表
• 5.6.3 内存分配和组织方式
• 5.6.4 实验数据
• 5.7 本章小结
• 第六章 从中间到后端的寄存器分配
• 6.1 常用寄存器分配算法
• 6.1.1 特定寄存器分配
• 6.1.2 全局寄存器分配
• 6.1.3 图染色法
• 6.1.4 基于存活期的寄存器分配
• 6.2 CROSSBIT 中的寄存器分配实现
• 6.2.1 最简单的寄存器分配
• 6.2.2 一对一的寄存器分配
• 6.2.3 全局寄存器分配
• 6.2.4 基于next-use 信息的寄存器分配
• 6.2.5 图染色法
• 6.3 CROSSBIT 中各分配算法比较
• 6.4 本章小结
• 第七章 结论
• 参考文献
• 致谢
• 参与课题及已发表论文