当前位置：首页 > news >正文

llvm数据流分析

news 来源：原创 2025/8/21 15:40:37

llvm数据流分析

1.数据流分析
2.LLVM实现
- 2.1.常量传播
- 2.2.活跃性分析

相关参考文档：DataFlowAnalysisIntro、ustc编译原理课程、南大程序分析课程1、南大程序分析课程2。

1.数据流分析

数据流分析在编译优化等程序分析任务上都有重要应用。通常数据流分析可被抽象为一个IFDS-based worklist算法。核心是给每个CFG结点 $s$ (结点表示一个语句或者基本块)计算两个集合 $\text{IN}[s]$ 和 $\text{OUT}[s]$ 。

meet运算: $\text{IN}[s] = \text{meet}_{s_i \in \text{prev}(s)} \text{OUT}[s_i]$ ， $\text{meet}[s] = \cup_{s_i \in \text{next}(s)} \text{IN}[s_i]$ (反向数据流传播任务)。
update: $\text{OUT}[s] = \text{gen}[s] \cup (\text{IN}[s] - \text{kill}[s])$ , $\text{IN}[s] = \text{gen}[s] \cup (\text{OUT}[s] - \text{kill}[s])$ (反向数据流传播任务)。通常具体实现中 $\text{gen}$ 和 $\text{kill}$ 可由update操作完成。

数据流分析的worklist算法 (前向) 如下。worklist算法会不断循环直到 $\text{IN}[s]$ 和 $\text{OUT}[s]$ 收敛（集合不再变大）为止。 $\text{IN}[s]$ 和 $\text{OUT}[s]$ 的元素为fact，fact的具体类型视数据流分析任务而定。需要注意的是这个分析框架是flow-sensitive & path-insensitive的，path-sensitive的分析（符号执行）不会有 meet 操作，而是直接将当前分析状态 fork 多份然后将每个 fork 后的状态单独添加到 worklist中。

def DataFlowAnalysis(cfg: CFG):for stmt in CFG:worklist.append(stmt)Out[stmt].clear()while (!worklist.empty()):cur_stmt = worklist.pop()for prev_stmt in Prev(cur_stmt):meet(In[cur_stmt], Out[prev_stmt])changed = update(cur_stmt, Out[cur_stmt], In[cur_stmt])if (changed):worklist.append(cur_stmt)

数据流分析任务	方向	meet操作	fact	示例	`gen`	`kill`
到达定值分析 (reaching-define analysis)	前向	$\cup$	变量定义	`l: x = a`	`x: l`	`x: prevL`, `prevL` 为上一个定义 `x` 的语句
常量传播 (constant propagation)	前向	$\cup$	变量值	`x = a`	`x: val(a)`, `val(a)` 表示 `a` 的值	`x: _`, `_` 表示之前的值
活跃变量分析 (live variabiles analysis)	反向	$\cup$	变量	`x = n`	`n`	`x`
可用表达式分析 (available expressions analysis)	前向	$\cap$	表达式	`a = x op y`	`x op q`	所有涉及 `a` 的表达式

1.reaching-define的结果可以用来构造数据依赖图（参考Joern），比如 l: x = a，中 $\text{OUT}[l] = \{(a, l_1), (x, l)\}$ ，那么可以知道引用的 a 在 l1 出定义，添加边 $l_1 \stackrel{a}{\rightarrow} l$ 。同时对于循环中的 x = y op z，如果 y 和 z 的定义在循环外，那么可以把 y op z 移动到循环外。
2.常量传播的结果 $\text{OUT}[s]$ 表示 $s$ 处为常量的变量情况。可以用来对变量进行常量替换。
3.活跃变量的分析结果中 $\text{IN}[s]$ 表示 $s$ 处的活跃变量，可以用来优化寄存器分配。
4.可用表达式的分析结果可以用来删除公共子表达式减少多余计算。

除了上述提到的经典问题外，flow-sensitive的指针分析、抽象解释也是一个数据流分析问题。指针分析的fact是指向关系 (比如 $\rightarrow o$ 表示 $x$ 可能指向 $o$ )，meet操作是 $\cup$ ，gen 和 kill 则需要考虑strong update和weak update。具体可参考blog。

