什么是SSA以及SSA的作用

yueyue.gao · · 6177 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

SSA概述

SSA在Go1.7中被引入,这个特性对编译器的性能有很大的提高,但是也导致编译过程有些减速。下面来结合网上的资粮和书籍,简单说明一下SSA以及SSA的应用。

SSA 代表 static single-assignment,是一种IR(中间表示代码),要保证每个变量只被赋值一次。这个能帮助简化编译器的优化算法。

 y := 1
 y := 2
 x := y

比如上面这段代码,y = 1其实是不可用的,这个要通过定义的可达分析来确定y是要用1还是2,而SSA有一个标识符可以称之为版本或者“代“。

 y1 := 1
 y2 := 2
 x1 := y2

这样就没有任何间接值了。用SSA表示的好处是对于同一个变量的无关使用表示成不同“代”,可以方便很多编译器的优化算法的实现。

一个概念:

Φ(读作fai) 函数,表示要根据控制流赋值的“代”。

例子可以参考维基里的这一段

三个定义:

A dominate B,如果从起点开始必须通过A到达B。也就是说A是到B的必经之路。

A strictly dominate B,如果 A dominate B,并且A和B不相等。

A 的 dominance frontier 含有B,如果A没有strictly dominate B,但是 dominate 了B的一个前驱节点。

用遍历的方式确定 dominance frontier 的伪代码。

for each node b
    if the number of immediate predecessors of b ≥ 2
        for each p in immediate predecessors of b
            runner := p
            while runner ≠ idom(b)
                add b to runner’s dominance frontier set
                runner := idom(runner)

idom(b) 代表相邻的strictly dominate b的结点。这样的点只有一个,因为相邻的点有两个的话就不会是必经之路了。

ssa_example

如图是一个例子,2的前驱是1和7,7没有sd(strictly dominate) 2,所以把2加入到7的DF(dominate frontiers)当中。3是7的相邻sd,然后3不是2的sd所以2加入到3的DF当中,接着2是3相邻的sd,然后2不是2的sd所以把2加入到2的DF中,最后遍历到7,5和6不是7的sd所以把7加入到5和6的df当中。

df(A)可以认为是可以通过A到达的,但不是必经之路的点的集合。

有了这个定义以后就可以插入Φ函数了和重命名了。如果X中有定义a那么所有df(X)都需要a的Φ函数。并且Φ函数本身也是一个定义。

比如还是同一个例子。

ssa_example

1当中有j的定义,但是df(1)是空的,5当中有j的定义,并且5的df有7所以7当中要插入一个φ(j, j)。j现在在7中定义了(通过φ函数)所以df(7)中的2也要有φ(j, j),6也有j的定义但是7已经有了φ函数了,2的df有2,但是2已经有φ函数了。类似的方式可以应用到i和k。接着对定义重命名就可以完成SSA的转换了。

SSA的应用

上面只是通俗的解释了一下SSA,没有给出更多详细的理论和算法以及证明,因为证明实在难看懂,下面说一下SSA的应用。

DEAD CODE 消除

因为每个变量都有“代”(因为大家都只被赋值一次),所以很容易检查出没有被使用的变量并且删除对应的定义。另外如果删除v=x这样的定义还要在x的use表中把这条语句删除。

简单的常量扩展

比如v = φ(c1,c2,...,cn)这种格式,如果c都是相等的可以直接替换成c,或者v=c,如果c是常量的话也可以直接替换掉。在做这些的同时也可以做其他的优化,能够在一趟遍历中都完成,比如copy propagationx=y或者x=φ(y)都可以直接用y替换掉x。比如constant foldingx=a+b如果a+b是常量的话,可以直接用常量赋值。

当然还有其他的优化算法,出发点都是基于SSA的简单性。

从SSA转换回原始代码

y = φ(x1, x2, x3)这样的形式要根据条件分支再拆分回原来的形态,比如满足1条件,使用y=x1这样的形式。并且可能会很自然的想把x1和x2变回使用同一个寄存器,但是通过优化过程中的一些手段(copy propagation)已经把大部分move指令给优化掉了,并且重新推回x可能会有生命周期的影响,所以还是保留了“代”。

总结

其实这个就是把def-use换成了use-def方便做代码优化呀:)害我看那么久

参考文献

  1. 虎书第十九章
  2. 维基百科

有疑问加站长微信联系(非本文作者)

本文来自:yueyue.gao

感谢作者:yueyue.gao

查看原文:什么是SSA以及SSA的作用

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

6177 次点击  
加入收藏 微博
下一篇:TiDB 源码初探
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传