用于在程序代码转换期间执行解释器优化的方法和装置

摘要

翻译器装置具有解释和翻译功能性的程序代码(17)，其中在确定源程序代码(17)的解释更有利的那些情况下，解释源程序代码(17)而不是翻译。翻译器(19)应用解释算法来确定源程序代码(17)的基本块是否应当被解释或翻译。从用于源程序代码(17)的整个指令集初始地选择由解释器支持的特定源指令。1)如果确定基本块内的所有指令在由解释器功能性支持的指令的子集内，以及2)如果基本块的执行计数低于一个翻译阈值，将解释基本块。如果不满足这两个条件的任何一个，则由翻译器(19)翻译基本块。

说明书

技术领域

本发明通常涉及计算机和计算机软件领域，以及更具体地说，涉及例如用在译码器、仿真器和加速器中的程序代码转换方法和装置。

背景技术

在内置和非内置CPU中，发现最主要的指令集体系结构(ISA)，存在能“加速”性能，或“转换”成能提供更好成本/性能好处的多种处理器的大的软件体，只要它们能透明地访问相关软件。还发现卓越的CPU体系结构，及时锁定到它们的ISA，以及不能在性能或市场占有率方面进展。这种体系结构将受益于“综合CPU”协同体系结构。

程序代码转换方法和装置便于这些加速、翻译和协同体系结构能力并在例如公开专利号WO 00/22521名为“Program CodeConversion”中解决。

发明内容

根据本发明，提供一种如在附加权利要求书中阐述的装置和方法。本发明的优选特性将从从属权利要求及下述说明书显而易见。

下文是根据本发明的各个实施例可实现的各种方面和优点的概述。提供为帮助本领域的技术人员更快速地吸收随之发生的详细设计论述的介绍，以及不是而且不打算用任何方式限制附加的权利要求的范围。

具体地，发明人已经开发出针对加速程序代码转换，特别是结合采用将源程序代码的连续基本块翻译成目标代码的运行时间翻译器使用的多种优化技术，其中，在生成用于下一基本块的目标代码之前，执行对应于第一基本块的目标代码。

在这样一种优化中，翻译器具有程序代码解释和翻译两种功能，其中，在确定源程序代码的解释更有利的那些情况下，解释源程序代码，而不是翻译。翻译器应用解释算法来确定应当解释还是翻译源程序代码的基本块。首先从用于源程序代码的整个指令集中选择解释器功能性所支持的特定源指令。1)如果确定基本块内的所有指令均在解释器功能性所支持的指令子集内，以及2)如果基本块的执行计数低于翻译阈值，则将解释基本块。如果不满足这两个条件的任何一个，那么将由翻译器翻译基本块。

附图说明

包含在并构成说明书的一部分的附图示例说明当前的优选实现以及描述如下：

图1是本发明的实施例发现应用的装置的框图；

图2是示例说明运行时间翻译过程以及在该过程期间生成的相应IR(中间表示)的示意图；

图3是示例说明根据本发明的示例性实施例的基本块数据结构和高速缓存的示意图；

图4是示例说明扩展的基本块过程的流程图；

图5是示例说明等成块(isoblocking)的流程图；

图6是示例说明组成块和附带优化的流程图；

图7是示例说明组块(group block)优化的例子的示意图；

图8是示例说明运行时间翻译，包括扩展基本成块、等成块和组成块的流程图；

图9是示例说明组成块和附带优化的另一优选实施例的流程图；

图10A-10B是表示示例说明局部死码消除优化的例子的示意图；

图11是示例说明局部死码消除优化的流程图；

图12是示例说明延缓字节交换优化的例子的流程图；

图13A-13C是表示示例说明延缓(lazy)字节交换优化的例子的示意图；

图14是其中本发明的实施例发现应用的装置的框图；以及

图15是示例说明解释过程的流程图。

具体实施方式

用于实现下述各个新颖特征的示例性装置如图1所示。图1示例说明包括目标寄存器15的目标处理器13以及存储多个软件成分19、20、21的内存18，提供包括基本块高速缓存23、全局寄存器库27的工作存储器16和将转换的源代码17。软件成分包括操作系统20、翻译器代码19和已翻译代码21。翻译器代码19可以例如充当将一个ISA的源代码翻译成另一ISA的翻译代码的仿真器，或充当用于将源代码翻译成翻译代码的加速器，每个具有相同的ISA。

翻译器19，即实现翻译器的源代码的编译版本，以及已翻译代码21，即，由翻译器19生成的源代码17的翻译，与操作系统20，诸如例如在目标处理器13，通常是微处理器或另一适当的计算机上运行的UNIX结合运行。将意识到图1所示的结构仅是示例性的，以及例如，根据本发明的软件、方法和过程可以用驻留在操作系统内或下的代码来实现。源代码、翻译器代码、操作系统和存储机制可以是多种类型的任何一个，如本领域的技术人员所公知的。

在根据图1的装置中，在已翻译代码21运行的同时，在运行时间，最好动态地执行程序代码转换。翻译器19与已翻译器21内联运行。翻译过程的执行路径是包括下述步骤的控制循环：执行翻译器代码，将源代码17的一个块翻译成已翻译代码21，然后，执行已翻译代码的块；已翻译代码的每一块的末尾包含使控制返回到翻译器代码19的指令。换句话说，交错翻译然后执行源代码的步骤，使得每次仅翻译部分源程序17，以及在翻译后续基本块之前，执行第一基本块的已翻译代码。翻译器的基本翻译单元是基本块，指的是翻译器19每次翻译源代码17的一个基本块。基本块形式上被定义为具有正好一个入口点和正好一个出口点的代码段，使块代码限制到单个控制路径。为此，基本块是控制流的基本单元。

在生成已翻译代码21的过程中，基于源指令序列而生成中间表示(“IR”)树。IR树是所计算的表达式和由源程序执行的操作的抽象表示。稍后，基于IR树，生成已翻译代码21。

在此所述的IR节点的集合通俗地被称为“树”。我们注意到形式上，这些结构实际上是有向非循环图(DAG，directed acyclic graph)，而不是树。树的正式定义要求每个节点具有至多一个父辈。因为所述实施例在IR生成期间使用公共子表达式消除，节点将总是具有多个父辈。例如，可以由对应于目的地源寄存器和标记结果参数的两个抽象寄存器引用标志影响的指令结果的IR。

例如，源指令“add％r1，％r2，％r3”执行相加源寄存器％r2和％r3的内容并将结果存储在源寄存器％r1中。因此，该指令对应于抽象表达式“％r1＝％r2+％r3”。该举例包含用加法表达式来抽象寄存器％r1，该加法表达式包含表示指令操作数％r2和％r3的两个子表达式。在源程序17的上下文中，这些子表达式可以对应于其它、先前的源指令，或它们可以表示当前指令的详情，诸如中间常量值。

当解析“加法”指令时，对应于加法的抽象数学运算符，生成新的“+”IR节点。“+”IR节点存储对表示操作数的其它IR节点的引用(在IR中表示为子表达式树，通常保存在源寄存器中)。“+”节点由定义其值的源寄存器自身引用(用于％r1的抽象寄存器，指令的目的地寄存器)。例如，图20的中心右部分表示对应于X86指令“add％ecx，％edx”的IR树。

如本领域的技术人员将意识到的，在一个实施例中，使用面向对象的编程语言，诸如C++来实现翻译器19。例如，IR节点被实现为C++对象，以及对其它节点的引用被实现为对相应于那些其它节点的C++对象的C++引用。因此，IR树实现为IR节点对象的集合，包含彼此的各种引用。

另外，在论述中的实施例中，IR生成使用一组抽象寄存器。这些抽象寄存器对应于源体系结构的具体特征。例如，对于源体系结构上的每个物理寄存器存在唯一一个抽象寄存器(“源寄存器”)。类似地，对于在源体系结构上存在的每个条件码标志存在唯一一个抽象寄存器。抽象寄存器在IR生成期间，用作用于IR树的占位符。例如，源指令序列中指定点处的源寄存器％r2的值用特定IR表达式树来表示，其与用于源寄存器％r2的抽象寄存器有关。在一个实施例中，抽象寄存器被实现为C++对象，其经由对那个树的根节点对象的C++引用与特定IR树有关。

在上述的示例性指令序列中，翻译器已经生成对应于％r2和％r3的值的IR树，同时解析在“add”指令前的源指令。换句话说，计算％r2和％r3的值的子表达式已经表示为IR树。当生成用于“add％r1，％r2，％r3”指令的IR树时，新的“+”节点包含对用于％r2和％r3的IR子树的引用。

在翻译器代码19和已翻译代码21中的各组件之间，划分抽象寄存器的实现。在翻译器19内，“抽象寄存器”是用在IR生成过程中的占位符，因此抽象寄存器与计算特定抽象寄存器对应的源寄存器的值的IR树有关。如此，翻译器中的抽象寄存器可以被实现为包含对IR节点对象(即IR树)的引用的C++对象。由抽象寄存器集引用的所有IR树的集合被称为工作IR森林(“森林”，因为它包含多个抽象寄存器根，每个被称为一个IR树)。工作IR森林表示源代码中特定点处的源程序的抽象运算的快照(snapshot)。

在已翻译代码21内，“抽象寄存器”是全局寄存器库内的特定位置，来往该位置源寄存器值与实际目标寄存器同步。或者，当从全局寄存器库加载一个值时，能将已翻译代码21中的抽象寄存器理解为目标寄存器15，该目标寄存器在保存回寄存器库之前，临时保存执行已翻译代码21期间的源寄存器值。

如上所述的程序翻译的例子如图2所示。图2表示x86指令的两个基本块的翻译，以及在翻译过程中生成的相应IR树。图2的左侧表示在翻译期间，翻译器19的执行路径。在步骤151，翻译器19将源代码的第一基本块153翻译成目标代码21，然后，在步骤155，执行那个目标代码21。当目标代码21结束执行时，控制返回到翻译器19，在步骤157中，翻译器将源代码17的下一基本块159翻译成目标代码21，然后，执行那个目标代码21，步骤161等等。

在将源代码的第一基本块153翻译成目标代码的过程中，翻译器19基于那个基本块153，生成IR树163。在这种情况下，由为标志影响指令的源指令“add％ecx，％edx”，生成IR树163。在生成IR树163的过程中，由该指令定义四个抽象寄存器：目的地抽象寄存器％ecx167、第一标志影响指令参数169、第二标志影响指令参数171以及标志影响指令结果173。对应于“add”指令的IR树是“+”运算符175(即，算术加法)，其操作数是源寄存器％ecx177和％edx179。

因此，第一基本块153的模拟通过存储标志影响指令的参数和结果，使标志处于未决状态。标志影响指令为“add％ecx，％edx”。指令的参数是模拟的源寄存器％ecx177和％edx179的当前值。在源寄存器177，179前使用的“@”符号表示当先前未由当前基本块加载那些特定的源寄存器时，从全局寄存器库分别对应于％ecx和％edx的位置检索源寄存器的值。然后，将这些参数值存储在第一和第二标志参数抽象寄存器169、171中。加法运算175的结果存储在标志结果抽象寄存器173中。

在生成IR树之后，基于IR而生成相应的目标代码21。由普通IR生成目标代码21的过程在本领域很好理解。将目标代码插入已翻译块的尾部以便将抽象寄存器，包括用于标志结果173和标志参数169、171的那些保存到全局寄存器库27。在生成目标代码之后，然后执行步骤155。

图2表示交错翻译和执行的例子。翻译器19首先基于第一基本块153的源指令17，生成已翻译代码21，然后，执行用于基本块153的已翻译代码。在第一基本块153的结束，已翻译代码21将控制返回到翻译器19，然后，翻译第二基本块159。然后执行用于第二基本块161的已翻译代码21。在执行第二基本块159结束时，已翻译代码将控制返回到翻译器19，然后翻译下一基本块等等。

由此，在翻译器19下运行的源程序具有用交错方式执行的两种不同代码：翻译器代码19和已翻译代码21。在运行时间之前，基于翻译器19的高级源代码实施，由编译器生成翻译器代码19。由翻译器代码19基于正被翻译的程序的源代码17，在整个运行时间中生成已翻译代码21。