对于赋值语句 $s : x = y$ ， $\text{gen}[s] = \{x \rightarrow o \mid \forall o \in \text{pts}(y)\}$ ， $\text{kill}[s] = \{x \rightarrow \_ \}$ ，进行strong update。
对于 $s : * x = y$ ， $\text{gen}[s] = \{z \rightarrow o \mid \forall z \in \text{pts}(x) \; \forall o \in \text{pts}(y) \}$ $\text{kill}$ 情况就比较复杂。
- 如果 $x$ 只指向内存对象 $z$ ，那么 $\text{kill}[s] = \{z \rightarrow \_ \}$ ，依旧可以进行strong update。
- 如果 $x$ 可能指向好几块内存对象，那么 $\text{kill}[s] = \{\}$ ，此时进行的是weak update。

抽象解释可参考blog，fact为变量值域，SVF的抽象解释模块对 p = c (c 为整型常量，p 为整型变量) 生成的fact为 $\rightarrow \langle [c, c], \top \rangle$ ，包括值域 $[c, c]$ 和指向集 $\top$ ，同时进行抽象解释和指针分析（也就是对应paper提到的Combined Abstract Domains）。和指针分析一样，抽象解释中 store 指令可能涉及到 kill 操作，也需要考虑strong update和weak update。

难点：C/C++中别名的存在是数据流分析的一大难点（参考blog），不同变量对同一内存的引用导致多个定义可能指向一个变量，通常数组、指针、结构体的使用可能带来别名关系，为了保证soundness，越保守的策略通常越不会 kill 不确定的fact。通常可以先进行一个指针分析来确定大致别名关系。或者参考Dr.Checker和Falcon将指针分析和到达定值一起分析。考虑到二者到达收敛的循环次数可能不一致，Dr.Checker预设了一个循环次数上限，不过这种策略可能会导致指针分析不够可靠（unsound）。对于Falcon，它用到了两个集合 $E$ 和 $S$ 来分别保存top-level pointer的指向集和address-taken object的到达定值， $(\pi, l, q) \in S(o)$ 表示 store 语句 $l : * p = q$ 中 $\in \text{pts}(p)$ 因此 $o$ 在 $l$ 处的到达定值为 $(\pi, q)$ ( $\pi$ 是路径条件，Falcon采用路径敏感的分析策略)，Falcon中只有 store 语句会更新 $S$ 集合，其它语句(load, gep 等) 会查询 $S$ 并更新top-level variable对应 $E$ 集合。

2.LLVM实现

2.1.常量传播

llvm提供了source code level和LLVM IR level的常量传播算法，source code level通过ConstantPropagationAnalysis类实现，不过由于只是简单实现没法适用到real-world环境下，因此只是放到unittests下。在这个实现中变量值有上界 $\top$ , 下届 $\bot$ , 常量值 $c$ 3种类型。用 $a$ 表示任意值，其中有 $\bot \cup a = a$ ， $\top \cup a = \top$ , $\cup c = c$ , $c_1 \cup c_2 = \top$ 。对于给定 Stmt* S, ConstantPropagationAnalysis 类通过AST分析识别其中是否存在: 1.变量声明并初始化 (int x = 42)、2.赋值语句 (x = 24)、3.复合赋值 (x += 4)。对于前两种语句 ConstantPropagationAnalysis 会尝试计算右表达式的常量值，如果不是常量则设置左表达式对应变量为 $\top$ ，反之设置为具体值。对于复合赋值直接将左变量设置为 $\top$ 。这里会调用 Expr::EvaluateAsInt 对表达式进行求值。x = a 中，如果 a 是常量那么返回常量值，如果 a 是变量似乎不会再递归求值直接返回 $\top$ 。

LLVM IR level的通过SCCPPass来进行函数内Sparse Conditional Constant Propagation (SCCP)。跨函数传播通过IPSCCPPass实现。SCCP相比普通常量传播的改进在于增加对分支条件的处理。普通常量传播不会考虑分支条件为常量 (true 或 false)，SCCP则会基于分支条件的常量值删除不可达分支。根据这个stackoverflow post，启用常量传播pass的前提条件应该是先使用mem2reg优化。

