一种基于RISC处理器常量池布局分析与整合的Cache优化方法

摘要

本发明公开了一种基于RISC处理器常量池布局分析与整合的Cache优化方法。本发明提出的方法，实现对RISC处理器常量池的布局分析及整合优化，包括：以ELF文件作为输入，通过遍历所有访问常量池的LDR指令计算出对应常量的地址。并通过构建两个散列表来遍历所有的LDR指令，删除误判为LDR指令的常量，将所有地址连续的常量池整合起来，得到所有常量池的位置和大小。通过对发现的常量池进行重排序，将零散的小常量池尽可能合并为大的常量池，减少Cache填充过程中的无效数据，包括被装载到ICache中的常量数据以及被装载到DCache中的指令。从而降低Cache的缺失率，提升Cache性能。

说明书

技术领域

本发明涉及精简指令处理器的软件优化技术领域，特别是涉及一种基于RISC处理器常量池布局分析与整合的Cache优化方法。

背景技术

立即数在处理器的指令集中被广泛应用。不同的指令集对立即数有不同的处理方式。基于x86的处理器在编译时往往直接将立即数写在指令中。x86的指令足够复杂，可以实现寄存器到寄存器、立即数到寄存器、以及内存到寄存器的赋值。但是在RISC处理器中，没有这样复杂的指令。RISC指令大部分是32位或者16位。以32位ARM指令来说，只有12bits用于表述立即数。这显然只能表示很少一部分立即数，不能表示任意的32bits的立即数和地址。

为了表示任意长度的立即数，RISC处理器通常采用LDR指令加常量池的方法来装载立即数。在32位ARM的LDR指令当中，由于本来表示立即数的12bits指令位宽现在表示了该立即数相对于当前指令(LDR指令)PC的偏移量，因此常量池紧邻引用它的函数，在函数地址周围的1024个字以内，所处的位置在代码段(.text)。

虽然常量池解决了由于RISC的指令长度导致的立即数存放问题。但是对于具有Cache的RISC处理器，常量池的存在降低了Cache的性能。由于Cache是按照Cache行(CacheBlock)进行填充的，在代码执行的过程中，常量池中的常量会可能会被ICache缓存，同时在对常量寻址的过程中，常量池附近的代码也可能会被DCache缓存。显然，ICache中的常量和DCache中的代码是无用的，它们永远不可能被访问，却挤占了Cache的存储空间。这些无用却被缓存的数据会降低Cache的命中率，对RISC处理器的性能造成一定影响。

发明内容

有鉴于此，本发明的目的在于提供一种基于RISC处理器常量池布局分析与整合的Cache优化方法，用以解决背景技术中提及的技术问题。本发明面向常见RISC编译器输出的ELF格式文件，分析常量池的大小以及分布信息，通过对常量池进行重新排序，降低了RISC处理器运行程序时由于常量池的存在而导致Cache缺失率上升。

为了解决上述技术问题，本发明提出如下技术方案：

一种基于RISC处理器常量池布局分析与整合的Cache优化方法，该方法包括以下步骤：

步骤S1、采用相应的编译工具，以获取ELF格式的输出文件作为常量池布局分析方法的输入；

步骤S2、依据常量池的特点对常量池在程序中的布局进行分析，具体包括如下步骤：

步骤S201、将步骤S1中获得的ELF文件格式做输入，遍历ELF文件的代码段，根据LDR指令对常量寻址的格式，找到所有对常量寻址的LDR指令，得到LDR指令的地址和内容；

步骤S202、通过LDR指令的地址和内容，计算出对应常量的地址；

步骤S203、构建两个散列表，分别是Ldr2Literal和Literal2Ldr；前者通过LDR指令地址索引它引用的常量地址，后者通过常量地址索引引用它的LDR指令地址；

步骤S204、由步骤S201中得到的LDR指令，存在本身为常量却被误判成LDR指令的情况，遍历步骤S203构建的散列表，如果通过Ldr2Literal的索引值能够在Literal2Ldr中索引到对应的数据，那么该Ldr2Literal的索引值就是一个误判，删除所有误判的常量；

步骤S205、将所有地址连续的常量合并为一个常量池，遍历整个代码段得到所有常量池的位置和大小信息；

步骤S3、对常量池进行分类、重排序，并将被打乱的代码段的指令进行修复，最后生成优化后的二进制文件，具体包括如下步骤：

步骤S301、通过解析ELF文件中符号表，得到函数块的起始地址，按照函数块的起始地址，把常量池之间的代码区域，分割为独立的函数块；