在翻译器19和已翻译代码21的各组件之间，同样地划分源处理器状态的表示。翻译器19在各种显式编程语言设备，诸如变量和/或对象中存储源处理器状态；用于编译翻译器的编译器确定如何用目标代码实现状态和操作。通过比较，已翻译代码21将源处理器状态隐含地存储在直接由已翻译代码21的目标指令操作的目标寄存器和内存位置中。

例如，全局寄存器库27的低级表示简单地是分配的内存区域。这是已翻译代码21如何通过在所定义的内存区和各个目标寄存器之间保存和恢复，来查看抽象寄存器并与之交互作用。然而，在翻译器19的源代码中，全局寄存器库27是数据阵列或能在更高级存取和操作的对象。相对于已翻译代码21，简单地不存在高级表示。

在一些情况下，为静态或在翻译器19中可静态地确定的源处理器状态被直接编码成已翻译代码21，而不是动态地计算。例如，翻译器19可以生成在最后一个标志影响指令的指令类型上指明的已翻译代码21，表示如果改变最后一个标志影响指令的指令类型，则翻译器对于相同基本块，将生成不同的目标代码。

翻译器19包含对应于每个基本块翻译的数据结构，特别便于扩展的基本块、等块(isoblock)、组块和高速缓存的翻译状态优化，如下所述。图3示例说明这种基本块数据结构30，包括源地址31、目标代码指针33(即已翻译代码的目标地址)、翻译提示(translation hint)34、入口和出口条件35、剖析量度(profiling metric)37、对前导和后续基本块38，39的数据结构的引用，以及入口寄存器图40。图3进一步示例说明基本块高速缓存23，其是由源地址索引的基本块数据结构，例如30，41，42，43，44...的集合。在一个实施例中，对应于特定已翻译基本块的数据可以存储在C++对象中。当翻译基本块时，翻译器创建新的基本块对象。

基本块的源地址31是源程序17的存储空间中那个基本块的起始地址，表示如果源程序17正运行在源体系结构上，将定位基本块的内存地址。这也被称为源起始地址。当每个基本块对应于源地址的范围(一个用于每个源指令)时，源起始地址是基本块中第一条指令的源地址。

基本块的目标地址33是目标程序中已翻译代码21的内存位置(起始地址)。目标地址33也被称为目标代码指针，或目标起始地址。为执行已翻译块，翻译器19将目标地址视为解除引用以调用(传送控制到)已翻译代码的函数指针。

基本块数据结构30，41，42，43，...存储在基本块高速缓存23中，其是按源地址组织的基本块对象的储存库。当基本块的已翻译代码结束执行时，其将控制返回到翻译器19，以及还将基本块的目的地(后继)源地址31的值返回给翻译器。为确定是否已经翻译了后继基本块，翻译器19将目的地源地址31与基本块高速缓存23中的基本块的源地址31(即已经翻译的那些源地址)进行比较。翻译还没有被翻译的基本块，然后执行。仅执行已经翻译(以及具有可兼容入口条件，如下所述)的基本块。随时间过去，将已经翻译所遇到的许多基本块，导致降低递增的翻译成本。如此，翻译器19随时间变得更快，因为越来越少的块要求翻译。

扩展的基本块

根据示例性实施例提供的一种优化是通过被称为“扩展的基本块”的技术来增加代码生成的范围。在基本块A仅具有一个后继块(例如基本块B)的情况下，翻译器能静态地确定(当译码A时)B的源地址。在这种情况下，将基本块A和B组合成单个块(A’)，被称为扩展的基本块。不同地提出，扩展的基本块机制能应用于其目的地可静态地确定的无条件跳转，如果跳转是有条件的或如果目的地不能静态地确定，那么必须形成单独的基本块。扩展的基本块仍然形式上是基本块，因为去除从A至B的中间跳转之后，块A’的代码仅具有单个控制流，因此，在AB边界处无需同步。

即使A具有包括B的多个可能的后继块，扩展的基本块可以用来将A扩展到B中，用于特定执行，其中，B是真正的后继块，而B’的地址可静态地确定。

可静态地确定的地址是翻译器能在译码时确定的地址。在构成块的IR森林期间，构成用于目的地源地址的IR树，其与目的地地址抽象寄存器有关。如果可静态地确定目的地地址IR树的值(即，不取决于动态或运行时间源寄存器值)，那么，可静态地确定后继块。例如，在无条件跳转指令的情况下，目的地地址(即，后继块的源起始地址)隐含在跳转指令本身中，跳转指令的源地址加上在跳转指令中编码的偏移值等于目的地地址。同样地，常数合并(例如X+(2+3)＝＞X+5)以及表达式合并(例如(X*5)*10＝＞X*50)的优化会使得另外的“动态”目的地地址变为可静态地确定。由此，目的地地址的计算包括从目的地地址IR中提取常量值。

当创建扩展的基本块A’时，当执行IR生成、优化和代码生成时，翻译器随后将其视为与任何其它基本块相同。因为代码生成算法在更大范围(即组合基本块A和B的代码)上运算，翻译器19生成更优的代码。

本领域的普通技术人员将意识到，译码是从源代码中提取各源指令的过程。源代码存储为未格式化字节流(即内存中字节的集合)。在具有可变长度指令的源体系结构(例如X86)的情况下，译码首先要求识别指令边界。在固定长度的指令体系结构的情况下，识别指令边界是无关紧要的(例如，在MIPS上，每四个字节是一个指令)。然后，将源指令格式应用于构成指定指令的字节以便提取指令数据(即指令类型、操作数寄存器号、立即字段值以及在指令中编码的任何其它信息)。使用该体系结构的指令格式，由未格式化的字节流译码公知体系结构的机器指令的过程在本领域是非常好理解。

图4示例说明扩展的基本块的创建。当译码最早的适当基本块(A)时，检测适合成为扩展的基本块的组成基本块集。如果翻译器19检测到可静态地确定A的后继块(B)51，则它计算B的起始地址53，然后，在B的起始地址重新开始译码过程。如果将B的后继块(C)确定为可静态地确定55，则译码过程进行到C的起始地址等等。当然，如果后继块不是可静态地确定，那么正常翻译和执行重新开始61，63，65。

在所有基本块译码期间，工作IR森林包括计算当前块的后续块的源地址31(即目的地源地址，翻译器具有用于该目的地地址的专用抽象寄存器)的IR树。在扩展的基本块的情况下，为补偿中间跳转被消除的事实，当通过译码过程同化每个新组成基本块时，修剪用于那个块的源地址的计算的IR树(图4)。换句话说，当翻译器19静态地计算B的地址以及在B的起始地址重新开始译码时，修剪对应于B的源地址31的动态计算的IR树(在译码A的过程中构成)，当译码进入C的起始地址时，修剪对应于C的源地址的IR树59等等。“修剪”IR树是指去除目的地地址抽象寄存器和无其它抽象寄存器所依赖的任何IR节点。不同地提出，修剪断开IR树和目的地抽象寄存器之间的链接，到相同IR树的任何其它链接保持不受影响。在一些情况下，修剪的IR树也由另一抽象寄存器所依赖，在这种情况下，IR树仍然保持源程序的执行语义。

为防止代码激增(传统上，减缓因子对抗这种代码专用技术)，翻译器将扩展的基本块限定到源指令的最大数。在一个实施例，将扩展的基本块限定到最大200个源指令。

等块(isoblock)

在所示的实施例中实现的另一优化是所谓的“等成块”。根据该技术，在为描述源处理器状态和翻译器状态的可变条件集的兼容列表上，用参数表示或指明基本块的翻译。兼容性列表对于每个源体系结构是不同的，从而考虑不同体系结构特征。特定基本块翻译的入口和出口处的兼容性条件的实际值被分别称为入口条件和出口条件。

如果执行达到已经翻译但先前的翻译的入口条件不同于当前工作条件(即先前块的出口条件)的基本块时，那么必须再次翻译基本块，这次基于当前工作条件。该结果是，现在用多个目标代码翻译来表示相同的源代码基本块。同一基本块的这些不同翻译被称为等块。

为支持等块，与每个基本块翻译有关的数据包括一组入口条件35和一组出口条件36(图3)。在一个实施例中，首先通过源地址31然后通过入口条件35，36(图3)来组织基本块高速缓存23。在另一实施例中，当翻译器在基本块高速缓存23中查询源地址31时，查询可以返回多个已翻译基本块(等块)。

图5示例说明等块的使用。在第一已翻译块的执行结束时，已翻译代码21计算并返回下一块(即后继块)71的源地址。然后，控制返回到翻译器19，如由虚线73分开。在翻译器19中，步骤75，使用返回的源地址31来查询基本块高速缓存23。基本块高速缓存可以返回零个、1个或具有相同源地址31的多于一个基本块数据结构。如果基本块高速缓存23返回零个数据结构(表示还没有翻译该基本块)，那么步骤77，必须由翻译器19翻译该基本块。由基本块高速缓存23返回的每个数据结构对应于源代码的同一基本块的不同翻译(等块)。如判定菱形79所示，如果(第一翻译块的)当前出口条件不匹配由基本块高速缓存23返回的任何数据结构的入口条件，那么步骤81，必须再次翻译该基本块，这次确定那些出口条件的参数。如果当前出口条件与由基本块高速缓存23返回的一个数据结构的入口条件匹配，那么步骤83，那个翻译是可兼容的并且能被执行，而不需要重新翻译。在所示的实施例中，翻译器19通过解除引用作为函数指针的目标地址，执行可兼容的已翻译块。

如上所述，最好确定兼容性列表上基本块翻译的参数。现在，描述用于X86和PowerPC体系结构的示例性兼容性列表。

用于X86体系结构的示例性兼容性列表包括下列的表示：(1)源寄存器的延缓传播(lazy propagation)，(2)重叠抽象寄存器，(3)未决条件码标志影响指令的类型，(4)条件码标志影响指令参数的延缓传播，(5)串拷贝操作的方向，(6)源处理器的浮点单元(FPU)模式，以及(7)段寄存器的修改。

用于X86体系结构的兼容性列表包括由翻译器进行的源寄存器的任何延缓传播的表示，也称为寄存器混叠。当翻译器知道两个源寄存器在基本块边界处包含相同值时，出现寄存器混叠。只要源寄存器值保持相同，通过将其保存到全局寄存器库，仅同步相应的抽象寄存器中的一个。直到盖写所保存的源寄存器为止，对未保存的寄存器的引用仅使用或拷贝(经移动指令)所保存的寄存器。这避免了已翻译代码中的两个存储器访问(保存+恢复)。

用于X86体系结构的兼容性列表包括当前定义哪一个重叠抽象寄存器的表示。在一些情况下，源体系结构包含翻译器使用多个重叠抽象寄存器表示的多个重叠源寄存器。例如，使用多个重叠抽象寄存器来表示可变宽度源寄存器，一个用于每个存取大小。例如，X86“EAX”寄存器能使用下述源寄存器的任何一个存取，每个具有相应的抽象寄存器：EAX(位31...0)，AX(位15...0)，AH(位15...8)以及AL(位7...0)。

用于X86体系结构的兼容性列表包括对于每个整数和浮点条件代码标志，正常化还是未决标志值，以及是否未决该未决标志影响指令的类型的表示。

用于X86体系结构的兼容性列表包括用于条件代码标志影响指令参数的寄存器混叠的表示(如果一些源寄存器仍然保存标志影响指令参数的值，或如果第二参数的值与第一相同)。兼容性列表还包括第二参数是否是小常数(即立即指令候选值)，以及如果是的话，其值的表示。

用于X86体系结构的兼容性列表包括源程序中串拷贝操作的当前方向的表示。该条件字段表示在内存中，串拷贝操作向上还是向下移动。这通过确定对于函数的方向变量的翻译的参数，支持“strcpy()”函数调用的代码专门化。

用于X86体系结构的兼容性列表包括源处理器的FPU模式的表示。FPU模式表示源浮点指令是否以32或64位模式操作。

