php optimizer about ssa

0x01 e-SSA Pis

在SSA我们经常能听见Phi,那么什么是Pi呢?,Pi就是一个特殊的Phi,它有range和constraint.,例如:

1
2
3
4
5
if($a>5){
$a = pi($a) > 5
//..
}
$a = phi($a) <= 5 ???

在路径条件的约束下,转头去执行不同路径分支时,某些变量就自动的满足了约束,但是有些情况我们是可以确定的,比如插入的第一个pi,但是第二个的phi的约束不一定完全正确,因为if分支可能影响$a的值。

php里面只考虑条件分支影响下的局部约束,记录一下几种特殊的约束法则的应用。

  • $a > 5 很显然的约束
  • $a + 5 == 0 这里可以做一个变换 $a = 0 - 5 ,分两种情况讨论即
  • $a + 5 == $b +6 同样这里也可以做变换 $a = $b+((-5)-(-6))$a+((-6)-(-5)) = $b. 这里的range除了constant还有其他变量的依赖. 这里为什么要写成上述的形式,我是按照php里面的计算方式来的,他会有一个操作数的adjustment,比如上面equal的RHS操作数的adjustment就是-5. 同理LHS操作数的adjustment是-6. 最后需要把$a$b都单独表示表示出来,就需要adjustment之间做一下运算了.

上述提到的只是php中关于range的特殊约定格式,你也可以写出自己独特的约定。局部约束真的还是挺优雅的。

考虑几种情况不需要插

  1. 变量在target位置并不活跃,只用了一次,后面就不用了,我们在target位置插入一个,没有什么意义.

  2. 依赖于incoming edge,如果有两条相同的incoming edge就不插,这是什么意思呢? 两条相同的incoming edge会无法区分pi是属于哪条edge. 但是我好奇什么时候会导致有两条相同的incoming edge,真奇怪?

  3. 还有一种非常特殊的情况,首先给一个definition: incoming edge定义为从'from'到'to',我们需要在to这里插入pi,我们考虑插入的pi目的是在to这里添加constraint,给我们后面的分析带来一些便利,但是可能你添加constraint是冗余的,举个例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    $a = $b??$c;

    /*
    *1: T1 = ZEND_COALESCE $b,3

    *2: T1 = QM_ASSIGN $c

    *3: ASSIGN $a,T1
    */

    这里有3行opcode对应了三个blocks,第1行这里是可以尝试给第3行这里添加一个pi的,因为如果从第1行跳到第3行,那么$b肯定不是null. 自然地我们可以在第3行这里添加一个pi断言$b不是null. 但是这没有意义,因为如果执行了第2行,那么第3行这里$b又是一个null,相当于之前添加的那个pi没有任何effort在这里起作用,即. 我们$b是什么还是一无所知.

    所以我们需要识别可能某个opcode造成的两种互斥的约束是否会merge,如果互斥的值同时可能流到to上,那我们去添加pi几乎没有任何意义的,幸运是,当前php的control flow相关的opcode都只有两个successors,所以我们可能不用考虑多个互斥的值同时作用.

    所以我们现在需要考虑from另外的successor(除了from到to的这条edge),我们记为other. 那么具体的问题是other到to是否有一条路径,并且这条路上,里面constraint对应var没有发生变化?.

    其实这个问题回答其实是比较复杂的,因为找路径的同时你还要去关注var没有发生变化. php里面只做了最简单的优化. 记住我们在这里考虑要不要插pi,只是为了避免冗余的constraint,并不是说不能插,也就是说即使插了也是safe的. 所以尽量能减少多少算多少)php在这里会直接考虑to的直接前驱predecessor,如果predecessor里面的var发生变化了,不用想,经过这个predecessor都不会在我们的考虑范围之内了. 如果var没有发生变化,我们就要考虑other到这个predecessor有没有一条路径了,判断有没有路径最简单的方法就是看other是不是这个predecessor的dominator. (笑死!!!!) 再结合我们的问题下一步就显而易见了,有路径不插入pi, 实际上这个是不太准确的,我们在这里只知道有路径,但是路径具体是那条我们并不知道,并且在predecessor前面的路径上的节点var有没有发生变化,我们也是不知道. 所以这里只是作者的小推测. 其他我们没有提到的情况都会插入pi.

    这里考虑如果插入的是prefect pi,那么它是真的有作用的. 如果插入是冗余的pi,这个constraint会造成一些错误吗?因为整个模式都偏向于不要插(留下这个问题,我要去看inference). 但是实际是要插入,而导致没有插入,将会导致后面inference的精度降低.

    exmaple