步骤S302、根据独立函数块里LDR指令对常量的引用关系，建立函数块与经过步骤S205后得到的常量池的对应关系，并将合并后的常量池分为三种类型，具体为：

类别一、被低地址的函数块引用；

类别二、被高地址的函数块引用；

类别三、同时被低地址以及高地址的函数块引用；

步骤S303、通过双指针的方式，对函数块以及类型为类别一和类别二的常量池进行重排序，使得重排序后常量池的分布更加集中，并使重排序后的所有常量池都在引用它的函数块下方；

步骤S304、修改每一行因为打乱代码段而无效的指令，将修复后的内容写进二进制文件中，完成常量池的重排序。

进一步的，通过对编译后的ELF文件解析得到程序的独立函数块及其对应常量池的分布信息；在不改变引用关系的情况下，对函数块和常量池进行重排序，将地址分布离散的常量池进行合并。

进一步的，所述步骤S303具体包括：

步骤S3031、构建post指针和pre指针，其中，所述post指针指向接下来需要重新排序的函数块，所述pre指针指向第一个已经排序但是还未将其对应常量池排序的函数块；

步骤S3032、从pre指针指向的函数块到post指针指向的函数块之间的，如果函数块大小之和小于设定值，那么就将post指针指向的函数块排序，post指针自增，并且指向下一个未排序的函数块；

如果函数块大小之和大于设定值，那么就将pre指针指向的函数块到post指针指向的前一个函数块对应的常量池按照函数块的顺序排序，之后让pre指针指向post指针对应的函数块，post指针继续自增；

步骤S3033、循环执行步骤S3032直到完成最后一个函数块及其对应常量池的重排序。

本发明的有益效果是：

1、本发明可用于所有的RISC处理器，具有很高的适用性。

2、本发明通过对常量池的布局分析，可以直观的获得该常量池所处的位置以及大小信息。

3、本发明通过对常量池的整合以及布局优化，使得常量池的分布更加集中，降低了由于Cache缺失导致的缓存无效数据的次数，提高了Cache的命中率。

附图说明

图1是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的流程示意图。

图2是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的查找常量池的伪码图。

图3是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的删除错误指令的伪码图。

图4是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的通过LDR指令查找常量的示意图。

图5是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的散列表内容示意图。

图6是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的重排序的伪码图。

图7是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的常量池以及代码块重排序示意图。

图8是本发明提出一种基于RISC处理器常量池布局分析与整合的Cache优化方法的常量池以及代码块重定位示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例1

参见图1-图8，本实施提供一种基于RISC处理器常量池布局分析与整合的Cache优化方法，具体包括如下步骤：

步骤A：采用相应的编译工具，以获取ELF格式的输出文件作为常量池布局分析方法的输入。

步骤B：依据常量池的特点对常量池在程序中的布局进行分析，具体包括如下步骤：

步骤B1：将步骤A获得的ELF文件格式做输入，遍历ELF文件的代码段，根据LDR指令对常量寻址的格式，找到所有对常量寻址的LDR指令，得到LDR指令的地址和内容。

具体的说，以32位ARM指令为例，首先通过对ELF格式的文件进行解析，找到该文件的代码段(.text)，之后对代码段的数据按照地址从低到高的顺序进行遍历，如果当前的数据和0x0F7F0000按位与之后，得到的数据是0x051F0000，则可以认为当前是对常量池寻址的LDR指令。

步骤B2：通过LDR指令的地址和内容，计算出对应常量的地址。

具体的说，以32位ARM指令为例，如果LDR的地址为ldrOffset，LDR的内容为instruction，那么常量的地址literalOffset就为：literalOffset＝ldrOffset±instruction&0x00000FFF+8。LDR指令的低12位是对应常量的偏移量，通过instruction&0x00000FFF来获得该值。加8是因为指令流水的原因。

步骤B3：构建两个散列表(hashmap)，分别是Ldr2Literal和Literal2Ldr。前者通过LDR指令地址索引它引用的常量地址，后者通过常量地址索引引用它的LDR指令地址。

步骤B4：由步骤B1得到的LDR指令，存在本身为常量却被误判成LDR指令的情况。遍历步骤B3构建的散列表，如果通过Ldr2Literal的索引值(LDR指令地址)能够在Literal2Ldr中索引到对应的数据，那么该Ldr2Literal的索引值(LDR指令地址)就是一个误判，删除所有误判的常量。

步骤B5：将所有地址连续的常量合并为一个常量池，遍历整个代码段得到所有常量池的位置和大小信息。

步骤C：对常量池进行分类、重排序。并将被打乱的代码段的指令进行修复，最后生成优化后的二进制文件。具体包括如下步骤：

