GCC 4.0 的新特性

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，这样就保证了每个变量仅仅被赋值一次。