包含栈变量函数的优化方法

技术领域

本发明涉及函数优化方法，特别涉及包含栈变量函数的优化方法。

背景技术

CPU(中央处理器)在计算机中起着核心作用，随着科技的不断进步，处理器技术也在不断发展。如按照CPU处理信息的字长，CPU就经历了四位微处理器、八位微处理器、十六位微处理器、三十二位微处理器以及六十四位微处理器的发展历程。一般来说，新的处理器与旧的处理器相比会引入一些新的特性，如增加寄存器数量、添加新的指令、增加cache容量等。

为了方便用户，新的处理器会兼容基于旧处理器所开发的软件，但已有应用程序(即为旧的处理器编译生成的二进制代码)在新处理器上运行时可能不能利用新处理器较原有处理器新增加的某些特性来加速程序的运行，使得新处理器的性能潜力并没有被完全发掘，在一定程度上造成了资源浪费。

以处理器中的寄存器(register)为例，寄存器作为处理器中运行速度最快的存储器，通常被用来保存参加运算的操作数和中间结果。由于寄存器相对于内存单元具有数量少和访问速度快的特点，因此根据程序的局部性原则，操作系统会将经常使用的值放在寄存器中以减少访存开销，从而提高整个程序的性能。出于上述原因，在一个应用程序中使用较多的寄存器将会加速程序的运行。新的处理器(如六十四位微处理器)较旧的处理器(如三十二位微处理器)在寄存器数目上有所增加，因此，当在新的处理器上运行已有应用程序时，可以利用新处理器中增加的寄存器来加速程序运行。

在利用新处理器中增加的寄存器来加速程序运行时，需要把一些原先保存在内存中的数据存储到空闲寄存器中，这一过程被称为寄存器提升优化。但为了保证优化后程序运行结果的正确性，必须解决内存别名的问题。所谓的内存别名是指在将变量数据存储到空闲寄存器后，系统中就存在了同一个变量的两个版本，一个在寄存器中，另一个在内存中。为了保证程序运行的正确性，需要将所有对这个变量的操作都重定向为对相应寄存器的操作。但是，由于程序中存在大量的指针访问以及缺乏程序信息的支持，因此可能无法出程序中所有对被提升变量进行操作的指令。

以栈变量为例，程序中大多数对栈变量的访问都是通过显式的栈式访问(即访问基址是栈顶或栈帧指针，如图1中的0x18(％esp)和0x24(％esp))，但是也有一些隐式的访栈操作是通过指针对栈变量进行存取的(如图1中的0x4(％edx，％ebx，1)和0x4(％eax))。因此，为了保证程序运行的正确性，操作系统必须识别出程序中的所有隐式访问被提升的栈变量的访存操作。现有技术中的一个简单的方法是在每个非栈式访存操作(访存地址不是以栈顶或栈帧指针为基址)前添加指令检查访存地址是否与被提升的栈变量的内存地址相同。但这种方法会带来很大的运行时开销。图1中给出了一个在X86-64平台上利用栈变量寄存器提升来优化X86-32代码的例子。图1中左边是优化前的X86-32代码，其中含有两个栈变量0x18(％esp)和0x24(％esp)。如果这两个栈变量和其他访存地 址之间没有别名关系，那么在程序运行时可以直接将这两个栈变量提升到X86-64平台上的空闲寄存器中。但是，如果不能确定被提升的栈变量和其他访存地址之间没有别名关系，那么就必须采取一些措施来保证优化后代码执行结果的正确性。如前所述，现有技术可以通过添加别名检查指令的方式在运行时保证优化后代码的正确性。图1中给出了检查内存别名的代码示例，从示例代码中可以发现这种方法会带来很大的运行时开销。

发明内容

本发明的目的是克服现有技术采用别名检查指令来克服内存别名问题时运行开销大的问题，从而提供运行开销小的函数优化方法。

为了实现上述目的，本发明提供了一种包含栈变量函数的优化方法，包括：

