CN1186722C - 用于使用寄存器分配器建立调用约定序言和收尾程序代码的方法和装置 - Google Patents

Abstract

公开一种用于使一个寄存器分配器建立一个调用约定的方法和装置。根据本发明的一个方面，一种用于产生与调用约定有关的代码的计算机实现的方法包括获得源代码，并识别至少一个与调用约定有关的变量。由一个寄存器时标描述变量相对于存储器空间的位置。该方法还包括使用用于分配寄存器的寄存器分配器执行寄存器分配。在寄存器分配期间，在不需要使用特定的序言和收尾程序代码发生器的情况下由分配器内的溢出-代码机构自动产生与调用约定有关的代码。

Description

用于使用寄存器分配器建立调用约定序言和 收尾程序代码的方法和装置

技术领域

本发明一般涉及一种用于提高软件应用程序性能的方法和装置。具体地说，本发明涉及一种使寄存器分配器建立用于子程序的调用约定序言和收尾程序代码的方法和装置

背景技术

在致力于提高与计算机程序执行有关的效率的努力中，很多计算机程序在编译过程中被“优化”。优化一个计算机程序一般用以消除实质上不使用的计算机代码部分。另外，作为编译处理的一部分的优化计算机程序可以重新构成计算操作以提供更为高效地执行的全部计算，从而消耗较少的计算机资源。

一个优化器用于将一个计算机程序、例如以诸如C++，FORTRAN，或Java字节码之类的程序设计语言编写的计算机程序高效变换或者否则编译为更快的程序。更快的或者被优化的程序一般包括基本上所有与原始的或预先变换的计算机程序一样的、可观察到的行为。具体地说，被优化程序包括与其相关原始程序相同的数学行为。然而，优化器一般使用更少的计算重新创建相同的数学行为。

正如本领域技术人员所了解的，一个优化器一般包括一个用于控制寄存器在一个优化的或者否则为编译的程序内部表示内的使用的寄存器分配器。一个寄存器分配器分配一个其中存储与程序有关的数据的寄存器空间。与存取和一个计算机相关的“常规”存储器空间、例如被分为栈页槽的栈空间相关的速度相比，一个寄存器是一个与计算机的处理器相关的、可以被相对较快存取的存储单元。

在寄存器分配处理之前，一组值、即输入变量为编译器所知，并且位于一个调用约定所规定的固定存储单元中。如本领域技术人员所公知的，一个调用约定一般是一个由此进行到子程序的调用的约定。一个调用约定一般规定变量从哪里经过，即，每个变量所出现在的寄存器或栈页槽。另外，一个调用约定可以规定在子程序期间必须保留的寄存器，即，被被调用者-保存寄存器。如果在子程序中使用被被调用者-保存寄存器，则一般需要保存并恢复被被调用者-保存寄存器。调用约定可能还规定某些寄存器是不用于还是用于特定目的。保存和恢复寄存器以及任何其他的特定处理，一般发生在子程序的入口和出口，并且被称为序言和收尾程序代码。在寄存器分配处理完成之后可使用附加信息。这样的附加信息包括，与子程序有关的栈帧大小以及要保存和恢复的一组寄存器，但是附加信息不限于这些。

图1是一个包括一个寄存器分配器和一个调用约定代码发生器的编译器的图示。源代码102作为输入提供给编译器106，该编译器可能是一个优化编译器。一般地，源代码102包括一个对子程序110的调用108，以及与该调用108有关的输入变量112。具体地说，相对于调用108规定输入变量112的位置。

编译器106所包括的一个寄存器分配器116用于分配源代码102所使用的存储器空间。在寄存器分配器116执行一个寄存器分配之后，调用约定代码发生器118产生与源代码102有关的序言和收尾程序代码。以实例方式，如果在分配的任何部分使用任何被被调用者-保存寄存器，则将用于保存和恢复被被调用者-保存寄存器的代码插入到序言和收尾程序代码。序言和收尾程序代码被包括在一个源代码102的内部表示120中。一旦产生内部表示120，编译器106从内部表示120创建机器指令124。

除一个子程序的调用约定之外，内部表示120包括复制、加载和存储与变量定义和使用有关的指令。如图所示，变量或值“c”和“d”存储在一个栈内。如本领域技术人员所公知的，变量“d”必须在子程序调用过程中溢出。因此，变量“d”在子程序调用之后被再次从栈加载到“foo”。