用于X86体系结构的兼容性列表包括段寄存器的修改的表示。所有X86指令内存引用基于六个内存段寄存器中的一个：CS(代码段)、DS(数据段)、SS(堆栈段)、ES(附加数据段)、FS(通用段)以及GS(通用段)。在正常情况下，应用将不修改段寄存器。如此，代码生成是通过对于假定段寄存器值保持恒定的假定的缺省专门化。然而，程序修改其段寄存器是可能的，在这种情况下，将设置相应的段寄存器兼容位，使翻译器使用适当的段寄存器的动态值，生成用于广义存储器存取的代码。

用于PowerPC体系结构的兼容性列表的示例性实施例包括下列的表示：(1)损坏的寄存器(mangled register)；(2)链接值传播；(3)未决条件码标志影响指令的类型；(4)条件码标志影响指令参数的延缓传播；(5)条件码标志值混叠；以及(6)概括(summary)溢出标志同步状态。

用于PowerPC体系结构的兼容性列表包括损坏的寄存器的表示。在源代码包含将源寄存器用于基址的多个连续存储器存取的情况下，翻译器可以使用损坏的目标寄存器来翻译那些存储器存取。在源程序数据在目标存储器中，不位于与其在源存储器中相同的地址的情况下，翻译器必须包括由源代码计算的每个存储器地址的目标偏移值。当源寄存器包含源基址时，损坏的目标寄存器包含对应于那个源基址的目标地址(即，源基址+目标偏移值)。通过寄存器损坏，可以通过将源代码偏移值直接应用于在损坏的寄存器中存储的目标基址，更有效地翻译存储器存取。通过比较，在没有损坏的寄存器机制的情况下，以空间和执行时间为代价，该情况将要求对于每个存储器存取的目标代码的另外的操作。兼容性列表表示如果有的话，哪些抽象寄存器被损坏。

用于PowerPC体系结构的兼容性列表包括链接值传播的表示。对于叶函数(即，不调用其它函数的函数)，可以将函数体(如通过上述扩展基本块机制)扩展到调用/返回点。因此，一起翻译函数体和跟随函数的返回的代码。这也被称为函数返回专门化，因为这种翻译包括代码形式，因此，专用于函数的返回点。不管在出口条件中，是否反映特定块翻译使用的链接值传播。如此，当翻译器面对其翻译使用链接值传播的块时，必须估计当前返回点是否与在前返回点相同。函数返回到它们被调用的相同位置，因此，调用点和返回点实际上相同(由一个或两个指令偏移)。因此，翻译器能通过将各个调用点比较，确定返回点是否相同，这等效于比较(函数块的在前和当前执行的)各前继块的源地址。如此，在支持链接值传播的实施例中，与每个基本块翻译有关的数据包括对前继块翻译的引用(或先前块的源地址的一些其它表示)。

用于PowerPC体系结构的兼容性列表包括对于每个整数和浮点条件码标志正常化还是未决标志值，以及是否未决该未决标志影响指令的类型的表示。

用于PowerPC体系结构的兼容性列表包括用于标志影响指令参数的寄存器混叠的表示(如果标志影响指令参数值正好存在于源寄存器中，或如果第二参数的值与第一相同)。兼容性列表还包括第二参数是否是小常数(即立即指令候选值)，以及如果是，其值的表示。

用于PowerPC体系结构的兼容性列表包括用于PowerPC条件码标志值的寄存器混叠的表示。PowerPC体系结构包括用于将整个PowerPC标志集显式地加载到通用(源)寄存器中的指令。源寄存器中的源标志值的该显式表示防碍翻译器的条件码标志仿真优化。兼容性列表包含标志值是否存在于源寄存器中，以及如果是，哪个寄存器的表示。在IR生成期间，对保存标志值的这种源寄存器的引用被翻译成对相应抽象寄存器的引用。该机制消除了需要显式地计算和将源标志值存储在目标寄存器中，反过来，允许翻译器应用标准的条件码标志优化。

用于PowerPC体系结构的兼容性列表包括概括溢出同步的表示。该字段通过全局概括溢出位，表示八个概括溢出条件位的哪些是当前的。当更新PowerPC的八个条件字段中的一个时，如果设置全局概括溢出，将其拷贝到特定条件码字段中的相应的概括溢出位。

翻译提示

在示例性实施例中实现的另一优化采用图3的基本块数据结构的翻译提示34。该优化从识别存在专用于特定基本块但对那个块的每个翻译是相同的静态基本块数据进行。对计算代价大的静态数据的一些类型，在相应块的第一翻译期间，翻译器一次计算数据，然后存储结果用于相同块的未来翻译更有效。因为该数据对相同块的每次翻译是相同的，它不确定翻译的参数，因此，形式上，它不是块的兼容性列表的一部分(如上所述)。然而，因为保存数据比重新计算它更便宜，昂贵的静态数据仍然存储在与每个基本块翻译有关的数据中。在相同块的以后翻译中，即使翻译器19不能重新使用在前翻译，翻译器19能利用这些“翻译提示”(即高速缓存的静态数据)来降低第二和稍后翻译的翻译成本。

在一个实施例中，与每个静态块翻译有关的数据包括翻译提示，其在那个块的第一翻译期间计算过一次，然后在每个后续翻译时拷贝(或引用)。

例如，在用C++实现的翻译器19中，翻译提示可以实现为C++对象，在这种情况下，对应于相同块的不同翻译的基本块对象将分别存储对相同翻译提示对象的引用。或者，在用C++实现的翻译器中，基本块高速缓存23可以每个源基本块(而不是每个翻译)包含一个基本块对象，以及每个这种对象包含或保存对相应翻译提示的引用。这种基本块对象还包含按入口条件组织的、对于对应于那个块的不同翻译的翻译对象的引用。

用于X86体系结构的示例性翻译提示包括下列的表示：(1)初始指令前缀，以及(2)初始重复前缀。用于X86体系结构的这种翻译提示特别包括该块中的第一指令具有多少前缀的表示。一些X86指令具有修改指令的操作的前缀。该体系结构的特征使得难以(即昂贵)译码X86指令流。一旦在块的第一译码期间，确定初始前缀的数量，然后由翻译器将该值保存为翻译提示，使得相同块的后续翻译不需要再确定它。

用于X86体系结构的翻译提示进一步包括该块中的第一指令是否具有重复前缀的表示。一些X86指令，诸如串操作具有告诉处理器执行多次那个指令的重复前缀。翻译提示表示这种前缀是否存在，以及如果是，其值。

在一个实施例中，与每个基本块有关的翻译提示还包括对应于那个基本块的整个IR森林。这有效地高速缓存由前端执行的所有译码和IR生成。在另一实施例中，翻译提示包括在被优化前存在的IR森林。在另一实施例中，IR森林不高速缓存为翻译提示，以便保存被翻译器的内存资源。

组块

在示例性翻译器实施例中实现的另一优化针对消除由在执行每个已翻译基本块结束时，需要同步所有抽象寄存器而引起的程序开销。该优化被称为组块优化。

如上所述，在基本块模式(例如图2)下，使用所有已翻译代码序列可存取的存储区，即全局寄存器库27，将状态从一个基本块传递到下一基本块。全局寄存器库27是用于抽象寄存器的储存库，每个抽象寄存器对应于和模拟特定源寄存器或其它源体系结构特征的值。在执行已翻译代码21期间，抽象寄存器保存在目标寄存器中以便它们可以参与指令。在执行已翻译器代码21期间，抽象寄存器值被存储在全局寄存器库27或目标寄存器15中。

因此，在诸如图2所示的基本块模式下，由于两个原因(1)控制返回到翻译器代码19，可能盖写所有目标寄存器，以及(2)因为代码生成一次仅看见一个基本块，在每个基本块结束时，必须同步所有抽象寄存器，翻译器19必须假定所有抽象寄存器值存在(即将用在后续基本块中)，因此必须被保存。组块优化机制的目的是通过将多个基本块作为连续整体进行翻译，减少跨越频繁越过的基本块边界的同步。通过一起翻译多个基本块，即使不消除，也能最小化块边界处的同步。

在当前块的剖析量度达到触发阈值时，触发组块构建。该块被称为触发块。该构建可分成下述步骤(图6)：(1)选择构件块71，(2)排序构件块73，(3)全局死码消除75；(4)全局寄存器分配77；以及(5)代码生成79。第一步骤71通过执行程序的控制流图的深度优先搜索(DFS，depth-first search)遍历，从触发块开始并通过包含阈值和最大构件限制来调节，识别将包括在组块中的块集合。第二步骤73排序块集合以及识别通过组块的关键路径，以便启动最小化同步码和减少分支的有效代码布局。第三和第四步骤75、77执行优化。最后步骤79依次生成用于所有构件块的目标代码，产生具有有效寄存器分配的有效代码布局。

在构成组块和由此生成目标代码过程中，翻译器代码19实现图6所示的步骤。当翻译器19遇到先前翻译过的基本块时，在执行那个块之前，翻译器19相对于触发阈值，校验块的剖析量度37(图3)。当基本块的剖析量度37超出触发阈值时，翻译器19开始组块创建。翻译器19通过遍历控制流图，从触发块开始以及由包含阈值和最大构件极限调节，识别组块的构件。接着，翻译器19创建构件块的排序，识别通过组块的关键路径。然后，翻译器19执行全局死码消除，翻译器19使用对应于每个块的IR，收集用于每个构件块的寄存器活性信息。接着，翻译器19根据体系结构专用政策，执行全局寄存器分配，定义用于所有构件块的统一寄存器映射的局部集合。最后，翻译器19与全局寄存器分配约束一致和使用寄存器活性分析，按顺序生成用于每个构件块的目标代码。

如上所述，与每个基本块有关的数据包括剖析量度37。在一个实施例中，剖析量度37是执行计数，表示翻译器19计数执行特定基本块的次数。在该实施例中，剖析量度37表示为整数计数字段(计数器)。在另一实施例中，剖析量度37是执行时间，表示翻译器19保持用于特定基本块的所有执行的执行时间的运行总计，诸如通过在基本块的开始和结束中插置代码以便分别开始和停止硬件或软件定时器；在该实施例中，剖析量度37使用总计执行时间(定时器)的一些表示。在另一实施例中，翻译器19存储用于每个基本块的多种剖析量度37。在另一实施例中，翻译器19对应于每个前导基本块和/或每个后继基本块，存储用于每个基本块的多个剖析量度37的集合，以便为不同控制路径维持不同剖析数据。在每个翻译器周期内(即，执行已翻译代码间执行翻译器代码19)，更新用于适当的基本块的剖析量度37。

在支持组块的实施例中，与每个基本块有关的数据另外包括对已知前导和后续基本块对象的引用38、39。这些引用聚集构成所有先前执行的基本块的控制流图。在组块形成期间，翻译器19遍历该控制流图以便确定在形成中，哪些基本块包括在组块中。

所示实施例的组块形成基于三个阈值：触发阈值、包含阈值，以及最大构件极限。触发阈值和包含阈值是指用于每个基本块的剖析量度37。在每个翻译器周期中，下一基本块的剖析量度37与触发阈值相比。如果量度37满足触发阈值，那么组块形成开始。然后，通过识别哪些后续基本块包括在组块中，使用包含阈值来确定组块的范围。最大构件极限定义有关将包括在任何一个组块中的基本块的数量的上限。

当对于基本块A，达到触发阈值时，形成一个新的组块，A作为触发块。然后，翻译器19开始定义遍历，遍历控制流图中的A的后继，以便识别包括的其它构件块。当遍历达到指定基本块时，将其剖析量度37与包含阈值进行比较。如果量度37满足包含阈值，将那个基本块标记为包含以及遍历继续块的后继。如果块的量度37低于包含阈值，排除那个块以及不遍历其后继。当遍历结束时(即，所有路径达到排除块或周期返回包含的块，或达到最大构件极限)，翻译器19基于所有包括的基本块，构成一个新的组块。

