[WebKit] JavaScriptCore解析--高级篇(一) SSA (static single assignment)

野性酷女 2022-01-23 12:15 286阅读 0赞

在编译器优化领域，数据结构的选择会直接影响程序优化的有效性。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函数就是带有一个参数的基本块。

就像这样:

![20130611155223125][]

上面的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 ][Landin_ Steele_ letrec_ and labels]**.**

这是个比较生僻的内容，主要来自学习和翻译以下两篇资料:

1. Cytron, Ferrante, Rosen, Wegman, and Zadeck, [Efficiently Computing Static Single Assignment Form and the Control Dependence Graph ][Efficiently Computing Static Single Assignment Form and the Control Dependence Graph]**.**

2. Wingolog, [Static Single Assignment for Functional Programmers][]

因为能力有限，一定会有理解错误的地方，欢迎指正。

转载请注明出处:[http://blog.csdn.net/horkychen][http_blog.csdn.net_horkychen]

**系列索引:**

> [基础篇 (一)JSC与WebCore][_JSC_WebCore]
> 
> [基础篇(二)解释器基础与JSC核心组件][JSC]
> 
> [基础篇(三)从脚本代码到JIT编译的代码实现][JIT]
> 
> [基础篇(四) 页面解析与JavaScript元素的执行][_JavaScript]
> 
> [高级篇(一) SSA (static single assignment)][SSA _static single assignment]
> 
> [高级篇(二) 类型推导(Type Inference)][_Type Inference]
> 
> [高级篇(三) Register Allocation & Trampoline][Register Allocation _ Trampoline]
> 
>   
>

[20130611155223125]: /images/20220123/f32bede4070644899573ca07a70deec3.png
[A Correspondence Between Continuation-Passing Style and Static Single Assignment Form]: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.6773
[Landin_ Steele_ letrec_ and labels]: http://wingolog.org/archives/2009/08/10/goto-
[Efficiently Computing Static Single Assignment Form and the Control Dependence Graph]: http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/cytron-efficientSSA.pdf
[Static Single Assignment for Functional Programmers]: http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers
[http_blog.csdn.net_horkychen]: http://blog.csdn.net/horkychen
[_JSC_WebCore]: http://blog.csdn.net/horkychen/article/details/8915907
[JSC]: http://blog.csdn.net/horkychen/article/details/8928578
[JIT]: http://blog.csdn.net/horkychen/article/details/8963124
[_JavaScript]: http://blog.csdn.net/horkychen/article/details/9003351
[SSA _static single assignment]: http://blog.csdn.net/horkychen/article/details/9075827
[_Type Inference]: http://blog.csdn.net/horkychen/article/details/9076425
[Register Allocation _ Trampoline]: http://blog.csdn.net/horkychen/article/details/9078111