编译器笔记50-代码优化-活跃变量分析

活跃变量分析

活跃变量

对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在点p是活跃(live)的，否则称变量x在点p不活跃(dead)。

例-各基本块的出口处的活跃变量.png

注1：d7对i是没有引用，而d4对i是用引用的，要注意这两者的区别。另外定义中从程序点p出发是可以包含多条路径的，例如从基本块的B3出发的基本路径就有B3-B4-exit B3-B4-B2-B4-exit。而从基本块B1 B2 B3 B4的出口出发它们都有路径经过u2，因此u2在这四个基本块都是活跃变量。而从基本块B1 B2 B3 B4出发都没有对应的路径经过u1因此u1都不是B1 B2 B3 B4出口处的活跃变量。

注2：注意区分入口处的定值和出口处的活跃量

入口处的定值（判断变量是否有被重新赋值，判断的路径起点是对应的定值d后终点是对应基本块的入口；通俗点说就是某个定值d在去往某个基本块B入口前对应的变量是否又被重新赋值）

出口处的活跃量（判断变量是否有被引用，判断的路径起点是对应的基本块的出口终点不确定；通俗点说就是从某个基本块开始之后要判断的变量是否有被引用）前者用于判断定值在某个基本块是否能用？后者用于判断变量是否是无用变量？

活跃变量信息的主要用途

• 删除无用赋值
  无用赋值：如果x在点p的定值在基本块内所有后继点都不被引用，且x在基本块出口之后又是不活跃的，那么x在点p的定值就是无用的。

• 为基本块分配寄存器

1. 如果所有寄存器都被占用，并且还需要申请一个寄存器，则应该考虑使用已经存放了死亡值的寄存器，因为这个值不需要保存到内存。

2. 如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

活跃变量的传递函数

活跃变量的传递函数.png

def_B是在基本块中首次出现是以定值形式出现的集合。
use_B是在基本块中首次出现而且是以引用形式出现的那些变量构成的集合。
因为这是一个逆向数据流问题，所以我们用x表示在基本块出口处活跃变量的集合，用f_B(x)表示在入口处活跃变量的集合。

注：我们说一个变量在基本块中的出现无非是两种形式，一种是以定值的形式出现，一种是以引用的形式出现。

例：各基本块B的use_B和def_B.png

活跃变量数据流方程

活跃变量数据流方程.png

计算活跃变量的迭代算法

计算活跃变量的迭代算法.png 例.png 例.png

定值-引用链(Definition-Use Chains)

定值-引用链.png 定值-引用链 (2).png 无标题.png