本文侧重介绍了 GCC 4.0 内部结构相对于 3.4.x 版本的一些全新变化。

GCC(GNU Compiler Collection) 是 GNU(GNU’s Not Unix) 计划提供的编译器家族，他能够支持 C, C++, Objective-C, Fortran, Java 和 Ada 等等程式设计语言前端，同时能够运行在 x86, x86-64, IA-64, PowerPC, SPARC 和 Alpha 等等几乎现在任何的硬件平台上。鉴于这些特征，连同 GCC 编译代码的高效性，使得 GCC 成为绝大多数免费软件研发编译的最好选择工具。虽然对于程式员们来说，编译器只是个工具，除了研发和维护人员，很少有人关注编译器的发展，但是 GCC 的影响力是如此之大，他的性能提升甚至有望改善任何的免费软件的运行效率，同时他的内部结构的变化也体现出现代编译器发展的新特征，所以 2005年4月20日，GNU 组织发布的 GCC 4.0 引起了广泛的关注。那么这次 GCC 从 3.4.x 直接跃迁到 4.x 的主版本变化到底有什么值得关注的呢？

我们能够从不同的角度看待 GCC 的这次变迁，对于普通程式员来说，关注的主要是GCC 的前端支持情况连同编译性能的变化。

1. GCC 4.0 的前端支持
GCC 的研发者和使用者当中，大多数人都是 C 或 C++ 的用户，所以 GCC 对Fortran 语言支持不足也不令人奇怪。但是，这并不代表 Fortran 是无足轻重的，事实上，研发商业的 Fortran 编译器的公司要远远多于研发 C 和 C++ 编译器的公司。

在科学计算和工程应用领域，程式员们仍然在频繁使用 Fortran 程式，同时，大量的经过长时间考验的函数库也为Fortran语言的数值计算提供了强有力的支持，所以，在一些"终极电脑" (supercomputer)上，Fortran仍然是绝大多数应用的最好选择语言。

然而，在GCC 4.0发布之前，假如不想购买商用的Fortran编译器，那么程式员们的唯一选择就是GNU的g77编译器。但是g77编译器是个相当陈旧的技术，很多Fortran语言的新特性都不能支持，比如流行的Fortran 95，他能够支持的模块化编程，并行处理和数组操作等等，g77编译器基本上都无法支持。

这次GCC 4.0发布时推出了支持Fortran 95语言前端的编译器gfortran，他已能够大大超越g77编译器，支持Fortran 95标准中的很多新特性，虽然gfortran更有一些缺陷，比如不能支持自动并行化(automatic parallelization)，不能支持Fortran 2003中的面向对象特性等等，他已给了Fortran程式员除了商业编译器和g77以外一个更好的选择。

2. GCC 4.0的编译性能
编译器的性能主要能够从三个方面来考查：

1. 编译时间(compile time)，指编译器编译一个源程式得到目标代码所需要的时间。

2. 目标代码的大小(object size)，编译得到的目标代码当然是越精悍越好了。

3. 目标代码运行时间(run time)，运行时间体现了速度和效率。

这里，作者没有亲自测试和实验，引用了Scott Robert Ladd的《GCC 4.0: A Review for AMD and Intel Processors》文章中的一些实验结果。这篇文章引起了比较大的反响，其实验结果和结论也得到了广泛的认可，假如对Scott的具体测试采用的软件和硬件平台和工具方法感兴趣，原文能够在http://www.coyotegulch.com/reviews/gcc4/index.html看到。

Scott 使用AMD和Intel的两款处理器：64位的Opteron处理器和32位的Pentium 4处理器，分别针对GCC 3.4.3和GCC 4.0来进行测试。他选用了POV-Ray 3.6.1, LAME 3.96.1, SciMark 2.0和Linux 2.6.11.8作为benchmark来进行测试，分别记录了GCC 3.4.3和GCC 4.0在ADM Opteron和Intel Pentium 4下的编译时间、代码大小和代码运行时间进行比较，具体的实验结果请参见原文。

这样，根据这些实验数据，我们能够给出一个粗糙的结论，在编译性能方面，GCC 4.0似乎不如GCC 3.4.3，因为在很多时候，GCC 4.0的编译时间、代码大小连同代码运行时间全面高于GCC 3.4.3。这样的结果看似出人意料，GCC这次大的版本变化就是因为引入了新的优化框架，怎么会编译性能有所下降呢？这主要是因为：首先，这是一次主版本变化，我们能够理解巨大的变化带来的性能损耗；另外，更主要的是，GCC新的优化框架的潜力尚未完全发挥出来，这一点，在我们文章结束的时候，读者会有更深的理解。

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-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 来进行计算，关于怎样高效计算这个 Φ 函数的算法研究本文不作深入讨论。

3.2.3 GCC 4.0 中的 Tree SSA 框架的设计和实现