函数内常量传播的入口为runSCCP函数，lattice定义为ValueLatticeElement，变量值通常通常有以下状态。

状态	含义
`unknown`	该值尚无已知信息，可以转换为任何其他状态。通常作为起始状态
`undef`	该值是 `UndefValue` 或产生 `undef`，可以与 `constant` 或 `constantrange` meet后转化为 `constant`。可以转换为 `constant`、`constantrange_including_undef` 或 `overdefined`。
`constant`	该值是一个特定的常量，不能是 `undef`。
`notconstant`	该值已知不是某个特定常量（适用于非整数类型）。
`constantrange`	该值属于某个范围（仅适用于整数类型）。
`constantrange_including_undef`	该值属于某个范围，但也可能是 `undef`。`undef` 与 `constantrange` meet后为 `constantrange_including_undef`。与其他fact meet后仍为 `constantrange_including_undef`。
`overdefined`	该值无法精确建模，即可能具有多个动态值，不再进行任何状态转换。相当于 $\bot$

涉及到merge (meet)操作时，状态转移关系定义在ValueLatticeElement::mergeIn，状态转移关系如下。对于 res = lhs op rhs，运算结果如下：

lhs\rhs	`unknown`	`overdefined`	`undef`	`constant`	`constantrange`	`notconstant`	`constantrange_including_undef`
`unknown`	`unknown`	`overdefined`	`undef`	`constant`	`constantrange`	`notconstant`	`constantrange_including_undef`
`overdefined`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`overdefined`
`undef`		`overdefined`	`undef`	`constant`	`constantrange`	`overdefined`	`overdefined`
`constant`	`overdefined`	`overdefined`	`constant`	`constant` (lhs == rhs), `overdefined` (lhs != rhs)	`overdefined`	`overdefined`	`overdefined`
`notconstant`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`notconstant`	`overdefined`
`constantrange`	`overdefined`	`overdefined`	`overdefined`	`overdefined`	`constantrange` (值域会进行union)	`overdefined`	`overdefined`

其中还有一个辅助类SCCPInstVisitor来收集中间结果。

成员变量	类型	作用
`BBExecutable`	`SmallPtrSet<BasicBlock *, 8>`	记录可执行的基本块
`ValueState`	`DenseMap<Value *, ValueLatticeElement>`	记录 `Value` 的lattice状态, `Value` 通常对应1个llvm指令
`StructValueState`	`DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement>`	记录结构体字段的 lattice 状态
`TrackedGlobals`	`DenseMap<GlobalVariable *, ValueLatticeElement>`	记录全局变量的lattice状态
`TrackedRetVals`	`MapVector<Function *, ValueLatticeElement>`	记录单返回值函数的返回值状态
`TrackedMultipleRetVals`	`MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>`	记录多返回值函数的返回值状态
`MRVFunctionsTracked`	`SmallPtrSet<Function *, 16>`	存储 `TrackedMultipleRetVals` 中的函数，方便查找
`MustPreserveReturnsInFunctions`	`SmallPtrSet<Function *, 16>`	存储返回值不可修改的函数
`TrackingIncomingArguments`	`SmallPtrSet<Function *, 16>`	存储需要分析参数的函数
`OverdefinedInstWorkList`	`SmallVector<Value *, 64>`	记录即将 `overdefined` 的指令，加速SCCP收敛
`InstWorkList`	`SmallVector<Value *, 64>`	记录待 SCCP 处理的指令，加速SCCP收敛
`BBWorkList`	`SmallVector<BasicBlock *, 64>`	记录待 SCCP 处理的基本块，主worklist
`KnownFeasibleEdges`	`DenseSet<Edge>`	记录已确认的CFG边，避免重复计算
`AnalysisResults`	`DenseMap<Function *, AnalysisResultsForFn>`	存储函数SCCP分析结果

这里worklist算法大致如下，相比原版worklist算法再次做了些优化：

