GCC 4.0 的新特性

由于 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 的形式。