IR

  • Intermediate Representation 中间表示

3AC

  • 三地址码 3-Address Code
  • 每条3AC至多有三个地址，地址可以是名称，常量，编译器生成的临时变量
  • 其实3AC就是指令的一种表示形式

BB

  • 基本块 basic block
  • 基本块是满足一下性质的连续3AC：只能从块的第一条指令进入；只能从块的最后一条指令离开 Untitled.png
  • 构建程序P的基本块算法
    • 寻找leader（leader就是基本块的入口）
      • P的第一条指令是一个leader
      • 跳转目标是一个leader
      • 跳转指令的后一条指令也是一个leader
      • 一个基本块就是一个leader一直到下一个leader前的所有指令

CFG

  • 控制流图 control flow graph
  • 控制流图的一个结点可以是一条单独的3AC，更常见的是一个基本块BB
  • 构建控制流图算法
    • 首先构建程序基本块
    • 构建边：块 A 和块 B 之间有一条边，当且仅当：A 的末尾有一条指向了 B 开头的跳转指令；A 的末尾紧接着 B 的开头，且 A 的末尾不是一条无条件跳转指令

数据流分析

PP

  • 程序点 program point
  • 在数据流分析中，我们会把每一个PP关联一个数据流值，代表在该点中可观察到的抽象的程序状态。

输入输出状态

  • 每一条IR的执行，都会使状态从输入状态变成新的输出状态
  • 输入/输出状态与语句前/后的 program point相关联。

转移方程

  • 每条语句 s 都会使程序状态发生改变，这个所谓的方程f_x()对应的就是语句使得状态发生变化的操作
  • 分析数据流有前向后后向两种，每条语句对应的状态转移方程也有两种。

控制流约束

  • 这指的是状态的变化需要和控制流对应，比如说有两个基本块A1和A2都指向基本块B，那么B的输入状态就应该是A1、A2输出状态的交集

Reaching Definitions Analysis 到达定义分析

  • 假设v在PPp处有定义x，如果存在一个路径从PPp到PPq，并且在该路径上没有v的其他定义，则称v的定义x到达p点。
  • 如果在这条路径上有v的其他定义，则称变量v的定义x被killed
  • 应用举例：分析程序是否存在变量未初始化：在程序入口为各变量引入一个 dummy 定值。当程序出口的某变量定值依然为 dummy，则我们可以认为该变量未被定义。

到达定义的转移方程

$$ \begin{matrix}OUT[B]=gen_B\cup(IN[B]-kill_B) \ IN[B]=\cup_{p,a,predecessor,of, B}OUT[P] \end{matrix}
$$

  • 从输入状态减掉kill掉的变量，并加入新生成的变量

到达定义的更新算法

  • 一个迭代算法，具体看视频吧。 Untitled 1.png

Live Variables Analysis 活跃变量分析

  • 假设v在PPp处有定义x，如果存在一个路径从PPp到PPq，并且在该路径上使用变量v并且在使用前没有重新定义v，则称v的定义x在这段路径上活跃。
  • 反之称为被killed
  • 应用举例：可以用于寄存器分配，当一个变量不会再被使用，那么此变量就可以从寄存器中腾空，用于新值的存储。

活跃变量分析的转移方程（与上面reach分析不同的是，这里用backward的分析）

$$ \begin{matrix}OUT[B]=\cup_{s,a,successor,of,B}OUT[S] \ IN[B]=use_B\cup(OUT[B]-def_B) \end{matrix}
$$

算法

Untitled 2.png

Available Expression Analysis 可用表达式分析

  • 从流图入口结点到达 p 的每条路径都对 x + y 求了值，且在最后一次求值之后再没有对 x 或 y 赋值，则称x+y可用
  • 应用举例：可用表达式可以用于全局公共子表达式的计算。也就是说，如果一个表达式上次计算的值到这次仍然可用，我们就能直接利用其中值，而不用进行再次的计算。

转移方程

$$ \begin{matrix}OUT[B]=gen_B\cup(IN[B]-kill_B) \ IN[B]=\cap_{p,a,predecessor,of, B}OUT[P] \end{matrix}
$$ 注意这里公式里的in是交集，因为定义中要求每条路径都对表达式求值而且最后一次求值后没有定义，所以对于每条路径的out进行merge用交集。 Untitled 3.png 比如上图这个例子，左边的路径中对x进行赋值了，但是是在最后一次计算表达式之前赋值，所以out仍然是表达式。如果左边路径的BB中把最后一次计算去掉，那out就是空了，最后两条路径merge的in就是空。

算法

Untitled 4.png 上述算法的共同点都是不同迭代直到每个结点的值都不再更新了，那么此时每个结点的值就是真实程序会达到的状态吗，到达此状态后每个结点就真的不会再变化了吗？下面老师进行数学上的证明

Upper and Lower Bounds

对于偏序集中的某子集 S 来说： 若存在元素 u 使得 S 的任意元素 x 有 x$\sqsubseteq$u，那么我们说 u 是 S 的上界（Upper bound）。 同理，若存在元素 l 使得 S 的任意元素 x 有 l$\sqsubseteq$x，那么我们说 l 是 S 的下界（Lower bound）。 然后我们衍生出最小上界和最大下界的概念： 在 S 的所有上界中，我们记最小上界（Least upper bound, lub）为 $\sqcup$ S，满足所有上界 u 对 lub 有：$\sqcup$ S $\sqsubseteq$ u 类似地我们也能定义出最大下界（Greatest lower bound, glb）为$\sqcap$ S。 并不是每个偏序集都有 lub 和 glb，但是如果有，那么该 lub, glb 将是唯一的。

Lattice, Semilattice, Complete and Product Lattic

  • 给定一个偏序集，如果任意元素 a, b 都有 lub和glb，那么这么偏序集就叫做 格（lattice）
  • 如果在此之上更加严格一些，任意集合都存在 lub 和 glb，那么我们说这个 lattice 为“全格（complete lattice）”
  • 另外还有 Product Lattice，多个 lattice 的笛卡尔积也能形成一个新的 lattice。

Data Flow Analysis Framework via Lattice

一个数据流分析框架（D, L, F）由以下元素组成：

  • D: 数据流的方向，前向还是后向
  • L: 包含了数据值 V 和 meet, join 符号的格
  • F: V -> V 的转移方程族

从而，数据流分析可以被视为在 lattice 的值上迭代地应用转移方程和 meet/join 操作符。

参考

数据流分析 1