在使用等块和组块的实施例中，控制流图是等块的图，表示为组块创建目的，相同源块的不同等块被视为不同块。因此，不总计用于相同源块的不同等块的剖析量度。

在另一实施例中，等块不用在基本块翻译中，但用在组块翻译中，表示概括非组基本块翻译(不专用在入口条件上)。在该实施例中，由每个执行的入口条件分解基本块的剖析度量，使得对每个理论等块(即，对于每个不同入口条件集)，维持不同剖析信息。在该实施例中，与每个基本块有关的数据包括剖析列表，其每个构件是三项集合，包含：(1)入口条件集，(2)相应的剖析量度，以及(3)相应的后继块的列表。该数据维持用于到基本块的每个入口条件集的剖析和控制路径信息，即使真正基本块翻译不专用于那些入口条件。在该实施例中，将触发阈值与基本块的剖析量度列表内的每个剖析量度进行比较。当遍历控制流图时，将指定基本块的剖析列表中的每个元素视为控制流图中的单独节点。因此，将包含阈值与块的剖析列表中的每个剖析度量进行比较。在该实施例中，为热源块的特定热等块(专用于特定入口条件)，创建组块，而使用那些块的一般(非等块)翻译，执行那些相同源块的其它等块。

在定义遍历后，翻译器19执行排序遍历，步骤73，图6，以确定将翻译构件块的顺序。构件块的顺序影响已翻译代码21的指令高速缓存行为(热路径应当是连续的)，以及构件块边界上有必要的同步(沿热路径，应当最小化同步)。在一个实施例中，翻译器19使用按执行计数排序的排序深度优先搜索(DFS)算法，执行排序遍历。遍历在具有最高执行计数的构件块开始。如果遍历的构件块具有多个后继，则优先遍历具有较高执行计数的后继。

本领域的技术人员将意识到，组块不是正式的基本块，因为它们可以具有内部控制转移、多个入口点和/或多个出口点。

一旦形成一个组块，可以将进一步优化应用于它，在此被称为“全局死码消除”。这种全局死码消除采用活性分析的技术。全局死码消除是从一组基本块上的IR去除冗余工作的过程。

通常，必须在翻译范围边界上同步源处理器状态。一个值，诸如源寄存器被认为对于从其定义开始和在被重新定义(盖写)之前其最后一次使用结束的代码范围是“有效的”；因此，值(例如IR生成的上下文中的临时值，代码生成的上下文中的目标寄存器或翻译的上下文中的源寄存器)的使用和定义的分析在本领域中被称为活性分析。不管翻译器所具有的有关数据和状态的使用(读取)和定义(写入)的知识(即活性分析)怎样局限于其翻译范围，程序的其余部分是未知的。更具体地说，因为翻译器不知道在翻译的范围外(例如在后继基本块中)，将使用哪些源寄存器，必须假定将使用所有的寄存器。如此，在那个基本块结束时，必须保存在指定基本块内修改的任何源寄存器的值(定义)(保存到全局寄存器库27)，防备它们将来使用的可能性。类似地，在开始那个基本块时，必须恢复将在指定基本块中使用其值的所有源寄存器(从全局寄存器库27加载)，即，用于基本块的已翻译代码必须在其在那个基本块内的首次使用之前，恢复指定源寄存器。

IR生成的一般机制包含“局部”死码消除的隐形式，其范围立即被局部化到仅小的IR节点组。例如，将通过具有多个父节点的用于A的单IR树，而不是表达式树A本身的多个实例，来表示源代码中的普通子表达式A。由于一个IR节点能具有到多个父节点的链接的事实，“消除”是隐含的。同样地，将抽象寄存器用作IR占位符是死码消除的隐含形式。如果用于指定基本块的源代码从不定义特定源寄存器，那么在用于那个块的IR生成结束时，对应于那个源寄存器的抽象寄存器将引用空的IR树。代码生成阶段意识到在该情况下，适当的抽象寄存器不需要与全局寄存器库同步。如此，在当创建IR节点时递增出现的IR生成阶段，局部死码消除是隐含的。

与局部死码消除相反，将“全局”死码消除算法应用于基本块的整个IR表达式森林。根据所示实施例的全局死码消除要求活性分析，表示分析组块中每个基本块的范围内的源寄存器使用(读取)和源寄存器定义(写入)，以识别活区和死区。变换IR以便去除死区，从而减少必须由目标代码执行的工作量。例如，在源代码中的指定点，如果翻译器19识别或检测到在其下次使用前，将定义(盖写)一个特定源寄存器，则该源寄存器被说成在达预先定义的码中的所有点处为失效。关于IR，被定义但在被重新定义之前从未使用过的源寄存器是可在IR阶段中被消除，而不产生目标代码的死码。关于目标代码生成，为失效的目标寄存器能用于其它临时或源寄存器值，而不泄漏。

在组块全局死码消除中，对于所有构件块执行活性分析。活性分析生成用于每个构件块的IR森林，然后用来导出用于那个块的源寄存器活性信息。在组块创建的代码生成阶段中，还需要用于每个构件块的IR森林。一旦在活性分析中，生成用于每个构件块的IR，它可被保存用于代码生成中的后续使用，或能在代码生成期间被删除和重新生成。

组块全局死码消除能用两种方式有效地“变换”IR。首先，能修改活性分析期间为每个构件块生成的IR森林，然后，能将整个IR森林传播到代码生成阶段(即该阶段期间保存和重新使用)。在该情况下，通过将它们直接应用于IR森林，然后保存变换后的IR森林，通过代码生成阶段，传播IR变换。在该情况下，与每个构件有关的数据包括活性信息(将另外用在全局寄存器分配中)，以及用于那个块的变换后的IR森林。

另外以及最好，使用先前创建的活性信息，在组块创建的最终代码生成阶段期间，执行变换用于构件块的IR的全局死码消除步骤。在该实施例中，能将全局死码变换记录为“失效”源寄存器的列表，然后编码在与每个构件块有关的活性信息中。由此，通过后续代码生成阶段，执行IR森林的实际变换，使用失效寄存器列表来修剪IR森林。该情况允许翻译器在活性分析期间生成一次IR，然后扔掉IR，然后，在代码生成期间，重新生成相同的IR，在该点，使用活性分析来变换IR(即，将全局死码消除应用于IR本身)。在该情况下，与每个构件块有关的数据包括活性信息，其包括失效源寄存器的列表。不保存IR森林。具体地，在代码生成阶段中(重新)生成IR森林之后，修剪(在活性信息内的失效源寄存器列表中列出的)用于失效源寄存器的IR树。

在一个实施例中，在提取活性信息后，扔掉在活性分析期间创建的IR以便保存内存资源。在代码生成期间，重新创建IR森林(每个构件块一个)，每次一个构件块。在该实施例中，用于所有构件块的IR森林不共存于翻译中的任何点。然而，分别在活性分析和代码生成期间创建的IR森林的两个版本是相同的，因为它们使用相同的IR生成过程从源代码生成。

在另一实施例中，翻译器在活性分析期间，为每个构件块创建IR森林，然后将IR森林保存在与每个构件块有关的数据中，以便在代码生成期间重新使用。在该实施例中，从活性分析的结束(全局死码消除步骤中)到代码生成，用于所有构件块的IR森林共存。在实施例的一个替代方案中，在从其初始创建(活性分析期间)和其最后一次使用(码生成)的周期期间，不对IR执行变换或优化。

在另一实施例中，在活性分析和代码生成的步骤之间，保存用于所有构件块的IR森林，以及在代码生成前，对IR森林执行块间优化。在该实施例中，翻译器利用所有构件块IR森林共存于翻译中的相同点处，以及在变换那些IR森林的不同构件块的IR森林上执行优化的事实。在这种情况下，用在代码生成中的IR森林可以不同于用在活性分析中的IR森林(如在上述两个实施例中)，因为已经通过块间优化随后变换了IR森林。换句话说，用在代码生成中的IR森林可以不同于每次一个构件块再生成它们而产生的IR森林。

在组块全局死码消除中，由于将活性分析同时应用于多个块的事实，增加了死码检测的范围。因此，如果在第一构件块中定义源寄存器，然后在第三构件块中重新定义(通过无干预使用或出口点)，能从第一构件块消除用于第一定义的IR树。通过比较，在基本块代码生成中，翻译器19将不能检测出该源寄存器失效。

如上所述，组块优化的一个目的是减少或消除基本块边界处的寄存器同步的需要。因此，现在提供在组成块期间，翻译器19如何实现寄存器分配和同步的论述。

寄存器分配是将抽象(源)寄存器与目标寄存器相关联的过程。寄存器分配是代码生成的必要成分，因为抽象寄存器值必须驻留在目标寄存器中以便参与目标指令。目标寄存器和抽象寄存器之间的这些分配的表示(即映射)被称为寄存器图。在代码生成期间，翻译器19维持工作寄存器图，其反映寄存器分配的当前状态(即目标与抽象寄存器映射实际上存在于目标代码中的指定点处)。在下文中，将引用出口寄存器图，其抽象地说，其是关于来自构件块的出口的工作寄存器图的快照。然而，由于同步不需要出口寄存器图，不记录它，因此它完全是抽象的。入口寄存器图40(图3)是关于到构件块的入口的工作寄存器图的快照，有必要记录它用于同步目的。

同样，如上所述，组块包含多个构件块，以及分别对每个构件块执行代码生成。如此，每个构件块具有其自己的入口寄存器图40和出口寄存器图，其分别反映在用于那个块的已翻译代码的开始和结束，特定目标寄存器到特定源寄存器的分配。

通过其入口寄存器图40(有关入口的工作寄存器图)，确定用于组构件块的代码生成的参数，但代码生成也修改工作寄存器图。用于构件块的出口寄存器图反映当由代码生成过程修改时，在那个块的结束的工作寄存器图。当翻译第一构件块时，工作寄存器图为空(经受全局寄存器分配，如下所述)。在用于第一构件块的翻译的结束，工作寄存器图包含由代码生成过程创建的寄存器映射。然后，将工作寄存器图拷贝到所有后继构件块的入口寄存器图40中。

在用于构件块的代码生成的结束，一些抽象寄存器可以不要求同步。通过识别哪些寄存器真正要求同步，寄存器图允许翻译器19最小化构件块边界上的同步。通过比较，在(非组)基本块情况中，在每个基本块的结束，必须同步所有的抽象寄存器。

在一个构件块的结束，基于后继块，三个同步情况是可能的。首先，如果后继块是还没有被翻译的构件块，将其入口寄存器图40定义成与工作寄存器图相同，因此，不需要同步。第二，如果后继块在组外，那么，必须同步所有的抽象寄存器(即全同步)，因为在后继块执行前，控制将返回到翻译器代码19。第三，如果后继块是其寄存器图已经固定的构件块，则必须插入同步码以便使工作寄存器图与后继块的入口寄存器图一致。

通过组块排序遍历减少了寄存器图同步的一些成本，最小化了寄存器同步或沿热路径完全地消除它。按由排序遍历生成的顺序，翻译构件块。当翻译每个构件块时，将其出口寄存器图传播到其入口寄存器图还没有固定的所有后继构件块的入口寄存器图40中。实际上，首先翻译组块中的最热路径，以及沿那个路径的大多数如果不是所有构件块边界不要求同步，因为相应的寄存器图均是一致的。

例如，第一和第二构件块之间的边界将总是不要求同步，因为第二构件块将总是具有固定到与第一构件块的出口寄存器图41相同的入口寄存器图40。构件块之间的一些同步可以是不可避免的，因为组块可以包含内部控制转移和多个入口点。这表示可通过不同时间的不同工作寄存器图，执行可以从不同前导达到相同的构件块。这些情况要求翻译器19将工作寄存器图与适当的构件块的入口寄存器图同步。

如果需要，寄存器图同步出现在构件块边界上。翻译器19将代码插入构件块的结尾处以便使工作寄存器图与后继块的入口寄存器图40同步。在寄存器图同步中，每个抽象寄存器落在十个同步条件中的一个下。表1示例说明十个寄存器同步情况，作为翻译器的工作寄存器图和后继的入口寄存器图40的函数。表2通过用情形的文本描述和相应同步动作的伪代码描述(下面说明伪代码)，列举十个形式同步情形，来描述寄存器同步算法。因此，在每个构件块边界处，使用10个情形算法，使每个抽象寄存器同步。同步条件和动作的详细联接方式允许翻译器19生成有效的同步码，其最小化用于每个抽象寄存器的同步成本。

