一、概述
公共子表达式消除(Common Subexpression Elimination,CSE)也有书上称为冗余表达式消除,旨在减少程序中重复计算相同表达式的次数,从而提高程序的执行效率。
在程序中,如果同一个表达式在不同的地方多次出现并且具有相同的输入,则这个表达式就是一个公共子表达式。公共子表达式消除的目标是识别这些重复的表达式,并将它们计算一次,然后在需要时重用结果,而不是每次都重新计算。
以下是一个简单的公共子表达式:
x = b + c
y = a - d
z = b + c
在这个例子中,表达式 b + c
在两个地方都出现了,它是一个公共子表达式。如果程序执行这两个语句,那么每次都重新计算 b + c
,这可能会浪费计算资源。通过公共子表达式消除优化,可以将这个表达式计算一次,然后将结果存储起来,以后需要时直接使用存储的结果,而不是重新计算。
通过公共子表达式消除优化后的代码如下所示,程序就不再重复计算表达式b + c
,而是引用已经计算的值x
。
x = b + c
y = a - d
z = x
【注】关于公共子表达式的介绍,在《编译器设计》的局部值编号、可用表达式、缓式代码移动中都有与之相关的讲解。
二、公共子表达式消除
Golang中关于CSE的实现在文件src/cmd/compile/internal/ssa/cse.go中,算法的开始函数是cse(f *Func) 函数。CSE算法实现的步骤主要分为:
- 初始划分等价值:算法会遍历函数中的每个基本块(Block),然后遍历每个基本块中的每个值(Value)。在遍历过程中,根据一组规则,将具有相同特征的值初始的划分为一组等价值,依赖规则在cmpVal(…)函数中。
- 细分等价值:初始划分后,算法会进一步细分等价值,直到无法继续细分为止。细分等价值的过程主要是根据值的参数进行判断,如果一组等价值的参数不是等价值,则将其分割成不同的等价值。在细分等价值的过程中,算法会对每组等价值按照一定的顺序进行排序,以便进行比较和查找。
- 替换重复表达式:细分等价值后,算法会对每组等价值选择一个代表值,然后将该等价值中的其他值替换为代表值。替换过程中,算法会检查值的参数是否符合支配关系,以确保替换后不会破坏程序的语义。在替换过程中,算法会记录替换的次数,以便在分析完成后进行统计和优化。
以下是我提取的 SSA IR 代码片段。接下来,将详细介绍 CSE 算法的实现步骤,并在解释过程中引入这段代码,以帮助理解。
b1:
v1 = InitMem <mem>
v5 = Const64 <int> [0]
v6 = Const64 <int> [1]
v7 = Const64 <int> [2]
v8 = Const64 <int> [3]
v9 = Add64 <int> v8 v7
v10 = Less64 <bool> v5 v6
If v10 → b3 b2
b3: ← b1
v13 = Add64 <int> v6 v7
Plain → b2
b2: ← b1 b3
v19 = Phi <int> v9 v13
v16 = Add64 <int> v6 v7
v18 = Add64 <int> v7 v8
v20 = Add64 <int> v19 v16
v21 = Add64 <int> v20 v18
v23 = MakeResult <int,mem> v21 v1
Ret v23
2.1 初始划分等价值
在cse(f *Func) 函数中,首先遍历所有基本块的所有值,只要值的返回值类型不是mem
,将其都存入数组a
中。类型相关的操作会有不稳定性。比如在一个代码中有v3 = Load v1
,v8 = Load v1
两个值,v8
的定义看似冗余,可以用v8 = v3
去替换,实则不可。因为我们不确定数据从v3
到v8
流动的过程中,是否有Store
操作在v1
地址写入了新的值。
IR片段中的值存入数组a中后如下:
a = {v5,v6,v7,v8,v9,v10,v13,v19,v16,v18,v20,v21}
以数组a
为参数,调用partitionValues函数,对数组中的值排序后再进行初步分类。排序和分类依赖cmpVal(v, w *Value, …)函数,调用其依次比较v
和w
的:opcode、auxint、参数个数nargs、如果值是Phi
还需比较两个值是否在同一个块中、aux。如果这些属性全部相等,则v
和w
可划分为一组初始等价值。
将IR代码片段带入到这部分算法中,重排后的数组a
和初步划分得到的等价值数组partition
如下。partition
是个二维数组,每一项元素都是一组等价值,且任何一组等价值Value的个数都是大于1
的。一组等价值只有一条指令Value,说明程序中没有该指令的公共子表达式,不需要消除,所以也就没有必要将其加入到partition
数组进行分析。
// 排序后的a
a = {v9,v13,v16,v18,v20,v21,v10,v19,v5,v6,v7,v8}
// 初步划分得到的等价值
partition = {
{v9,v13,v16,v18,v20,v21},
}
2.2 细分等价值
细分等价值的过程主要是根据值的参数进行判断,如果一组等价值的参数不是等价值,则将其分割成不同的等价值。
2.2.1 给所有值标号
为了更好的完成这一过程,定义了一个数组valueEqClass
,其下标Values.ID
对应的值是对Value的一个标号。非等价值都有自己独一无二的标号(为-v.ID
),而一组等价值的标号是相同的。valueEqClass
数组中对值的标号,在细分等价值的过程中发挥着很重要的作用。
首先将遍历函数的所有值,执行valueEqClass[v.ID] = -v.ID
,将每个值在数组valueEqClass
中对应的项初始化为-v.ID
。然后再遍历等价值数组partition
,将一组等价值的Value在valueEqClass
数组中对应下标的元素改成相同的值。
经过上面操作后,valueEqClass
中的值如下所示。valueEqClass
是个一维数组,我为了方便理解写成了下面这种形式,实际上写成[v1.id], [v5.id], ... ,[v21.id], [v23.id]
这种形式更贴合其排列结构。
// 此时标号数组的值
valueEqClass[v1.ID] = -1
[v5.ID] = -5
[v6.ID] = -6
[v7.ID] = -7
[v8.ID] = -8
[v10.ID] = -10
[v19.ID] = -19
[v23.ID] = -23
[(v9,v13,v16,v18,v20,v21).ID] = 1
2.2.2 根据参数细分等价值
根据参数细分等价值,就是比较等价值的参数,如果一组等价值的参数是非等价值,则将其拆分成多组等价值。重复这一动作,直到所有的等价值都不可拆分。
下列代码就是重复拆分等价值直至不可拆分的逻辑。当遍历一次数组partition
后,如果changed
的值没有被改成true
,说明等价值已经不可拆分(留意代码满足什么条件时不会改变changed
的值)。遍历数组partition
的每一组等价值时,对一组等价值做一下操作:确定值的参数位置、按照参数的valueEqClass
值为等价值排序、寻找一组等价值的拆分点、按照差分点拆分等价值。
for {
changed := false
for i := 0; i < len(partition); i++ {
// 确定值的参数位置
// 按照参数的valueEqClass值为等价值排序
// 寻找一组等价值的拆分点
// 按照差分点拆分等价值
changed = true
}
if !changed {
break
}
}
确定值的参数位置,是为了消除具有交换性的操作(加法、乘法等)给细分等价值带来的错误判断。如a + b
与b + a
其实是等价的,但是算法判断时会误以为其不等价,我们要避免这种情况。代码中结构type opInfo struct
的commutative
字段用来表示一个值的参数是否具有交换性,true
为可交换,false
为不可交换。
- 如果一个值的参数不具有交换性,则不用对其进行任何操作;如
v10 = Less64 <bool> v5 v6
。 - 如果一个值的参数具有交换性,则将参数
valueEqClass[value.ID]
值较小的放在前面。如:v13 = Add64 <int> v6 v7 valueEqClass[v6.ID] = -6 valueEqClass[v7.ID] = -7 // 因为 -6 > -7 ,所以将两个参数的位置调换 v13 = Add64 <int> v7 v6
对于等价值{v9,v13,v16,v18,v20,v21}
,确定参数位置前后的情况如下:
// 参数交换之前,及每个参数具体的valueEqClass值
v9 = Add64 <int> v8 v7 // (-8 -7)
v13 = Add64 <int> v6 v7 // (-6 -7 ) can commutative
v16 = Add64 <int> v6 v7 // (-6 -7 ) can commutative
v18 = Add64 <int> v7 v8 // (-7 -8) can commutative
v20 = Add64 <int> v19 v16 // (-19 1)
v21 = Add64 <int> v20 v18 // (1 1)
// 参数交换之后
v9 = Add64 <int> v8 v7
v13 = Add64 <int> v7 v6 // commutative
v16 = Add64 <int> v7 v6 // commutative
v18 = Add64 <int> v8 v7 // commutative
v20 = Add64 <int> v19 v16
v21 = Add64 <int> v20 v18
按照参数的valueEqClass
值为等价值排序。一组等价值对应的valueEqClass
值是相等的,如{v9,v13,v16,v18,v20,v21}
的valueEqClass[(v9,v13,v16,v18,v20,v21).ID] = 1
;而每一个值的参数的valueEqClass
值不一定相等,所以需要对交换参数后的等价值排序。
对于两个等价值,按照参数的个数,排序规则如下:
- 将两个值的第一个参数比较,
valueEqClass
值小的放在前面,大的放在后面,相等则保持位置不变。 - 如果第一个参数相等,再比较第二个参数,
valueEqClass
小的放在前面,大的放在后面。 - 第一、二个参数都相等,再比较第三个。最多只能有三个参数。
对于{v9,v13,v16,v18,v20,v21}
这一组交换参数后的等价值,排序前后的变化如下:
// 排序之前
v9 = Add64 <int> v8 v7 // (-8 -7)
v13 = Add64 <int> v7 v6 // (-7 -6)
v16 = Add64 <int> v7 v6 // (-7 -6)
v18 = Add64 <int> v8 v7 // (-8 -7)
v20 = Add64 <int> v19 v16 // (-19 1)
v21 = Add64 <int> v20 v18 // (1 1)
// 排序之后
v20 = Add64 <int> v19 v16 // (-19 1)
v9 = Add64 <int> v8 v7 // (-8 -7)
v18 = Add64 <int> v8 v7 // (-8 -7)
v13 = Add64 <int> v7 v6 // (-7 -6)
v16 = Add64 <int> v7 v6 // (-7 -6)
v21 = Add64 <int> v20 v18 // (1 1)
// 存放等价值的二维数组也会跟着变化
partition = {
{v20,v9,v18,v13,v16,v21},
}
接下来就是在确定参数位置、且按照参数valueEqClass
值排序后的等价值中查找拆分点。查找方式是:依次比较相邻的两个值的参数,如果值所有对应位置参数的valueEqClass
值相等,则这两个值之间没有拆分点,否则这两个值之间就是一个拆分点; 将找到的拆分点存放在数组splitPoints
中,等一组值的所有拆分点找完后,再利用splitPoints
作拆分操作。
对于等价值{v20,v9,v18,v13,v16,v21}
,找到的拆分点是{1,3,5}
,所以数组splitPoints = {0,1,3,5}
。拆分点就是等价值数组的下标。
最后是按照差分点拆分等价值,也就是将一组等价值按照拆分点拆分为多组等价值。如果一组等价值没有拆分点,则结束当前遍历不执行循环中的后续代码,即不进行拆分操作。不执行拆分操作,也就不会执行changed = true
。如果所有的等价值都找不到拆分点,则changed = false
的值不会改变,说明所有的等价值都不可拆分。
拆分等价值时,将存放所有等价值的数组partition
的最后一项(最后一组等价值),移到当前遍历的等价值位置。实现代码如下:
partition[i] = partition[len(partition)-1]
partition = partition[:len(partition)-1]
再将拆分的多组等价值满足条件的组,从partition
的最后一项位置(会将其覆盖,因为已经移到前面)开始追加(append)至其中。条件的具体限定如下:
- 拆分的等价值只有一条指令,说明其已是非等价值,则不需要将其append至
partition
。原因之前已经解释过:一组等价值只有一条指令Value,说明程序中没有该指令的公共子表达式,不需要消除,所以也就没有必要将其加入到partition
数组进行分析。执行valueEqClass[f[0].ID] = -f[0].ID
将非等价值的标号改为其-v.ID
。 - 如果拆分的等价值有多条指令,则给这一组值在
valueEqClass
对应的项上赋一个新的标号,并将其append至partition
。
将等价值{v20,v9,v18,v13,v16,v21}
按照其拆分点{1,3,5}
拆分后,变成四组值,分别是:{v20}
、{v9,v18}
、{v13,v16}
、{v21}
。其中{v9,v18}
和{v13,v16}
会被append到partition
数组中,{v20}
和{v21}
则会变成非等价值。此时标号数组valueEqClass
和等价值数组partition
的状态如下:
// 此时标号数组的值
valueEqClass[v1.ID] = -1
[v5.ID] = -5
[v6.ID] = -6
[v7.ID] = -7
[v8.ID] = -8
[v10.ID] = -10
[v19.ID] = -19
[v20.ID] = -20
[v21.ID] = -21
[v23.ID] = -23
[(v9,v18).ID] = 2
[(v13,v16).ID] = 3
// 此时等价数组的状态
partition = {
{v9,v18},
{v13,v16}
}
第一次对partition
遍历之前,其中只有一组等价值,且遍历过程对其进行了拆分。第二次对partition
遍历之前,其中有两组等价值,遍历过程中分析发现其不可拆分。至此,所有的等价值都不可拆分,细分等价值任务已经完成。
// 第一次遍历之前的partition
partition = {
{v20,v9,v18,v13,v16,v21},
}
// 第二次遍历之前的partition
partition = {
{v9,v18},
{v13,v16}
}
2.3 替换重复表达式
细分等价值得到的等价值数组partition
,其中的每一组等价值都可以看作是一组重复的表达式。这些重复表达式并不能随意消除,要看其Value所在块的支配性,只有一个块b1
支配另一个块b2
(也就是b1
是b2
的支配者)时,才能用b1
中的Value消除b2
中的Value。
假设有如下所示的CFG和Value,其中a、b、c、d均为常量。b1
的支配者为b1
,b2
的支配者为{b1,b2}
,b3
的支配者为{b1,b3}
,b4
的支配者为{b1,b4}
。
可以用v1
消除v4
,即v5 = v1 + v2
,因为v1
所在块b1
支配v4
所在块b4
。v2
和v3
之间无法消除,因为b2
不支配b3
,b3
也不支配b2
。
2.3 .1 按支配性排序并找出替换关系
关于支配性相关的知识,这里只介绍这么多。在《编译器设计》中总结过支配性、支配者树等知识,后面我会写文章来讲解Golang对这些内容的实现。
将等价值按照支配性排序。调用f.Sdom().domorder(v.Block)
会返回一个值,排序则依赖这个值的大小。对于x
、y
和z
三个基本块,作为参数分别调用domorder()
函数,得出的值适用于如下规则:
- 规则1:如果
domorder(x) > domorder(y)
则x
不支配y
。 - 规则2:如果
domorder(x) < domorder(y)
且domorder(y) < domorder(z)
且x
不支配y
,那么x
也不支配z
。 - 规则3:如果
domorder(x) < domorder(y) < domorder(z)
且x
支配y
但不支配z
,那么y
也不支配z
。
检查两个块的支配关系。调用f.Sdom().IsAncestorEq(x, y *Block)
检查在支配者树中x
是否为y
的祖先结点或者x
等于y
,也就是检查x
是否支配y
。
既然可以直接检查两个块的支配关系,是否还有必要将等价值按照支配性排序呢?答案是有必要的,可以降低算法的时间复杂度。懒得解释了,很容易推出来,由O(n^2)
降为O(n log n)
。
遍历等价值数组partition
;将一组等价值e
按照支配性排序,再遍历e
中的值;如果e[i].Block
支配e[j].Block
,0 <= i < j < len(e)
,则可以使用e[i]
代替e[j]
,rewrite[e[j].ID] = e[i]
;重复以上过程直至partition
遍历完成。
将我们的IR代码片段的等价数组带入此算法,得到的替换关系数组rewrite
如下:
// 将partition带入到算法
partition = {
{v9,v18},
{v13,v16}
}
// 得出的替换关系数组
rewrite[v18.ID] = v9
[v16.ID] = v13
2.3 .2 进行替换操作
遍历所有块的所有值,根据替换关系数组rewrite
替换Value的参数和ControlValues。以rewrite[v18.ID] = v9
为例,说明v18
可以被v9
替换,因此:所有引用v18
的Value的参数,都要替换成v9
;所有以v18
作为控制判断的ControlValues,也要替换成v9
。文章来源:https://www.toymoban.com/news/detail-860939.html
完成替换操作后的IR代码片段如下。替换完成后,v16
和v18
会变成死代码,在死代码删除时会将其删除。文章来源地址https://www.toymoban.com/news/detail-860939.html
b1:
v1 = InitMem <mem>
v5 = Const64 <int> [0]
v6 = Const64 <int> [1]
v7 = Const64 <int> [2]
v8 = Const64 <int> [3]
v9 = Add64 <int> v8 v7
v10 = Less64 <bool> v5 v6
If v10 → b3 b2
b3: ← b1
v13 = Add64 <int> v6 v7
Plain → b2
b2: ← b1 b3
v19 = Phi <int> v9 v13
v16 = Add64 <int> v6 v7 // become deadcode
v18 = Add64 <int> v7 v8 // become deadcode
v20 = Add64 <int> v19 v13 // v16 => v13
v21 = Add64 <int> v20 v9 // v18 => v9
v23 = MakeResult <int,mem> v21 v1
Ret v23
到了这里,关于Golang编译优化——公共子表达式消除的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!