基于VLIW的机器相关优化编译技术研究.doc

基于VLIW的机器相关优化编译技术研究

摘要 VLIW体系结构性能的发挥在很大程度上依赖于其相应的编译器。编译优化主要包括两个方面：一方面是传统的编译器优化技术；另一方面是针对具体机器平台特定的优化技术。VLIW机器相关的编译优化技术应该针对具体的机器平台，基于超长指令字体系结构的特点，考虑如何充分利用机器提供的硬件资源，以达到软件（编译器）和硬件（CPU）的最大匹配，从而生成高效率高并行度的目标代码。本文从超长指令字的特点出发，探讨了在VLIW体系结构下与机器相关的编译优化的实现方案，同时提出了几点在具体进行与机器相关的优化编译时的优化思路。
关键词 VLIW 超长指令字 机器相关 优化编译 ILP 预测

Research on architecture-dependent compiler optimization technology
based on VLIW

Abstract The performance of VLIW architecture heavily depends on the quality of relevant compilers. The compiler optimization technology consists of two aspects: one is traditional optimization technology; the other is architecture-dependent optimization technology. Before implementing architecture-dependent optimization, we should adequately analyze the architecture characters of machine platform concerned, and consider how to make the best of the hardware resources. Software (compiler) and hardware (CPU) must match well to produce object codes with high efficiency and high ILP. After analyzing the general characters of VLIW architecture, this paper develops a design of architecture-dependent compiler optimization scheme based on VLIW, and brings forward some optimization points during the actual implementation.
Key words VLIW, architecture-dependent, compiler optimization, ILP, predication

引言
1983年美国教授JFisher[1]受水平微代码思想的启示，提出了VLIW（超长指令字）体系结构。VLIW由编译器将多个可以同时并行执行的操作排在一条超长指令字中，在一个指令周期内由CPU并行发射，以减少对存储器的访问。与传统结构相比，这种体系结构既可以提供较高的指令级并行度，同时又具有简单的硬件译码和控制逻辑。在近二十年内，从著名的FPS AP-120B，Multiflow、Cydrome Cydra 5发展到E2K，以及Intel公司推出的下一代处理器IA-64，使得VLIW成为继CISC、RISC后的又一重要的体系结构。
目前，国外针对VLIW结构的研究主要有Illinois大学可靠性与高性能计算中心研制的IMPACT系统、斯坦福大学研制的SUIF系统框架，俄罗斯开发的E2K芯片及其系统，以及Intel微处理器实验室研制的IA-64编译器等。我国在这方面的研究Page: 1

起步较晚，目前还没有相应的自主系统[2]。Page: 1
太绝对

VLIW体系结构性能的发挥在很大程度上依赖于其相应的编译器，这对编译器及其优化技术提出了新的需求。因此，如何针对具体VLIW机器平台的特点，研究相应的机器相关优化技术，在整个VLIW编译技术研究中占有重要地位，并对快速提高国产VLIW编译器性能有着重要的意义。

1． VLIW体系结构概述
VLIW体系结构是将水平微码和超标量处理这两种普遍采用的概念相结合的产物。
从指令系统上讲，VLIW指令系统的设计思想与水平微码类似。VLIW机器具有较长的机器指令字，机器指令字具有固定的格式（一种或者多种），每条指令字中包含着多个独立的字段，字段中的操作码被送往不同的功能部件。为了与通常的指令区别，我们称这种操作为算子（或者微操作）。通常，在编译过程需要将算子拚装成超长指令字，这是VLIW编译系统实现过程中的一个重要任务。
从结构上讲，VLIW与超标量的RISC机类似，机器内部提供多个可以并发的功能部件， 所有功能部件共享使用大型寄存器堆，CPU在一个时钟周期内可发射多条指令。与传统的RISC技术不同的是VLIW采用静态指令调度技术，它的流水线是非保护的，没有用于防止资源冲突和隐藏流水线延时的硬件的互锁机制，完全依赖编译器静态地分析程序中指令的依赖关系，来决定指令是否可以并行执行以及执行顺序，而超标量机是在指令运行时由硬件来进行并行检测和指令调度的。因此，VLIW并行性能的提高在很大程度上依赖于VLIW编译系统的实现，支持此结构的编译器应该在保证并行执行的操作不会超过机器提供的并行资源最大限度的前提下，尽可能的提高算子的并行度，这是系统实现的又一重要任务。

