Next: Alias analysis, Previous: SSA Operands, Up: Tree SSA
大多数树优化器都依赖于静态单赋值（SSA）形式所提供的数据流信息。 我们是按照R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991中的描述来实现SSA形式的。
SSA形式基于的前提是程序变量只在程序中的一个位置被赋值。 对同一变量的多次赋值将创建那个变量的新的版本。 实际的程序最初自然很少是SSA形式的，因为变量一般会被赋值多次。 编译器修改程序表示，使得代码中每次变量被赋值的时候，便会创建一个新版本的变量。 不同版本的同一变量通过变量名字的版本号作为下标来区分开。 在表达式右端使用的变量被重命名，使得它们的版本号匹配最近的赋值。
我们使用SSA_NAME节点来表示变量版本。
tree-ssa.c中的重命名程序将每个实操作数和虚操作数，
用包含了版本号和创建SSA_NAME的语句的SSA_NAME节点包裹起来。
只有定义和虚定义可能会创建新的SSA_NAME节点。
有时，控制流使得无法确定变量的最近版本是多少。这种情况下， 编译器插入一个那个变量的人造定义，称作PHI function或者PHI node。 这个新的定义将变量的所有可能引入的版本合并一起，以创建一个新的名字。例如，
if (...)
a_1 = 5;
else if (...)
a_2 = 2;
else
a_3 = 13;
# a_4 = PHI <a_1, a_2, a_3>
return a_4;
由于不可能确定在运行时，将运行三个分支中的哪一个，
所以我们不知道在return语句中要使用a_1,a_2或a_3中的哪一个。
因此，SSA重命名将会创建一个新的版本a_4，其被赋值为“合并”a_1, a_2和a_3的结果。
因此，PHI节点意味着“这些操作数中的一个，我不知道是哪一个”。
下面的宏可以用来检查PHI节点。
一些优化过程会改变函数并使得不再具有SSA特性。 这可能会发生在当一个过程增加了新的符号或者改变了程序使得变量不再被别名的时候。 不管什么时候发生类似的情况，受到影响的符号必须被再次重命名为SSA形式。 产生新代码或者替代存在的语句的转换也需要更新SSA形式。
由于GCC为寄存器和虚变量实现了两种不同的SSA形式， 所有保持SSA形式的更新取决于你是否正在更新寄存器或者虚名字。 这两种情况对于不断的SSA更新的背后思想是类似的：当新的SSA名字被创建时， 它们通常意味着要替换程序中的其它存在的名字。
例如，给定下列代码：
1 L0:
2 x_1 = PHI (0, x_5)
3 if (x_1 < 10)
4 if (x_1 > 7)
5 y_2 = 0
6 else
7 y_3 = x_1 + x_7
8 endif
9 x_5 = x_1 + 1
10 goto L0;
11 endif
假设我们插入了新的名字x_10和x_11（第4行和第8行）。
1 L0:
2 x_1 = PHI (0, x_5)
3 if (x_1 < 10)
4 x_10 = ...
5 if (x_1 > 7)
6 y_2 = 0
7 else
8 x_11 = ...
9 y_3 = x_1 + x_7
10 endif
11 x_5 = x_1 + 1
12 goto L0;
13 endif
我们想使用x_10和x_11的新的定义来替换x_1的所有使用。
注意将要被替换的使用只在行5, 9和11中。而且，
第9行x_7的使用不应被替换
（这就是为什么我们不能仅仅标记符号x为重命名）。
另外，我们可能需要在第11行插入一个PHI节点，
因为有一个x_10和x_11的合并点。
所以x_1在第11行的使用将用新的PHI节点来替换。
PHI节点的插入是可选的。它们并不完全必要用于保持SSA形式，
并且取决于调用者的插入内容，它们可能对优化器没有用处。
更新SSA形式分为两步。首先，过程必须分别出哪些名字需要被更新，
以及哪些符号需要被重命名为SSA形式。当新的名字被引入以替换程序中现存的名字时，
新旧名字之间的映射通过调用register_new_name_mapping来注册
（注意如果你的过程通过复制基本块创建了新的代码，
对tree_duplicate_bb的调用将会自动建立所需的映射）。另一方面，
如果你的过程使得一个新的符号需要为SSA形式，
则新符号需要使用mark_sym_for_renaming来注册。
在替换映射被注册完，并且新符号被标记了要重命名后，
将会调用update_ssa来按照注册的进行改变。
这可以通过显示的调用或者为你的过程在tree_opt_pass结构体中创建
TODO标记来完成。
这里有几个TODO标记用于控制update_ssa的行为：
TODO_update_ssa.
采用为新出现的符号插入PHI节点，以及虚名字进行标记的方式更新SSA形式。
当更新实名字时，只为O_j的所有新旧定义所到达的块中的实名字O_j
插入PHI节点。如果O_j的迭代的dominance边界没有被截枝，
我们可以在块中危机具有一个或多个没有即来定义的O_j结束插入PHI节点。
这将导致对O_j符号的未初始化警告。
TODO_update_ssa_no_phi.
不使用插入任何新PHI节点的方式来更新SSA形式。这被用于要自己插入所有PHI节点的
过程或者只需要更新use-def和def-def链的虚名字的过程（例如，DCE）。
TODO_update_ssa_full_phi.
在任何需要的地方都插入PHI节点。不进行IDF的截枝。
这被过程用于需要O_j的PHI节点的情况
（例如，pass_linear_transform）。
警告: 如果你需要使用这个标记，则有可能你的过程是在做一些错误的事情。 为一个旧名字插入PHI节点可能会导致沉默的codegen错误或者虚假的未初始化警告。
TODO_update_ssa_only_virtuals.
自己更新SSA的过程可能想要使用虚名字更新来代表通用的更新。因为FUD链易于维护，
所有这简化了他们所需的工作。注意：如果使用了该标记，
则任何实名字OLD->NEW的映射将被显式的破坏，只有标记为重命名的符合被处理。
虚SSA形式比非虚SSA形式要难以保持，主要是因为语句的虚操作数集可能会意外的改变。
通常，语句修改应该被对push_stmt_changes和pop_stmt_changes的调用
所包裹。例如，
munge_stmt (tree stmt)
{
push_stmt_changes (&stmt);
... rewrite STMT ...
pop_stmt_changes (&stmt);
}
对push_stmt_changes的调用保存了语句操作数的当前状态，
对pop_stmt_changes的调用比较保存的状态和现在的，
并对适当的符号标记为SSA重命名。
当处理一个语句栈时，通过使用LIFO顺序来调用push_stmt_changes和
pop_stmt_changes，可以一次修改多条语句。
另外，如果过程在调用push_stmt_changes后发现它不需要改变语句，
它可以通过调用discard_stmt_changes来简单的丢弃最顶层的缓存。
这将避免用来确定是否符合需要被标记为重命名所需的昂贵的操作数重扫描操作和缓存比较。
SSA_NAME节点返回创建
SSA_NAMEvar的语句s。 如过s是空语句（即，IS_EMPTY_STMT (s)返回true）， 则意味着对该变量的第一个引用是一个USE或者VUSE。
对use-def链的遍历起始于
SSA_NAME节点var。 对每一个发现的可达定义调用函数fn。函数fn接受三个参数：var， 它的定义语句（def_stmt）和一个通用指针指向fn可能想要维护的任何状态 信息（数据）。函数fn可以通过返回true来停止遍历，否则要继续遍历， fn应该返回false。注意，如果def_stmt是一个
PHI节点，则语法有点不同。 对PHI节点的每个参数arg，该函数将：
- 为arg遍历use-def链
- 调用
FN (arg,phi,data).注意不管fn的第一个是否还是最初的变量var，目前都会检测PHI的参数。 如果fn想获得var，则应该调用
PHI_RESULT(phi)。
该函数遍历当前CFG的支配树， 并调用在domwalk.h中struct dom_walk_data里定义的一系列回调函数。 你所需要定义的回调函数可以用于在遍历过程中的不同点执行自定义的代码：
- 当处理bb和它的孩子（children）时，在初始化所需要的任何局部数据的时候。 该局部数据被压入一个内部的栈中，该栈在遍历支配树时会被自动的压入和弹出。
- 在遍历bb中的所有语句之前。
- 对于bb中的每条语句。
- 当遍历过所有语句之后，并在递归到bb的支配孩子之前。
- 然后递归到bb的所有支配孩子。
- 在递归到bb的所有支配孩子之后，可选的， 重新遍历bb中的每条语句（即，重复步骤2和3）。
- 当遍历完bb和bb的支配孩子中的所有语句之后。这时，块局部数据栈被弹出。