1.visit(BB) 表示对basic block BB 下的所有指令 (Value) 进行 meet 和 update。
2.markUsersAsChanged 会对 I 的所有 users 进行 visit，也就是优先处理 OverdefinedInstWorkList 中的元素和非 overdefined 的结构体元素。
3.优先处理 OverdefinedInstWorkList 的原因是如果变量 (Value) I 的状态为 Overdefined，它的 user 状态多半为 Overdefined，没法再收敛了，减少这部分的迭代次数能加速SCCP收敛。
4.InstWorkList 主要用于处理值从 undef 变成 constant 的情况。尽早传播 constant，让更多值变成 constant，提高优化效果。

def SCCP_Worklist():while !BBWorkList.empty() or !OverdefinedInstWorkList.empty() or !InstWorkList.empty():# 优先处理 OverdefinedInstWorkList，尽快传播 overdefined 状态while !OverdefinedInstWorkList.empty():I = OverdefinedInstWorkList.pop()markUsersAsChanged(I)# 处理普通指令工作列表while !InstWorkList.empty():I = InstWorkList.pop()# 只处理未 overdefined 的值if isStructType(I) or not isOverdefined(I):markUsersAsChanged(I)# 处理基本块工作列表while !BBWorkList.empty():BB = BBWorkList.pop()visit(BB)

具体的update规则可以参考 SCCP::visitXXInst 函数。这里有意思的是:

1.SCCPInstVisitor::visitStoreInst，其中只对全局变量进行处理，也就是局部变量的 store 都不操作。
2.SCCPInstVisitor::visitLoadInst中如果加载的是结构体变量直接为 overdefined ( $\bot$ )，SCCPInstVisitor::resolvedUndefsIn中对于其它 load 将值设为 undef。这可能是考虑到别名的一种保守处理。根据这个stackoverflow post，对于下面代码，llvm编译器压根没做优化。原因是 c = a + b 中存在 load a 与 load b 和 store 1, a, store 2, b 操作。而 SCCPPass 没有详细地处理，因此，没能优化。也是因此开启该优化的一个前提是先用 mem2reg。

int a,b,c;
a = 1;
b = 2;
c = a + b;

3.SCCPInstVisitor::visitCmpInst中调用ValueLatticeElement::getCompare对 r = cmp op1, op2 计算 r 的值，最终结果有 overdefined, constant(1), constant(0) 3种。
4.SCCPInstVisitor::visitSelectInst中会根据 cmp 的计算结果计算当前值。如果 cond 的常量值为 1，则选 true branch的值，反之亦然；如果为 overdefined，则合并两个分支的常量值。

runSCCP结尾会调用SCCPSolver::simplifyInstsInBlock对变量进行常量替换以及删除无用指令并调用removeNonFeasibleEdges删除infeasible CFG edge以及随后删除无用基本块。

2.2.活跃性分析

llvm提供两个level的活跃性（包括活跃变量和可用表达式）分析：source code和machine code，source code level可通过clang static analyzer的LiveVariablesDumper (CSA参数为 debug.DumpLiveVars) 以及LiveExpressionsDumper(CSA参数为 debug.DumpLiveExprs)打印活跃变量信息。在machine code level会通过LiveVariablesAnalysis进行活跃变量分析。

source code level的活跃性分析这位大佬的两篇blog（clang中的活跃性分析讲解源码,clang中的活跃性分析（续）给出示例）对clang的源代码进行了具体说明。负责活跃性分析的包括LiveVariables和RelaxedLiveVariables类，后者相比前者分析结果更不精确，不过source code level的活跃性分析主要是辅助clang static analyzer而不是编译优化，因此在analyzer中反而应用了 RelaxedLiveVariables，而 LiveVariables 纯粹只是用来dump source code level的活跃变量信息。transfer function的定义在TransferFunctions中，活跃性分析的dataflow fact分别用VarDecl*(变量分析)和Expr*(表达式分析)表示。

llvm数据流分析

1.数据流分析

2.LLVM实现

2.1.常量传播

2.2.活跃性分析

相关文章：