下文描述表2中列出的同步动作函数。“Spill(E(a))”将抽象寄存器a从目标寄存器E(a)保存到源寄存器库(全局寄存器库的组成)中。“Fill(t，a)”将抽象寄存器a从源寄存器库加载到目标寄存器t。“Reallocate()”如果可用的话，将抽象寄存器移动和重新分配(即改变映射)到新的目标寄存器，或如果目标寄存器不可用，溢出抽象寄存器。“FreeNoSpill(t)”将目标寄存器标记为空闲，而不溢出相关的抽象源寄存器。FreeNoSpill()函数对于避免相同同步点处的算法的多个应用上的过量溢出是有必要的。注意对具有“Nil”同步动作的情形，对相应的抽象寄存器，同步码是不必要的。

翻译器19在组块内执行两级寄存器分配，全局和局部(或临时)。全局寄存器分配是在代码生成前特定寄存器映射的定义，在整个组块上(即贯穿所有构件块)持续。局部寄存器分配由在代码生成的过程中创建的寄存器映射组成。全局寄存器分配定义特定寄存器分配约束，通过约束局部寄存器分配，来确定构件块的代码生成的参数。

全局分配的抽象寄存器不要求在构件块边界上同步，因为它们保证被分配到每个构件块中的相同的各目标寄存器。该方法具有对于在构件块边界上的全局分配的抽象寄存器，永不要求同步码的优点(补偿块间的寄存器映射的差异)。组块寄存器映射的缺点在于它防碍局部寄存器分配，因为全局分配的目标寄存器不立即可用于新的映射。为了补偿，对于特定组块，可以限制全局寄存器映射的数量。

通过全部寄存器分配政策，定义实际全局寄存器分配的数量和选择。全局寄存器分配政策可基于源体系结构、目标体系结构和所翻译的应用来配置。经验地导出全局分配的寄存器的最佳数量，并且是目标寄存器的数量、源寄存器的数量、翻译的应用类型，以及应用使用模式的函数。数量通常是目标寄存器的总数减去一些小数的尾数，以便确保足够的目标寄存器保留用于临时值。

在存在许多源寄存器，但很少目标寄存器的情况下，诸如MIPS-X86和PowerPC-X86翻译器中，全局分配的寄存器的数量为零。这是因为X86体系结构具有太少目标寄存器，以致观察到使用任何固定的寄存器分配产生比根本没有更槽的目标代码。

在存在许多源寄存器和许多目标寄存器的情况下，诸如X86-MPIS翻译器，全局分配的寄存器的数量(n)为目标寄存器的数量(T)的四分之三。因此，

X86-MPIS：n＝3/4*T

即使X86体系结构具有很少通用寄存器，将其视为具有许多源寄存器，因为需要许多抽象寄存器以便模拟复杂的X86处理器状态(包括例如条件码标志)。

在源寄存器和目标寄存器的数量几乎相同的情况下，诸如MIPS-MIPS加速器，全局分配大多数目标寄存器，仅少数为临时值预留。因此，

MIPS-MIPS：n＝T-3

在整个组块上使用中的源寄存器的总数(s)小于或等于目标寄存器的数量(T)的情况下，全局映射所有的源寄存器。这表示整个寄存器图在所有构件块上是恒定的。在其中(s＝T)的特殊情况下，表示目标寄存器和有效源寄存器的数量相同，这表示没有为临时计算留下目标寄存器；在这种情况下，将临时值局部分配给全局分配给没有在相同的表达式树内没有进一步用途的源寄存器的目标寄存器(通过活性分析获得该信息)。

在组块创建的结束，按遍历顺序，对于每个构件块执行代码生成。在代码生成期间，(重新)生成每个构件块的IR森林，以及使用失效源寄存器的列表(包含在那个块的活性信息中)在生成目标代码之前，修剪IR森林。当翻译每个构件块时，将其出口寄存器图传播到所有后继构件块的入口寄存器图40(除已经固定的那些外)。因为按遍历顺序翻译块，这具有最小化沿热路径的寄存器图同步，以及使热路径翻译在目标存储器空间中连续的效果。如与基本块翻译，组构件块翻译特殊化在一组入口条件，即创建组块时的当前工作条件。

图7提供根据示例性实施例，通过翻译器代码19的组块生成的例子。示例性组块具有五个构件(“A”至“E”)，以及最初一个入口点(“入口1”，稍后通过聚集生成入口2，如下所述)以及三个出口点(“出口1”、“出口2”以及“出口3”)。在该例子中，用于组块创建的触发阈值是执行计数45000，以及用于构件块的包含阈值是执行计数1000。当块A的执行计数(现在为45074)达到触发阈值45000时，触发该组块的构建，在该点，执行控制流图的搜索以便识别组块构件。在该例子中，发现五块超出包含阈值1000。一旦识别到构件块，则执行排序的深度优先搜索(按剖析量度排序)，使得首先处理更热的块及它们的后继块，这产生具有关键路径排序的一组块。

在该阶段，执行全局死码消除。分析每个构件块的寄存器使用和定义(即活性分析)。这用两种方式，使代码生成更有效。首先，局部寄存器分配可以考虑在组块中哪些源寄存器有效(即在当前和后继构件块中，将使用哪些源寄存器)，这有助于最小化溢出的成本，首先溢出失效寄存器，因为它们不需要被恢复。另外，如果活性分析显示特定源寄存器被定义、使用，然后重新定义(盖写)，在最后一次使用(即能释放其目标寄存器)后，可随时丢弃该值。如果活性分析显示，没有任何干预使用的情况下，特定源寄存器被定义然后被重新定义(不同的是，因为这表示源编译器生成了死码)，那么，能丢弃用于那个值的相应IR树，使得不再为它生成目标代码。

全局寄存器分配如下。翻译器19将频繁被访问的源寄存器指定一个在所有构件块上恒定的固定目标寄存器映射。全局分配的寄存器是非溢出的，表示那些目标寄存器不可用于局部寄存器分配。当存在比目标寄存器更多的源寄存器时，必须保持目标寄存器的百分比用于临时源寄存器映射。在组块内的整个源寄存器集能适合目标寄存器的特殊情况下，完全避免了溢出和充满。如图7所示，翻译器插置代码(“Pr1”)以便在输入组块的头部(“A”)之前，从全局寄存器库27加载这些寄存器，这种代码被称为序言负载。

组块现在准备好目标代码生成。在代码生成期间，翻译器19使用工作寄存器图(抽象寄存器和目标寄存器之间的映射)来跟踪寄存器分配。每个构件块开始处的工作寄存器图的值被记录在那个块的相关入口寄存器图40中。

首先，生成序言块Pr1，其加载全局分配的抽象寄存器。在该点，Pr1结束时的工作寄存器图被拷贝到块A的入口寄存器图40。

然后翻译块A，将目标代码直接插置在用于Pr1的目标代码后。插置控制流代码以便处理用于由至结尾块Ep1(稍后插置)的伪转移(稍后修补)组成的出口1的出口条件。在块A的结尾，将工作寄存器图拷贝到块B的入口寄存器图40。B的入口寄存器图40的该固定具有两个结果：首先，在从A至B的路径上不需要同步，第二，从任何其它块(即，该组块的构件块或使用聚集的另一组块的构件块)到B的入口要求那个块的出口寄存器图与B的入口寄存器图的同步。

块B是关键路径上的下一块。其目标代码被直接插置在块A后，然后插置处理两个后继C和A的代码。第一后继块C还没有使其入口寄存器图40固定，因此，将工作寄存器图简单地拷贝到C的入口寄存器图中。然而，第二后继，块A先前已经使其入口寄存器图40固定，因此，块B的结尾处的工作寄存器图和块A的入口寄存器图40会不同。寄存器图中的任何差异要求沿从块B到块A的路径的一些同步(“B-A”)，以便使工作寄存器图与入口寄存器图40一致。该同步采用寄存器溢出、满和交换的形式以及在上述十个寄存器图同步情况中详述过。

现在翻译块C以及直接将目标代码插置在块C后。同样地翻译块D和E并连续插置。从E至A的路径再次要求从E的出口寄存器图(即E的翻译的工作寄存器图)到插置在块“E-A”中的A的入口寄存器图40的寄存器图同步。

在退出组块和将控制返回到翻译器19之前，必须使全局分配的寄存器同步到全局寄存器库，该代码被称为结尾存档。在已经翻译构件块后，代码生成插置用于所有出口点(Ep1，Ep2和Ep3)的结尾块以及固定整个构件块的转移目标。在使用等块和组块的实施例中，根据唯一源块(即源代码中的特定基本块)而不是那个块的等块，进行控制流图遍历。如此，等块对组块创建是透明的。相对于具有一个翻译或多个翻译的源块，不进行特殊区别。

在所示的实施例中，可以有利地采用组块和等块优化。然而，等块机制可以创建用于相同源代码序列的不同基本块翻译的事实使得确定哪些块包括在组块中的过程变复杂，因为将包括的块可能不存在直到形成组块为止。必须在被用在选择和布局过程之前，改编使用在优化前存在的未专门化块收集的信息。

示例性实施例进一步采用用于在组块生成中，适应嵌套循环的特征的技术。通过仅一个入口点，即触发块的开始，初始创建组块。程序中的嵌套循环使得内循环首先变热，创建表示内循环的组块。稍后，外循环变热，创建包括内循环和外循环的所有块的新组块。如果组块生成算法不考虑为内循环完成的工作，而是重做所有工作，那么包含深度嵌套循环的程序将逐渐生成越来越大的组块，要求有关每个组块生成的更多存储和更多工作。另外。较早(内)组块会变得不可达到，因此提供更少或没有好处。

根据示例性实施例，组块聚集用来使先前构建的组块与另外的优化块结合。在选择包括在新组块中的块的阶段期间，识别已经包括在先前组块中的那些候选块。与插置用于这些块的目标代码不同，执行聚集，由此翻译器19创建到现有组块中的适当位置的链接。因为这些链接可以跳转到现有组块的中间，必须实施对应于那个位置的工作寄存器图，相应地，根据需要，为该链接插置的代码包括寄存器图同步码。

存储在基本块数据结构30中的入口寄存器图40支持组块聚集。将构件块的开始用作入口点，聚集允许其它已翻译代码跳转到组块的中间。这种入口点要求当前工作寄存器图同步到构件块的入口寄存器图40，翻译器19通过在前导块的出口点和该构件块的入口点之间插置同步码(即溢出和满)来实现。

在一个实施例中，有选择地删除一些构件块的寄存器图以便节省资源。初始地，无限地存储组中所有构件块的入口寄存器图，以便于在任何构件块的开始进入组块(从聚集组块)。当组块变大时，可以删除一些寄存器图来节省存储器。如果这发生，聚集有效地将组块分成区，它们中的一些(即已经删除其寄存器图的构件块)聚集入口不能达到。使用不同的政策来确定存储哪些寄存器图。一个政策是存储所有构件块的所有寄存器图(即永不删除)。另一政策是仅存储最热构件块的寄存器图。另一政策是仅存储为向后转移的目的地(即循环的开始)的构件块的寄存器图。

在另一实施例中，与每一组构件块有关的数据包括用于每个源指令位置的记录的寄存器图。这允许其它已翻译代码在任一点跳转到组块的中间，而不仅仅是构件的开始处，因为在一些情况下，当形成组块时，组构件块可以包含未检测到的入口点。该技术消耗大量存储器，因此，仅当存储器节约不是问题时才适用。

组块提供用于识别频繁执行的块或块组以及对它们执行另外的优化的机制。因为将更多计算昂贵的优化应用于组块，最好将它们的形成限制到已知频繁执行的基本块。在组块的情况下，通过频繁执行来证明额外计算有效，频繁执行的连续块被称为“热路径”。

