CN106406972B - 程序编译方法和编译器 - Google Patents

Abstract

本发明涉及一种程序编译方法和编译器，该方法包括读取待编译的程序并记录每条内存访问指令的基地址及偏移地址；将基地址相同的内存访问指令分为一个大类；将各大类中偏移地址最小的指令的内存地址作为该大类中所有指令的新的基地址；根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小；若是，则修改待编译的程序的代码，将这些大类中的每条指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。本发明通过将基地址相同的指令归为一个集合后，重新选择该集合中的指令的基地址，使得内存访问指令的偏移减少，从而缩减内存访问指令的尺寸，进而减少了总的程序的尺寸。

Description

程序编译方法和编译器

技术领域

本发明涉及计算机领域，特别是涉及一种程序编译方法和编译器。

背景技术

目前，按照统计显示，程序中使用最多的一类指令就是内存访问的指令。在待编译的程序，比如C源代码中，对于一个结构体的访问通常会被编译器翻译为对应的内存访问指令。不同的架构指令集的内存访问指令一般都属于以下两种的类型：第一种是通过一个寄存器(即，基地址寄存器)加上一个常量偏移地址访问一块内存地址的内容，第二种是通过一个寄存器(即，基地址寄存器)加上另外一个寄存器(即，偏移寄存器)的地址访问一块内存地址的内容。例如，在AArch64架构指令集中，ldr w8,[x1,#4]，属于第一类的内存访问指令，表示把寄存器x1的内容加上常数4，把得到的结果作为内存地址，并将该地址的内容读入到寄存器w8中；而ldr w8,[x1,x2]，则属于第二类的内存访问指令，表示将寄存器x1的内容加上寄存器x2的内容，得到的结果作为内存地址，并将该地址的内容读入到寄存器w8中。在PI32-V2架构指令集中，也有类似的第一类指令，如r8＝[r1+4]，表示r8的寄存器是基地址r1加上4的内容；第二类指令，如r8＝[r1+r2]，表示r8的寄存器是基地址r1加上偏移寄存器r2。

由于每条指令需要一定长度的编码，而这个编码是有限的，所以通常而言，第一类内存访问指令的常数偏移范围是有限制的，例如AArch64中，第一类指令的偏移范围是-128×4到128×4。如果我们需要访问的偏移地址比限定的范围要大，我们只能首先利用一条移动常数的指令，把偏移移动到一个寄存器中，然后再通过第二条指令来访问。这一多余的步骤会使得代码尺寸变大。另外一方面，一些指令集中，如PI32-V2中，第一类指令会有两种不同的编码形式，一种是短编码形式，只能编码更短的偏移范围，另外一种是长编码形式，可以编码更长一些的偏移范围。如果一个程序中生成了更多的长编码形式的第一类指令，也会使得最终的代码尺寸变大。

传统的编译技术中，对于结构体访问，通常会生成上述的内存访问指令，例如，对于C源代码中的f.a＝10；f.b＝10；假设f的地址储存在r0，域a的偏移是80，域b的偏移是84，则对于PI32-V2指令集，这条赋值会翻译三条汇编指令为：r1＝10；[r0+80]＝r1；[r0+84]＝r1；这里生成的指令是第一类中的长编码形式的指令。在实际程序中，这样的赋值语句往往比较多，且会比较集中，这样传统的方法会生成比较多的长编码形式的指令，使得代码尺寸较大。

发明内容

基于此，有必要提供一种程序编译方法和编译器，可以减少内存访问指令的编码尺寸。

一种程序编译方法，所述方法包括：

读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址，所述内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址；

将基地址相同的所述内存访问指令分为一个大类；

将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址；

根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小；若存在总代码长度变小的大类，则修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

在其中一个实施例中，所述将基地址相同的所述内存访问指令分为一个大类的步骤，还包括将各大类中的所述内存访问指令按偏移地址从小到大进行排序。

在其中一个实施例中，所述将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址的步骤之后，还包括将各大类中的所述指令进一步分组的步骤；

将一个大类中的所述指令进一步分组的步骤包括：

步骤A，按照偏移地址从小到大查看该大类中的所述指令，并将以所述新的基地址为基地址时、指令的编码长度是最短编码长度的所述指令加入到以所述新的基地址为基地址的组中；

步骤B，当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组；

重复步骤A、B直到将该大类中的所有指令分组完毕。

在其中一个实施例中，所述步骤B是：

当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则

尝试在保证当前组的指令的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令的偏移地址达到最短编码长度，并将增大后的基地址作为当前组的新的基地址；

若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。

在其中一个实施例中，所述修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序的步骤，具体为：

将每一大类的修改基地址的指令插入至所述目标程序的目标位置处；其中，所述目标位置为使得每一大类的修改基地址的指令在该大类中所有所述指令之前被执行的位置；

将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址。

在其中一个实施例中，所述读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址的步骤，具体为：

读取待编译的程序，并将所述待编译的程序划分成若干函数；

记录每一函数中每条内存访问指令的基地址以及偏移地址。

一种程序编译器，所述编译器包括：

程序加载模块，该程序加载模块用于读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址；所述内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址；

基地址变换模块，该基地址变换模块的输入端与所述程序加载模块的输出端相连接，该基地址变换模块用于将基地址相同的所述内存访问指令分为一个大类，且将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址；

编码长度计算模块，该编码长度计算模块的输入端与基地址变换模块的输出端相连接，该编码长度计算模块用于根据各大类的新的基地址计算各大类使用新的基地址后，该大类的内存访问指令的总代码长度；

代价判断模块，该代价判断模块的输入端与所述编码长度计算模块的输出端相连接，该代价判断模块用于根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小；

目标程序生成模块，该目标程序生成模块的输入端与所述代价判断模块的输出端相连接，该目标程序生成模块用于在存在总代码长度变小的大类，则修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

在其中一个实施例中，还包括：

排序模块，该排序模块的输入端与所述基地址变换模块的输出端相连接，该排序模块的输出端与所述编码长度计算模块的输入端相连接，该排序模块用于将各大类中的所述内存访问指令按偏移地址从小到大进行排序。

在其中一个实施例中，所述基地址变换模块包括：

分组控制单元，该分组控制单元的输入端与所述排序模块的输出端相连接，该分组控制单元用于判断该大类中的所有指令是否分组完毕；

第一分组单元，该第一分组单元的输入端与分组控制单元的输出端相连接，该第一分组单元用于在该大类中的所有指令未分组完毕时，按照偏移地址从小到大查看该大类中的所述指令，并将以所述新的基地址为基地址时、指令的编码长度是最短编码长度的所述指令加入到以所述新的基地址为基地址的组中；

第二分组单元，该第二分组单元的输入端与所述第一分组单元的输出端相连接，该第二分组单元用于在查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组。

在其中一个实施例中，所述第二分组单元包括：

编码长度判断子单元，该编码长度判断子单元的输入端与所述第一分组单元的输出端相连接，该编码长度判断单元用于查看是否存在以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令；

分组子单元，该分组子单元的输入端与该编码长度判断子单元的输出端相连接，该分组子单元用于当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则尝试在保证当前组的偏移地址的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令的偏移地址达到最短编码长度，并将增大后的基地址作为当前组的新的基地址，若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。

在其中一个实施例中，所述目标程序生成模块还用于将每一大类的修改基地址的指令插入至所述目标程序的目标位置处；其中，所述目标位置为使得每一大类的修改基地址的指令在该大类中所有所述指令之前被执行的位置。

在其中一个实施例中，所述程序加载模块包括：

程序读取单元，用于读取待编译的程序；

程序划分单元，该程序划分单元的输入端与该程序读取单元的输出端相连接，该程序划分单元用于将所述待编译的程序划分成若干函数；

记录单元，该记录单元的输入端与所述程序划分单元的输出端相连接，该记录单元用于记录每一函数中每条内存访问指令的基地址以及偏移地址。

上述的程序编译方法和编译器，通过将基地址相同的指令归为一个集合后，重新选择该集合中的指令的基地址，使得内存访问指令的偏移减少，从而缩减内存访问指令的尺寸，进而减少了总的程序的尺寸，应用范围较为广泛。

附图说明

图1为一实施例中计算机程序的编译流程；

图2为一实施例中程序编译方法的流程图；

图3为一实施例中程序编译器的结构示意图。

其中，

100 程序加载模块

110 程序读取单元

120 程序划分单元

130 记录单元

200 基地址变换模块

210 第一分组单元

220 第二分组单元

230 分组控制单元

221 编码长度判断子单元

222 分组子单元

300 编码长度计算模块

400 代价判断模块

500 目标程序生成模块

600 排序模块

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用于解释本发明，并不用于限定本发明。

在详细说明根据本发明的实施例前，应该注意到的是，所述的实施例主要在于与程序编译方法和编译器相关的步骤和系统组件的组合。因此，所属系统组件和方法步骤已经在附图中通过常规符号在适当的位置表示出来了，并且只示出了与理解本发明的实施例有关的细节，以免因对于得益于本发明的本领域普通技术人员而言显而易见的那些细节模糊了本发明的公开内容。

在本文中，诸如左和右，上和下，前和后，第一和第二之类的关系术语仅仅用来区分一个实体或动作与另一个实体或动作，而不一定要求或暗示这种实体或动作之间的任何实际的这种关系或顺序。术语“包括”、“包含”或任何其他变体旨在涵盖非排他性的包含，由此使得包括一系列要素的过程、方法、物品或者设备不仅包含这些要素，而且还包含没有明确列出的其他要素，或者为这种过程、方法、物品或者设备所固有的要素。

请参阅图1所示，图1为一实施例中计算机程序的编译流程，在该实施例中，待编译的程序经过前端分析得到中间表示，中间表示经过若干次的中端优化后，得到最终的中间表示，最后对该中间表示进行代码生成，得到最后的目标程序。本发明中的编译方法可以是整个图1中所示的编译流程，也可以仅仅是其中将一个中间表示转换成另一个中间表示的过程。在本实施例以及后文中以一段C源代码作为例子以说明该实施例以及该发明。假设源程序为：

在经过上述的前端分析和若干次中端优化后，假设在进行本发明的方法前，上述源程序被翻译为PI32-V2指令后的中间表示为：

foobar:

v1＝r1

v0＝r0

v2＝[v0+256]

v3＝[v1+256]

v4＝v3+v2

v5＝[v0+260]

v6＝v4+v5

v7＝[v1+260]

v8＝v6+v7

v9＝[v0+264]

v10＝v8+v9

v11＝[v1+264]

v12＝v10+v11

v13＝[v1+268]

v14＝v13<<1

v15＝v12+v14

r0＝v15

Rts

此时还未进行寄存器的分配，其中r0、r1表示物理寄存器，r0是第一个参数，r1是第二个参数，v0，v1，……，v15是虚拟寄存器，此时只有一个foobar函数，因此待编译的程序只有该foobar函数。本发明中的编译方法主要是通过收集一段程序(例如，一个函数体内)的内存访问指令，然后选择恰当的基地址，并在恰当的位置插入新的基地址计算指令，使得内存访问指令的偏移可以减少，最终达到缩减总的代码尺寸的目的。

请参阅图2所示，图2为一实施例中程序编译方法的流程图，在该实施例中，该方法可以包括：

S202：读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址。可以看出内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址，在该实施例中，首先要逐条检查函数体的指令，而后可以得到内存访问指令及其大致情况。例如在上述的实施例中，内存访问指令有：

v2＝[v0+256]

v3＝[v1+256]

v5＝[v0+260]

v7＝[v1+260]

v9＝[v0+264]

v11＝[v1+264]

v13＝[v1+268]

在其中一个实施例中，读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址的步骤，可以包括读取待编译的程序，并将待编译的程序划分成若干函数。记录每一函数中每条内存访问指令的基地址以及偏移地址。在本实施例中，可以以函数为基本单位，即该方法中每次只考虑一个函数范围内的内存访问指令，且该方法在执行寄存器分配前进行。一般在编译器内部，一个函数被标识为一些基本块的集合，一个基本块被表示为一系列的指令。

S204：将基地址相同的内存访问指令分为一个大类。在该实施例中，以基地址寄存器作为大类的划分依据，因此将基地址相同的内存访问指令分为一大类。例如在上述的实施例中包括两个大类：

第一大类，以v0为原始的基地址：

v2＝[v0+256]

v5＝[v0+260]

v9＝[v0+264]

第二大类，以v1为原始的基地址：

v3＝[v1+256]

v7＝[v1+260]

v11＝[v1+264]

v13＝[v1+268]

S206：将各大类中偏移地址最小的指令的内存地址作为该大类中所有指令的新的基地址。例如上述实施例中，偏移地址最小为256，因此以该偏移地址最小的指令的内存地址为该组中所有指令的新的基地址，即第一大类中，以v2＝[v0+256]为新的基地址的指令包含：

v2＝[v0+256]该指令的新的偏移地址为+0。

v5＝[v0+260]该指令的新的偏移地址为+4。

v9＝[v0+264]该指令的新的偏移地址为+8。

第二大类中，以v3＝[v1+256]为新的基地址的指令包含：

v3＝[v1+256]该指令的新的偏移地址为0。

v7＝[v1+260]该指令的新的偏移地址为+4。

v11＝[v1+264]该指令的新的偏移地址为+8。

v13＝[v1+268]该指令的新的偏移地址为+12。

S208：根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小。

S210：若存在总代码长度变小的大类，则修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

具体地，在上述的例子中，第一大类中的指令，需要增加一条修改基地址的指令：

v16＝v0+256增加了该条加法指令，以修改该第一大类中的所有指令的基地址，该指令为一条长编码指令，代价是4字节。

且在该例子中，第一大类中的内存访问指令相应地修改为：

v2＝[v16+0]该条指令相比于原来的指令v2＝[v0+256]减少2字节。

v5＝[v16+4]该条指令相比于原来的指令v5＝[v0+260]减少2字节。

v9＝[v16+8]该条指令相比于原来的指令v9＝[v0+264]减少2字节。

因此综上分析，在第一大类中的指令经过编译后可以减少2字节的代码空间。

即将上述实施例中的基地址从v0修改为v0+256处需要一条加法指令，或者需要额外的4字节的代价，但同时能够把该第一大组中的其他三条指令的代价每条减少2个字节，所以这是有利可图的。

同理可以得出第二大类中的指令可以减少4字节的代码空间：

v17＝v1+256增加了该条加法指令，以修改该第一大类中的所有指令的基地址，该指令为一条长编码指令，代价是4字节。

且在该例子中，第二大类中的指令：

v3＝[v17+0]该条指令相比于原来的指令v3＝[v1+256]减少2字节。

v7＝[v17+4]该条指令相比于原来的指令v7＝[v1+260]减少2字节。

v11＝[v17+8]该条指令相比于原来的指令v11＝[v1+264]减少2字节。

v13＝[v17+12]该条指令相比于原来的指令v13＝[v1+268]减少2字节。

上述的程序编译方法，通过将基地址相同的指令归为一个集合后，重新选择该集合中的指令的基地址，使得内存访问指令的偏移减少，从而缩减内存访问指令的尺寸，进而减少了总的程序的尺寸，应用范围较为广泛。

在其中一个实施例中，将基地址相同的内存访问指令分为一个大类的步骤，即上述步骤S204，还可以包括将各大类中的内存访问指令按照偏移地址从小到大进行排序。例如上述第一大类中的三个指令可以按照其偏移地址256、260、264的顺序进行排序，即v2＝[v0+256]、v5＝[v0+260]、v9＝[v0+264]。同理也可以对第二大类中的指令进行排序，且排序的方式可以是按照偏移地址从小到大排列，也可以是按照偏移地址从大到小进行排列，在此不再赘述。

在其中一个实施例中将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址的步骤之后，即步骤S206之后还可以包括将各大类中的指令进一步分组的步骤。

在其中一个实施例中，根据将各大类中的指令进一步分组的步骤，具体为：

步骤A，按照偏移地址从小到大查看该大类中的指令，并将以新的基地址为基地址时、指令的编码长度是最短编码长度的指令加入到以新的基地址为基地址的组中。

例如，可以参阅上述实施例，对于第一大类中，首先按照偏移地址进行排序，选取最小偏移地址所对应的指令的地址为新的基地址，即偏移为256处，对于该第一大类中，包含的指令有：

v2＝[v0+256]该指令的新的偏移地址为+0。

v5＝[v0+260]该指令的新的偏移地址为+4。

v9＝[v0+264]该指令的新的偏移地址为+8。

可以看出上述指令只需要短编码形式的指令即可实现，因此不需要再继续分组。

步骤B，当查看到以新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组。

例如，假设在第一大类中存在一个在采用新的基地址时、需要以长编码形式进行编码的内存访问指令，则以该指令的内存地址作为新的基地址创建一新的组。

重复步骤A、B直到将该大类中的所有指令分组完毕。

在其中一个实施例中，上述的步骤B可以包括：

当查看到以新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则尝试在保证当前组的指令的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令达到最短编码长度，并将增大后的基地址作为当前组的新的基地址。若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。例如，假设在第一大类中存在一个在采用新的基地址时、需要以长编码形式进行编码的内存访问指令A，则首先尝试修改该新的基地址，在第一大类中，新的基地址为v2＝[v0+256]，可以尝试修改该新的基地址为v5＝[v0+260]，则指令v2＝[v0+256]在基地址为v5＝[v0+260]的情况下的新的偏移地址为-4，指令v9＝[v0+264]在基地址为v5＝[v0+260]的情况下的新的偏移地址为+4，同理计算指令A的新的偏移地址，如果该指令A在基地址为v5＝[v0+260]的情况下的编码长度为最短编码长度，则修改基地址v2＝[v0+256]为v5＝[v0+260]，如果不存在这样一个基地址，则可以以该指令的内存地址作为新的基地址创建一个新的组，例如以指令A的内存地址为新的基地址，或者继续尝试其他的基地址，例如以v9＝[v0+264]为基地址等。

在其中一个实施例中，修改待编译的程序的代码，将这些大类中的每条指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序的步骤，具体可以为：将每一大类的修改基地址的指令插入至目标程序的目标位置处；其中，目标位置为使得每一大类的修改基地址的指令在该大类中所有指令之前被执行的位置。将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址。例如，从上述实施例中，函数foobar的执行可以看出，插入新的基地址的指令的目标位置处时在v0＝r0之后，该位置能够保证变换基地址的指令在其他的内存访问指令被执行之前而被执行，因此经过上述的编译后，待编译的程序最终转换为：

foobar:

v1＝r1

v0＝r0

v16＝v0+256

v17＝v1+256

v2＝[v16+0]

v3＝[v17+0]

v4＝v3+v2

v5＝[v16+4]

v6＝v4+v5

v7＝[v17+4]

v8＝v6+v7

v9＝[v16+8]

v10＝v8+v9

v11＝[v17+8]

v12＝v10+v11

v13＝[v17+12]

v14＝v13<<1

v15＝v12+v14

r0＝v15

rts

经过上述分析可以看出，该目标程序相较于原待编译的程序减少了6个字节的代码尺寸空间，且经过试验，以编译Linux 3.10内核到PI32-V2指令集为例，使用本发明中的方法比起传统的编译方法能够减少大概2％的代码尺寸。

请参阅图3所示，图3为一实施例中程序编译器的结构示意图，在该实施例中，编译器可以包括程序加载模块100、基地址变换模块200、编码长度计算模块300、代价判断模块400以及目标程序生成模块500，该基地址变换模块200的输入端与程序加载模块100的输出端相连接，该编码长度计算模块300的输入端与基地址变换模块200的输出端相连接，该代价判断模块400的输入端与编码长度计算模块300的输出端相连接，该目标程序生成模块500的输入端与代价判断模块400的输出端相连接。

其中，该程序加载模块100用于读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址；该内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址。

该基地址变换模块200用于将基地址相同的内存访问指令分为一个大类，且将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址。

该编码长度计算模块300用于根据各大类的新的基地址计算各大类使用新的基地址后，该大类的内存访问指令的总代码长度。

该代价判断模块400用于根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小。

该目标程序生成模块500用于在存在总代码长度变小的大类，则修改待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

在其中一个实施例中，该编译器还可以包括排序模块600，该排序模块600的输入端与基地址变换模块200的输出端相连接，该排序模块600的输出端与编码长度计算模块300的输入端相连接，该排序模块600用于将各大类中的内存访问指令按照偏移地址从小到大进行排序。

在其中一个实施例中，基地址变换模块200可以包括第一分组单元210、第二分组单元220和分组控制单元230，该分组控制单元230的输入端与排序模块600的输出端相连接，该第一分组单元210的输入端与分组控制单元230的输出端相连接，该第二分组单元220的输入端与第一分组单元210的输出端相连接。

其中，该分组控制单元230用于判断该大类中的所有指令是否分组完毕。

该第一分组单元210用于按照偏移地址从小到大查看该大类中的指令，并将以新的基地址为基地址时、指令的编码长度是最短编码长度的指令加入到以新的基地址为基地址的组中。

该第二分组单元220用于当查看到以新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组。

在其中一个实施例中，该第二分组单元220可以包括编码长度判断子单元221以及分组子单元222，该编码长度判断子单元221的输入端与第一分组单元210的输出端相连接，该分组子单元222的输入端与该编码长度判断子单元221的输出端相连接。

其中，该编码长度判断子单元221用于查看是否存在以新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令。

该分组子单元222用于当查看到以新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则尝试在保证当前组的偏移地址的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令的偏移地址达到最短编码长度，并将增大后的基地址作为当前组的新的基地址，若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。

在其中一个实施例中，该目标程序生成模块500还用于将每一大类的修改基地址的指令插入至目标程序的目标位置处；其中，目标位置为使得每一大类的修改基地址的指令在该大类中所有指令之前被执行的位置。

在其中一个实施例中，该程序加载模块100可以包括程序读取单元110、程序划分单元120和记录单元130，该程序划分单元120的输入端与程序读取单元110的输出端相连接，该记录单元130的输入端与程序划分单元120的输出端相连接。

其中，该程序读取单元110用于读取待编译的程序。该程序划分单元120用于将待编译的程序划分成若干函数。该记录单元130用于记录每一函数中每条内存访问指令的基地址以及偏移地址。

此处不再赘述关于编译器的实施例，具体可以参见上述编译方法中所述。

以上所述实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。

Claims (12)

1.一种程序编译方法，其特征在于，所述方法包括：

读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址，所述内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址；

将基地址相同的所述内存访问指令分为一个大类；

将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址；

根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小；若存在总代码长度变小的大类，则修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

2.根据权利要求1所述的程序编译方法，其特征在于，所述将基地址相同的所述内存访问指令分为一个大类的步骤，还包括将各大类中的所述内存访问指令按偏移地址从小到大进行排序。

3.根据权利要求2所述的程序编译方法，其特征在于，所述将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址的步骤之后，还包括将各大类中的所述指令进一步分组的步骤；

将一个大类中的所述指令进一步分组的步骤包括：

步骤A，按照偏移地址从小到大查看该大类中的所述指令，并将以所述新的基地址为基地址时、指令的编码长度是最短编码长度的所述指令加入到以所述新的基地址为基地址的组中；

步骤B，当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组；

重复步骤A、B直到将该大类中的所有指令分组完毕。

4.根据权利要求3所述的程序编译方法，其特征在于，所述步骤B是：

当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则

尝试在保证当前组的指令的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令的偏移地址达到最短编码长度，并将增大后的基地址作为当前组的新的基地址；

若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。

5.根据权利要求1所述的程序编译方法，其特征在于，所述修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序的步骤，具体为：

将每一大类的修改基地址的指令插入至所述目标程序的目标位置处；其中，所述目标位置为使得每一大类的修改基地址的指令在该大类中所有所述指令之前被执行的位置；

将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址。

6.根据权利要求1所述的程序编译方法，其特征在碍于，所述读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址的步骤，具体为：

读取待编译的程序，并将所述待编译的程序划分成若干函数；

记录每一函数中每条内存访问指令的基地址以及偏移地址。

7.一种程序编译器装置，其特征在于，所述编译器包括：

程序加载模块，该程序加载模块用于读取待编译的程序，并记录每条内存访问指令的基地址以及偏移地址；所述内存访问指令的内存地址等于该指令的基地址加上该指令的偏移地址；

基地址变换模块，该基地址变换模块的输入端与所述程序加载模块的输出端相连接，该基地址变换模块用于将基地址相同的所述内存访问指令分为一个大类，且将各大类中偏移地址最小的指令的内存地址作为该大类中所有所述指令的新的基地址；

编码长度计算模块，该编码长度计算模块的输入端与基地址变换模块的输出端相连接，该编码长度计算模块用于根据各大类的新的基地址计算各大类使用新的基地址后，该大类的内存访问指令的总代码长度；

代价判断模块，该代价判断模块的输入端与所述编码长度计算模块的输出端相连接，该代价判断模块用于根据各大类的新的基地址计算各大类使用新的基地址是否能使该大类的内存访问指令的总代码长度变小；

目标程序生成模块，该目标程序生成模块的输入端与所述代价判断模块的输出端相连接，该目标程序生成模块用于在存在总代码长度变小的大类，则修改所述待编译的程序的代码，将这些大类中的每条所述指令的基地址修改成新的基地址、偏移地址修改为新的偏移地址，以生成目标程序。

8.根据权利要求7所述的程序编译器装置，其特征在于，还包括：

排序模块，该排序模块的输入端与所述基地址变换模块的输出端相连接，该排序模块的输出端与所述编码长度计算模块的输入端相连接，该排序模块用于将各大类中的所述内存访问指令按偏移地址从小到大进行排序。

9.根据权利要求8所述的程序编译器装置，其特征在于，所述基地址变换模块包括：

分组控制单元，该分组控制单元的输入端与所述排序模块的输出端相连接，该分组控制单元用于判断该大类中的所有指令是否分组完毕；

第一分组单元，该第一分组单元的输入端与分组控制单元的输出端相连接，该第一分组单元用于在该大类中的所有指令未分组完毕时，按照偏移地址从小到大查看该大类中的所述指令，并将以所述新的基地址为基地址时、指令的编码长度是最短编码长度的所述指令加入到以所述新的基地址为基地址的组中；

第二分组单元，该第二分组单元的输入端与所述第一分组单元的输出端相连接，该第二分组单元用于在查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则以该指令的内存地址作为新的基地址创建一个新的组。

10.根据权利要求9所述的程序编译器装置，其特征在于，所述第二分组单元包括：

编码长度判断子单元，该编码长度判断子单元的输入端与所述第一分组单元的输出端相连接，该编码长度判断单元用于查看是否存在以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令；

分组子单元，该分组子单元的输入端与该编码长度判断子单元的输出端相连接，该分组子单元用于当查看到以所述新的基地址为基地址时、指令的编码长度不是最短编码长度的内存访问指令，则尝试在保证当前组的偏移地址的编码长度不变的前提下、将当前组的基地址增大以使当前查看到的内存访问指令的偏移地址达到最短编码长度，并将增大后的基地址作为当前组的新的基地址，若尝试不成功，则以该指令的内存地址作为新的基地址创建一个新的组。

11.根据权利要求7所述的程序编译器装置，其特征在于，所述目标程序生成模块还用于将每一大类的修改基地址的指令插入至所述目标程序的目标位置处；其中，所述目标位置为使得每一大类的修改基地址的指令在该大类中所有所述指令之前被执行的位置。

12.根据权利要求7所述的程序编译器装置，其特征在于，所述程序加载模块包括：

程序读取单元，用于读取待编译的程序；

程序划分单元，该程序划分单元的输入端与该程序读取单元的输出端相连接，该程序划分单元用于将所述待编译的程序划分成若干函数；

记录单元，该记录单元的输入端与所述程序划分单元的输出端相连接，该记录单元用于记录每一函数中每条内存访问指令的基地址以及偏移地址。