黎明灰烬 博客 +

IA-32 执行层:一个用于在安腾系统上支持 IA32 应用的两阶段动态翻译器

review on IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium®-based systems.

Abstract

IA-32 Execution Layer (IA-32 EL) 是在 Intel 安腾(Itanium)系统上运行 IA-32 应用的新技术。当前,在安腾平台增加了额外硬件电路来兼容 IA-32 应用。在安腾平台的操作系统(包括 Windows 和 Linux)中集成IA-32 EL 软件,这种兼容能力会得到有效增强。

主要介绍了 IA32EL 的技术特征,包括通用的两阶段翻译架构和一个可用于多种操作系统的翻译器。还针对二进制翻译(binary translation)中的技术挑战和解决方法作了深入探讨,包括精确例外、浮点计算模拟、MMX 和 SSE 指令、非对齐处理。最后介绍了一些性能测试结果。

引言

安腾系统是 Intel 公司的新型高性能处理器平台,完全抛弃了 IA-32(x86)架构的历史包袱。但这带来的负面效果就是安腾系统不能运行 IA-32 指令。目前的结局方案是在安腾处理器中增加额外的硬件电路,从而实现IA32 指令兼容。而 IA-32 EL 是针对安腾处理器和 IA32 指令现状设计的一套纯软件系统,能加速安腾平台的 IA32 应用软件。

IA-32 EL 主要有三个特点:

概览

总体架构

从概念上讲,IA-32EL 是一个进程级的翻译器,和被翻译的进程共享一套地址空间和系统权限,原进程的映像和数据和它们在 IA-32 平台上运行一致。

IA-32 EL 被分为两部分:核心模块 BTGeneric、系统兼容模块 BTLib,从而有效地支持多个操作系统。其中,BTLib 用于为 BTGeneric 提供操作系统的服务,如内存分配等,两者通过精确定义的 API 协作。 

IA-32 EL 是一个独特的两阶段翻译器。第一阶段称作“冷代码翻译”(cold codetranslation)。这部分翻译器速度很快,开销很低,并负责在翻译后代码中插入用于鉴别热点代码段的测量器。冷代码翻译基于基本块(basic block),每个基本块包含约4-5 条 IA-32 指令。第二阶段称作“热代码翻译”(hot code translation)。热代码翻译将代码翻译识别出来的热点代码重新翻译、优化。热代码翻译基于踪迹(trace),每个踪迹包含约20 条 IA-32 指令。

冷代码翻译

一般的翻译器都没有所谓的「冷代码翻译」阶段,而是直接解释执行(interpretation)。IA-32 EL 的冷代码翻译使用附近的代码块信息来优化当前代码块的翻译。这种信息分析包含的步骤如下图所示。这种技术可以减少计算 IA-32 EFlags 的计算需求,也可加速浮点计算。分析会持续数个基本块,但不会执行到的基本块不会生成。

ia32el-cold-code-trans

 冷代码翻译阶段使用了预先准备的翻译模版来加速翻译和提高翻译效果。这些手工编写的翻译模版充分了利用安腾平台的特性。执行翻译后冷代码时会统计基本块执行次数、跳转边执行次数和非对齐检测。相比于常规的解释器信息统计,冷代码块的统计更加精确,代价也低。

翻译后基本块使用了直接跳转技术(direct jump)。未能预测到的间接分支通过一个快速查找表来检索分支目标。如果目标是一个尚未翻译的基本块,那么将跳转到翻译器中。翻译器负责翻译基本块,并更新块间直接跳转信息。有几个冷代码块会一直存在,它们用于处理浮点例外(FPexception)、自修改代码(self-modify code)等情况。冷代码块可能会因为多种原因而被回收:垃圾收集、库卸载和自修改代码检测。

热代码翻译

在翻译后冷代码执行过程中,当一个基本块的执行次数达到阈值,便将其注册为热代码预备块。注册过程由翻译器中的特殊函数完成,插在基本块中的阈值检测函数负责转向该函数。

当已注册的块数达到一定数量,或者一个块被注册了两次,即刻启动热代码翻译。热代码翻译首先评估多个代码块,并将它们重新组合、分割。大约有 5-10% 的冷代码块回达到注册阈值。

ia32el-overall-code-trans

 热代码翻译分为多个步骤,下面将一一介绍。 

踪迹筛选

首先,翻译器选择多个基本块来组成一个超块(hyperblock),又称踪迹。踪迹是一段包含一个入口和多个出口的代码。踪迹筛选基于块计数和分支边计数的统计数据。类似 if … then …if … then … else … 的分支的两边都可能会被筛选为一个线性踪迹的一部分。这种预测性筛选将会提高运行效率。被识别为循环的代码段可能会被展开(loop unroll)。只有约 6% 的热踪迹会发生早期退出(一个踪迹尚未执行完时发生跳转)。