步骤1)、申请一段物理内存空间作为所要优化的函数的映像栈，然后再申请一段虚拟内存空间作为所要优化的函数的影子栈，将该段虚拟内存空间映射到与所述映像栈相同的物理内存；

步骤2)、在所述所要优化的函数中识别栈变量，从中选择要被提升到空闲寄存器中的栈变量；

步骤3)、在所要优化函数的入口处插入将被优化函数的函数栈从系统栈切换到映像栈的指令、将栈变量的内容提升到寄存器中的指令以及将映像栈中的虚存页设为保护状态的指令；

步骤4)、在所要优化函数的代码中，将所有包含对所提升栈变量操作的指令替换为对相应寄存器操作的指令，将所有对未提升的栈变量的操作替换为对所述影子栈上相应虚存地址的操作；

步骤5)、在所要优化函数的出口处依次插入将映像栈中的虚存页解除保护状态的指令、将被提升的栈变量的内容从寄存器存回内存的指令、将函数栈帧从映像栈切换回系统栈的指令。

上述技术方案中，还包括对被优化函数在执行过程中出现的异常进行处理的步骤6)；该步骤包括：当发生异常的指令位于被优化函数所调用的函数中，或者发生异常的指令位于被优化的代码中且访存地址发生在被保护的虚存页的被提升的栈变量的地址范围内时，放弃对函数的优化；当发生异常的指令位于被优化的代码中且访存地址发生在被保护的虚存页的未被提升的栈变量的地址范围内时，生成别名检查指令并插入到优化代码中。

上述技术方案中，所述的步骤6)包括：

步骤61)、从异常现场上下文得到发生越权访问的指令地址及其访存地址；

步骤62)、判断所述访存地址是否在所述映像栈中被保护的虚存页内，如果在，执行下一步，否则，直接对所发生的异常进行处理；

步骤63)、判断发生异常的指令是否在被优化函数的优化代码中，如果在，执行下一步，如果不在，且发生异常的指令在被优化函数所调用的函数中，则放弃对被优化函数的优化；

步骤64)、将被保护的虚存页中包含提升变量的地址范围分为两个部分，一个部分包含了所有的提升变量，另一部分不包含任何提升变量；

步骤65)、判断发生异常的指令的访存地址是否在包含提升变量的地址范围内，如果在，则放弃对被优化函数的优化，否则，生成相应的别名检查指令并将其插入到优化代码中。

上述技术方案中，在所述的步骤1)之前，还包括对所要优化的函数进行选择的步骤；在该步骤中，选择不存在调用关系的且执行时间相对较长的函数作为被优化的函数。

上述技术方案中，在所述的步骤2)中，采用下列方式中的一种选择被提升到寄存器的栈变量：随机选择、按照静态被访问次数的多少选择、按被访问次数多少选择。

上述技术方案中，在所述的步骤4)中，若被优化函数中存在用于调用其它函数的函数调用指令，则在被优化函数的代码中的所述函数调用指令前插入用于将栈顶指针切换到影子栈中的栈顶指针切换指令。

上述技术方案中，所述的步骤3)包括：

步骤31)、在被优化函数的入口后插入将被优化函数的函数栈从系统栈切换到映像栈的栈切换指令，并插入将与被优化函数有关的参数从系统栈拷贝到映像栈的指令；

步骤32)、在所述的栈切换指令后插入用于将所要提升的栈变量的内容取到相应寄存器的预取指令；

步骤33)、在所述的预取指令后插入用于将映像栈中的虚存页设为保护状态的置页保护代码状态代码。

上述技术方案中，所述的步骤4)包括：

步骤41)、将被优化函数的代码中所有包含对所提升栈变量操作的指令替换为对相应寄存器操作的指令；

步骤42)、将被优化函数的代码中所有对未提升的栈变量的操作替换为对影子栈上相应虚存地址的操作；

步骤43)、将优化后的代码保存在代码缓存中，并将优化函数的入口插入指令跳转到代码缓存中的优化代码；

步骤44)、在被优化函数中的函数调用指令前插入栈顶指针切换指令，以将栈顶指针切换到影子栈中。