因此，综上所述，VLIW体系结构的特点主要是：
l 具有较长的机器指令字，一般为128位甚至上千位。机器指令字具有固定的格式，并且被划分成多个控制字段，每个字段可以直接独立的控制相应的功能部件。一条指令字可以填入多个独立的并行操作，为了与通常的机器区别，我们称这种操作为算子，把按照机器指令字格式将算子组成超长指令字的过程称为拼装[2]。超长指令字中的多个可并行执行的算子的调度和拼装是由编译器来完成的。
l 含有大量的数据通路和多个可以并行的运算部件，由于数据相关和资源相关性是通过编译器来进行处理，因此硬件本身具有较简单的控制逻辑[3]。
l 控制部件每个周期启动一条机器指令，但同时发射其中的一条或多条算子。其并发操作主要是在流水的执行阶段进行的。
l 用大量的全局共享寄存器，存储单元，寄存器堆来连接多个功能部件。

2． VLIW体系结构下机器相关编译优化的实现方案
编译优化的主要任务是使编译出来的代码能够以更快的速度、使用更少的空间进行运行。代码优化首先必须保持代码原有的语义，其次必须能够显著的提高程序运行的速度，最后优化过程应当具有一定的效率。优化主要包括两个方面：一方面是传统的编译器优化技术；另一方面是针对具体机器平台特定的优化技术。

传统的编译优化技术包括三个部分：控制流分析，数据流分析和转换。控制流和数据流分析是为转换做准备的。转换则是进行一定代码的变更、替代、移动和重组。代码优化的具体办法很多，通常包括：公共子表达式的删除，循环语句的优化，死代码的删除，代码移动，减少变量和重复等。这部分优化主要集中在中间代码上进行，而且一般与具体硬件平台无关。传统的优化技术国内外的研究已经很多，而且比较成熟，在现有的许多编译系统中也都有相关的实现。
机器相关的编译优化技术则应该针对具体的机器平台，基于超长指令字体系结构的特
点，考虑如何充分利用机器提供的硬件资源（通用寄存器，寄存器堆，冗余运算部件等），以达到软件（编译器）和硬件（CPU）的最大匹配结合，从而生成高效率高并行度的目标代码。
如上节所述，VLIW指令系统上最小的单位是算子（即超长指令字里各个字段对应的微
操作），由编译器把算子拼装起来完成通常汇编指令的功能。一条汇编指令既可以对应着单个的算子，也可以对应着多个算子。对于一些功能比较单一的运算类的汇编指令，一条汇编指令就对应着一个算子，只填入超长指令字的一个字段里；但是，对于功能比较复杂的指令，特别是一些系统指令，一条汇编指令就可以对应着多个算子，由多个算子联合起来完成这一条汇编指令的功能，当然这就需要填入超长指令字的多个字段里。

例如：最常用的PUSH REG 指令，就需要由下列三个算子联合起来完成
修改堆栈指针算子 || 写内存算子 || 数据来源选通算子
每个算子也就对应了在执行阶段具体发射时机器的最小执行单元。

编译器拼装起来放在一条超长指令字当中的多个算子，即可以联合起来实现我们通常
意义上的汇编指令，也可以互不相干，各自独立。因此，在VLIW编译系统里，如何通过优化来决定实现程序功能的最小数目算子集，以及如何将这最小数目的算子集最大可能的并行拼装在一条超长指令字当中以生成最小数目的机器指令，是与机器相关的编译优化工作的关键。
鉴于VLIW体系结构指令系统的这种特点， 这里给出一种优化方案来实现与机器相关
的编译优化工作。我们的优化方案从两个层次来展开。第一个层次是在汇编指令级，主要进行指令归并，常数传播，依赖和数据相关分析及消除，寄存器重命名等等优化的工作。上述这些具体优化的技术正是国内外现在研究的热点，可以根据机器平台的实际情况有选择的采用和实现。通过这一层的优化，可产生最精简的汇编程序，从而决定了最小数目的算子集合（微操作集合）。我们把经过这一层优化产生的汇编程序转换成算子形式的程序（这一转化必须要保证语义上的完全一致性），然后，再传递给第二个优化层次：算子级。这一层的优化工作主要是将上一层传递来的算子序列进行数据依赖及相关性分析，并做算子调度，从而进行优化拼装和重排，要充分利用超长指令字以及硬件的并行资源，尽最大可能的在一条超长指令字里填入多个算子，减少超长指令字当中无效的位数，以提高超长指令字的利用效率，从而生成最小数目的机器指令，同时还必须保证逻辑以及时序上的正确性。整个方案的流程图如图1：
总的来说，优化方案体现在时间和空间两个方面。在时间上，应该最大可能的减少目标代码的执行周期数，这是汇编指令层优化的重点。在空间上，应该最大可能的减少机器指令的条数，这是算子层优化的重点。当然，时间和空间总是交织在一起的，在两个层次的优化工作里必然都会涉及到。