参照图2，该图描述一个从包括调用约定的源代码产生机器指令的过程。如本领域技术人员所公知的，过程202一般包括“虚拟”寄存器到“真实”寄存器的转换。在分配之前，编译器假设有不限数目的“虚拟”寄存器一起工作。分配器的工作是将无限制的虚拟寄存器映象到整个机器具有的非常有限的真实寄存器组。过程202在步骤204开始，在该步骤将调用约定代码插入到编译器所得到的源代码。

一般地，在编译器插入调用约定代码或与一个子程序调用可能产生的约定有关的代码之后，编译器在步骤206研究调用约定。具体地说，编译器研究与调用约定有关的输入变量。在步骤208，确定输入值或变量是否与一个寄存器或栈位置、例如栈页槽有关。当确定输入变量存储在一个寄存器时，过程流进入步骤216，在这里将输入值复制到一个虚拟寄存器。一般地，使用寄存器到寄存器复制命令完成该复制。

一旦输入值被复制到虚拟寄存器，则在步骤212，执行寄存器分配。与执行寄存器分配有关的步骤将在下面参照图3讨论。寄存器分配过程产生分配选择。即，整个寄存器分配过程可用于确定指定给寄存器、即“真实”寄存器和栈页槽的值是如何不同。在寄存器分配过程完成之后，在步骤214通过编译器将寄存器分配过程产生的分配选择转换为机器指令。应该认识到，将分配选择变为机器指令包括使用寄存器分配过程期间所获得的信息建立序言和收尾程序代码。一旦分配选择已被转换，就完成创建机器指令的过程。

回到步骤208，确定输入值是否与一个寄存器或栈位置有关，当确定输入值存储在一个栈位置时，则在步骤210，将输入值加载到一个虚拟寄存器。从步骤210，处理流程进入到步骤212，在这里执行寄存器分配。

图3是表示响应着色干涉图与分配栈空间、即图2的步骤212有关的步骤的流程图。分配与一个源代码段有关的存储器的过程212在步骤302开始，在这里构造一个用于源代码段的干涉图。在干涉图构成之后，在步骤306尝试着色干涉图。一般地说，在尝试着色干涉图时可以使用各种不同的方法。一旦在步骤306尝试着色干涉图，就在步骤310确定对着色干涉图的尝试是否成功。换言之，确定在没有冲突的情况下与干涉图有关的每个变量是否被成功指定到一个寄存器。

如果确定为对着色的尝试不成功，则暗示在没有干涉的情况下没有足够的寄存器使得源代码段内的每个变量被指定一个寄存器。由于处理器内的寄存器数量是固定的，当没有可用于代码存储的寄存器空间时，识别“溢出代码”。如本领域技术人员所公开的，溢出代码是将数据移动到栈页槽以及从栈页槽移开的代码，以减少同时需要的寄存器数目。当所有寄存器占满时，栈页槽是分配器用于保留信息的一段栈帧。一般地说，一个优化器包括用于根据需要分配用于溢出代码的栈页槽的专门栈页槽分配器。当除适合寄存器的变量之外的变量通过栈时一般也需要用于溢出代码的栈页槽。

如果在步骤310确定为对着色干涉图的尝试不成功，则流程从步骤310移动到步骤314，在这里得到一个有效范围列表作为溢出候选者。即，识别可溢出到栈页槽的变量。

一旦识别出溢出候选项，则在步骤318，将加载指令和存储指令指定到定义周围并在源代码段内使用。具体地说，在源代码段内使用变量之前插入加载变量的加载命令，同时在源代码段内定义变量之后插入存储变量的存储指令。

在指定加载指令和存储指令、即加载和存储之后，在步骤322分配一个栈页槽用于每次加载和存储。通常，与寄存器分配器分开的一个栈页槽分配器用于分配栈页槽。尽管栈页槽分配器与一个寄存器分配器分开，应该明白，两个分配器都包括在一个优化器或一个编译器内。分配栈页槽允许溢出候选项溢出到栈页槽。从步骤322，处理流程回到步骤302，在这里构成一个干涉图。

回到步骤310，如果确定为对着色干涉图的尝试成功，则暗示每个变量已被成功地与一个寄存器或一个栈页槽关联。因此，处理流程进入步骤326，在这里清除或结束该分配。在清除一个分配期间，栈页槽号被转换为到栈帧的偏移，复制根据需要表示为加载或存储，实际的寄存器号插入到机器指令，并且专著于其他的内务清零杂务，如本领域技术人员所公知的。

