基于过程集成的编译优化

摘 要 过程间的优化是扩大编译器的视野，把一个一个的过程作为其优化的对象。文章对实现过程集成的前提条件和具体实现步骤进行研究，分析其特点、算法和性能。

关键词 编译优化；过程集成；语言内嵌

中图分类号：TP202 文献标识码：A 文章编号：1671-7597（2013）22-0071-02

编译程序的主要任务就是把用户用高级语言的编写的程序转换成机器语言，在确保正确转换的前提下编译程序应尽可能的根据目标机器的特点对源程序进行优化，以提高目标程序的运行效率。传统的编译器对源程序的优化大多集中在单个过程内部，而事实上一个程序可有很多过程组成，如果编译器能够进行过程间的优化，充分利用过程间的信息，那么必将大大提高目标程序运行效率。

1 过程集成

过程集成也称作自动内嵌，它通过复制过程的程序体来置换对过程的调用。是一种非常有用的优化技术。它把调用从一个不透明的对象——这个对象会对重名的变量和参数产生不可预知的影响，转变成本地的代码，这个代码不仅能够展示其作用也能被作为调用过程的一部分而加以优化。

一个程序有很多过程组成，过程之间存在调用，很多时候这些调用是非常频繁的。如果我们不对其处理，每次调用时程序都要在内存中为调用开辟空间来存放上下文信息，甚至有些时候这些空间可能大于被调用的程序的本身。因此我们设想用被调用过程本身来替换对其的调用，也就是把调用和被调用者整合为一个程序，这样通过整合消除了调用，节省了系统资源，减少了运行时开辟调用空间的时间，大大提高了程序的运行效率。

但是我们不可能整合所有的过程来消除所有的调用，因为整合会带来源代码体积的增大，会引起指令缓存的失效。我们必须根据一定的规则来整合过程。这种调用的规则有如下几种：

平均循环体积大小算法。使用失效代价来决定是否合并过程。当失效代价增大时，建议合并较少的过程。

体积临界值方法。所有体积小于该临界值的方法我们都加以整合。

比例临界值方法。比例指的是被调用过程在每一个调用点执行的次数和被调用过程的体积的比。如果这个比例超过某个临界值，那么我们就合并这个过程。

2 过程集成的前提

当我们决定在一个编译系统中应提供多大程度的过程集成以及如何实现这种程度时，我们必须考虑以下的几个问题。

1）提供基于多个编译单元还是基于单个编译单元？如果是前者，我们需要提供一种方法来保存过程的中间代码表示，或者更有可能保存整个编译单元到文件，因为我们通常并不是依赖编译用户来决定集成哪个过程的。如果是后者，我们仅仅需要当在单独的编译单元中需要做合适的内嵌时，我们能够保存中间代码。

2）如果我们提供基于多个编译单元的过程集成，我们需要决定是不是需要调用者和被调用者用同一种语言编写或者是不是支持用不同的语言编写他们。在这里主要考虑的问题是不同的语言有不同的传递参数和访问非本地变量的规则，这些规则需要根据内嵌的过程分别加以考虑。处理参数传递规则不同的一种技术是：给在源语言中单独被编译的过程提供一个“外部语言名过程名”声明作为接口的一部分，这样也说明了书写外部语言的源语言。这将会引起对外部程序的调用，这个程序遵循编写他所用的语言的参数传递规则。

3）在交错编译单元过程集成中，我们是不是需要保存被内嵌的过程的中间代码复本，尤其是一些语言把过程的可见性限制在它嵌套的范围中。例如：Pascal中的被嵌套过程，模块化语言族和Mesa中的非接口过程，Fortran 77中的声明过程，Fortran 90中没有被外部声明的过程。如果保存中间代码的目的仅仅是为了完成过程集成，那么对编译单元而言这些过程的复本不需要被保持在一种被保存的中间代码的状态，因为在其视野外部我们不能引用他们。从另一方面来说如果目的是为了减少在对源语言作出改动后重编译的时间，那么我们需要保存中间代码。

4）假定我们在所有可见的调用点内嵌了一个过程，那么我们是不是需要编译整个过程的复本？如果过程的地址采用C语言的形式或者将会被当前不可见的其他的编译单元调用，我们才需要这样做。