C程序
汇编程序
指令级优化模块
AS汇编
翻译模块
AS算子
翻译模块
C compiler
汇编到算子转化模块
算子级优化模块
优化过的算子
助记符程序
算子
助记符程序
精简
汇编程序
不带机器相关优化选项
带机器相关优化选项
算子级调度，算子优化拼装，重排
指令归并，依赖及数据相关分析
常数传播
二进制
机器码文件

图1： VLIW体系结构下机器相关编译优化的实现方案

3． 在机器相关优化编译具体实施时的几点思路Page: 4
方法

目前，国内外具体针对于VLIW体系结构的优化编译技术研究大部分都集中在提高指令并行度（ILP）上，其基本出发点是利用硬件提供的各种并行资源，在一个周期内执行尽可能多的指令，从而提高程序运行效率。其中通常采用的优化技术有：循环优化，指令依赖检测及删除，指令调度，数据预读，分支检测与删除，寄存器及功能部件的分配策略等等。VLIW体系结构为采用上述先进的优化编译技术提供了可能，反过来说，只有采用这些先进的编译优化技术，才能充分发挥VLIW体系结构的高性能[5]。上述这些优化技术在实施的时候，都需要预先分析大量的汇编程序实例，以决定在具体实施时该如何操作，并检验该种优化技术对当前的机器平台是否能起到好的优化效果。本文在这里不对这些优化技术做具体探讨，我们只是从实际开发或者移植一个VLIW编译器的角度出发，针对与机器相关的优化，给出几点在做具体工作时值得考虑的优化思路。

3.1 最大可能的利用超长指令字的指令空间
1) 延迟机制
VLIW体系结构通常支持128位或者更多位数的指令字，还提供了相应的指令格式，编译器需要按照机器提供的机器指令格式来把指令（算子）进行合并拼装，以生成128位的机器代码。当不考虑优化，只考虑正确性时，编译器当然可以孤立的对汇编程序中每条指令按前后顺序依次生成只完成该指令功能的机器代码，这样避免了相关性的分析，可保证运行结果正确，但这显然没有体现VLIW结构的特点，造成了指令字极大的浪费。因此如何在拼装生成机器代码的过程当中充分利用超长指令字的位数资源，在优化工作中占有举足轻重的地位。
要想最大可能的利用超长指令字空间，其总的原则当然就是一条指令字中尽可能的多拼指令（算子）。VLIW通常是把在一个周期里可以并行执行的指令，即不存在依赖和相关性的指令，并排在一条超长指令字里，来同时发射，这种方式采用的最为广泛，它的好处是逻辑上简单易行，但是这种拼装方式导致了一个限制，就是即使当前的超长指令字还可以继续容纳其他的指令，但如果后继的指令由于相关性而都不能跟当前指令字中已经填入的指令并行执行时，编译器只能浪费掉相应的指令字空间。因此，为了能够更灵活的使用超长指令字的位数资源，我们除了前面提到的那种通常的并行拼装方式以外，还可以考虑支持延迟的拼装方式——其做法可以是在指令正常的编码里加入相应的延迟位，来表明该指令延迟执行的周期数。