上述技术方案中，其特征在于，所述的步骤5)包括：

步骤51)、在函数优化代码的出口处插入用于将映像栈中的虚存页解除保护状态的指令；

步骤52)、在所述解除虚拟页保护状态的指令后插入用于将被提升的栈变量的值从寄存器存回内存的同步指令；

步骤53)、在所述的同步指令后插入用于将函数栈帧从映像栈切换回系统栈中的栈切换指令。

上述技术方案中，在所述的步骤1)中，调用mmap(NULL，image_stack_size，PROT_READ|PROT_WRITE，MAP_ANON|MAP_SHARED，0，0)函数来申请映像栈。

上述技术方案中，在所述的步骤1)中，调用mremap(old_address，old_size，new_size，flags)函数来申请影子栈。

本发明的优点在于：

与现有技术通过对被优化函数中所有非显式访栈操作添加别名检查指令来优化 函数的方法相比，本发明可以高效地发现优化代码中所有的隐式访栈指令，降低栈变量提升优化的运行时开销。

附图说明

图1为包含栈变量的函数代码的示意图；

图2为本发明的包含栈变量函数的优化方法的流程图；

图3为被优化函数的函数栈关系示意图；

图4为函数代码在优化前后的比较图；

图5为对函数代码进行优化的方法的流程图；

图6为异常处理方法的流程图。

具体实施方式

下面结合附图和具体实施方式对本发明进行说明。

在对本发明予以说明前，首先对本发明中所涉及的概念做统一介绍。

页保护机制：在使用页式内存管理的操作系统中会对内存页面进行读写访问控制，有可读、可写、可执行三个属性。页保护机制就是利用设置不同页面访问属性来保护数据安全性及程序运行结果的正确性。

在对相关概念予以说明后，下面对本发明如何实现已有应用程序在新处理器上的优化做详细说明。

由于应用程序以函数为基本单元，因此在下文中将以函数的优化为例来说明应用程序的优化。

在一个应用程序中，一般包含多个函数，虽然在理论上可以对该应用程序中的所有函数都按照本发明的方法做优化，但由于本发明的优化方法是利用页保护机制来识别程序中与提升变量存在别名关系的访存操作，如果对所有函数都进行优化则会在程序运行时引起大量的异常，对程序性能产生很大影响，因此，作为一种优选实现方式，应当对被优化的函数加以选择。考虑到不同函数在做优化时所需要完成的操作、所要花费的时间大致相同，因此对执行时间较长的函数进行优化的效率相对更高。另外，如果对存在调用关系的两个函数同时进行优化，那么需要在优化代码中的函数调用点之前将提升变量的值从寄存器存回内存，函数调用后再从内存中将提升变量的值从内存预取到寄存器中，这样也会带来较大的运行时间开销。基于上述原因，在本实施例中可选择不存在调用关系的且执行时间相对较长的函数作为被优化的函数。

在选定被优化函数后，结合图2，并以其中一个被优化函数为例来说明其优化过程，对于应用程序中的其它被优化函数而言，它们的优化过程并没有实质区别。

本领域的普通技术人员都应当了解，系统栈(system stack)不允许将多个虚拟页映射到其申请的物理页上，所以在优化过程中首先申请一段物理内存空间用作被优化函数的栈帧，这段物理内存空间被称为映像栈(image stack)。对映像栈的申请可以采用现有技术实现，如在linux操作系统中，可以使用系统调用mmap(NULL，image_stack_size，PROT_READ|PROT_WRITE，MAP_ANON|MAP_SHARED，0，0)来申请这段物理内存空间。

