llvm数据流分析

相关参考文档： 、 、 、 。

1.数据流分析

数据流分析在编译优化等程序分析任务上都有重要应用。通常数据流分析可被抽象为一个IFDS-based worklist算法。核心是给每个CFG结点

s s

s (结点表示一个语句或者基本块)计算两个集合

IN [ s ] \text{IN}[s]

IN

[

s

] 和

OUT [ s ] \text{OUT}[s]

OUT

[

s

] 。

• meet运算:

  IN [ s ]

  meet s i ∈ prev ( s ) OUT [ s i ] \text{IN}[s] = \text{meet}_{s_i \in \text{prev}(s)} \text{OUT}[s_i]

  IN

  [

  s

  ]

  =

  meet

  s

  i

  ​

  ∈

  prev

  (

  s

  )

  ​

  OUT

  [

  s

  i

  ​

  ] ，

  meet [ s ]

  ∪ s i ∈ next ( s ) IN [ s i ] \text{meet}[s] = \cup_{s_i \in \text{next}(s)} \text{IN}[s_i]

  meet

  [

  s

  ]

  =

  ∪

  s

  i

  ​

  ∈

  next

  (

  s

  )

  ​

  IN

  [

  s

  i

  ​

  ] (反向数据流传播任务)。

• update:

  OUT [ s ]

  gen [ s ] ∪ ( IN [ s ] − kill [ s ] ) \text{OUT}[s] = \text{gen}[s] \cup (\text{IN}[s] - \text{kill}[s])

  OUT

  [

  s

  ]

  =

  gen

  [

  s

  ]

  ∪

  (

  IN

  [

  s

  ]

  −

  kill

  [

  s

  ]) ,

  IN [ s ]

  gen [ s ] ∪ ( OUT [ s ] − kill [ s ] ) \text{IN}[s] = \text{gen}[s] \cup (\text{OUT}[s] - \text{kill}[s])

  IN

  [

  s

  ]

  =

  gen

  [

  s

  ]

  ∪

  (

  OUT

  [

  s

  ]

  −

  kill

  [

  s

  ]) (反向数据流传播任务)。通常具体实现中

  gen \text{gen}

  gen 和

  kill \text{kill}

  kill 可由update操作完成。

数据流分析的worklist算法 (前向) 如下。worklist算法会不断循环直到

IN [ s ] \text{IN}[s]

IN

[

s

] 和

OUT [ s ] \text{OUT}[s]

OUT

[

s

] 收敛（集合不再变大）为止。

IN [ s ] \text{IN}[s]

IN

[

s

] 和

OUT [ s ] \text{OUT}[s]

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)

• 1.reaching-define的结果可以用来构造数据依赖图（参考 ），比如 l: x = a ，中

  OUT [ l ]

  { ( a , l 1 ) , ( x , l ) } \text{OUT}[l] = {(a, l_1), (x, l)}

  OUT

  [

  l

  ]

  =

  {(

  a

  ,

  l

  1

  ​

  )

  ,

  (

  x

  ,

  l

  )} ，那么可以知道引用的 a 在 l1 出定义，添加边

  l 1 → a l l_1 \stackrel{a}{\rightarrow} l

  l

  1

  ​

  →

  a

  l 。同时对于循环中的 x = y op z ，如果 y 和 z 的定义在循环外，那么可以把 y op z 移动到循环外。

• 2.常量传播的结果

  OUT [ s ] \text{OUT}[s]

  OUT

  [

  s

  ] 表示

  s s

  s 处为常量的变量情况。可以用来对变量进行常量替换。

• 3.活跃变量的分析结果中

  IN [ s ] \text{IN}[s]

  IN

  [

  s

  ] 表示

  s s

  s 处的活跃变量，可以用来优化寄存器分配。

• 4.可用表达式的分析结果可以用来删除公共子表达式减少多余计算。

除了上述提到的经典问题外，flow-sensitive的 指针分析 、 抽象解释 也是一个数据流分析问题。指针分析的fact是指向关系 (比如

x → o x \rightarrow o

x

→

o 表示

x x

x 可能指向

o o

o )，meet操作是

∪ \cup

∪ ， gen 和 kill 则需要考虑strong update和weak update。具体可参考 。

• 对于赋值语句

  s : x

  y s: x = y

  s

  :

  x

  =

  y ，

  gen [ s ]

  { x → o ∣ ∀ o ∈ pts ( y ) } \text{gen}[s] = {x \rightarrow o \mid \forall o \in \text{pts}(y)}

  gen

  [

  s

  ]

  =

  {

  x

  →

  o

  ∣

  ∀

  o

  ∈

  pts

  (

  y

  )} ，

  kill [ s ]

  { x → _ } \text{kill}[s] = {x \rightarrow _ }

  kill

  [

  s

  ]

  =

  {

  x

  →

  _

  } ，进行strong update。