中间代码生成

接下来,原始的 IA-32 代码会被再次解码和分析。这里的解码和冷代码翻译无关。冷代码会被转换成一种目标机器指令的中间语言(Intermediate Language)表示,并存储在链表中。这种中间表示生成和预先准备的翻译模版源自同一套模版源代码。

在中间代码生成阶段,翻译器主要展开以下几方面优化:

  1. 在非对齐访存处加入避免非对齐的代码。非对齐由冷代码的检测器检测。
  2. 跟踪 IA-32 地址和其值,并消除类似 [offset + base + index * scale] 的典型的 IA-32 代码。
  3. 跟踪寄存器中的值,并用它们来简化翻译。
  4. 用冷代码翻译中类似的技术来减少 EFlags 生成。
  5. 分析浮点栈和 SSE 模式变化。
  6. 执行其他浮点优化,如寄存器分配和 FXCHG 削弱。

执行流图优化

翻译器扫描中间代码表来建立一个数据依赖关系图。然后移除死边(dead ILs),并将边出口(side-exits)的标记为边缘(sideway ILs)。翻译器为每个边计算权重,并对图进行调度。基于窥孔,使用依赖关系消除多余指令。

调度中间代码

紧接着,调度器将指令分配成热块。中间代码将基于架构的特点被重排、组合。翻译器使用寄存器重命名和控制和数据推测来优化重排。 

精确处理

翻译器还生产可用于处理例外和中断的恢复信息。边缘会独立与主块调度,除非他们能高效地整合进主块。

组织

最后编码后的块及其信息被放到翻译缓冲中,并和其他的代码连接起来。 

总体来说,每条 IA-32 指令的热代码翻译开销大约是冷代码翻译开销的 20 倍。

与操作系统交互

IA-32 EL 在 64 位系统上以应用的虚拟地址空间和特权级运行,代替操作系统为 IA-32 应用提供透明的运行时环境。IA-32 EL 要使用操作系统的诸多服务,如内存分配、同步堆笑等;也要执行 IA-32 应用发出的系统调用、信号处理、例外等系统通知。

IA-32 EL 分为两部分以方便地支持多个操作系统—— BTGenericBTLib 。系统抽象层 BTLib 约占 IA-32 EL 映像的 1%. BTGeneric 模块在所有平台上都是同一份代码,运行时由 BTLib 加载。

BTGenericBTLib 之间的接口 BTOS API 是二进制兼容的,且不依赖于编译器或操作系统。BTOS API 由两者联合实现。BTLibBTGeneric 提供诸如内存分配、例外处理的服务。为了维护 BTGenericBTLib 的兼容性,还使用了一个私有的版本控制系统。

interacting with OS

高效精确的例外处理

状态恢复/精确例外是二进制翻译和虚拟机的一大难题,对于 IA-32 EL 这样高度优化的软件而言就更为艰巨。这主要是因为一个源指令会被翻译为多个目标指令,而例外未必发生在最后一条目标指令。高性能的二进制翻译软件大多采用激进的代码调度算法,源机器和目标机器之间的状态一致性难以得到保证。

例外处理

当翻译后代码发生例外时,执行的是安腾代码,这意味着:PC 不同、例外代码不同、寄存器是 64 位的。在例外传递给 IA-32 应用前,IA-32 EL 要讲安腾转换成对应的 IA-32 状态,从而模拟 IA-32 例外处理。在第一次例外处理过程中,例外处理代码可能被更改过,从而能对应于 IA-32 应用的例外。

某些情况下,例外会被忽略或终止,因为原来的 IA-32 代码不应该发生例外,从而避免进一步破坏应用的例外处理函数。例如,IA-32 代码屏蔽了浮点例外,而翻译后代码要求启用浮点例外来支持 SSE 例外。(IA-32 可以分别屏蔽 FP 和 SSE 例外,但安腾不行。)

冷代码翻译的状态恢复

冷代码翻译要求任何例外发生时 IA-32 状态都能正确地恢复。IA-32 EL 使用「懒惰更新」IA-32 状态来完成,即当(潜在的可能会发生错误的)翻译后指令全部执行完毕后才更新 IA-32 的状态,如下表所示。

ia32el lazy state update

在每个执行序列开始时,IA-32 EL 将 IA-32 的一些状态信息保存下来,以便当例外发生且定位时用于恢复原始状态。不过,这一操作只针对可能会发生错误的指令使用。冷代码翻译的例外处理机制几乎不会增加执行时间或代码大小。

