一、概述

公共子表达式消除（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

【注】关于公共子表达式的介绍，在《编译器设计》的局部值编号、可用表达式、缓式代码移动中都有与之相关的讲解。要理解CSE算法还需要知道支配性、支配者树等知识，在《编译器设计》中总结过，后面我会写文章来讲解Golang对这些的实现。

二、公共子表达式消除

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 v7v10 = Less64 <bool> v5 v6
If v10 → b3 b2b3: ← b1v13 = Add64 <int> v6 v7
Plain → b2b2: ← b1 b3v19 = Phi <int> v9 v13v16 = Add64 <int> v6 v7v18 = Add64 <int> v7 v8v20 = Add64 <int> v19 v16v21 = Add64 <int> v20 v18v23 = 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 := falsefor 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}，确定参数位置前后的情况如下：

// 参数交换之前
v9 = Add64 <int> v8 v7
v13 = Add64 <int> v6 v7
v16 = Add64 <int> v6 v7
v18 = Add64 <int> v7 v8
v20 = Add64 <int> v19 v16
v21 = Add64 <int> v20 v18// 每个参数具体的valueEqClass值
v9 => -8 -7
v13 => -6 -7    // can commutative
v16 => -6 -7    // can commutative
v18 => -7 -8    // can commutative
v20 => -19 1
v21 => 1 1// 参数交换之后
v9 = Add64 <int> v7 v8
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 => 6 7
v13 => 5 6
v16 => 5 6
v18 => 6 7
v20 => 1 3
v21 => 1 1// 排序之后						
v21 => 1 1
v20 => 1 3
v13 => 5 6
v16 => 5 6
v9 => 6 7
v18 => 6 7

接下来就是在确定参数位置、且按照参数valueEqClass值排序后的等价值中查找拆分点。查找方式是：依次比较相邻的两个值的参数，如果值所有对应位置参数的valueEqClass值相等，则这两个值之间没有拆分点，否则这两个值之间就是一个拆分点； 将找到的拆分点存放在数组splitPoints中，等一组值的所有拆分点找完后，再利用splitPoints作拆分操作。

对于等价值{v9,v13,v16,v18,v20,v21}，找到的拆分点是{1,4}，所以数组splitPoints = {0,1,4}。拆分点就是等价值数组的下标。

最后是按照差分点拆分等价值，也就是将一组等价值按照拆分点拆分为多组等价值。如果一组等价值没有拆分点，则结束当前遍历不执行循环中的后续代码，即不进行拆分操作。不执行拆分操作，也就不会执行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。
• 如果拆分的等价值有多条指令，则给这一组值赋一个新的标号，并将其append至partition。

【结】至此，细分等价值的所有操作都已经介绍完，剩下的就是重复这些操作，直到所有的等价值都不可拆分。可以思考一个问题：2.2.2小节贴的两层循环的代码，能保证最终退出循环或者退出循环后能保证等价值是最细分的嘛？答案是肯定的，但可以想想为什么。

2.3 替换重复表达式

2.3 .1 按照支配性排序

2.3 .2 进行替换操作