谈谈GCC4.0几个值得关注的新特性 （2）

3. GCC 4.0 的内部结构变化

GCC 遵循 GPL 协议，是开放源代码的，其开发过程也是完全开放的，任何人都可以对 GCC 的发展作出贡献，因而 GCC 特别适合用于学习和研究编译器。对于学习和研究编译器本身来说，GCC 内部的结构变化显然更吸引人。

目前 GCC 发行维护者 Mark Mitchell 在接受 internetnews.com 网站采访时这样说到："毫无疑问地，GCC 4.0 中最引人注意的特性以及为何把 GCC 的这个版本称作 4.0 而不是 3.5，就是因为其新的优化框架(optimization infrastructure)。大体上来说，GCC 以前的版本的代码优化工作主要在底层机器指令级别进行的。不幸的是，到了底层的时候，很多信息已经丢失了，因此，GCC 4.0 在更接近输入高级语言程序的级别上做了很多优化工作。"

Mark Mitchell 所说的 GCC 新的优化框架主要就是指 Tree SSA(Static Single Assignment)，Tree SSA 经过长时间的独立开发，最终整合进了 GCC 的主流(mainstream)中，可见这种设计是意义非凡的。Tree SSA 是什么？为什么要采用 Tree SSA? 使用了 Tree SSA 的 GCC 有什么不同？新的 GCC 编译和优化框架是什么样的？等等，这些将是本文探讨的主要问题。

这部分文章内容是这样组织的：首先回顾 GCC 4.0 版本之前的编译流程，以便进行对比；接下来介绍 GCC 4.0 的编译流程以及新的优化框架结构，这里先介绍 GENERIC Tree和 GIMPLE Tree，SSA 形式等基本概念，在读者对这些概念和理论有了一定的了解之后，再介绍 GCC 中是如何实现 Tree SSA 框架结构的。

3.1 GCC 4.0 之前的编译流程

这里有必要回顾一下 GCC4.0 之前的版本进行代码优化的框架结构，以便进行对比分析。GCC 的前端在接受了输入的源程序之后，经过分析器(parser)处理得到 Parse Tree（通常是一种抽象语法数，AST, Abstract Syntax Tree），根据这个 Parse Tree 生成程序的RTL(Register Transfer Language)表示，然后在 RTL 表示的基础上进行优化处理，然后生成相应的目标代码，如下图 1 所示。

但是 RTL表示是一个相当接近底层的表示，也就是说它更接近目标代码，适合进行目标相关的优化工作，比如寄存器分配等等。然而，很多的优化转换工作需要更高层的程序信息，比如数组引用、数据类型、控制流结构等等，这些很难用 RTL 表示，或者无法用 RTL表示。


图1 GCC 4.0之前版本的代码编译流程和优化框架

3.2 GCC 4.0 的优化框架(Optimization Infrastructure)

提供一个可移植性强、跨平台以及编译高效代码的编译器，是 GCC 一贯追求的目标，为了使 GCC 能够获得更好的编译性能，高层程序信息级别的优化工作是必须的。Tree SSA设计的主要目的就在于此，它既与前端语言无关，又与后端目标无关，而且能够提供在 RTL表示层很难或者无法进行的高级分析和转换。

Tree SSA 起先是作为 GCC 的一个分支(branch)进行独立开发的，经过两年多的努力开发，终于在 2004 年 5 月 13 日进入了 GCC 的主流版本。在 GCC 的 SSA for Trees 分支的网页上明确说明了，这个项目的目的就是构建一个对基于 SSA 形式的树的优化框架。在学习编译原理的时候我们知道，编译器通常会使用树的形式来描述程序，GCC 也是这样，在接受了输入的源程序后，GCC 驱动其相应语言的前端分析器(parser)，处理得到一个 Tree。从图 1 可以看到，4.0 版本之前的 GCC 几乎是立即把这些 Tree 转换成了 RTL 表示。那么现在 GCC4.0 的 Tree SSA 优化框架就是在前端生成 Parse Tree 之后，把这些 Tree 转换成基于 SSA 的 Tree，对这些 SSA 形式的 Tree 进行高层次的优化，然后才把 Tree 转换成 RTL 表示。

3.2.1 GENERIC Tree 和 GIMPLE Tree

这个框架结构看起来比较简单，而且 GCC 的 Parse Tree 能够提供足够的信息来实现SSA，但是在真是实施的时候，还是有很大的困难的，最主要的两个困难是这样的：

1. GCC 中的树没有统一的表示形式，每一个前端都定义了自己的树。这就意味着要得到基于SSA形式的树必须要对每种前端分析生成的树都进行处理。

2. GCC 前端得到的 Parse Tree 的复杂度是无法估量的。把这些树转换成基于 SSA形式的树需要进行复杂的处理工作。