0x02 SSA Definition

  • 在SSA表示下,任意状态下的某个变量使用,只有一个var definition能够生效。
  • 程序的控制流在SSA下保持不变。
  • 有一个特殊的merge操作,用于处理多个前驱node的变量definition的交汇取值。
  • 并不是所有node交汇处都需要
  • 自然地如果在交汇处所有前驱node对某个变量的definition都相同,则不需要使用
  • use-def analysis is faster on SSA (application)。
  • SSA to machine code???

如何精确的插入phi呢?

single reaching-definition: A definition of variable reaches a point in the CFG if there exists a path from to that does not pass through another definition of . (简而言之就是变量的definition和use之间只有一条确定的路径,且变量的值没有改变).

直觉上如果有两个distinct 基本块,他们都有关于同一个变量的definition,并且存在一个是它们一个join node即存在非空路径.那么我们应该在的开头插入,但是这样做可能会导致一些不必要的插入,所以在插入时候,考虑了minimality的问题,理论上我们需要去掉single reaching-definition的情况,所以这里就引入的join set的,它就表示了对于每个变量的应该至少需要插入的个数.

Join Set Definition 给定图上的节点集合, 表示一些特殊节点的集合(通常表示某个变量的Assignment BBs):

给定 , 至少有两条来自不同起始节点()的路径在点交汇,且这样的路径之间除了点以外不应该有其他相同的节点(也就是说之间只有一个交点),则

的迭代操作表示为,定义如下: 这样迭代的意义是什么呢? 如果给定的是某个变量被赋值的节点,即下面红色节点,得到了蓝色的结点,得到了绿色结点.这样做的目的就可以找到所有的变量的definition交汇的结点,其实也就是需要放置的位置。

it-of-ssa