5）我们是不是应该完成递归过程的所有内嵌？很显然我们不能这么做除非我们能够运行完所有的调用，而这将是一个没有穷尽的过程。但是内嵌递归过程一到两次还是很有意义的，因为能够降低对其的调用负载。

3 实现与应用

一旦我们选定了在哪个调用点集成哪个过程的标准，剩下的问题就是如何完成集成。一个明显的部分就是用相应的过程的复制来替换对其的调用。一般性起见，我们假定是在中间代码级实现的，这样就能够做多语言间的内嵌，在这里3个主要的问题：

1）满足语言所包含的参数传递的规则。

2）处理调用者和被调用者的参数名字的冲突。

3）处理静态变量。

首先如果没有提供“外部语言名过程名”声明，过程集成必须包含所有参与进程的参数传递机制的详细信息，以便能够确定需要做什么样的集成工作以及怎样使他们起作用。例如我们不能使用一个通过值传递来调用的C语言的参数来匹配一个通过引用来调用的Fortran参数，除非C参数是一个指针类型。类似的我们不能轻率的用调用者的变量名来替换一个传值调用的参数，如图1所示，这会给调用者的变量带来一个错误的分配。

图1 传值调用

如果我们工作在不包含源符号名字的中间代码状态，那么第二个问题就不称其为问题。符号引用通常是指向符号表的表项的指针，标签是指向中间代码的位置的指针。如果我们工作在字符描述状态，那么我们必须发现通常在被调用的过程中出现的名字冲突并通过重命名来解决这个问题。

静态的变量代表了不同的问题集合。尤其是在C语言中，一个具有静态存储类的变量通常具有一定的作用域，这个域存在于整个程序的执行期间。如果一个变量被声明为文件级的范围而不是函数级的，它将在程序执行前被初始化，对文件中的任何函数而言是可见的不需要重新声明。另一方面，如果被声明为函数级的，那么对别的函数而言是不可见的。如果一些函数声明了具有相同名字的静态局部变量，那么它们是不同的对象。

因此对文件级的静态变量，我们仅仅需要在作为结果的目标程序中对他加以复制，如果它被初始化，它仅需要被初始化一次。我们可以通过让变量具有全局视野并给他提供一个全局初始化来完成这件事情。

4 试验结果分析

在过程集成的效果方面，Cooper，Hall和Torczon了一个令人深省的结果。他们做了一个试验，在试验中他们集成了静态双精度LINPACK基准测量中44%的调用点，因此消除了98%的动态调用。他们希望能够带来性能上的提升，但是在基于MIPS R2000的系统上运行时却是超过8%的性能的下降。对代码分析的结果显示性能的下降并不是由于在关键循环中缓存影响或者寄存器压力，而是浮点互联锁数目增加了75%。

隐含在遵循Fortran 77标准和没有做内部过程数据流分析的MIPS编译器后面的问题是：标准允许编译器在进入一个过程时假定参数中不存在重名现象并且把这条信息使用到了产生代码时。

MIPS编译器对源代码也做了如此的编译。从另一方面来说，随着关键过程的内嵌和缺乏内部数据流分析，关于变量是否被改名没有可用的信息，因此编译器做了最保险的事情-他假定变量命中存在混淆现象并且生成了差的代码。

参考文献

[1]S. Watterson and S. Debray， “Goal-directed Value Profiling，” The Tenth International Conference on Compiler Construction （CC）， LNCS 2027， Springer Verlag， Genova， Italy， April 2001.

[2]Jan Hubicka. “Profile driven optimizations in GCC” Proceedings of the GCC Developers’ Summit. Pages 107-124 June 2005.

[3]Michael Bond， UT Austin，Kathryn McKinley， UT Austin，”Practical Path Profiling for Dynamic Optimizers”. Proceedings of the international symposium on Code generation and optimization table of contents Pages： 205 - 216 2005.

[4]Krintz C.Coupling On—Line and Off—Line Profile Information to Improve Program Performance.Code Generation and Optimiza tion.2003.CGO 2003.In：Int1.Symposium on，Mar.2003.69-78.

[5]T. M. Chilimbi， “Efficient Representations and A bstractions for Quantifying and Exploition Data Reference Locality，” ACM SIGPLAN Conference on Programming Language Design and Implementation， pages 191-202， Snowbird， Utah， June 2001.

作者简介

杨夏（1976-），女，湖南常德人，副教授，硕士研究生，研究方向：程序设计语言与编译系统。