为了解决以上两个问题，GCC Tree SSA 分支的开发小组引入了 GENERIC Tree 和GIMPLE Tree 两个概念：

1. GENERIC Tree 是特意创造出来的 GCC通用的树的表示形式，它能够表示不同的前端所需要的所有的结构，而且又能够去除语言相关性。

2. GIMPLE Tree是取自GENERIC Tree和SIMPLE两个短语的。因为GENERIC Tree的复杂性导致实现SSA形式的困难，需要把GENERIC Tree进行简化，这种简化的GENERIC Tree就称之为GIMPLE Tree。

好了，了解了这些内容之后，我们可以看看 GCC 4.0 的编译流程和优化框架，如下图2所示：


图2 GCC 4.0 的编译流程和优化框架

3.2.2 Single Static Assignment Form 的基础介绍

到现在为止，我们基本搞清了新的 GCC 的编译过程，也大概了解了所谓的新的 Tree SSA 优化框架。上面提到的 GENERIC Tree 和 GIMPLE Tree 都是为了实现 SSA 而做的准备工作，那么 SSA 本身究竟是什么？为什么 GCC 要把 Parse Tree 转换成基于 SSA 形式的 Tree 再做优化工作呢？为弄清楚这些问题，我们有必要多花一些篇幅对SSA的基本概念和理论做一些介绍。

SSA 的全称是 Static Single Assignment，直译过来就是静态单一赋值，它是IBM公司在上个世纪 80 年代研究的成果。从前面的讨论可以看出，Tree SSA 与 RTL 一样，也是一种中间表示形式，不过相比 RTL 要更高层一点。SSA 形式是一种相对而言比较新颖的中间表示形式，早期的讲编译原理或者编译器的课本中大多没有提及。

简单的说，SSA 形式就是每个变量只能被赋值一次。这样，非 SSA 形式的程序在转换成 SSA 形式的时候，其中的部分变量就会被分割成很多版本，通常使用下标来表示这些不同的版本。下面举一个简单的例子来说明，如下图 3 所示：


图3 程序的非 SSA 形式和 SSA 形式

上图中所示的代码片段，由于 y 变量被赋值两次，所以在转化成 SSA 形式的时候，y变量被分割成两个版本 y1 和 y2，这样就保证了每个变量仅仅被赋值一次。

由于 SSA 形式中每个变量只能被赋值一次，那么 SSA 形式就能有效地把程序中所操作的数值和这些数值的存储位置这两者分开，这样就能方便一些优化工作。比如我们刚才看的图 3 中的代码片段，我们可以通过肉眼分析发现在非 SSA 形式中的第一条语句y := 1是一条无效的冗余语句，真正决定 y 变量值的是第二条 y := 2 赋值语句。那么在代码优化的时候，第一条语句就应该被删除掉。但是这是我们人工发现的优化结果，如果想要编译器来完成这个优化工作，需要进行复杂的分析，在编译原理中称之为"定义可达性分析"(reaching definition analysis)。而在 SSA 形式中，显然，做出这样的优化决定则无需进行太多分析。

这只是 SSA 形式诸多优点中的一个而已，使用 SSA 形式可以利用更多的编译器优化算法或者是提高这些算法的效率，比如 constant propagation, sparse conditional constant propagation, dead code elimination, global value numbering, partial redundancy elimination 以及register allocation 等等。这里涉及太多编译理论和算法，本文不作详细讨论。

SSA 形式具有上文所述的优点，当然也会有其复杂和困难的地方了，下面我们通过一个稍微复杂点的程序片段来说明把非 SSA 形式的程序转换成 SSA 形式程序的时候有些什么需要考虑的问题：


图4

图 4-a 所示的非 SSA 形式的程序在转换成了图 4-b 所示的 SSA 形式的程序后，有一个问题很难解决，就是图 4-b 中最下面程序块中 y 的值无法确定。因为在此之前有一条选择语句，导致程序控制流产生了分支，此时 y 的值可能是 y1 也可能是 y2，这是由程序具体执行时经过哪一条控制流来决定的。处理的方法是在最后一块程序片段之前加上一个 Φ 函数，定义一个新的 y3，并从 y1 或者 y2 中选择一个适当的值赋给 y3，如图 4-c 所示。

推而广之，在将非 SSA 形式的程序转换成 SSA 形式后，如果某个变量被分割成了 n个不同版本的变量后，在某一点需要会合，那么在这个会合点 (joint point) 就需要加入一个 Φ 函数来确定应该选择这 n 个不同版本的变量中的某一个值。这样问题就转变成了如何计算这个 Φ 函数以及确定在程序中的什么位置应该插入 Φ 函数，这个可以使用 dominance frontiers 来进行计算，关于如何高效计算这个 Φ 函数的算法研究本文不作深入讨论。