在构成一个调用约定之前，例如，在产生调用约定的机器指令之前必须完成一个寄存器分配过程的要求具有几个缺点。例如，为产生序言和收尾程序代码，必须使用用于产生序言和收尾程序代码的专门代码段。这样的代码可能包含故障，并且最低程度可能需要调试。进一步地，这样的代码还常常是与机器相关的，因此减少了代码的可移植性。

因此，所需要的是一种高效产生用于调用约定的机器指令以便机器指令可以很容易地在不同计算系统之间移植的方法和装置。这样的方法和装置可以进一步允许溢出代码试探法以选择是否溢出一个被被调用者-保存寄存器并消除所需要的专门序言和收尾程序产生。具体地说，所需要的是一种使寄存器分配器实质上建立一个调用约定的方法和装置。

发明内容

本发明涉及在创建一个调用约定中使用寄存器分配器。根据本发明的一个方面，用于产生与一个调用约定有关的代码的计算机实现的方法包括获得可编译源代码，并识别至少一个与该调用约定有关的变量。变量相对于存储器空间的位置通过一个寄存器时标来描述。该方法还包括使用用于分配寄存器的寄存器分配器执行一个寄存器分配。在寄存器分配期间，产生与调用约定有关的代码。

根据本发明的另一个方面，一种用于在基于对象的系统中建立与一个调用子程序有关的调用约定的方法包括获得适合于编译的源代码，创建每个都具有一个带有相关有效范围的相关变量的多个寄存器时标，以及确定多个寄存器时标的交集。使用交集执行一个寄存器分配。除分配寄存器之外，该寄存器分配产生与调用约定有关的代码。在一个实施例中，该方法进一步包括将与调用约定有关的代码转换为机器指令，该机器指令适合于由一个计算系统执行。

通过允许在寄存器分配期间、即当一个寄存器分配器基本上自动产生调用约定代码时建立一个调用约定，该调用约定可以很容易地被特征化。该分配器可用于高效执行一个分配。此外，当一个寄存器分配器产生调用约定代码时，根据源代码调用约定代码可以很容易地在不同平台之间移植。

本发明提供如下方法和系统：

(一)一种用于产生与调用约定有关的代码的计算机实现的方法，该计算机实现的方法包括：

获得源代码，该源代码适合于由一个编译器编译，其中该编译器包括一个用于分配存储器空间的寄存器分配器；

识别至少一个与调用约定有关的变量，其中该变量在存储器空间中的位置由一个寄存器时标描述；以及

使用寄存器分配器执行寄存器分配过程，其中该寄存器分配过程用于产生与调用约定有关的代码。

(二).一种用于建立一个调用约定的计算机实现的方法，在基于对象的系统中，该调用约定与一个对子程序的调用相关，该计算机实现的方法包括：

获得源代码，该源代码适合于编译；

创建多个寄存器时标，多个寄存器时标中的每一个具有一个相关变量，每个相关变量具有一个相关有效范围，每个相关变量被进一步包括在源代码内；

确定多个寄存器时标的一个交集；以及

执行寄存器分配，其中执行寄存器分配包括使用交集并产生与调用约定有关的代码。

(三).一种用于建立一个调用约定的计算机系统，在与该计算机系统相关的基于对象的系统中，该调用约定与一个对子程序的调用相关，该计算机系统包括：

一个处理器；

源代码输入机构，用于获得源代码，该源代码适合于编译；

寄存器时标发生器，用于创建多个寄存器时标，多个寄存器时标中的每一个具有一个相关变量，每个相关变量具有一个相关有效范围；

确定器，用于确定多个寄存器时标的一个交集；和

编译器，该编译器包括一个寄存器分配器，其中该寄存器分配器用于使用交集产生与调用约定有关的代码。

附图说明

通过阅读下面的详细描述并参照各个附图，本发明的这些和其他优点将变得显而易见。

参照结合附图所作的描述，将更好地理解本发明，其中：

图1是用于建立一个调用约定的编译器的图示。

图2是描述与产生机器指令有关的步骤的过程流程图。

图3是描述与分配栈空间的过程即图2的步骤212有关的步骤的过程流程图。

图4a是根据本发明的一个实施例的一个包括用于建立一个调用约定的寄存器分配器的编译器的图示。

图4b是根据本发明一个实施例的一个寄存器时标的图示。