热代码翻译的状态恢复

热代码翻译的状态恢复就难多了:

IA-32 EL 使用「提交点」( commit point )来解决激进代码重排带来的精确例外问题。提交点是一种让翻译器能生成一致性 IA-32 状态的「屏障」:每个提交点可能涵盖了多个故障点(faulty points);限制属于不同提交点的指令重排;和冷代码类似,对于每次代码翻译,当最后一个故障点之后才更新 IA-32 状态。

IA-32 EL 尽量在提交点中包含更多的故障点(约每 10 条指令一个提交点)。第一个提交点经常设置在基本块的开始处,之后在不可恢复错误发生或无法维持 IA-32 状态时才会被更改。当例外发生时,翻译器将 IA-32 状态置为后备(提交点)的状态。

使用提交点后,IA-32 EL 能进行激进的指令重排,因为只有在分区的最后一个故障点才需要一致性的 IA-32 状态。如果在执行过程中发生例外(没到最后故障点),翻译器直接忽略例外直到分区的最后一条指令。

优化

IA-32 和安腾是架构差别巨大的两个平台,IA-32 EL 优化具有很大的挑战。

浮点模拟相关优化

IA-32 浮点指令使用八个组织在「浮点栈」中的 80bit 寄存器,SSE 指令使用八个 128bit 的 XMM 寄存器。Itanium 的浮点和 SSE 指令共同使用一个包含 128 个 82bit 寄存器的寄存器文件。IA-32 浮点栈的有效性由一个 TAG 寄存器标识;浮点单元控制字中的 TOS 域标识当前浮点栈的栈底 ST(0) 。栈底 ST(0) 是用得最多的浮点操作数,尽管它并不是浮点栈的一个固定位置。另外,IA-32 的 64bit MMX 寄存器在最开始被绑定成浮点栈里的寄存器。Itanium 的 MMX 指令直接操作整数寄存器。

本节主要介绍针对浮点处理的三个方面:消除浮点栈、将浮点寄存器绑定为 MMX 寄存器、处理 XMM 数据格式。

浮点模拟面临的问题

首先,浮点栈模拟主要有两个问题:第一,将动态浮点栈映射成静态寄存器会带来大量的数据搬移操作;而直接使用内存模拟的性能开销又太高。第二,每次访问浮点寄存器时都要检查 TAG ,以便发现条目缺失这样的浮点栈错误。

其次,浮点和 MMX 寄存器绑定也很麻烦:因为 Itanum 的 MMX 寄存器实际上是整数寄存器,因此浮点和 MMX 操作都会产生数据搬移,开销太大。

另外,IA-32 指令在处理 XMM 寄存器时使用四种数据形式——整数、单精度浮点、双精度浮点、向量。在安腾上操作是均需要做形式转换。

最后,IA-32 的浮点操作经常被限制为浮点栈底,这导致大量的 fxchg 操作来交换浮点栈中的数值。不过安腾没有这种限制,可以轻松的通过寄存器重命名来解决该问题。

基于程序行为的优化

IA-32 EL 主要依赖于「对程序行为的推断假设」来构造特殊的优化场景。每次翻译代码时,会在基本块头部插入一个检查机制来验证「推断」是否成功,如果失败了就进行特殊处理。基本块结束后悔更新状态从而继续该检查。这有点类似于「转移猜测」,不同之处是这里的猜测依赖于编程的某种「隐性约束」。下面将详细介绍。

针对浮点栈消除的推断是:对于同一个块而言,TOS 是个常量,且不产生栈例外。基于这种假设,可以对浮点寄存器使用固定映射,并在块的头部检查 TOSTAGTOS 不匹配时,调换寄存器值;TAG 不匹配时,重建一个特殊的块来捕获正确的栈错误。这种推断非常有效,正确性约为 99-100%。

针对浮点和 MMX 寄存器绑定的推断是:如果当前块包含浮点(MMX)指令,那进入当前块的前一条浮点或 MMX 指令是浮点(MMX)指令,分别地。因此,不存在浮点和整数寄存器之间的形式转换,只要用一个布尔值来检查就行。这种测量的正确性几乎达到了 100%,说明浮点和 MMX 指令确实没有被混合使用。

针对多 SSE 格式的推断是:当前块和上一个块的格式是一致的,不需要转换。块的头部将 XMM 寄存器和当前运行时状态比较,如果有需要才转换格式。在 SPEC2000 测试中,最坏情况下格式转换率只有 0.2%.

非对其访存的处理