例如：对于常用的双操作数运算指令，其编码为
指令功能控制域
操作数来源一选通域
操作数来源二选通域
如果支持延迟的拼装方式的话，如下：
指令功能控制域
操作数来源一选通域
操作数来源二选通域
延迟位（2位）
这样，当延迟位为00，表示该指令不延迟，01表示延迟1个周期执行，10表示延迟2
个周期执行，11表示延迟3个周期执行。
如果支持延迟的话，即使两条指令存在相关性，也可以同时放入一条超长指令字中，这样可以增加指令调度的灵活性，提高超长指令字的利用效率。当然，这种延迟的执行及拼装方式需要硬件译码的支持。
2) 指令字的控制粒度
超长指令字可控制的粒度会直接影响调度及优化的效果。一般来说，我们在汇编指令级采取各种优化技术，然后将指令并行排入超长指令字中，这时超长指令字控制的粒度较粗，更靠近高层的汇编指令。如本文前节所述，有些功能较复杂的指令在实现时，机器需要完成多个微操作，而这些微操作之间往往存在着相关性。如果超长指令字的控制粒度停留在指令级，功能复杂的指令所对应的多个微操作则必须看成一个整体，固定了必须要由同一条超长指令字来进行发射。当这种功能复杂的指令连续出现多条，而且彼此又有相关性时，超长指令字控制的粒度还停留在指令级就会大大限制我们的调度和优化的效果。事实上，对于VLIW体系结构，超长指令字控制的粒度越细，越靠近机器的功能部件，调度及优化的效果越好。同时，我们还应该打破一条汇编指令对应的微操作必须排在同一条超长指令字当中，由同一条超长指令字发射的思路，在把指令分拆成算子（微操作）之后，只考虑算子在执行上的逻辑性和时序性，将其最大限度的填入超长指令字当中，而不必拘泥于汇编指令和超长指令字之间的一一对应关系。

事实上，随着VLIW体系结构继续发展，有可能超长指令字的粒度会进一步细到电路微观的层次上，由超长指令字直接对部件的控制逻辑进行编码，这样一来硬件中指令编码的译码器数量会大大减少。硬件则完全开放给软件，软件和硬件的结合更为紧密，当然也会导致超长指令字的位数大大增加。

3.2 汇编指令级部件不可见
VLIW体系结构通常同时提供多个可同时发射的功能相同的运算部件，通过运算部件
的冗余，可以在同一时刻并行的完成某些功能，从而提高程序的运行效率。因此相应的在汇编手册中，可能会提供多套汇编指令来完成同样的功能。例如，如果硬件提供两个浮点运算部件，那么可能在汇编手册中就有两条指令FSADD和FSADD2，分别对应这两个浮点运算部件，都来完成浮点加法运算，在同一时刻可以完成两个浮点加法运算。

但是，大多数编译器在进行从高级程序到汇编程序的翻译时，是很难实现这一想法的。
事实上编译器在生成汇编程序的时候，无法决定什么时候该使用哪一个运算部件对应的汇编指令。例如上述情况，即使有两条指令来完成浮点加法，但在编译器这一层次上无法决定什么时候该用FSADD，什么时候该用FSADD2。也就是说，在编译器生成的汇编程序里，这些被多个运算部件支持的功能还是只能由同一套指令来完成，即只使用了其中的一个运算部件，其余的运算部件都空闲，这显然没有充分利用VLIW的硬件资源。针对这种现况，在我们进行优化工作时，必须要加以解决以充分利用硬件提供的硬件资源。如果上层编译器的转换机制不进行修改的话，可以考虑在汇编指令一级让部件不可见，即在汇编指令级上看不出有多少个运算部件可以完成同样的功能，将原来的多套指令都合并成为一套指令，这样编译器可以不进行改写，而在汇编器内部来决定用哪一个运算部件来完成该指令的功能，这样就可以充分的均等的利用支持这些功能的所有运算部件从而提高并行性，达到优化的目的。

例如：硬件有两个浮点运算部件，完成浮点单精度加法有FSADD和FSADD2两条指令，
现在我们可以将它们合并，即只提供一条指令FSADD来完成浮点单精度加法。这
样每次遇到FSADD指令，编译器内部具体为其生成机器码的时候，就可以采用轮循
的方式，用不同的运算部件来完成这条FSADD指令。当同时需要并行执行两个浮
点加法时，可以保证使用上两个浮点运算部件，而在编译器上层进行编译转换时就
无须考虑了。

3.3 支持带预测的汇编指令(predicated execution)
在汇编指令级的优化当中，消除分支是经常采用的技术，因为分支的存在会大大限制指
令并行度，因此我们经常采用预测技术来进行分支的转化和消除。尽管采用profile等静态分析技术可以找出最常使用的分支以进行预测，但是错误的预测也是时有发生的。因此，对于那些很难预测该走哪些分支的程序，在消除分支时往往需要有带预测的汇编指令（predicated execution）的支持。