图5是根据本发明的一个实施例的描述与产生机器指令有关的步骤的过程流程图。

图6是根据本发明的一个实施例的描述与分配栈页槽的过程、即图4的步骤508有关的步骤的过程流程图。

图7是一个适用于实现本发明的通用计算机系统的图示。

图8是由图7的计算机系统支持的并适用于实现本发明的虚拟机的图示。

具体实施方式

一个编译器、例如优化编译器常常包括一个用于分配保留变量的栈页槽的栈页槽分配器，由于与一个处理器相关的寄存器的数量有限这个事实，该变量可能不存储在寄存器中。这样的编译器一般还包括一个用于建立子程序调用约定代码的调用约定代码发生器。在一个编译器执行寄存器分配之前，一组值、即输入变量处于由一个调用约定规定的固定位置。为建立一个调用约定，需要诸如相关栈帧尺寸和用于存储与调用约定相关的变量的存储器组之类的附加信息。这样的信息一般不可用，直到寄存器分配过程完成之后为止。通过要求在建立调用约定之前进行寄存器分配过程，减少包括调用约定代码的代码的可移植性，因为在调用约定代码中关于调用约定的较小变化可能引起的较大的基于平台的变化。

当以与机器寄存器一样的方式处理基于栈的值或变量时，将不需要专门的栈页槽分配器。使用分配栈页槽的寄存器分配器使得以与寄存器相同的方式处理栈页槽，从而消除与通常用于处理存储在栈页槽内的值的试探法有关的故障。

进一步，使用寄存器分配器来基本上自动产生调用约定代码允许在了解到子程序调用的输入变量的位置时产生调用约定代码。具体地说，通过高效集成指令分配、即子程序调用、变量分配的输入和指令结果，寄存器分配器可以产生调用约定代码。

允许寄存器分配器产生调用约定代码一般对寄存器分配器具有最小的影响。通过实例的方式可看出，初始条件的设定影响寄存器分配器。因此，使用寄存器分配器产生调用约定代码增加了包括调用约定代码的全部代码的灵活性，并且使得更快地执行代码。另外，使用寄存器分配器产生调用约定代码使得调用约定代码基本上独立于机器。例如，通知分配器输入变量的实际初始位置，而不是将它们立即移动到虚拟寄存器。如果输入位置被认为是令人满意的，则避免移动到虚拟寄存器。如参照图4a所讨论的，变量“d”通过栈。如果变量“d”被提升到虚拟寄存器，则其必须通过一个调用溢出到foo。将变量“d”留在栈内的其初始位置避免该溢出。

在一个实施例中，一个溢出代码机构用于建立序言和收尾程序代码，并且一个相对简单的接口可用于描述被被调用者-保存寄存器的行为，从而使其相对容易地将该接口移植到不同的中央处理单元(CPU)。这样的接口还可以改变一组被被调用者-保存寄存器，即，相同CPU上的调用约定。使用溢出代码机构建立调用约定代码、例如序言和收尾程序代码允许溢出候选者选择试探法以全局方式组合溢出被被调用者-保存寄存器或者不溢出被被调用者-保存寄存器的作用。常规的溢出候选者选择技术通常是不完善的，因为常规技术或者“急切地”抓取被被调用者-保存寄存器，可能迫使被被调用者-保存寄存器在一般情况下被溢出以便使其可用于不被频繁执行的代码，或者在不了解该决定在整个分配过程中的作用的情况下就迫使对是否局部使用一个被被调用者-保存寄存器做出决定。

在所述实施例，取代插入调用约定代码，一个寄存器分配器声明基本上全部的被被调用者-保存寄存器在入口有效并在出口可用，例如，在到子程序的入口有效并在子程序的出口可用。这样的声明高效地创建了一组相对较长的有效范围，例如，它们可以覆盖整个方法，并且基本上仅具有一个单独用途和基本上仅一个单独定义。如果需要的话，这样的有效范围产生理想的溢出候选者。

如果被被调用者-保存有效范围溢出，则所插入的用于该有效范围的加载和存储将表现为传统的序言和收尾程序代码。应该认识到，不需要专门的序言和收尾程序代码发生器，因为使用常规的溢出机构的溢出被被调用者-保存有效范围的真正作用是产生序言和收尾程序代码。