在前面背景技术的描述中已经提到，当已有应用程序在新的处理器上运行时，由 于新的处理器较旧的处理器有更多的寄存器，因而可以将已有应用程序中的某些变量数据提升到寄存器中，以利用寄存器运行速度快的优点来提高程序的整体性能。但新的处理器较旧的处理器新增加的寄存器的数目有限，在大多数情况下函数中的栈变量会多于可使用的寄存器的数量，也就是说，在通常情况下被优化后的函数中仍然会有未被提升到寄存器中的栈变量。在下面的说明中将会提到，被优化后的函数在程序运行时会被保存在映像栈中，而映像栈中含有被提升栈变量的虚存页处于被保护状态，所有对这些被保护的虚拟页的访问都会引发异常。因此，如果不对被优化函数中那些未被提升的栈变量做处理，那么在运行时对保存在被保护虚拟页中的未被提升栈变量的访问将会产生大量的异常，这会对程序性能产生很大影响。针对上述问题，本发明采用了将多个虚拟页映射到同一个物理页的方法。具体的说，首先申请一段虚拟内存空间，然后将这段虚拟内存空间映射到与所述映像栈相同的物理内存，该段虚拟内存空间可被称为影子栈(shadow stack)。对虚拟内存空间的申请可以通过现有技术实现，如在linux操作系统上可通过系统调用mremap(old_address，old_size，new_size，flags)来申请这段虚存空间，其中old_size＝0。在后续的代码生成过程中，被优化函数中所有对未被提升的栈变量的访问都会被重定向到影子栈中，这样程序中所有显式的访栈操作就不会在运行过程中引起额外的访存异常，从而降低了优化系统的运行时开销。

在为被优化函数创建映像栈、影子栈后，结合系统中原有的系统栈，形成了一个有层次的栈间关系。如图3所示，被优化函数的调用函数(即调用被优化函数的函数)的栈帧在系统栈上，被优化函数的运行时栈帧在映像栈上，被优化函数所调用的函数的栈帧在影子栈上。在优化代码执行过程中，被优化函数的栈帧中包含提升变量的虚存页是处于保护状态的。

上述映像栈、影子栈的创建都是为函数优化的实现做准备，下面就可以对如何在被优化函数中选择栈变量以及如何生成该被优化函数的优化代码的过程加以说明。

在前面的说明中已经提到，在大多数情况下函数中的栈变量会多于可使用的寄存器的数量，因此需要对被优化函数中的栈变量加以选择。对被优化函数中的栈变量的选择方式可以有多种，如随机选取要提升的栈变量，或按照静态被访问次数的多少选择栈变量(即对这个栈变量进行访问的指令的静态数量)，或将被访问次数多的栈变量优先被提升到寄存器中。当然，在选择栈变量之前，还要从函数中识别出所有的栈变量，这一识别过程的实现为本领域技术人员所公知，因此不在此处做重复说明。

在选定要被提升到寄存器中的栈变量以后，根据所选择的栈变量生成优化代码。结合图4和图5，对优化代码的生成过程予以说明。