例如：如下有四个基本块的程序，采用带预测的汇编指令之后，可消除分支，转换为一个
基本块，这样在一个基本块中可以更容易的提高指令并行度[4]

Inst1
Inst2
Cmp a==b p1, p2
Inst3 p1 || inst5 p2
Inst4 p1 || inst6 p2
Inst 7
Inst 8
b0:
Inst3
Inst4
Br b3
Inst1
Inst2
Br a==b, b2

采用predicated execution
b1:

Inst5
Inst6
b2:

Inst7
Inst8
b3:

cmp执行之后将对p1和p2这两个标识进行赋值，随后再根据p1和p2的真假来决定是执行inst3, inst4还是inst5, inst6。

带预测的汇编指令就是由一般的指令带上标识位的判断，根据对标识位的判断结果来决
定是否执行该指令。通常的RISC汇编指令集不提供带预测的汇编指令，这满足不了上述分支消除技术的要求。因此，VLIW编译器应该支持带预测的汇编指令Page: 7
？？
，以便实现上述这种常用的分支消除技术。具体做法是：在汇编指令助记符写法上，如同上例，只需要多加上一个标识，指明该指令在执行时依赖于对哪个标识的判断即可；在硬件具体实现上，则可以有两种做法，一种是在指令本身的编码中就加入需要判断的标识位，一种是由条件判断算子配合指令一起完成。以常用的双操作数运算指令为例：

通常的双操作数运算指令的编码：
指令功能控制域
操作数来源一选通域
操作数来源二选通域

硬件实现方法一：将所需的标识直接放入指令的编码，不使用时为通常的指令，使用
时即成为带预测的汇编指令。
指令功能控制域
操作数来源一选通域
操作数来源二选通域
P1
P2
P3
……
标识

IA64即采用这种方式来提供对预测的支持，但是这种方式会导致指令本身编码位的增加，而且当机器提供标识较多的时候，这种方式有一定的局限。[6]

硬件实现方法二：指令本身的编码不做改变，硬件提供一个条件判断算子，其编码为
真有效/假有效（1位）
标识来源选通域（N位）
由标识来源选通域来决定到底当前判断哪个具体的标识( N = log2 [机器标识个数] )
这样的话，一般指令的实现可不做变化，当需要支持预测时，用条件判断算子加以配合，以决定指令是否需要执行。

结束语
笔者所在的实验室目前正在为一款我国自主设计的VLIW体系结构的新型CPU开发优化编译器，本文提出的与机器相关的优化方案及相关思路，从指令级和算子级两个层次着手，可进行更为底层的调度，可更为直接的控制运算部件和执行逻辑，粒度上比单纯指令级的优化更靠近机器硬件，在实际应用当中被证明是可行的，有效的。
在实际优化过程中，必须把编译优化和硬件设计结合起来：编译器应该为硬件设计者提出改进意见，指出数据通路以及指令数据来源的设计应该满足什么样的要求，才可以生成更为高效的代码；编译器还应该为硬件设计者指出超长指令格式应该如何设计，才能获得更高的并行性，通过分析编译器生成的汇编文件，找出最容易出现并行的指令，提交给硬件设计者，要求指令格式的设计必须满足这些常见的并行指令能在一条超长指令字中填入。硬件设计者改变设计之后，编译器也需随之进行改写，然后重新调式，再提出新的意见，这样反复交互，才可达到硬件设计与软件设计的最大匹配，从而获得最优的性能。

参 考 文 献
[1] J. Fisher, Very Long Instruction Word Architecture and the ELI-512, Proc. Tenth Symposium on computer Architecture (June), Stockhom, 140-150
[2] 朱凯佳 尹宝林， 基于GCC的VLIW编译系统研究 ， 1-2
[3] 陆鑫达主编 ， 计算机系统结构 ， 高等教育出版社 100-103
[4] Wen-mei W.Hwu, Compiler Technology for Future Microprocessors, Center for Reliable and High-Performance Computing, University of Illinois, Proc. IEEE, vol.83, no.12, Dec, 1995
[5] 康宝祥 栾贵兴 ，RISC体系结构及其实现技术， 科学出版社 208-210
[6] Carole Dulong, Rakesh Krishnaiyer, An Overview of the Intel IA-64 compiler ，
Microcomputer Software Laboratory, Intel Technology J., Q4, 1999