如何实现?为什么说在所有上插很浪费?举个例子说明中的某个不需要插 我还真找不到!!!!!! retard author(https://iith.ac.in/~ramakrishna/fc5264/ssa-intro-construct.pdf), join set 本身的提出就是为了解决minimality...

那么如何让插函数变得efficient呢?就需要用到dominator tree和dominance frontier的概念,dominator tree就不用介绍了,主要把dominance frontier的概念弄清楚,这个概念是相对于某个结点来说的,即某个dominator tree上结点的dominance frontier:

给定某个结点,表示的dominance frontier,若, 则之间存在一条路径,且是这条路径上第一个不支配的结点,如果换一句话来说就是如果如果在dominator tree上有前驱,且这个前驱不是最后支配这个前驱结点.

dominance frontier

为什么dominance frontier可以帮助我们解决在哪里插入 如果某个变量在结点下定义,理论上变量可能会被传到所有被它严格支配的结点上,当变量抵达dominance frontier时,就要考虑其他来自其他结点的是否也有关于变量的定义,这是最初的直觉。

那么如何计算呢?

how-to-compute-df

这算法很神奇啊,从每个结点的每个前驱开始,让在dominator tree上向上回溯,直到碰到停止,中间所有遇到的结点都把扔到它们的里面去。让我想想这背后的直觉到底是什么?

  1. 首先这个算法并不是一开始就对某个点寻找它的df,而是在确定是谁的df? 所以算法一开始从的前驱开始。
  2. 再看这其中while循环的limit,在从点的某个前驱开始时,如果 dom , 那么我们实际上已经不能接着分析下去了,因为我们考虑所有从开始过点到的路径,且 dom , 那么马上就可以得到 dom . 所以再接着分析所有过的路径已经没有什么意义了.
  3. 回溯dominator tree可以保证到过的路径存在,且路径的开始 dom . 这是很自然的,如果 不是dom 的,那么我们自然要考虑的所有dominators, 所以从idom(p)开始考虑所有合理的dominators.

还有一个小问题,为什么可以保证一定可以碰到,因为的前驱,有几种情况:

  1. 就是. 这是trivial的

  2. 如果不是,我们需要证明也必须是的dominator,假设不是的dominator,则存在一条经过不经过的路径抵达,产生矛盾了不支配.所以的一个dominator,所以往上回溯总可以碰到.

  3. 为什么回溯dominator tree的时候可以把扔到里面去呢?我们知道这条dom-tree回溯路径上的节点都是严格支配前驱结点的,但是并不严格支配,所以.

    这里也需要一个小lemma,dominator tree上的路径并不是CFG中的真实路径:

    dominator tree上任意两点,, 如果他们之间有一条路径, 不失一般性假设的level小于的level,那么也可以在CFG上找到一条的路径,且支配这条路径上的所有结点。

    proof: 假设不存在这样的路径,即所有这样的路径,都不完全支配其上的所有点,那么总可以找到一条从start不经过的路径,这和 dom 是矛盾. 所以原命题得证。

其实还可以证一下这样得到的是不是完全的,也就是说在用上面lemma找的过程是完全的,其实是完全的,因为这东西是依赖于dominator tree的.

0x03 SSA Construction

  1. 变量声明周期的维护,保证runtime阶段所有definition reachable且任一程序点某一时间点只有一个definition起作用.
  2. 每个变量只有一次的赋值机会,即每次assignment的左端的变量名都是独一无二的,保证definition的唯一性.

phi-insertion

这个算法看起来也很简单,先收集所有的变量的defBB, 丢到worklist里面,然后one by one算支配边界,在支配边界上插, 同时这个支配边界也变成了一个变量的defBB,直到worklist空为止.

直觉上是ok的,所有变量的defBB都会被考虑到,所以是不会漏掉,但是可能会造成不是minimal的,因为需要考虑一下是否used情况.

variable-renaming

让我们来推理一下这算法这背后的直觉?

这个过程里面糅杂了reachingDefinition的东西,这玩意儿就是一个definitions cache,也正是我们处理和use-def时候需要的, 大循环遍历所有基本块,内在两个小循环,一个小循环遍历每个instruction,另外一个小循环更新后继的phi的use. 在遍历每一个instruction的时候,我们需要先更新当前instrument的use-var,再考虑是否有def-var的情况. 在更新use-var时候,我们找离这个instrument最近的对应var的definition,注意这是是排除了phi函数的,phi函数的use-var由它的前驱负责更新. 如果有def-var的情况,我们需要考虑给def-var重命名,并且更新原var名的definition, 让后面的instruction在更新use-var的时候,使用这个新命名的变量名. 最后处理完当前的基本块所有instruction之后,更新后继节点的中phi函数可能用到的use-var.

这个reachingDefinition的record到底是如何实现的呢? 注意在上述在处理def-var的时候,会把老的definition和新的definition串起来,实际上这个record结构是一个list,在一个bb内原来相同var definition都是串起来了. 那么在不同的基本块之间definition又是如何传递的呢? 我们来考虑为什么updatedefinition就是找closest definition that dominates i?

传递过程就发生在上图中的更新successor中的phi函数use-var,但是我实在没有看懂在更新之前,为什么要updateReachingDef一下,如果当前bb不是dominate这个successor,那么所有新的var-definition不就清除了吗?图片来自ssabook,如果不出意外的话确实是错了...

use-def-chain
  1. 为什么要深度遍历dominator tree?

    我们目的是给每个assignment的左边重命名,把assignment右边的变量名再修正. 所谓重命名就是给某一变量在重新被赋值的时候,给变量名加了一个下标,这个东西叫version. 为了控制version我们需要有序东西存在,采用dominator tree有几个好处:

    1. tree!!! 它里面肯定没有环,不用考虑什么back-edge...
    2. 还有就是深度遍历,其实你可以理解为先序遍历,只要你是standard dominator tree(children从左到右,从大到小),在处理每一个基本块的时候,都能保证前面的过程执行完整,就是该到你这的definition 都会 reach! 不会存在有一个理论上definition到不了你这里. 画个图就能理解.