鲸书阅读笔记-------第八章数据流分析(二):到达---定值分析
本篇通过到达--定值分析来引出数据流分析的过程
什么是到达--定值?
定值是对某个变量的赋值。
假设变量x的定值为d,如果存在一条紧随在定值d后面的程序点到达某一个程序点p的路径,并且在这条路径上d并没有被“杀死”(也就是说,变量x没有被重新赋值为其他值),我们就说定值到达程序点p。一个编译器能够根据到达定值信息知道变量x在程序点p上的值是否为常量。
局部数据流分析和全局数据流分析
数据流分析可以在过程的流图上进行,一般分成两个阶段:局部数据流分析,在每个基本块上进行;全局数据流分析,在流图上进行。
分析过程采用的方法
采用向前迭代位向量
“迭代”:首先构造了一组表示信息流的数据流方程。,并从适当的初值集合开始,以迭代方式来求解这组方程;
“向前”:信息流是沿着程序中控制流边的执行方向流动的
“位向量”:使用1(意味着它可能到达给定点)或0(意味着它不能到达)来表示一个定值。可能到达一个点的所有定值的集合可以用一个位串或位向量来表示。
下列表给出了流程图中的定值和它们在位向量中的位置对应关系。采用8位的向量来表示程序中有哪些定值到达了每一个基本块的开始。
- Prsv(i) ,它表示由基本块i保留的那些定值。没有在基本块i中被重新赋值。
2. Gen(i) 由基本块i生成的定值集合。在基本块中有过赋值且随后的在该基本块中未被重新赋值。
集合Gen中包含了所有在紧靠基本块之后的点上“可见”的该基本块中的定值,“向下可见”。在一个基本块中,一个定值是向下可见的,仅当它没有被同一个基本块中较后面的同一个变量的定值“杀死”。
由基本块i产生的定值集合,定义表示到达基本块i末尾的那些定值的集合和相应的位向量。
现在,一个定值可以到达基本块i的末尾,当且仅当它要么在基本块i内出现,并且它定值的变量在i中没有被重新定值;要么它可能到达i的开始并且由i保留其定值。
可以使用集合和集合运算来表示;
为了求解RCHin(i)和RCHout(i)(位向量)方程组,简单将RCHin(i)初始化为前面给出的值,并且迭代地应用这些方程直到没有进一步的变化产生。
第一次迭代:
再一次迭代:
这里的迭代会发生改变:基本块B4的前驱块还有B6,B6的变化会影响到B4变量的变化,所以再次迭代循环里面的基本块信息会发生改变。
ps:执行迭代的规则绝不会将1变成0,变量的改变是单调的,所以可以保证迭代过程最终确实会终止。