可以构成实施例，其中，使用多级频率和优化，使得翻译器19检测多级频繁执行的基本块，以及应用日益复杂的优化。另外，如上所述，仅使用两级优化：将基本优化应用于所有基本块，以及使用上述组块创建机制，将单个进一步优化集应用于组块。

概述

图8示例说明在执行已翻译代码之间，在运行时间，由翻译器执行的步骤。当第一基本块(BB_N-1)完成执行时1201，它将控制返回给翻译器1202。翻译器递增第一基本块的剖析量度1203。然后，使用通过第一基本块的执行返回的源地址，翻译器在基本块高速缓存中查询当前基本块的先前翻译的等块(BB_N，其是BB_N-1的后继块)1205。如果已经翻译过后继块，基本块高速缓存将返回一个或多个基本块数据结构。然后，翻译器将后继块的剖析量度与组块触发阈值进行比较1207(这可以包含聚集多个等块的剖析量度)。如果不满足阈值，那么，翻译器校验由基本块高速缓存返回的任何等块是否与工作条件兼容(即，具有等于BB_n-1的出口条件的入口条件的等块)。如果找到兼容等块，执行翻译1211。

如果后继块剖析量度超出组块触发阈值，那么创建一个新组块1213并执行1211，如上所述，即使兼容等块存在。

如果基本块不返回任何等块，或所返回的等块没有一个是兼容的，那么将当前块翻译成专用于当前工作条件的等块1217，如上所述，在译码BB_N结束时，如果可静态地确定BB_N的后继块(BB_N+1)1219，那么创建扩展的基本块1215。如果创建扩展的基本块，那么翻译BB_n+11217等等。当完成翻译时，将新等块存储在基本块高速缓存中1221，然后执行1211。

局部死码消除

在翻译器的另一实施例中，在已经将所有寄存器定义添加到遍历数组之后以及在将存储添加到数组之后并在处理后继块之后，实质上在已经完全遍历IR之后，可以将进一步优化应用于组块，在此被称为“局部死码消除”并如图9的步骤76所示。这种局部死码消除采用另一种活性分析。局部死码消除是以在组块模式中应用的代码移动形式的优化，用于在未计算转移或计算跳转中结束的块。

在图9所示的实施例中，将局部死码消除步骤76添加到结合图6所述的组块构成步骤，其中，在全局死码消除步骤75后和全局寄存器分配步骤77前，执行局部死码消除。

如前所述，一个值，诸如源寄存器，对于以其定义开始并在重新定义(盖写)前其最后一次使用结束的代码范围是“有效的”，而值的使用和定义的分析在本领域中被称为活性分析。将局部死码消除应用于在非计算转移和计算跳转中结束的块。

对于在非计算的两个目的地转移中结束的块，分析那个块中的所有寄存器定义以便识别在转移目的地的一个中，那些寄存器定义的哪些是失效的(在使用前被重新定义)以及在其它转移目的地中是有效的。然后，能在其有效路径开始时，而不是在块的主码内，生成用于那些定义的每一个的代码，作为代码移动优化技术。参考图10A，提供示例说明两个目的地转移的有效和失效路径的例子，用于帮助理解所执行的寄存器定义分析。在块A中，寄存器R1定义为R1＝5。然后，块A以条件转移结束，转移到块B和C。在块B中，在使用为块A中的R1定义的值(R1＝5)之前，重新将寄存器R1定义为R1＝4。因此，块B被识别为对于寄存器R1的失效路径。在块C中，在重新定义寄存器R1之前，在定义寄存器R2中，使用来自块A的寄存器定义R1＝5，从而使到块C的路径为用于寄存器R1的有效路径。在其转移目的地的一个中，所示寄存器为失效，而在其转移目的地的另一个中有效，因此，将寄存器R1识别为局部失效寄存器定义。

用于非计算转移的局部死码消除方法也能应用于能跳转到多于两个不同目的地的块。参考图10B，提供用于示例说明识别多个目的地跳转的失效路径和可能有效路径而执行的寄存器定义分析。如上，在块A中，将寄存器R1定义为R1＝5。然后块A能跳转到块B、C、D等等的任何一个。在块B中，在使用在块A中为R1定义的值(R1＝5)之前，寄存器R1被重新定义为R1＝4。因此，块B被识别为用于寄存器R1的失效路径。在块C中，在重新定义寄存器R1之前，在寄存器R2的定义中，使用来自块A的寄存器定义R1＝5，从而使到块C的路径为用于寄存器R1的有效路径。对用于各个跳转的路径的每一个，继续该分析以便确定该路径是失效路径还是可能的有效的路径。

如果对最热(最多执行)目的地，寄存器定义为失效，能生成仅用于其它路径的代码。其它可能的有效路径的一些也可以变为失效，但该局部死码消除方法对最热路径有效，因为所有其它目的地不需要被研究。将仅参考条件转移，主要描述图9的步骤76的局部死码消除方法的剩余论述，因为理解到用于计算跳转的局部死码消除仅仅可从用于条件转移的解决方案延伸。

现在参考图11，示例说明实现局部死码消除技术的优选方法的更具体描述。如所述，局部死码消除要求活性分析，其中，在步骤401中，初始识别用于以非计算转移或计算跳转结尾的块的所有局部失效寄存器定义。为了识别寄存器定义是否局部失效，分析转移或跳转的后继块(甚至可以包括当前块)以便确定用于那个寄存器的活性状态是否在其后继块的每一个中。如果在一个后继块中，寄存器为失效，而在另一后继块中非失效，那么将该寄存器识别为局部失效寄存器定义。在全局死码消除步骤75中执行的完全死码的识别(其中，在两个后继中，寄存器定义为失效)后，出现局部失效寄存器的识别。一旦识别为局部失效寄存器，将寄存器添加到局部失效寄存器定义的列表中用在后续标记阶段中。

一旦识别出局部失效寄存器定义集，应用递归标记算法403来递归地标记每个局部失效寄存器的子节点(表达式)，以便实现局部失效节点集(即，局部失效的那些定义的寄存器定义集和子节点)。应注意到局部失效寄存器定义的每个子辈仅可能是局部失效。如果不由有效寄存器定义(或任何类型的有效节点)共享，子辈可以仅分类成局部失效。如果节点被证明是局部失效，那么确定其子辈是否是局部失效等等。这提供递归标记算法，确保在将节点识别为局部失效前，节点的所有引用者为局部失效。

因此，为递归标记算法403的目的，而不是保存单独引用是否局部失效，确定对节点的所有引用是否局部失效。如此，每个节点具有deadCount(即从局部失效父节点对该节点的引用数量)和refCount(对该节点的引用总数)。每次被标记为可能局部失效时，递增deadCount。将节点的deadCount与其refCount进行比较，如果这两个变为相等，那么对那个节点的所有引用局部失效以及将该节点添加到局部失效节点的列表上。然后，将递归标记算法应用于刚添加到局部失效节点的列表的节点的子辈，直到已经识别所有局部失效节点为止。

正好在已经将所有寄存器定义添加到遍历数组后以及将库添加到数组前，在步骤403中应用的递归标记算法最好出现在buildTraversalArray()函数中。对局部失效寄存器定义列表中的每个寄存器，通过两个参数调用recurseMarkPartialDeadNode()函数：寄存器定义节点和其有效的路径。最终丢弃为失效(即在失效路径中)的寄存器定义的节点，以及将局部有效路径的寄存器定义移进转移或跳转的路径之一，产生局部有效节点的单独列表。在条件转移的情况下，创建两个列表，一个用于如果条件估计为真，所遵循的“真路径”，以及一个用于如果条件估计为“假”，所遵循的“假路径”。这些路径和节点被称为“局部有效”而不是“局部失效”，因为丢弃用于它们为失效的路径的节点，以及仅保持其上节点为有效的路径的节点。为提供这种能力，每个节点可以包括识别节点为有效的哪一路径的变量。在recurseMarkPartialDeadNode()函数期间，执行下述伪代码：

----------

IF节点的deadCount为0

  设置路径变量以便与路径参数匹配

Else IF路径变量不与路径参数匹配

  返回(因为在两个列表中局部有效的节点实际上完全有效)

递增deadCount

IF deadCount与refCount匹配

  将节点添加到用于其路径变量的局部有效列表上

      调用用于其子辈的每一个的recurseMarkPartialDeadNode(使用相同路径)

---------

一旦对包含在局部失效寄存器定义集中的每个局部失效寄存器定义，调用了recurseMarkPartialDeadNode()函数，将存在三个节点集。第一节点集包含所有完全有效节点(即refCount高于它们的deadCount的节点)，以及其它两个节点集包含用于条件转移的每个路径的局部有效节点(即具有与它们的deadCount匹配的refCount的节点)。这三个集的任何一个能为空是可能的。作为优化形式，应用代码移动，其中，延迟插置用于局部有效节点的代码直到插置用于完全有效节点的代码之后。

由于排序限制，不总是可能对在步骤403中找到的所有局部有效节点执行代码移动。例如，不允许移动加载，如果存储在该加载后，因为存储可以盖写加载检索的值。类似地，如果对那个寄存器的寄存器定义完全有效，不能码移动寄存器引用，因为寄存器定义将盖写用来生成寄存器引用的源寄存器库中的值。因此，在步骤405中，不递归标记后面跟随存储库的所有加载，以及在步骤407中，不标记具有相应的完全有效寄存器定义的所有寄存器引用。

关于在步骤405中未标记的加载和存储，应注意到当初始构建中间表示时，在局部失效节点的集合之前，具有必须执行加载和存储的顺序。该初始中间表示用在traveseLoadStoreOrder()函数中，以便利用加载和存储之间的相关性来确保按适当顺序发生存储器存取和修改。为用简单的例子示例说明该特征，其中，存在跟随存储的加载，根据加载进行存储以便表示必须首先执行加载。当实现局部死码消除技术时，有必要取消标记加载及其子节点以确保在生成存储前生成它。recurseUnmarkPartialDeadNode()函数用来实现该标记取消。

局部死码消除技术的步骤405可以另外进一步提供用于加载-存储混叠信息的优化。加载存储混叠过滤出连续加载和存储函数访问相同地址的所有情形。如果他们使用的存储器地址相同或重叠，两个存储器访问(例如加载和存储、两次加载和两次存储)混叠。当在traveseLoadStoreOrder()函数期间，遇到连续的加载和存储时，它们一定不会混叠或它们可能混叠。在它们一定不会混叠的情况下，不需要添加加载和存储之间的相关性，从而消除还取消标记加载的需要。加载-存储混叠优化识别出两个访问一定混叠的情形并相应地去除冗余表达式。例如，如果没有干预的加载指令，不需要到相同地址的两个存储指令，因为第二次存储将盖写第一次存储。

关于在步骤407中取消标记的寄存器引用，当代码生成策略在相同寄存器的寄存器定义前，要求生成寄存器引用时，该方面很重要。

这源自表示寄存器在块的开始处具有的值的寄存器引用，使得首先执行寄存器定义将在其被读取前盖写那个值以及为寄存器引用留下错误值。如此，寄存器引用不能被代码移动，如果有相应的完全有效的寄存器定义的话。为说明该情形，使用traverseRegDefs()函数来确定是否存在这些情形以及在步骤407中取消标记落在该范畴中的任何寄存器引用。

在生成有效和局部有效节点集并分别被适当取消标记后，必须为这些节点生成目标代码。当不利用局部死码消除技术时，在traverseGenerate()函数内的循环中生成中间表示中用于每个节点的代码，其中，当它们被认为就绪，即已经满足它们的相关性，以及，生成除后继外的所有节点，后续最后进行。当实现局部死码消除时，这变得更复杂，因为现在有用来生成代码的三个节点集(完全有效集和两个局部有效集)。在条件跳转的情况下，节点集的数量将分别随计算跳转的数量增加。保证后继节点为有效，于是代码生成从所有完全有效节点开始以及由后继节点跟随，以及应用码移动来向后生成局部有效节点。

