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*(表達式分析)表示。