在编译器优化领域，数据结构的选择会直接影响程序优化的有效性。SSA是一种编译器使用的中间语言(intermediate language), 作为编译优化的基础(也是DFG JIT的基础)，它和Control Dependence Graph一起被用来表示程序的数据流和控制流。
大家都知道编译器是这样工作的:解析、优化，最后生成代码。中间会使用到一个中间语言的进行过度，好的中间语言一定要
1. 简单，这样优化工作就可以变得简单。
2. 很好的表达能力，这样就可以很容易从源代码中生成出来。
3. 实效性(utilitarian), 它的结构可以让你做到很多的优化。
SSA简介
如何为循环生成有效的机器代码是编译优化领域中一个关键的问题。要处理很多的控制流操作，都被集中到了一阶的控制流问题， 也就是一个直线型的代码(Straight-line code)。SSA中的变量是不会变化的，他们只会被指定一次。向一个变量赋个新值，都会导致一个新的绑定。
比如下面的函数:
function clamp (x, lower, upper) {
if (x < lower)
x = lower;
else if (x > upper)
x = upper;
return x;
}
SSA的转换结果为:
entry:
x0, lower0, upper0 = args;
goto b0;
b0:
t0 = x0 < lower0;
goto t0 ? b1 : b2;
b1:
x1 = lower0;
goto exit;
b2:
t1 = x0 > upper0;
goto t1 ? b3 : exit;
b3:
x2 = upper0;
goto exit;
exit:
x4 = phi(x0, x1, x2);
return x4;
SSA把过程区分出若干个基本块(basic blocks),每块在结尾或有条件，也或者无条件地转向其它分支。临时变量也有自己的命名，以便进行后期优化。
phi函数(phi functions)
SSA还有一个有趣的"phi" 函数，它被放置在控制流交汇点(control-flow joins). 上面的例子里，x可能来自参数，也可能在两个条件语句中被赋值，这时就有phi函数来表示它。第一个基本块(basic blocks)都可以认为是一个函数，而phi函数就是带有一个参数的基本块。
就像这样:
上面的phi函数表示在一个分支的交汇点后，后续对V的调用，就变为对V3的调用。这样做就可以方便地引入进一步的优化，比如Copy Propagation。
为了正确放置phi函数，你需要建立一个dominator tree. 如果所有的控制路径必须经过第一个，才能到达第二个，我们称这个基本块支配(dominate)另一个。比如入口的基本块就支配整个函数。上面的例子里，b0也支配其它块。而b1没有跳转到exit, 所以它就没有支配exit, 因为exit可能会从路径到达。
参考阅读: A Correspondence Between Continuation-Passing Style and Static Single Assignment Form,
Landin, Steele, letrec, and labels .
这是个比较生僻的内容，主要来自学习和翻译以下两篇资料:
1. Cytron, Ferrante, Rosen, Wegman, and Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph .
2. Wingolog, Static Single Assignment for Functional Programmers
因为能力有限，一定会有理解错误的地方，欢迎指正。
转载请注明出处:http://blog.csdn.net/horkychen
系列索引:
高级篇(一) SSA (static single assignment)
高级篇(三) Register Allocation & Trampoline