参照图4a，将描述根据本发明的一个实施例的一个包括用于产生调用约定代码的寄存器分配器的编译器。源代码402作为输入提供给一个编译器406，在所述实施例，该编译器是一个优化编译器。源代码402包括一个到子程序410的调用408，以及输入变量412。输入变量412与调用108有关，即，相对于调用108规定输入变量112的位置。输入变量的位置可以规定在寄存器时标内，如下面参照图4b所述。在一个实施例，每个输入变量具有一个相关的寄存器时标。

优化编译器406所包括的寄存器分配器416用于分配源代码402所使用的存储器空间。如下面参照图5和6所述，寄存器分配器416以与分配寄存器空间的相同方式分配栈空间。寄存器分配器416进一步用于使用输入变量412创建调用约定代码，该代码包括在源代码402的内部表示420中。换言之，增加了被被调用者-保存寄存器的有效范围。在图4a，增加了用于机器寄存器EDI的有效范围；将其定义为在到子程序的入口为有效，在子程序返回时需要回到EDI。优化编译器406进一步用于将内部表示420转换为适合于执行的机器指令424。

如前所述，由寄存器分配器使用以建立调用约定的每个输入变量或输入可变值可以具有一个相关的寄存器时标。一个寄存器时标是表示有效寄存器并且在某些情况下表示栈页槽的位、或位时标的集合。换言之，一个寄存器时标是用于表示所有可能的机器寄存器并且，如果恰当的话，表示栈页槽的数空间。寄存器时标内的位数可以根据执行机器指令的平台而变化。作为一个实例，在一个Intel平台、例如具有来自Santa Clara，California的Intel公司的商业上可得到的奔腾处理器的平台上，一个寄存器时标可以是96位的集合。

图4b是根据本发明一个实施例的寄存器时标的图示。寄存器时标452包括多个位460。每个位460设定为指示一个特定的寄存器相对于寄存器时标452关联的变量是否有效。位460的数目独立于与一个特定处理器关联的寄存器或栈页槽数量，至少部分是这样。在所述实施例，当一位、例如位460b设定到值“1”时，指示为与位460b相关的寄存器有效。或者，当一位、例如位460a设定到值“0”时，指示为相关寄存器无效。在一个实施例，在寄存器时标452中至多一位460被设定，即设定为“1”，这是因为位460表示诸如整数或浮点数之类的单个的精确值。在另一个实施例，就实例而言，当位460表示长整数时，可以设定两位460。

图5是根据本发明一个实施例表示与产生机器指令有关的步骤的过程流程图。具体地说，将描述与产生具有由一个寄存器分配器确定的调用约定的机器指令有关的步骤。使用包括一个寄存器分配器的优化编译器产生机器指令的过程502在步骤504开始，在这里得到用于调用约定的寄存器时标。如前所述，一个寄存器时标是表示有效寄存器集合并且在某些情况下表示栈页槽集合的位或位时标的集合。寄存器时标内所包括的位数例如可以根据与计算系统相关的处理器类型而变化很大。寄存器时标被高效地用于描述与一个调用约定有关的值的位置。

一旦得到寄存器时标，则在步骤506，收集用于有效范围的寄存器时标的交集。如前所述，一个有效范围是一个特定变量在其上保持可存取的范围和距离。寄存器时标的交集一般识别由多于一个值使用的寄存器或栈页槽。换言之，寄存器时标的交集提供一组用于干涉图着色过程的“节点”，如下面参照图6所讨论的。寄存器时标交集的使用简化一个着色过程，因为一般存在剩余颜色。在交集用于一个特定有效范围的寄存器时标之后，如果寄存器时标无颜色，则该有效范围必须立即溢出。例如，如果一个输入变量通过寄存器ECX，但在EDX内用作一个输出变量，则仅包含ECX和EDX的寄存器时标的交集将为空。至少，需要ECX和EDX之间的复制。

在得到寄存器时标的交集之后，则在步骤508执行寄存器分配。下面将参照图6描述一种用于允许优化编译器以分配寄存器和栈页槽的方法的实施例。该寄存器分配产生包括调用约定代码的分配选择。在步骤510将从步骤508的寄存器分配处理产生的分配选择转换为机器指令。一般地说，优化编译器将分配选择转换为机器指令。一旦分配选择被转换，就完成产生机器指令的处理。

