德阳移动网站建设,设计app界面,移动应用开发干什么的,iis网站目录权限设置文章目录 一、概述二、稀疏条件常量传播2.1 初始化worklist2.2 构建def-use链2.3 更新值的lattice2.4 传播constant值2.5 替换no-constant值 一、概述
常量传播#xff08;constant propagation#xff09;是一种转换#xff0c;对于给定的关于某个变量 x x x和一个常量 c … 文章目录 一、概述二、稀疏条件常量传播2.1 初始化worklist2.2 构建def-use链2.3 更新值的lattice2.4 传播constant值2.5 替换no-constant值 一、概述
常量传播constant propagation是一种转换对于给定的关于某个变量 x x x和一个常量 c c c的赋值 x ← c x\leftarrow c x←c这种转换用 c c c来替代以后出现的 x x x的引用只要在这期间没有出现另外改变 x x x值的赋值。
如下图a的CFG所示基本块B1中的指令 b ← 3 b\leftarrow 3 b←3将常量3赋给 b b b并且CFG中没有其他对 b b b的赋值。图b是对图a做常量传播的结果此时 b b b的所有出现都已被3替换但都没有对结果得到的常数表达式进行计算就是常量折叠这里也可以直接结算。 正是因为常量传播的优化操作使得指令 b ← 3 b\leftarrow 3 b←3成为无用代码没有在其他的指令操作数中引用死代码删除时可以将 b ← 3 b\leftarrow 3 b←3删除。
在《编译器设计》总结中介绍过稀疏简单常量传播Sparse Simple Constant PropagationSSCP如果常量传播掌握的不多建议仔细阅读重点要明白半格semilattice。
这里将要介绍的是稀疏条件常量传播Sparse Conditional Constant PropagationSCCP它和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 memv5 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 v232.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有v10v13和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不变。构建规则如下
如果一个Value v1的定义可能为常量且引用v1的Value v2也可能为常量则将v2加入到v1的def-use链defUse[v1]中如果一个Value v1的定义可能为常量但引用v1的Value v2不可能是常量则不能将v2加入到v1的def-use链defUse[v1]中如果一个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值