生成用于局部有效节点的代码的顺序取决于非计算转移中的特定转移的后继的位置，取决于是否转移后继中没有一个、一个或两个也在产生转移的组块中。如此，存在要求用于生成非计算转移的局部死码的代码的三个不同函数。

根据下表3中的顺序，生成为以非计算转移结束的块插置的代码，后续都不在相同的组块中。

                 表3  顺序  插置的码  A  完全有效码  B  后继码(如果为真，转移到E)  C  用于假的局部有效码  D  组块出口(到假目的地)  E  用于真的局部有效码  F  组块出口(到真目的地)

在部分A中插置的指令覆盖完全有效节点所需的所有指令。如果断开局部死码消除，或如果不能找到局部死码，来自部分A的完全有效节点将表示用于该块的所有IR节点(除后继外)。在部分B中插置的指令实现后继节点的功能性。然后，代码生成路径将朝下到C(如果转移条件为“假”)，或跳转到E(如果转移条件为“真”)。在没有实现局部死码消除的情况下，在部分D中插置的指令将正好跟随后继码。然而，当实现局部死码消除时，用于错误路径的局部有效节点需要在跳转到假目的地发生前执行。类似地，在没有局部死码消除的情况下，当条件为真时，在部分F中生成的第一指令的地址将通常是后继者的目的地，但当实现局部死码消除时，必须首先执行部分E中用于真路径的局部有效节点。

当两个后续转移均在相同的组块中时，需要生成同步码。多个因素会影响当两个后继均在相同组块中时插置码的顺序。诸如是否还没有翻译每个后继或哪个后继具有更高执行计数。当两个后继均在相同组块里时插置的码通常将与两个后继都不在组块中时所述的相同，除了在生成同步码(如果有的话)之前，现在必须生成局部有效节点。根据下表4中的顺序，生成为以非计算转移结束的块插置的代码，两个后继均在相同组块中：

                表4  顺序  插置的码  A  完全有效码  B  后继码(如果为真，转移到F)  C  用于假的局部有效码  D  同步码  E  内部转移  F  用于真的局部有效码  G  同步码  H  内部转移

当非计算转移的后继转移的一个在相同组块中，以及另一后继转移在组块外时，结合当两个后继均在相同组块中时所述，处理用于相同组块内的节点的局部有效码。

对于外部后继，在GroupBlockExit以及有时在组块的结尾部之前，有时联机插置用于外部后继的局部有效码。联机生成打算在结尾中的局部有效码，然后拷贝到结尾对象的临时区中。复位指令指针以及向后恢复状态，以便允许应当联机盖写它的代码。当时间到达生成结尾时，从临时区拷贝代码并进入结尾中的适当位置。

为实现用于局部死码的代码生成，利用具有与traverseGenerate()中的循环相同功能性的nodeGenerate()函数来生成三个节点集的每一个。为确保每次生成正确的集合，nodeGenerate()函数忽略具有与它们的refCount匹配的deadCount的节点。因此，第一次调用nodeGenerate()时(从traverseGenerate())，仅生成完全有效节点。一旦生成后继节点，可通过正好在再次调用nodeGenerate()前，将它们的deadCount设置成0，生成两个局部有效节点集。

延缓(lazy)字节交换优化

在翻译器19的优选实施例中实现的另一优化是“延缓”字节交换。根据该技术，通过防止执行基本块的中间表示(IR)内的连续字节交换操作来实现优化，使得连续字节交换操作被最佳化。该优化技术应用在组块内的基本块上，以便延迟字节交换操作以及仅在当将使用字节交换值时应用。

字节交换是指交换字内的字节位置以便颠倒字中的字节顺序。用这种方式，交换第一字节和最后一个字节以及交换第二字节和倒数第二字节的位置。当字用在为小尾(little-endian)计算环境创建的大尾(big-endian)或反之亦然计算环境上时，字节交换是有必要的。大尾计算环境按MSB顺序将字存储在存储器中，是指字的最高有效字节具有第一地址。小尾计算环境按LSB顺序将字存储在存储器中，是指字的最低有效字节具有第一地址。

任何给定的体系结构或是小尾或是大尾。因此，对于为翻译器配对的任何指定的源/目标处理器体系结构，必须确定当编译特定的翻译器应用时，源处理器体系结构和目标处理器体系结构是否具有相同的字节顺序(endianness)。按源字节顺序格式在存储器中排序数据以便源处理器体系结构理解。因此，为了目标字节顺序处理器体系结构理解数据，目标处理器体系结构必须具有与源处理器体系结构相同的字节顺序，或如果不同，必须将从存储器加载或存储到存储器的任何数据字节交换到目标字节顺序格式。如果源处理器体系结构和目标处理器体系结构的字节顺序不同，翻译器必须调用字节交换。例如，在源和目标处理器体系结构不同的情况下，当从存储器读出数据的特定字时，在执行任何操作前必须交换字节的排序以便字节按目标处理器体系结构期望的顺序。类似地，在存在已经计算并需要写出到存储器的数据的特定字的情况下，必须再次交换字节以便使它们处于按存储器期望的顺序。

延缓字节交换是指由本翻译器19执行的技术，延迟对字执行字节交换操作直到真正使用该值时。通过延迟对于字的字节交换操作直到真正利用其值时，能确定连续字节交换操作是否存在于块的IR中，从而能从生成的目标代码消除。对数据的相同字执行两次字节交换不产生有效效应以及仅颠倒字的字节的顺序两次，从而使字中的字节的顺序返回到它们的原始顺序。延缓字节交换允许执行优化，从IR中去除连续字节交换操作，从而消除需要为这些连续字节交换操作生成目标代码。

如前结合由翻译器19生成IR树所述，当生成块的IR时，每个寄存器定义是IR节点的树。每个节点称为表达式。每个表达式潜在地具有多个子节点。为提供这些术语的简单例子的目的，如果寄存器定义为“3+4”，其顶层表达式为“+”，其具有两个子辈，即“3”和“4”。“3”和“4”也是表达式，但它们没有子辈。字节交换是具有一个子辈，即，将字节交换的值的表达式类型。

参考图12，示例说明用于利用延缓字节交换优化技术的优选方法。当在组块模式中，在步骤100中检查块的IR以便定位每个源寄存器定义时，其中，对每个源寄存器定义，在步骤102中，确定其顶层表达式是否是字节交换。不将延缓字节交换应用于不拥有字节交换操作作为其顶层表达式的源寄存器定义(步骤104)。如果顶层表达式为字节交换，那么在步骤106中，从IR去除字节交换表达式，以及设置用于该寄存器的延缓字节交换标志。去除字节交换的表示实质上是指通过丢弃字节交换表达式，被重新定义为字节交换的子辈的寄存器。这导致定义到该寄存器的值按与所期望的相反字节顺序。必须记住就是这种情况，因为在可以正确地使用寄存器中的值之前，必须执行字节交换。

为提供已经去除字节交换表达式和定义到该寄存器的值按与所期望的相反字节顺序的表示，为那个寄存器设置延缓字节交换标志。存在与每个寄存器有关的一个标志，即布尔值，描述那个寄存器中的值是按正确字节顺序还是相反字节顺序。当期望使用寄存器中的值以及设置了那个寄存器的延缓字节交换标志(即标志的布尔值切换到“真”)时，寄存器中的值在使用它之前必须首先被字节交换。通过应用图12所示的优化，以延迟字节交换操作直到真正使用寄存器中的值为止的方式，从IR中去除字节交换表达式。该优化的语义允许在从存储器加载它们的点延迟字节交换直到真正使用值的点为止。如果当使用值时的点正好是返回到存储器的存储，从优化提供节约，源自能去除两个连续字节交换。

一旦引用具有设置成“真”的延缓字节交换标志的寄存器，必须修改IR以便将字节交换表达式插在块的IR中的被引用表达式上。如果另一字节交换表达式与IR中插入的字节交换表达式相邻，则应用优化以防止在目标代码中生成字节交换操作。

只要将一个新值存储到寄存器中，则清除那个寄存器的延缓字节交换状态，意指将用于那个寄存器的延缓字节交换标志的布尔值设置成“假”。当将延缓字节交换标志设置成“假”时，在使用寄存器中的值之前，不需要执行字节交换，因为寄存器中的值已经是按目标处理器体系结构所期望的正确字节顺序。“假”延缓字节交换状态是用于所有寄存器定义的缺省状态，使得只要定义寄存器，应当将标志设置成反映该缺省状态。

延缓字节交换状态是用于IR中的每一个寄存器的所有延缓字节交换标志的集合。在任何指定时间，将“设置”(它们的布尔值为“真”)或“清除”(它们的布尔值为“假”)寄存器，以表示每个寄存器的当前状态。组块内的指定块的出口状态(即延缓字节交换标志的设置)被拷贝为通过组块的热路径内的下一块的入口状态。如上文详细所述，组块包括用一些方式连接在一起的基本块的集合。当执行组块时，遵循通过不同基本块的路径依次执行每个基本块直到退出组块为止。对于指定组块，存在通过其不同基本块的多个可能执行路径，其中，所谓的“热路径”是最频繁遵循的通过组块的路径。由于其被频繁使用，当执行优化时，“热路径”比通过组块的其它路径更有利。为此，当生成组块时，“首先”生成沿“热路径”的块，将热路径中的每个块的入口字节交换状态设置成等于热路径中的在前块的出口状态。

在有效路径之一循环回具有用于已经生成的那个块的代码的基本块的情况中，必须确保在简单执行该所生成的代码前，寄存器的当前延缓字节交换状态如该代码所期望。通过在较冷路径上的块之间插置同步码，在用于那个块的入口延缓字节交换状态中编码该前提条件。同步是从当前基本块的出口状态移动到下一块的入口状态行动。对于每个寄存器，必须检查块之间的延缓字节交换标志以便确定它们是否相同。如果延缓字节交换标志相同，则不需要执行任何动作，而如果不同，必须字节交换当前寄存器的值。

当从组块模式回到基本块模式时，校正延缓字节交换状态。校正是从当前状态到零状态的同步，其中，当退出组块模式时，清除所有延缓字节交换标志。

延缓字节交换优化也能用于浮点寄存器中的加载和存储，由于浮点字节交换的费用，由于优化导致更多节省。在将加载的代码要求单精度浮点数的情况下，必须字节交换单精度浮点加载，然后立即转换成双精度数。类似地，只要代码要求稍后存储单精度数，则必须执行相反转换。为说明用于浮点存储和加载的这些情形，提供用于每个浮点寄存器的兼容性标签中的额外标志，允许延缓地执行字节交换和转换(即延迟直到需要该值为止)。

当引用延缓字节交换的寄存器，以便如上所述在被引用寄存器上插置字节交换操作时，进一步的优化是将字节交换的值写回到寄存器并清除延缓字节交换标志。当重复使用寄存器的内容时，这种优化，被称为回写机制是有效的。实现延缓字节交换优化的目的是，延迟实际的字节交换操作直到有必要使用该值为止，其中，如果永不用寄存器中的值，或如果能够优化掉连续字节交换操作，该延迟在减少目标代码方面是有效的。然而，一旦真正使用寄存器的内容，则必须执行已经延迟的字字交换操作，以及由延缓字节交换提供的节约不再存在。此外，当已经实现延缓字节交换优化以及如果在多个后续块中重复使用寄存器中的值时，则寄存器中的值将具有错误的字节顺序值并将需要在每次使用前插置的字节交换操作，从而要求多个字节交换操作。这会导致比不实现延缓字节交换优化更槽执行的低效目标代码。

为避免源自对相同寄存器值执行多个字节交换操作的该低效目标代码生成，延缓字节交换优化进一步包括回写机制，用于一旦要求对寄存器中的值执行第一字节交换操作，就将寄存器重新定义到其目标字节顺序值，使字节交换值被写回到寄存器。此时还清除用于该寄存器的延缓字节交换标志，以便表示该寄存器包含其期望的目标字节值。这导致对每个后续块，寄存器处于其校正后的目标字节顺序状态下，以及整体目标代码效率与从未应用延缓字节交换优化一样。用这种方式，延缓字节交换优化总是导致比不实现延缓字节交换优化生成的目标代码，如果不是更有效的话，至少一样有效生成的目标代码。