参照图6，将描述根据本发明一个实施例的与分配寄存器和栈页槽的过程、准确地说即图5的步骤508有关的步骤。具体地说，图6描述与分配寄存器和栈页槽协同操作的源代码内的干涉图着色的性能。寄存器分配处理常常与干涉图着色处理相关。分配存储器空间的处理在步骤601开始，在这里，相对于源代码插入被被调用者-保存有效范围。处理流程从步骤601进入步骤604，在这里创建，或“建立”一个用于特定源代码段的干涉图。源代码段一般为基本上以任何适宜的程序设计语言，例如，C程序设计语言或Java字节代码编写的软件应用程序部分。通常，干涉图的创建包括表示与源代码内的变量或值相关的有效范围以及表示有效范围之间的干涉，如前所述。从寄存器时标的交集得到干涉图的“节点”，如前面参照图5所描述的。

一旦建立干涉图，则在步骤608试图着色干涉图。着色干涉图包括在无冲突或干涉的情况下，将寄存器指定到不同的值。如本领域技术人员所知道的，用于着色一个干涉图以执行寄存器分配的方法可以变化很大。这样的方法可以包括但不限于Briggs-Chaitin寄存器分配方法、the Chow style分配方法、以及linear scan分配方法。

在步骤612就试图着色干涉图是否成功作出确定。换言之，确定在无任何冲突的情况下寄存器是否被指定给与干涉图相关的所有变量。当确定为试图着色干涉图不成功时，则指示没有足够的寄存器使得在无冲突的情况下指定与干涉图相关的所有变量。因此，在所述实施例，当使用所有可用寄存器时，分配栈页槽用于变量存储。

处理流程从步骤612进入步骤616，在这里得到与干涉图相关的有效范围列表作为溢出候选者。即，识别可溢出到栈页槽的值。通常，基本上可使用任何试探法以选择溢出候选者。一般地说，选择包括在试图着色一个干涉图之前，建立被被调用者-保存有效范围，即，步骤601内的建立。可以选择被被调用者-保存有效范围作为溢出候选者选择处理的一部分。在所述实施例，溢出被被调用者-保存有效范围高效地建立序言和收尾程序代码。

在步骤620识别溢出候选者之后，复制指令被高效地指定或插入到定义周围并使用相关的溢出候选者。在所述实施例，一个复制指令在与一个溢出候选者相关的定义之后并且在与一个溢出候选者相关、例如使用的指令之前指定。指定在定义或使用指令周围的一个复制指令一般具有寄存器到寄存器，即，“reg-reg”复制指令的特征。如本领域技术人员所公知的，一个复制指令可以包括将值置于栈，但是一般不需要将值置于栈。一旦在步骤620将复制指令指定到定义周围并使用相关的溢出候选者，则处理流程回到步骤604，在这里建立一个新的干涉图。

回到步骤612并确定对着色的尝试是否成功，当确定为着色尝试成功时，则指示为溢出是不必要的。即，当着色确定为成功时，则不需要存储变量的附加的栈页槽。在所述实施例，一般存在与着色处理相关的剩余颜色。因此，对着色的尝试一般是成功的。因此，处理流程进入到步骤628，其中与复制指令相关的每个复制被指定在定义周围并且评价使用以确定其是否对应于一个存储指令、一个加载指令或一个寄存器到寄存器复制指令。这样的确定是必要的，因为CPU内的真实的复制指令一般不在栈页槽和寄存器之间移动值。为在栈页槽和寄存器之间移动值通常需要加载和存储指令。

从步骤628，处理流程进入步骤632，在这里确定包括步骤624分配的栈页槽的栈帧尺寸。如前所述，调用约定代码的产生使用诸如栈帧尺寸之类的信息。尽管栈帧尺寸可以基于各种不同尺寸系数，在所述实施例，栈帧尺寸基于相关名称内的最大栈页槽，如本领域技术人员所公知的。一旦确定栈帧尺寸，就在步骤636清零该栈。清零栈一般包括将复制适当地转换为加载和存储。在所述实施例，不需要具体的“pass”以产生被被调用者-保存寄存器的保存和恢复，即，序言和收尾程序代码。在栈被清零之后，完成执行分配的处理器。

图7示出一个适用于实现本发明的典型的、一般的通用计算机系统。计算机系统1030包括任何数目的耦合到包括主存储设备1034(一般为一个随机存取存储器或RAM)和主存储设备1036(一般为只读存储器或ROM)的存储器设备的处理器1032(还称为中央处理单元或CPU)。

