不存在完美的完全精确静态分析方法
在程序分析中，宁可误报（假阳性）也不漏报（假阴性），即追求假阳性，避免假阴性很高，也就是说，在追求全面覆盖的情况下，对分析精度和分析速度进行一个平衡把握。
静态程序分析概括成两个词：抽象(Abstraction)+ 过近似(Over-approximation)
Over-approximation 表示可以有误报，但不能有漏报
under-approximation 表示可以有漏报，不能有误报
编译器工作流程：源代码–词法分析(scanner)–>Tokens–语法分析(Parser)–>AST–语义分析(类型检查)–>decorated AST–>translator–>IR–code generator–>机器码
对 IR 的分析就是静态程序分析。
三地址码：
AST：
三地址码：每条指令通常由一个操作符和三个操作数组成，这三个操作数可以是变量、常量、或者临时变量。
三地址码的特点：每条指令只进行一个操作，至多有一个操作符（可以没有）
如：t2 = a+b+3
其三地址码：t1=a+b t2=t1+3
常见的三地址码形式：
x=y bop``bop 是二目运算符
x=uopy uop 是单目运算符，如：负号、取反、类型转换
x=y
if xrelopy goto L relop 是关系操作符，如><==，L 是跳转的标签
goto L
SSA：基于三地址码的改进，其给每个变量定义一个新名字，即每个变量有唯一的定义
当不确定某个变脸的来源时，引入一个 fai 函数
SSA 的好处：流信息能够通过唯一的变量定义间接的体现；定义和使用成对出现，容易寻找。
坏处：变量过多、性能较低
CFG 是程序静态分析的基础
CFG 的节点是三地址码的指令，而更通常的是如下图使用 Basic Block（BB）
Basic Block（BB）：由三地址码中最长的序列构成
满足：（唯一入口出口）
输入：一段三地址码 P
输出：一系列的 BB
方法：
BB 的开始语句：
BB 的结束语句：
符合上述规则的三地址码中的最大序列就是 basic block
实现代码如下
def identify_basic_blocks(three_address_code):
basic_blocks = []
leaders = set()
n = len(three_address_code)
# Create a dictionary to map line numbers to indices
line_number_to_index = {}
for i,instruction in enumerate(three_address_code):
# Line numbers start from 1,so map i+1 to the index i
line_number_to_index[i + 1] = i
# Identify leaders
for i in range(n):
instruction = three_address_code[i].strip()
# First instruction is a leader
if i == 0:
leaders.add(i)
# Instruction containing goto makes the target a leader
if"goto"in instruction:
parts = instruction.split()
if parts and parts[-1].isdigit():
line_number = int(parts[-1])
# Map line number to index if it exists
if line_number in line_number_to_index:
leaders.add(line_number_to_index[line_number])
if i + 1 < n:
leaders.add(i + 1)
# Create basic blocks
leaders = sorted(leaders)
current_block = []
i = 0
while i < n:
if i in leaders and current_block:
basic_blocks.append(current_block)
current_block = []
current_block.append(three_address_code[i])
if"goto"in three_address_code[i]:
basic_blocks.append(current_block)
current_block = []
i += 1
if current_block:
basic_blocks.append(current_block)
return basic_blocks
# Sample three address code
three_address_code = [
"×=input",
"y=×-1",
"z=×*y",
"if z<× goto 7",
"p=×/y",
"q=p+y",
"a=q",
"b=x+a",
"c=2a-b",
"if p==q goto 12",
"goto 3",
"return",
]
basic_blocks = identify_basic_blocks(three_address_code)
for idx,block in enumerate(basic_blocks):
print(f"Basic Block {idx + 1}:")
for instruction in block:
print(instruction)
print()
# Basic Block 1:
# ×=input
# y=×-1
# Basic Block 2:
# z=×*y
# if z<× goto 7
# Basic Block 3:
# p=×/y
# q=p+y
# Basic Block 4:
# a=q
# b=x+a
# c=2a-b
# if p==q goto 12
# Basic Block 5:
# goto 3
# Basic Block 6:
# return
规则：
Entry节点作为程序入口，在结尾加上 Exit作为程序出口如下面的三地址码转换为控制流图
"×=input",
"y=×-1",
"z=×*y",
"if z<× goto 7",
"p=×/y",
"q=p+y",
"a=q",
"b=x+a",
"c=2a-b",
"if p==q goto 12",
"goto 3",
"return",
在控制流图中，
对于一条语句的输入输出状态来说，执行这条语句就相当于执行了一个转换函数（transfer function）：
$ OUT(s) = f_s(IN(s)) $
$ IN(s) = f_s(OUT(s)) $
类似的，在 Basic Block 中的转换函数：
Reaching Definitions 是 may analysis
这里的定义 definition 可以理解为给变量赋值就相当于定义了一个变量
Reaching Definitions：在某个程序点$ p $定义的一个变量$ v $（变量的赋值），到在$ p->q
$的路径上，如果没有对该变量$ v $新的定义，称$ v $可以从$ p 到达(reach)q $
Reaching Definitions 可以用来检测可能未定义（为初始化）的变量
这里的数据是所有变量的定义（definition），一般使用位向量（bit vector）的形式来表示
如变量的定义：D1，D2，···，D100使用位向量00···0共一百个 0 来表示
每个位表示一个定义
$ \mathrm{OUT}[B]=gen_{B}\cup(\mathrm{IN}[B]-kill_{B}) $
$ gen_B $表示在 B 中新生成的定义
在语$ B $中定义了$ v
$，那么就$ kill $掉其他块中（不只是前面的块，是所有）所有对$ v $的定义，而其余传入$ B $中的定义不受影响
这里的 x 和 y 的定义不受影响
意思就是在 B 中定义了 v，那么从 B 中输出的定义就是新定义的 v 以及 x 和 y 的定义
$ \mathrm{IN}[B]=\bigcup_{P-a-predecessor-of-B}\mathrm{OUT}[P] $
P1、P2 是 B 的前驱（predecessor），B 的输入是 P1、P2 输出的 Union
reaching definition analysis 的算法设计：
输入：CFG
输出：每个 BB 块的输入 IN[B]和输出 OUT[B]
方法：
OUT[entry] = 空集;
for(each BB 除了 entry)
# 初始化，在 may analysis 中一般都定义为空集，must analysis 中定义为 top(undefined)
OUT[B] = 空集;
while(changes to any OUT occur) # 迭代到所有程序点的当前状态与上一个迭代的状态相同
for(each BB 除了 entry){
IN[B] = Union(OUT[P]);
OUT[B] = gen[B] U(IN[B]-kill[B]])
}
为什么该算法迭代会停止？
无论迭代多少次，对于同一个 BB 来说，其$ gen_B $和$ kill_B
$都是固定不变的，那么公式中，当输入 IN 与上一次迭代相同时，输出 OUT 也不会改变，且程序点的状态某个位只会从 0->1、1->1，并不会经过一次迭代后，就从 1->0。而对于一个程序点的状态来说，迭代过程中，能使状态改变的无非是在 Union 中前驱的输出发生改变。
当迭代停止时，我们得到最终的结果，称其 reach a fixed point（不动点），与单调性相关。
每个程序点关联着一个数据流的值，表示当前状态
活跃变量分析：如果一个变量$ v $，从程序点$ p $处，沿着 CFG 的某条路径，在该路径上$ v
$被使用，且在此之前$ v $没有被重新定义，那么称 v 在 p 点处 live，否则就是 dead
某条路径指的是任意长短的路径
该种分析可以用于寄存器分配，即寄存器若满了，那么可以将 dead 的变量用来设置新的变量
may analysis、backward analysis
如前所述，这里的数据是所有的变量（variable），一般使用位向量（bit vector）的形式来表示
如有不同的变量：x1，x2，···，x100使用位向量00···0共一百个 0 来表示
每个位表示不同的变量
$ \mathrm{IN[B]}= use_{B}\cup(\mathrm{OUT[B]} - def_{B}) $
由于使用逆向分析， 所以用 OUT[B]求 IN[B]，use 表示变量在 define 之前被使用
在 B 中，若一个变量首先被使用，再被重新定义，那么 IN[B]仍然是 Live，因为在被定义之前已经被使用了。
若先重新定义再被使用，则 IN[B]为 dead
$ \mathrm{OUT[B]}=\bigcup_{S -a -successor -of -B}\mathrm{IN[B]} $
算法设计
输入：CFG
输出：每个 BB 块的输入 IN[B]和输出 OUT[B]
方法：
IN[exit] = 空集;
for(each BB 除了 exit)
# 初始化，在 may analysis 中一般都定义为空集，must analysis 中定义为 top(undefined)
IN[B] = 空集;
while(changes to any IN occur) # 迭代到所有程序点的当前状态与上一个迭代的状态相同
for(each BB 除了 exit){
OUT[B] = Union(IN[S]);# S 是 B 的所有后继节点
IN[B] = use[B] U(OUT[B]-def[B]])
}
对于表达式 x op y和某个程序点 p，当 entry 节点到程序点 p 的所有路径都经过该表达式，且在计算表达式之后没有对 x 或 y 的重新定义，那么九城，表达式 x op y在程序点 p 处**available，**即 Available Expressions
是 must analysis、under-approximation
如前所述，表示为位向量的形式，每个位表示一个表达式，1 为 available。
$ \mathrm{OUT}[B]=gen_{B}\cup(\mathrm{IN}[B]-kill_{B}) $
$ \mathrm{IN}[B]=\bigcap_{P -a -predecessor -of -B}\mathrm{OUT}[P] $
算法：
输入：CFG
输出：每个 BB 块的输入 IN[B]和输出 OUT[B]
方法：
OUT[entry] = 空集;
for(each BB 除了 entry)
# 初始化，在 may analysis 中一般都定义为空集，must analysis 中定义为 ALL
OUT[B] = ALL;# 即为全 1
while(changes to any OUT occur) # 迭代到所有程序点的当前状态与上一个迭代的状态相同
for(each BB 除了 entry){
IN[B] = intersection(OUT[P]); # intersection 表示交集，所有的前驱节点的交集
OUT[B] = gen[B] U(IN[B]-kill[B]])
}
不动点：对于某个函数$ F $，存在点$ X $，使得$ X=F(X) $,那么称$ X $是函数$ F $的不动点。
提出问题：
偏序：
定义一对偏序集$ (P,\sqsubseteq) $其中$ \sqsubseteq $是定义在$ P $上的二元偏序关系，且有以下性质：
例 1：$ P
$是实数集，$ \sqsubseteq $是$ \leq $，其满足三个性质，因此这就是一对偏序集
例 2：$ P $是下面这些英文单词，而$ \sqsubseteq $表示子串关系，他们满足三个性质，因此也是偏序集
例 3：$ P $是幂集合$ {a,b,c} $，如下图$ \sqsubseteq $表示子集(subset)，他们满足三个性质，因此也是偏序集
换句话说，偏序就是集合中的两个元素可以不满足$ \sqsubseteq $的关系，即元素之间可以是不可比较的关系，如例 2 中，pin 和 sin 并不是子串的关系。