步骤C1：通过ELF文件中符号表的相关信息，找到所有的独立的函数块。

步骤C2：根据独立函数块里的LDR指令对常量的引用关系，建立函数块与经过步骤B5后得到的常量池的对应关系。并将合并后的常量池分为三种类型。

步骤C3：通过双指针的方式，对函数块以及常量池进行重排序，使得重排序后常量池的分布更加集中。

步骤C4：修改每一行因为打乱代码段而无效的指令。将修复后的内容写进二进制文件中，完成常量池的重排序。

具体的说，在本实施例中，ELF格式文件由SPECCPU2006在arm-linux-gcc编译下获得，并在Gem5的AtomicSimpleCPU模式下运行被测试程序。

具体的说，在本实施例中，在步骤B1中，通过步骤A所获得的ELF文件格式的输入，找到所有对常量池寻址的LDR指令，得到LDR指令的地址和内容。对应的伪码如图2所示。

更具体的说，首先通过对ELF格式的文件进行解析，找到该文件的代码段(.text)，将代码段作为图2伪码的输入。如伪码第四行所示，对代码段的数据按照地址从低到高的顺序进行遍历，判断是否为LDR指令，其中LdrFormat是LDR指令格式。以32位ARM指令为例，可将第四行的判断逻辑改写为Text[addr]&0x0F7F0000＝0x051F000。如果当前的数据同0x0F7F0000按位与之后，得到的结果是0x051F0000，则可以认为当前是对常量寻址的LDR指令。伪码第五行中，InstLength是指令的长度，OffsetLength是LDR指令中指向常量的地址偏移量的长度。假设InstLength为32，OffsetLength为12的情况下，即Text[addr]&0x00000FFF，表示取出地址的低12位作为常量的偏移量offset。伪码第六行判断该LDR指令对应常量的分布是位于LDR指令的上方还是下方。

具体的说，在本实施例中，在步骤B2中，图2伪码第九行为通过LDR指令的地址和内容，计算出对应常量的地址。如果LDR的地址为addr，常量池的偏移量为offset，那么常量的地址literalAddr就为：literalAddr＝addr+offset+InstPipeLength。加InstPipeLength是因为指令流水的原因。

如图4所示的代码段(.text)指令，地址位于0x8160的内容为“LDRR3,[PC,0X14]”的LDR指令引用的常量池就位于0x817C＝0x8160+0x14+8。对应图2伪码的第九行。

具体的说，在本实施例中，在步骤B3中，根据LDR指令的地址和相关常量的地址，构建两个散列表(hashmap)，分别是Ldr2Literal和Literal2Ldr，对应图2伪码的第十行和第十一行。前者通过LDR指令地址索引它引用的常量地址，后者通过常量地址索引引用它的LDR指令地址。

构建的两个散列表如图5所示。可以在Ldr2Literal表中通过LDR指令的地址0x8160找到引用的常量池地址0x817C，也可以在Literal2Ldr表中通过常量池地址0x817C找到对应的LDR指令的地址0x8160。Ldr2Literal以及Literal2Ldr这两个散列表里的数据互相对应。

具体的说，在本实施例中，在步骤B4中，遍历找到的所有常量，删除误判的常量。由于步骤B1通过遍历ELF文件代码段每一个字的方式查找LDR指令，这样会遍历到常量池的范围。遍历到一些非指令的常量，这些常量的内容是没有规律的。有可能出现恰好有一个常量，按照B1的方法被误认为是一条LDR指令，从而造成误判。因为Literal2Ldr的索引值是常量的地址，因此可以对所有得到的LDR指令地址进行一个遍历，如果LDR指令地址可以在Literal2Ldr中索引到数据，那么说明该LDR指令同时也被记录为一个常量，是一个误判。将Ldr2Literal以及Literal2Ldr中错误的映射删除。图3的伪码展示了这一过程。在第四行进行LDR指令是否被其他LDR指令引用的判断，在第五、六行进行了错误指令的删除。

具体的说，在本实施例中，在步骤C中，对常量池进行分类、重排序。并将被打乱的代码段的指令进行修复，最后生成优化后的二进制文件。

更具体的说，在本实施例中，步骤C具体包括如下步骤：

步骤C1：在建立函数块到常量池的对应关系之前，首先需要找到所有的独立的函数块。通过ELF文件中符号表的相关信息，得到函数块的起始地址。按照函数块的起始地址，把常量池之间的代码区域，分割为独立的函数块；