图13A-13C提供了上述延缓字节交换优化的例子。在例子的图13A中，将源代码200示为伪码而不是来自任何特定体系结构的机器码以便简化该例子。源代码200描述循环多次，将值加载到寄存器r3中，然后存回那个值。生成组块202以便包括两个基本块，块1和块2，在图13A所示。不实现延缓字节交换机制，为两个基本块生成的中间表示(IR)将出现如图13B所示。为简化起见，用于基于寄存器r1来设置条件寄存器的IR在该图中未示出。

一旦已经创建用于块1和2的IR，检查寄存器定义列表，查找作为定义的顶层节点的字节交换。在执行该操作中，观察到用于寄存器r3的顶层节点204已经定义为字节交换(BSWAP)。将寄存器r3的定义修改成字节交换节点204的子辈的定义，即LOAD节点206，其中必须记住已经调用了延缓字节交换。在用于块2的IR中，已经看出由节点208引用寄存器r3。由于在寄存器r3的定义中已调用延缓字节交换，字节交换必须在引用能被使用前插置在该引用上，如由图13C中的插入字节交换(BSWAP)节点214所示。在该情况下，存在两个连续字节交换，BSWAP字节210和BSWAP节点214出现在用于块2的IR中。然后，延缓字节交换优化将这些字节交换210和214折叠起来，使得从用于块1和块2的1R中去除字节交换表达式，如图13C所示。作为该延缓字节交换优化的结果，将从IR去除LOAD节点206上的字节交换204(处于循环中并且执行多次)以及与块2中的存储节点212有关的字节交换210，从而通过消除这些字节交换操作生成为目标代码，实现大的节省。

解释器

用于结合翻译器特征，实现不同新颖解释特征的另一示例性装置如图14所示。图14示例说明包括目标寄存器15的目标处理器13和存储多个软件成分19，20，21和22的存储器18。软件成分包括翻译器代码19、操作系统20、已翻译代码21和解释器代码22。应注意到图14中所示的装置基本上与图1所示的翻译装置类似，除通过解释器代码22在图14的装置中添加另外的新颖解释功能外。图14的成分起与参考图1所述的类似编号成分相同的功能，以便将从图14的描述省略这些类似的编号的成分的描述，因为不必要的重复。下文图14的论述将集中在所提供的另外的解释功能。

如上详细所述，当尝试在目标处理器13上执行源代码17时，翻译器19将源代码17的块翻译成用于由目标处理器13执行的已翻译代码21。在某些情况下，解释源代码17的部分以便直接执行它们而不首先将源代码17翻译成用于执行的已翻译代码21更有利。解释源代码17能通过消除存储已翻译代码21的需要而节省存储器，以及通过避免由等待翻译源代码17引起的延迟而进一步提高等待时间数值。解释源代码17通常慢于简单地运行已翻译代码21，因为解释器22每次执行时必须分析源程序中的每个语句，然后执行所需动作，而已翻译代码21仅执行动作。该运行时间分析被称为“解释开销”。解释代码尤其慢于已翻译用于执行多次的源代码部分的代码，使得能重新使用已翻译代码，而不需要每次翻译。然而，解释源代码17能快于将源代码17翻译成已翻译代码21，然后运行用于仅执行少数几次的源代码17部分的已翻译代码的组合。

为优化在目标处理器13上运行源代码17的效率，图14中具体化的装置利用解释器22和翻译器19的组合来执行源代码17的各个部分。典型的机器解释器支持那个机器的整个指令集以及输入/输出能力。然而，这种典型的机器解释器相当复杂以及如果要求支持多个机器的整个指令集的话，甚至更复杂。在用源代码具体化的典型的应用程序中，源代码的多个块(即基本块)将仅利用设计成执行的源代码上的机器的指令集的少量子集。

因此，在该实施例中所述的解释器22最好是仅支持用于源代码17的可能指令集的子集的简单解释器，即，支持源代码17的多个基本块上利用的指令的子集。用于利用解释器22的理想情形是当仅执行少数几次可由解释器22处理的源代码17的大多数基本块时。解释器22在这些情况下特别有用，因为源代码17的大量块永不必由翻译器19翻译成已翻译代码21。

图15提供一种示例性方法，通过该方法，图14的装置确定解释还是翻译源代码17的各个部分。初始地，当分析源代码17时，在步骤300确定解释器22是否支持将执行的源代码17。解释器22可以设计成支持用于任何多个可能的处理器体系结构的源代码，包括但不限于PPC和X86体系结构。如果解释器22不能支持源代码17，如上所述，与本发明的其它实施例有关，在步骤302中，通过翻译器19翻译源代码17。为了允许解释器22对所有类型的源代码17起等效作用，能将NullInterpreter(即不执行任何操作的解释器)用于不被支持的源代码以便不被支持的源代码不必被特殊对待。对于解释器22所支持的源代码17，在步骤304中，确定将由解释器22处理的源代码指令集的子集。该指令子集允许解释器22解释大多数源代码17。确定由解释器22支持的指令的子集，在此称为指令的解释器子集的方式将在下文更详细地描述。指令的解释器子集可以包括针对单一体系结构类型的指令或可以覆盖在多个可能的体系结构上扩展的指令。在实际实施图15的解释算法前，最好确定和存储指令的解释器子集，其中，很可能在步骤304中检索所存储的指令的解释器子集。

在步骤306中，每次一块地分析源代码的块。在步骤308中确定源代码17的特定块是否仅包含由解释器22支持的指令的子集内的指令。如果指令的解释器子集覆盖源代码17的基本块中的指令，那么在步骤310中，解释器22确定用于该块的执行计数是否达到所确定的翻译阈值。将翻译阈值选择为解释器22在解释该块变得比翻译该基本块更低效之前，可执行基本块的次数。一旦执行计数达到翻译阈值，在步骤302中，由翻译器19翻译源代码17的块。如果执行计数小于翻译阈值，则解释器22在步骤312中，基于逐个指令，解释那个块中的源代码17。然后控制返回到步骤306以便分析源代码的下一基本块。如果被分析的块包含不被指令的解释器22子集覆盖的指令，则将源代码17的块标记为不可解释，以及在步骤302中，由翻译器翻译。用这种方式，按照符合最佳性能，解释或翻译源代码17的各个部分。

使用该方法，解释器22将解释源代码17的基本块，除非基本块被标记为不可解释或其执行计数已经达到翻译阈值，其中，在那些实例中，将翻译基本块。在一些情况下，解释器22将运行码和遇到已经标记为不可解释或具有已经达到翻译阈值(通常存储在转移处)的执行计数的源代码中的源地址，使得在这些情况下，翻译器19将翻译下一基本块。

应注意到，解释器22不创建基本块对象以便节省存储器，以及执行计数存储在高速缓存中而不是基本块对象中。每次解释器22遇到支持的转移指令时，解释器22使与转移目标的地址有关的计数器加1。

可以用各种可能的方式来确定指令的解释器子集，以及可以基于在解释和已翻译代码间获得的性能折衷可变地选择。最好，通过测量在被选程序应用集上找到指令的频率，在分析源代码17前，定量地获得指令的解释器子集。尽管可选择任何程序应用，最好仔细地选择它们以便包括明显不同的类型来覆盖宽的指令范围。例如，应用可以包括目标C应用(例如TextEdit，Safari)、Carbon应用(例如OfficeSuite)、广泛使用的应用(例如Adobe，Macromedia)，或任何其它类型的程序应用。然后，选择指令子集，提供被选应用上的最高基本块覆盖率，表示该指令子集提供能使用该指令子集解释的最多个完整的基本块。尽管完全覆盖最多个基本块的指令不一定与最频繁执行或翻译的指令相同，但最终指令子集将粗略地对应于最频繁执行或翻译的指令。该指令的解释器子集最好存储在存储器中并在解释器22上调用。

通过对特定的被选程序应用执行实验，以及还通过使用模型，本发明的发明人发现最频繁翻译的指令(超出用于特定测试应用的总共115指令)和使用最频繁翻译的指令解释的基本块的数量之间的关联能根据下表表示：

  指令集(115)  可解释块  翻译的前20个  70％  翻译的前30个  82％  翻译的前40个  90％  翻译的前50个  94％

从这些结果能确定源代码17的基本块的80-90％能仅使用30个最频繁解释的指令，由解释器22解释。此外，具有较低执行计数的块被给予解释的较高优先级，因为通过使用解释器22提供的一个优点是节省存储器。通过选择30个最频繁翻译的指令，进一步发现可解释块的25％仅执行一次，以及可解释块的75％被执行50或更多次。

为了估计通过解释最频繁翻译的指令提供的节省，仅通过例子，使用翻译约50μs的10个源指令的“平均”基本块和执行该基本块中的一个源指令的假定成本花费15ns，包含在下表中的估计示例说明有关解释器22将必须如何执行以便基于使用用于解释器22的30个最高翻译的指令，提供显著的优点。

  相对于翻译速度的解释  器速度  最大翻译阈值  永不翻译的块的比例  ＜10x更慢  300执行  74％  ＜20x更慢  150执行  71％  ＜30x更慢  100执行  68％  ＜60x更慢  50执行  62％

将最大翻译阈值设置成等于在成本超出翻译该块的成本前，解释器22能执行块的次数。

根据解释和翻译函数的所需操作，能可变地调整从源代码指令集选择的指令的特定解释器子集。另外，在与翻译相反，应当解释的解释器22指令子集中，包括专用源代码17段也很重要。特别要求解释的一种这种专用源代码段被称为蹦床(trampoline)，通常用在OSX应用中。蹦床是在运行时间动态生成的小的代码片。有时在高级语言(HLL)和程序覆盖实现(例如在Macintosh)上发现蹦床，包含小的可执行代码对象的传输中生成以便在代码段之间的间接寻址。在BSD下以及可能在其它Unixes中，当将信号(通常具有所安装的处理器)发送到过程时，蹦床码用来将控制从内核传送回用户模式。如果不解释蹦床，必须为每个蹦床创建分区，导致非常高的存储器使用。

通过使用能处理一定百分比的大多数频繁翻译的指令(即前30)的解释器22，发现解释器22解释测试程序中源代码的所有基本块的约80％。通过将翻译阈值设置到50和100执行之间，同时防止解释器每源指令块比翻译块慢不超出20倍，将永不翻译所有基本块的60-70％。作为减少永不生成的目标代码21的结果，这提供存储器的典型30-40&节省。通过延迟可能不必要的工作，等待时间也可以改进。

应注意到，由解释器22实现的上述节省基于从解释器22的特定使用获得的实验结果。解释器22的各种特征，诸如从源代码指令选择的指令的特定解释器子集以及所选择的特定翻译阈值，将基于解释器22的特定实现和在解释和翻译功能之间实现的所需平衡而可变地选择。此外，特定解释器源指令可以选择为能解释专用目标应用程序。

尽管已经示出和描述了一些优选实施例，本领域的技术人员将意识到在不背离本发明的范围的情况下，可以做出各种改变和改进，如附加权利要求书中所定义的。

注意到与本申请有关，与本说明书同时或在本说明书前提交的以及通过本说明书，向公众调查开放的所有论文和文献，以及所有这些论文和文献的内容在此包含以供参数。

在该说明书(包括任何附加权利要求书、摘要和附图)的所有特征，和/或所公开的任何方法和过程的所有步骤可以结合在任何组合中，除相互排斥的这些特征和/或步骤的一些的组合外。

在该说明书(包括任何附加任何权利要求书、摘要和附图)中公开的每个特征可以用实现相同、等效或类似目的的另外的特征代替，除非特别表述外。因此，除非特别表述外，所公开的每个特征仅是通用等效或类似特征系列的一个例子。

本发明不限于上述实施例的细节。本发明扩展到本说明书(包括任何附加任何权利要求书、摘要和附图)中公开的特征的任何新颖一个特征，或任何新颖组合，或所公开的任何方法或过程的步骤的任何新颖一个步骤或任何新颖组合。