Golang编译优化——稀疏条件常量传播

一、概述

常量传播（constant propagation）是一种转换，对于给定的关于某个变量$x$和一个常量$c$的赋值$x\leftarrow c$，这种转换用$c$来替代以后出现的$x$的引用，只要在这期间没有出现另外改变$x$值的赋值。

如下图a的CFG所示，基本块B1中的指令$b\leftarrow 3$将常量3赋给$b$，并且CFG中没有其他对$b$的赋值。图b是对图a做常量传播的结果，此时$b$的所有出现都已被3替换，但都没有对结果得到的常数表达式进行计算（就是常量折叠，这里也可以直接结算）。

正是因为常量传播的优化操作，使得指令$b\leftarrow 3$成为无用代码（没有在其他的指令操作数中引用），死代码删除时可以将$b\leftarrow 3$删除。

在《编译器设计》总结中介绍过稀疏简单常量传播（Sparse Simple Constant Propagation，SSCP），如果常量传播掌握的不多建议仔细阅读，重点要明白半格（semilattice）。

这里将要介绍的是稀疏条件常量传播（Sparse Conditional Constant Propagation，SCCP），它和SSCP实现方法相似，只是传播方式不同，两者在CFG中处理常量传播时的主要区别如下：

• 传播方式。SCCP的常量值只沿着可达的控制流路径传播，当遇到条件分支时，只有符合条件的路径上的常量值才会被传播；SSCP则是一种更为简单的常量传播方法，它不考虑控制流条件，而是在整个控制流图中的所有路径上进行常量传播。
• 传播精度。SCCP由于只在符合条件的控制流路径上传播常量，因此稀疏条件常量传播的精度相对较高。它能够更准确地确定哪些值可以在运行时被计算为常量。SSCP稀疏简单常量传播的精度相对较低，因为它忽略了条件分支，常常会导致在一些路径上的常量传播不正确。
• 复杂度。SCCP由于考虑了控制流条件，稀疏条件常量传播的算法复杂度相对较高，但它更准确。SSCP稀疏简单常量传播的算法相对简单，但它的精度较低，可能会导致一些常量传播的机会被忽略。

二、稀疏条件常量传播

Golang中关于SCCP的实现在文件src/cmd/compile/internal/ssa/sccp.go中，算法的开始函数是sccp(f *Func) 函数。SCCP算法实现的步骤主要分为：

• 初始化worklist： 首先，需要初始化worklist中存放的必要数据结构，以便记录控制流图、变量的使用情况和 lattice 等信息。
• 构建 def-use 链： 遍历函数的基本块和值，构建每个值的 def-use 链，以确定哪些值的常量可以被传播。
• 更新值的lattice： 遍历每个基本块和其中的值，对每个值应用稀疏条件常量传播算法。这包括检查值的操作类型，确定其是否可以被折叠为常量，并根据其值更新 lattice。
• 传播常量值： 通过控制流图传播常量值。对于具有多个后继的基本块，根据条件值的 lattice 更新传播路径。
• 替换非常量值： 一旦确定了可以替换为常量的值，将其替换为相应的常量。同时，更新相应基本块的控制流以反映这些常量值的传播。

以下是我提取的 SSA IR 代码片段。接下来，将详细介绍 SCCP 算法的实现步骤，并在解释过程中引入这段代码，以帮助理解。

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 初始化worklist

worklist是一个存放多种数据结构的集合，也可以认为是SCCP算法的上下文，其结构定义如下：

type worklist struct {f            *Func               // 当前正在优化的函数edges        []Edge              // 传播时遍历CFG的edge队列，广度优先遍历uses         []*Value            // 当一个值的lattice改变时，将其使用链append其中visited      map[Edge]bool       // 记录一条edge是否传播过latticeCells map[*Value]lattice  // 值的lattice，传播过程会更新defUse       map[*Value][]*Value // 非控制值的def-use链defBlock     map[*Value][]*Block // 控制值的def-use链，控制值只在个别块中使用visitedBlock []bool              // 记录一个block是否访问过
}

初始化worklist就是初始化worklist中的数据结构，如上代码块。需要注意defUse和defBlock，其map的key是Value对象，map的value是个一维数组。

2.2 构建def-use链

def-use链是指Value的定义和使用之间的关系链，对任意一个Value的定义，都可以通过def-use链找到所有使用该Value的目标（以该Value为参数的Value）。如IR片段中的定义v6，使用过v6的Value有v10，v13和v16，所以defUse[v6] = {v10, v13, v16}。控制Value的定义，对应的使用都是Block。如IR片段中的定义v10，使用v10的Block有If，所以defBlock[v10] = {If}

这里不需要为所有的Value构建def-use链，而只为可能为常量（lattice为top或constant） 的Value构建。因为对于不可能是常量（lattice为bottom） 的Value，不管其lattice更新多少次，都会保持bottom不变。构建规则如下：

1. 如果一个Value v1的定义可能为常量，且引用v1的Value v2也可能为常量，则将v2加入到v1的def-use链defUse[v1]中；
2. 如果一个Value v1的定义可能为常量，但引用v1的Value v2不可能是常量，则不能将v2加入到v1的def-use链defUse[v1]中；
3. 如果一个Value v1的定义不可能是常量，则不用构建v1的def-use链defUse[v1]。

检测一个Value是否可能为常量由possibleConst函数实现。如果一个Value的opcode是常量操作（ConstBool、ConstString、ConstNil、Const8等），那么该Value肯定就是一个常量。如果一个Value的opcode能够满足，一旦操作数是常量，其结果肯定就是常量，那么该Value可能就是一个常量。这类opcode有算数运算、位运算、比较、转换等。

构建def-use链的过程，在buildDefUses函数中实现。其主要逻辑如下：

• 遍历函数的Block。
  • 遍历Block的Value的定义val。
    如果val与其参数arg满足上文构建规则1，则将val加入到arg对应的def-use链中，即t.defUse[arg] = append(t.defUse[arg], val)。
  • 遍历Block的控制Value ctl。
    如果ctl可能是常量，则将当前块加入到ctl对应的def-use链中，即t.defBlock[ctl] = append(t.defBlock[ctl], block)。

构建IR片段def-use链，Value和控制Value分别得到的defUse和defBlock分别如下：

defUse = map[*Value][]*Value {//def   usev5:     {v10},v6:     {v10,v13,v16},v7:     {v9,v13,v16,v18},v8:     {v9,v18},v9:     {v19},v13:    {v19},v19:    {v20},v16:    {v20},v18:    {v21},v20:    {v21},// v1不可能是常量
}defBlock = map[*Value][]*Block {//def   usev10:     {If},// v23不可能是常量
}

2.3 更新值的lattice

2.4 传播constant值

2.5 替换no-constant值