步骤C2：根据独立函数块里LDR指令对常量的引用关系，建立函数块与经过步骤B5后得到的常量池的对应关系。并将合并后的常量池分为三种类型。类别一：被低地址的函数块引用，类别二：被高地址的函数块引用，类别三：同时被低地址以及高地址的函数块引用。类型为类别一或类别二的常量池接下来将会进行重排序，由于类别三的常量池对应的函数块过长，所以在重排序时不对其进行处理；

步骤C3：尽最大可能地把函数块合并、常量池合并。因为只是打乱了原有代码段的结构顺序，所以代码段的位置和大小都没有发生变化。合并的规律如下：

规律1：如果每个函数块都有对应的常量池，合并后每一个代码区域的函数块的数量等于它们对应常量池的数量。

根据规律1，为了合并更多的常量池，让每一个常量区域的常量池的数量尽可能的多，就要让常量区域和代码区域尽可能远，代码区域尽可能的大。

规律2：函数块的长度总是大于等于其对应的常量池的长度。

规律2的推论：如果每个函数块都有对应的常量池，假设合并后的代码区域包含n个函数块C

该推论的证明：

D

由规律2：

SizeC

所以：

D

以32位ARM指令为例，由于LDR指令长度的原因，常量到引用它的LDR指令的距离有一个限制，这个限制是1024个字。由规律2的推论得出：在常量池的重定位中，对于每一个代码区域，只要第一个函数块(最低地址)和它对应的常量池之间的距离满足这个限制，那么该代码区域后面的所有函数块均也满足这个限制。

又根据规律1，应该让第一个(最低地址)函数块到其对应的常量池之间的距离尽可能的远，因此取最大值1024字，让第一个函数块的开头到该函数块对应的常量池的距离最大为1024字即可。

通过双指针的方式，对函数块以及常量池进行重排序，使得重排序后常量池的分布更加集中，并使重排序后的所有常量池都在引用它的函数块下方。对应的伪码如图6所示。第二行构建了两个指针，post指针指向接下来需要重新排序的函数块，pre指针指向第一个已经排序但是还未将其对应常量池排序的函数块。如果从pre指向的函数块到post指向的函数块大小之和sum小于MaxLength，对于32位的ARM指令来说MaxLength为2

将因为长度过长而分割的函数块称为特殊的函数块，这些函数块对应的常量池为类型三。因为这些函数块已经过长，所以我们不对它进行合并。

本实施例中，如图7所示。其中post指针指向下一个要写入的函数块5，pre指向已经写入但是对应的常量池未写入的函数块3。从pre指针指向的函数块3到post指针指向的函数块5之间的所有函数块求和，即函数块5的大小加上函数块4的大小加上函数块3的大小小于1024字，那么就将post指向的函数块5写入，post指针自增1，指向函数块6；如果函数块之和大于1024字，那么就将pre指向的函数块3到post指向的函数块的前一个函数块4对应的常量池3、4写入常量池，然后让pre和post均指向函数块5。

更具体的说，在本实施例中，在步骤C4中，由于步骤C3完全打乱了代码段的结构，每一行代码、每一个常量的地址都发生了变化，所以原先的跳转指令、对常量的寻址指令的目标地址等都是错误的目标地址。接下来的工作是要修改每一行因为打乱代码段而无效的指令。将修复后的内容写进二进制文件中，完成常量池的重定位。

由于重定位工作是基于每一个函数块和其对应的常量池的，它们内部的指令或常量的相对位置并没有发生变化。所以只需要计算每一个函数块从重定位前到重定位后的映射、每一个常量池从重定位前到重定位后的映射。得到这样的两个映射后，在计算具体的指令或常量的映射时，只需要得到该指令或常量所处的函数块或常量池，然后通过映射找到对应的重定位后的函数块或常量池的起始位置，再加上这个指令或常量在该函数块或常量池的偏移即可。

本实施例中，如图8所示。B指令的地址为AddressB0，目标跳转的地址为AddressT0。经过重排序之后，得到新的目标跳转的地址AddressT1，以及新的B指令的地址AddressB1。根据新的B指令地址和目标跳转地址之间的偏移量。更改B指令的内容。完成了该B指令以及常量池的重定位。

综上所述，本实施例提供的一种基于RISC处理器常量池布局分析与整合的Cache优化方法，相比现有技术，具有以下效益：

1、该优化方法可用于所有的RISC处理器，具有很高的适用性。

2、通过对常量池的布局分析，可以直观的获得该常量池所处的位置以及大小信息。

3、过对常量池的整合以及布局优化，使得常量池的分布更加集中，降低了由于Cache缺失导致的缓存无效数据的次数，提高了Cache的命中率。

本发明未详述之处，均为本领域技术人员的公知技术。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。