计算机系统1030或，具体地说，CPU1032可以用于支持一个虚拟机，如本领域技术人员所公知的。下面参照图8将描述支持计算机系统1030的一个虚拟机的实例。如本领域技术人员所公知的，ROM用于单向传送数据和指令到CPU1032，而RAM一般用于以双向方式传送数据和指令。CPU1032一般包括任何数目的处理器。两个主存储设备1034、1036可以包括任何适当的计算机可读介质。一般为大容量存储器设备的第二存储介质1038还双向耦合到CPU1032并提供附加的数据存储容量。大容量存储器设备1038是可用于存储包括计算机代码，数据，和类似数据的程序的计算机可读介质。一般地说，大容量存储器设备1038是通常比主存储设备1034、1036慢的诸如磁盘和磁带之类的存储介质。大容量存储器设备1038可以采取磁带或纸带读取器的形式或某些其他公知的设备。应该认识到，在适当的情况下，大容量存储器设备1038内保留的信息可以加入到标准形式作为虚拟机的RAM1036的一部分。诸如CD-ROM之类的具体的主存储设备1034可以单向通过数据到CPU1032。

CPU1032还耦合到一个或多个输入/输出设备1040，输入/输出设备1040可以包括但不限于诸如视频监视器、跟踪球、鼠标、键盘、麦克风、触摸-敏感显示器、转换器卡读取器、磁带或纸带读取器、输入板、指示笔、语音或手写识别器之类的设备或其他诸如自然包括其他计算机之类的公知输入设备。最后，CPU1032可以使用一般在1012示出的网络连接，可选地耦合到一个计算机或电信网络，例如，一个局域网、一个因特网或一个企业网。使用这样的网络连接，希望在执行上述方法步骤的过程中CPU1032可以接收来自网络的信息并将信息输出到网络。常常表示为使用CPU1032执行的指令序列的这些信息可以例如以载波体现的计算机数据信号的形式从网络接收并输出到网络。上述设备和材料为计算机硬件和软件领域内的技术人员所熟知。

如前所述，可以在计算机系统1030执行虚拟机。图8是图7的计算机系统1030支持，并适用于实现本发明的虚拟机的图示。当执行一个计算机程序，例如，以Palo Alto，California的SunMicrosystems开发的Java^TM程序设计语言编写的计算机程序时，在编译时间环境1105将源代码1110提供给编译器1120。编译器1120将源代码1110转换为字节代码1130。通常，在软件开发者创建源代码1110时源代码1110被转换为字节代码1130。

字节代码1130一般被复制、下载或另外通过一个网络、例如图7的网络1012分发，或存储在诸如图7的主存储器1034之类的设备。在所述实施例，字节代码1130为与平台无关的。即，基本上可以在运行适当的虚拟机1140的任何计算机系统执行字节代码1130。作为一个实例，在Java^TM环境下，字节代码1130可以在运行Java^TM虚拟机的计算机系统上执行。

将字节代码1130提供给包括虚拟机1140的运行时环境1135。一般使用诸如图7的CPU1032之类的处理器执行运行时环境1135。虚拟机1140包括一个编译器1142，一个解释器1144，和一个运行时间系统1146。字节代码1130一般可以提供给编译器1142或解释器1144。

当字节代码1130提供给编译器1142时，字节代码1130所包含的方法被编译为机器指令，如上所述。另一方面，当字节代码1130提供给解释器1144时，字节代码1130一次一个字节地读取到解释器1144。接着在每个字节代码被读取到解释器1144时，解释器1144执行每个字节代码定义的操作。通常，解释器1144处理字节代码1130并随后连续执行与字节代码1130相关的操作。

当从操作系统1160调用一个方法时，如果确定调用该方法作为一个解释方法，则运行时间系统1146可以从解释器1144得到该方法。如果，另一方面，确定调用该方法作为一个编译方法，则运行时间系统1146启动编译器1142。接着编译器1142从字节代码1130产生机器指令，并执行机器语言指令。通常，当虚拟机1140终止时放弃该机器语言指令。

尽管已经描述了本发明的几个实施例，应该明白，在不脱离本发明的精神和范围的情况下，本发明可以以多种具体的形式体现。作为一个实例，可以记录，移走或增加产生与调用约定有关的机器指令所包含的步骤。通常，在不脱离本发明的精神和范围的情况下，可以记录、移走或增加使用本发明方法所包含的步骤。

