Golang编译优化——消除Copy指令

一、优化概述

以下是Go编译器对某个代码段编译生成的SSA IR摘选，对于Golang SSA IR的介绍我写了文章，但是在犹豫要不要发。

b1:-...
Plain → b2 (5)b2: ← b1 b4-v9 (5) = Phi <int> v8 v16 (i[int])v22 (8) = Phi <int> v7 v14 (r[int])v10 (5) = Copy <int> v6 (n[int])v11 (+5) = Leq64 <bool> v9 v10
If v11 → b3 b5 (likely) (5)b3: ← b2-v12 (6) = Copy <int> v22 (r[int])v13 (6) = Copy <int> v9 (i[int])v14 (+6) = Add64 <int> v12 v13 (r[int])
Plain → b4 (6)

编译器在中间代码生成和优化阶段，不可避免的会生成一些非必要的指令，如上面b3块中的copy v22 to v12，copy v9 to v13。消除Copy指令的操作会遍历所有IR，迭代找到Copy指令的最终引用，将其替换到合适的位置。

下列v14 = Add64 v12 v13，引用参数v12和v13会分别替换为其指令的参数v22和v9。而v12和v13这两条指令如果在其他地方都没有引用，它将变成死代码，会在后续的死代码删除优化（以后会写文章来讲解）中将其消除。

v12 (6) = Copy <int> v22 (r[int])
v13 (6) = Copy <int> v9 (i[int])
v14 (+6) = Add64 <int> v12 v13 (r[int])Copy 指令消除后 ==>v12 (6) = Copy <int> v22 (r[int])
v13 (6) = Copy <int> v9 (i[int])
v14 (+6) = Add64 <int> v22 v9 (r[int])

二、具体实现

消除Copy指令的实现逻辑在src/cmd/compile/internal/ssa copyelim.go中，由三个函数来完成。

copySource(v *Value)函数，从Copy指令的参数迭代查找，直至找到第一个非Copy的操作，并将其返回。形如：

for w.Op == OpCopy {w = w.Args[0]
}

对于下列代码块，copySource(v2)返回v0。

v0 = Def...
v1 = Copy v0
v2 = Copy v1
v3 = Add64 v2 v0

Copy的引用链路可能会形成一个环，比如在一些特殊的情况下，会出现以下情况。这在迭代时就要考虑如何处理这种情况的发生，copySource函数采用了快慢指针来判断是否存在环。如果有环存在，说明这一系列操作是存在歧义的，copySource会将快慢指针的交汇点修改成Unknown，其也将会变成死代码。

v0 = Copy v2    // copy v1也是一个环
v1 = Copy v0
v2 = Copy v1
v3 = Add64 v2 v0

迭代一旦完成，copySource(v *Value)的参数v的指令参数将会被设置成Copy链的第一个非Copy指令值。如下列代码v2的引用参数v1变成了v0，剩下的v1如果在其它地方没有引用，将会变成死代码。

v0 = Def...
v1 = Copy v0
v2 = Copy v1	=> v2 = Copy v0
v3 = Add64 v2 v0

copyelimValue(v *Value) 函数，这个函数确保指令v的所有参数都不是Copy指令。它遍历一个指令的所有参数，如果参数a是Copy，则调用copySource(a)找到Copy链第一个非Copy指令，并用其替换参数a。

v0 = Def...
v1 = Copy v0
v2 = Copy v1
v3 = Add64 v2 v0调用copyelimValue(v3)后 =>v0 = Def...
v1 = Copy v0
v2 = Copy v0
v3 = Add64 v0 v0

copyelim(f *Func)函数，它遍历函数中的每个基本块，然后遍历每个基本块中的每个值，并调用copyelimValue函数，该函数确保每个值的参数都不是Copy的结果。