至此，我们已比较清楚的了解了什么是 SSA，SSA 形式有什么好处，怎样将非 SSA表示转换成基于SSA形式的表示连同这个过程中需要解决的主要问题等等，本文将不再对SSA进行深入的讨论了，回到我们的主题，继续讨论GCC 4.0 的 Tree SSA 优化框架是怎样设计和实现的，他是怎样把 Tree SSA 融入到 GCC 的编译过程中去的。

回顾上图 2表示的 GCC 4.0 编译流程，在得到 GIMPLE Tree 之后，经过 GIMPLE optimizer 和 GIMPLE expander 的处理，得到了程式的 RTL 表示。其实把程式转换成 SSA形式和在此基础上进行优化就在这个过程中完成的，下面我们就来具体看看 GCC 4.0 是怎么做的。在 GIMPLE 和 RTL 之间是树优化 (Tree Optimization) 的过程，如下图 5 所示。图 5 中所示的树优化器 (Tree Optimizer) 主要完成这几个功能：

1. 生成一个控制流转换图 CFG(Control Flow Graph)。

2. 将 GIMPLE Tree 转换成基于 SSA 形式的 Tree。

3. 进行 Tree SSA 的优化。

4. 将优化后的基于 SSA 形式的 Tree 转换成 RTL 接口所能识别的非 SSA Tree 的形式。

图5. GCC 4.0 的 Tree Optimizer 结构

结合 GCC 4.0 代码中的部分源文档来说明：图 5 中这个 Tree Optimizer 的行为是由tree-optimize.c 文档驱动的，tree-ssa.c, tree-into-ssa.c 连同 tree-outof-ssa.c 负责完成 SSA 形式的转换、验证连同其他需要和 SSA 形式交互的功能，建立和管理控制流转换图 CFG 的工作由 tree-cfg.c 完成。不同的树分析和优化功能分别在相应的源文档中单独实现，这些分析和优化函数必须向 GCC 注册，然后才能由 tree-optimize.c 进行驱动和管理，结合图 5来看，SSA pass1, SSA pass2 … SSA passn 代表了实现各种不同功能的 SSA 分析器，他们向 Tree Optimizer 注册，在编译时刻 Tree Optimizer 根据编译选项等等选择相应的SSA分析器进行优化或其他处理工作，并确保在基于 SSA 形式的处理完成之后将 SSA 树转换成非 SSA树，交给下面的 RTL 模块处理。

至此，GCC 4.0 的 Tree SSA 优化框架结构应该比较清楚了。读者可能会注意到，文中多次提到Tree SSA是个优化框架结构(Optimization Infrastructure)，为什么说是个Infrastructure 呢？其实把 Infrastructure 称作框架结构或许并不贴切，更精确地说 Tree SSA是 GCC 提供的一种进行优化工作的基础设施。图 5 中已体现出了这一点，Tree SSA 的分析和优化工作不是一成不变的，具体选择哪些优化功能和算法是由Tree Optimizer选择驱动的，而且这个Infrastructure是相当灵活的，我们能够很方便的加入一个 SSA 分析器，只需要如下步骤：

1. 创建一个 struct tree_opt_pass 类型的全局变量。

2. 在 tree-pass.h 头文档中为这个新的分析器添加一个外部声明(extern declaration)。

3. 调用 NEXT_PASS 把这个新的分析器加入到 tree-optimize.c: init_tree_optimization_passes 序列中。

所以这种 Infrastructure 是个相当灵活和方便的设计，使得我们能够便利地加入新的SSA 分析器，或使用更高效的算法来重新设计完成一些优化功能等等。

4. 总结
GCC 4.0 发布以来得到了引起了广泛的关注，新的 gfortran 前端给 Fortran 程式员带来了福音，但也有很多不尽如人意的地方，比如编译性能的损耗，连同向后兼容问题。比如KDE(K Desktop Environment) 研发小组在发现 GCC 4.0 无法正常编译 KDE 后，迅速的抛弃了 GCC 4.0。而且，出于稳定性的考虑，GCC 3.x 版本的研发仍然在进行中。这些似乎给 GCC 4.0 的前景笼罩上了一层阴影，但我们应该容忍一点，给 GCC 4.0 一些信心，向后兼容的问题应该是能够解决的。

至于编译性能的问题，通过我们这篇文章的讨论，我们能够看到 GCC 4.0 Tree SSA 的优化框架结构并没有充分发挥出其潜能，还能够增加和改进更多 Tree SSA 的优化工作，假以时日，GCC 4.0 的编译性能会得到提高的。

总的来说，这次 GCC 从 3.x 版本跃迁到 4.x 版本更像一个进化 (evolution) 的过程，而非一个革命性 (revolution) 的过程，他采用的 Tree SSA 优化框架代表了编译器发展的方向，我们应该关注 GCC 4.0 的进一步发展。