从图4的左半部分可以看出，一个函数可以被分为函数入口、函数代码、函数出口三个部分。所述的生成优化代码主要是对其中的函数代码部分加以改变，但在对函数中的代码做优化之前首先要插入指令，以将被优化函数的函数栈从系统栈切换到映像栈，并插入指令将与函数有关的参数从系统栈拷贝到映像栈(图5中的步骤101)。从图4的右半部分可以看出，函数入口之后新插入有栈切换代码1。接着，在优化代码入口插入预取指令，该指令用于将要提升的栈变量的内容取到相应的寄存器中(步骤102)。在图4的右半部分中，预取指令位于栈切换代码1之后、置页保护状态代码和优化代码之前，而在图1中也给出了预取指令的范例。再接着，还要在优化代码的入口处插入用于将映像栈中的虚存页设为保 护状态的代码，即前面所提到的置页保护代码状态代码(步骤103)，如插入调用mprotect的函数，使得映像栈中包含被提升栈变量的虚存页的保护状态被设为PROT_NONE。在PROT_NONE状态下，虚存页既不能被写也不能够被读，使得在程序执行过程中如果有对所保护虚存页的访问，系统将产生异常。在图4右半部分中，用于将虚存页设为保护状态的代码位于预取指令之后。完成上述操作后就要对函数代码加以优化。对函数代码的优化包括：将所有包含对所提升栈变量操作的指令替换为对相应寄存器操作的指令(步骤104)；将所有对未提升的栈变量的操作替换为对影子栈上相应虚存地址的操作(步骤105)。优化后的代码可以被保存在代码缓存(code cache)中，并将优化函数的入口插入指令跳转到code cache中的优化代码，这样当程序执行到被优化函数时将运行优化代码(步骤106)。在被优化函数的代码中存在函数调用的情况，因此，如果优化代码中有函数调用指令，那么在这些函数调用指令之前要插入栈顶指针切换指令，以将栈顶指针(esp或sp)切换到影子栈中(步骤107)。通过这一操作，被调用函数的栈帧将在影子栈上。所插入的栈顶指针切换指令位于函数调用指令之前、参数传递指令之后，因此，如果在被调用函数中通过指针参数来访问映像栈中被保护的页，则会引起访问越权异常。由于在函数代码被优化之前，进行了诸如插入栈切换指令、插入设定虚存页保护状态指令、插入预取指令等一系列的准备操作，因此在函数代码优化完成以后，还要做一系列的“善后”操作，以消除前述准备操作所带来的影响。如图4所示，首先，在函数优化代码的出口处插入用于将映像栈中的虚存页解除保护状态的指令(步骤108)，如调用mprotect函数，以将被保护的映像栈中的虚存页由保护状态转换为原来的可写/可读的状态。然后，在优化代码出口处插入同步指令，以将被提升的栈变量的值从寄存器存回内存中(步骤109)。图1中给出了同步指令的一个范例。最后，在函数出口再次插入栈切换指令，此处的栈切换指令用于将函数栈帧从映像栈切换回系统栈中(步骤110)。

本发明除了要将函数中的栈变量提升到寄存器以实现优化外，还要对优化代码执行过程中所产生的异常按情况分别处理。

在优化代码执行过程中发生异常后，操作系统会自动保存异常现场上下文，然后由在系统中注册的访存异常处理函数进行异常处理。在处理过程中，包括多种情况，下面结合图6予以说明。

首先，从操作系统保存的异常现场上下文可以得到发生越权访问的指令地址及其访存地址(步骤201)。然后分情况加以讨论。

如果发生异常的访存地址不是在映像栈中被保护的虚存页中，那么异常不是由本发明的优化引起的，在这种情况下，不对该异常做额外的处理，将由系统中默认的异常处理程序处理该异常(步骤202)。

如果发生异常的指令在被优化函数所调用的函数中，那么此次优化会被放弃。在这种情况下，在异常处理函数中会将提升的变量的值从寄存器存回内存，解除对映像栈中虚存页的保护状态，删除在原代码中插入的指令(步骤203)。

如果发生异常的指令在优化代码中，并且访存地址在被保护的页中，则要根据访存地址具体所在的位置生成内存别名检查指令并将其插入到优化代码中，或者放弃优化(步骤204)。具体的说，首先将包含提升变量的地址范围划分为两个部分。一个区域包含了所有的提升变量，另外一个不含任何提升的变量。这样，在运行时只需要简单地检查发生异 常指令的访存地址是否在包含提升变量的地址范围内。如果异常发生在不含提升变量的地址范围内，生成相应的别名检查指令并将其插入到优化代码中。如果异常发生在包含提升变量的地址范围内，那么放弃对当前函数所进行的优化，即要将提升变量的值从寄存器存回内存，解除对映像栈中虚存页的保护状态，删除在原代码中插入的指令，然后返回到原代码中与发生异常的指令相对应的指令。上述操作中所提到的别名检查指令的主要功能是在运行时(执行到发生异常指令的时候)判断该指令的访存地址是否在第一个地址范围内，如果在，则执行修改后的代码(通过影子栈来访问已被保护的地址)，否则执行未修改的代码。如果执行未修改的代码时发生异常(说明该指令可能访问了含有被提升的栈变量的地址范围)，该次异常将由异常处理函数再次处理。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。