IA-32 平台的非对其访存开销不高,因而被应用程序广泛使用。而安腾作为现代体系结构,硬件是不支持非对其访存的,软件模拟的开销往往高达上千个时钟周期。因此在模拟 IA-32 时,非对其访存是个重要问题( FX!32 系统也面临这样的问题)。IA-32 EL 的非对其访存优化机制非常高效。有一个曾经耗时 1236 秒的应用在采用了「非对其检测与避免」机制后,执行时间减少到 133 秒。

一个非对其检测与避免的例子如下面所示。尽管该方法避免了非对其惩罚(由操作系统模拟),但开销也很大,因为每条访存指令都需要这样的处理。(特别地,由「转移猜测失效」引起的开销会很大,这源于现在处理器的架构设计。)

// test bit0 to see if address is 2byte aligned.
// Predicates p.mis and p.al set appropriately.
// Will use p.mis and p.al to predicate the following instructions.
tbit p.mis,p.al = r.addr, 0
  
// 2 byte load if aligned
(p.al) ld2 r.val = [r.addr]
  
// if misaligned load each byte separately
(p.mis) ld1 r.val = [r.addr]
(p.mis) add r.addrH = 1, r.addr
(p.mis) ld1 r.valH = [r.addrH]
  
// combine the separately loaded bytes 
(p.mis) dep r.val = r.valH, r.val, 8, 8

IA-32 EL 对非对其访存的处理分为三个阶段:

  1. 冷代码翻译阶段插入简单的剖析仪表:当非对其访存出现时跳转到翻译器中,重新翻译该块。这里的剖析是粗粒度的,只知道某个块里发生了非对其访存,而不知道具体指令。
  2. 重新翻译的代码带有非对其检测与避免功能:执行过程被精确剖析,比如非对其指令和非对其类型。有了这样的高精度仪表后,在执行热代码翻译时生产的代码量就非常小。
  3. 在热代码翻译阶段,每个冷代码块的信息都会被手机起来,每条「非对其访存指令」都会使用如上述的检测与避免代码。同时,还包括两点改进:首先,非对其检测会记录地址,如果这次非对其访存的类型和上一次一致(比如都是双字节访存),那么直接使用上一次的非对其检测结果;其次,如果非对其检测与避免的代码太长了,那么这些代码会和翻译后热代码分开存放,按序跳转,类似旁路指令。

对于这套机制依然不能处理的特殊情形,还需要改进第三阶段:如果某条指令没有被观察到非对其访存,但发生的后果很严重时,会为这样的指令插入开销极地的特殊剖析仪表。当非对其发生时,翻译器再次启动,重新翻译这些代码,并为这些指令加入非对其检测与避免功能。

性能测试

这里主要介绍在 1G 双核安腾芯片(3MB L3 缓存,2GB 内存)上的测试结果,包括 SPEC CPU2000 和 Sysmark 2002. IA-32 二进制使用 ICC 6.0 编译。

speccpu2000 score

SPEC CPU2000 大约有 65% 的本地(应该是指安腾)性能。其中 mcf 比本地性能更高应该是因为 IA-32 使用的是 32 位数据,相比于 64 位的本地测试,内存消耗更少。SPEC CPU2000 测试中有 95% 的时间在执行热代码,这说明 IA-32 EL 的踪迹筛选是非常有效的。冷代码对此也有贡献:其他的使用解释器的翻译器要尽早进入翻译阶段,所以收集的剖析数据不够具有代表性。热代码的性能一般比冷代码高出 3 倍,这说明踪迹筛选高效且有可优化空间。

speccpu2000 exec time

sysmark2000 exec time

Sysmark2000 是更为复杂的应用,热代码执行时间只占 46%,翻译代价也较高。不过越有 22% 的时间都花在了内核和驱动上,这些功能是本地执行的,Windows 应用大多都是这样。仍有 15% 的时间系统挂起,这些应该是潜在的可以用作翻译器工作的时间。

relative-performance-of-ia32el

在安腾上 IA-32 EL 性能和 IA-32 平台相比如上图,两者基本上差不多。值得注意的是浮点数据,这一方面是源于安腾强大的浮点性能,另一方面源于 IA-32 EL 的浮点优化。

Review

总体而言,IA-32 EL 的设计比较工程化,采用的优化手段也比较工程师……可惜,以「兼容性」为目标的二进制翻译从来都是会失败的,Intel 也不例外。即使是相隔十年之后的 Houdini 也逃脱不了这种命运,不过还是很荣幸能成为该小组的一员。

黎明灰烬 博客

Creative Commons License 信箱:i(at)jackwish.net

计算机

清 谈