如本领域技术人员所公知的，一个被被调用者-保存寄存器是一个子程序调用不破坏其内容的寄存器。一个被被调用者-保存寄存器的实例是Intel 80×86CPU内的EDI寄存器。一般地说，一个计算机系统不使用与被被调用者-保存寄存器相关的寄存器空间。相反，计数所使用的被被调用者-保存寄存器的数目，并且执行一个溢出以得到补偿所有前面的被被调用者-保存寄存器的栈页槽。通过将与被被调用者-保存寄存器相关的信息存储到栈，使用被被调用者-保存寄存器作为一个“常规”寄存器，接着将相关信息返回到被被调用者-保存寄存器可以将本发明用于被被调用者-保存寄存器。具体地说，无论何时试图避免使用与被被调用者-保存寄存器相关的空间。然而，当需要空间时，该空间被声明使用。应该明白，基本上自动产生调用约定代码的一个寄存器分配器一般用于处理到调用的输入变量，来自调用，被被调用者-保存寄存器以及被调用者-保存寄存器的输出变量。

尽管一种使用寄存器分配器建立一个调用约定的被描述为包括使用寄存器分配器根据需要分配栈页槽，应该明白，替换的方法和机构可以用于分配栈页槽。例如，可以使用常规方法分配栈页槽。

与寄存器时标相关的位数例如根据该寄存器时标相关的平台可以变化很大。尽管本发明描述为适用于Intel平台，本发明基本上可以适用于任何适当的平台，这些平台包括但不限于Power PC平台和Spare平台。因此，本发明实例被认为是示意性的但不具备限定性，并且本发明不被本文所给出的细节所限定，在附属权利要求书的范围内可以修改本发明。

Claims (11)

1.一种用于产生与调用约定有关的代码的计算机实现的方法，该计算机实现的方法包括：

获得源代码，该源代码适合于由一个编译器编译，其中该编译器包括一个用于分配存储器空间的寄存器分配器；

识别至少一个与调用约定有关的变量，其中该变量在存储器空间中的位置由一个寄存器时标描述；以及

使用寄存器分配器执行寄存器分配过程，其中该寄存器分配过程用于产生与调用约定有关的代码。

2.一种用于建立一个调用约定的计算机实现的方法，在基于对象的系统中，该调用约定与一个对子程序的调用相关，该计算机实现的方法包括：

获得源代码，该源代码适合于编译；

创建多个寄存器时标，多个寄存器时标中的每一个具有一个相关变量，每个相关变量具有一个相关有效范围，每个相关变量被进一步包括在源代码内；

确定多个寄存器时标的一个交集；以及

执行寄存器分配，其中执行寄存器分配包括使用交集并产生与调用约定有关的代码。

3.如权利要求2所述的计算机实现的方法，进一步包括：

将与调用约定有关的代码转换为机器指令，该机器指令适合于由一个计算系统执行。

4.如权利要求2和3中的一个所述的计算机实现的方法，其中确定多个寄存器时标的一个交集包括：

识别用于与该交集有关的一个变量的有效寄存器。

5.如权利要求2和3中的一个所述的计算机实现的方法，其中确定多个寄存器时标的一个交集包括：

识别用于与该交集有关的一个变量的栈页槽。

6.如权利要求2所述的计算机实现的方法，进一步包括：

使用交集产生干涉图。

7.如权利要求6所述的计算机实现的方法，进一步包括：

着色干涉图。

8.如权利要求2所述的计算机实现的方法，其中执行寄存器分配包括：

分配一个寄存器；和

分配一个栈页槽。

9.一种用于建立一个调用约定的计算机系统，在与该计算机系统相关的基于对象的系统中，该调用约定与一个对子程序的调用相关，该计算机系统包括：

一个处理器；

源代码输入机构，用于获得源代码，该源代码适合于编译；

寄存器时标发生器，用于创建多个寄存器时标，多个寄存器时标中的每一个具有一个相关变量，每个相关变量具有一个相关有效范围；

确定器，用于确定多个寄存器时标的一个交集；和

编译器，该编译器包括一个寄存器分配器，其中该寄存器分配器用于使用交集产生与调用约定有关的代码。

10.如权利要求9所述的计算机系统，其中该编译器用于将与调用约定有关的代码转换为机器指令，该机器指令适合于执行。

11.如权利要求9和10中的一个所述的计算机系统，其中该寄存器分配器进一步用于分配一个寄存器以及分配一个栈页槽。

Images