• 对于

  s : ∗ x

  y s: *x = y

  s

  :

  ∗

  x

  =

  y ，

  gen [ s ]

  { z → o ∣ ∀ z ∈ pts ( x )    ∀ o ∈ pts ( y ) } \text{gen}[s] = {z \rightarrow o \mid \forall z \in \text{pts}(x) ; \forall o \in \text{pts}(y) }

  gen

  [

  s

  ]

  =

  {

  z

  →

  o

  ∣

  ∀

  z

  ∈

  pts

  (

  x

  )

  ∀

  o

  ∈

  pts

  (

  y

  )}

  kill \text{kill}

  kill 情况就比较复杂。

  • 如果

    x x

    x 只指向内存对象

    z z

    z ，那么

    kill [ s ]

    { z → _ } \text{kill}[s] = {z \rightarrow _ }

    kill

    [

    s

    ]

    =

    {

    z

    →

    _

    } ，依旧可以进行strong update。

  • 如果

    x x

    x 可能指向好几块内存对象，那么

    kill [ s ]

    { } \text{kill}[s] = {}

    kill

    [

    s

    ]

    =

    {

    } ，此时进行的是weak update。

抽象解释可参考 ，fact为变量值域，SVF的抽象解释模块对 p = c ( c 为整型常量， p 为整型变量) 生成的fact为

p → ⟨ [ c , c ] , ⊤ ⟩ p \rightarrow \langle [c, c], \top \rangle

p

→

⟨[

c

,

c

]

,

⊤

⟩ ，包括值域

[ c , c ] [c, c]

[

c

,

c

] 和指向集

⊤ \top

⊤ ，同时进行抽象解释和指针分析（也就是对应 提到的Combined Abstract Domains）。和指针分析一样，抽象解释中 store 指令可能涉及到 kill 操作，也需要考虑strong update和weak update。

难点 ：C/C++中别名的存在是数据流分析的一大难点（参考 ），不同变量对同一内存的引用导致多个定义可能指向一个变量，通常 数组 、 指针 、 结构体 的使用可能带来别名关系，为了保证soundness，越保守的策略通常越不会 kill 不确定的fact。通常可以先进行一个指针分析来确定大致别名关系。或者参考 和 将 指针分析和到达定值一起分析 。考虑到二者到达收敛的循环次数可能不一致，Dr.Checker预设了一个循环次数上限，不过这种策略可能会导致指针分析不够可靠（unsound）。对于Falcon，它用到了两个集合

E E

E 和

S S

S 来分别保存top-level pointer的指向集和address-taken object的到达定值，

( π , l , q ) ∈ S ( o ) (\pi, l, q) \in S(o)

(

π

,

l

,

q

)

∈

S

(

o

) 表示 store 语句

l : ∗ p

q l: *p = q

l

:

∗

p

=

q 中

o ∈ pts ( p ) o \in \text{pts}(p)

o

∈

pts

(

p

) 因此

o o

o 在

l l

l 处的到达定值为

( π , q ) (\pi, q)

(

π

,

q

) (

π \pi

π 是路径条件，Falcon采用路径敏感的分析策略)，Falcon中只有 store 语句会更新

S S

S 集合，其它语句( load , gep 等) 会查询

S S

S 并更新top-level variable对应

E E

E 集合。

2.LLVM实现

2.1.常量传播

llvm提供了source code level和LLVM IR level的常量传播算法，source code level通过 类实现，不过由于只是简单实现没法适用到real-world环境下，因此只是放到 下。在这个实现中变量值有上界

⊤ \top

⊤ , 下届

⊥ \bot

⊥ , 常量值

c c

c 3种类型。用

a a

a 表示任意值，其中有

⊥ ∪ a

a \bot \cup a = a

⊥

∪

a

=

a ，

⊤ ∪ a

⊤ \top \cup a = \top

⊤

∪

a

=

⊤ ,

c ∪ c

c c \cup c = c

c

∪

c

=

c ,

c 1 ∪ c 2

⊤ c_1 \cup c_2 = \top

c

1

​

∪

c

2

​

=

⊤ 。对于给定 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的通过 来进行函数内Sparse Conditional Constant Propagation (SCCP)。跨函数传播通过 实现。SCCP相比普通常量传播的改进在于增加对分支条件的处理。普通常量传播不会考虑分支条件为常量 ( true 或 false )，SCCP则会基于分支条件的常量值删除不可达分支。根据这个 ，启用常量传播pass的前提条件应该是先使用 优化。

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

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

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

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

visit(BB) 表示对basic block BB 下的所有指令 ( Value ) 进行 meet 和 update 。

markUsersAsChanged 会对 I 的所有 users 进行 visit ，也就是优先处理 OverdefinedInstWorkList 中的元素和非 overdefined 的结构体元素。

• 3.优先处理 OverdefinedInstWorkList 的原因是如果变量 ( Value ) I 的状态为 Overdefined ，它的 user 状态多半为 Overdefined ，没法再收敛了，减少这部分的迭代次数能加速SCCP收敛。

  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 函数。这里有意思的是:

，其中只对全局变量进行处理，也就是局部变量的 store 都不操作。

中如果加载的是结构体变量直接为 overdefined (

⊥ \bot

⊥ )， 中对于其它 load 将值设为 undef 。这可能是考虑到别名的一种保守处理。根据这个 ，对于下面代码，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;

中调用 对 r = cmp op1, op2 计算 r 的值，最终结果有 overdefined , constant(1) , constant(0) 3种。

中会根据 cmp 的计算结果计算当前值。如果 cond 的常量值为 1 ，则选 true branch的值，反之亦然；如果为 overdefined ，则合并两个分支的常量值。

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

2.2.活跃性分析

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

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