代码块+控制流图+程序切片的学习

代码基本知识点

代码基本块

严格的来说，基本块是满足下列条件的一组连续指令代码，程序的执行（控制流）只能从基本块的第一条语句（入口语句）进入，从基本块的最后一条语句离开。

1. int a,b;
2. a = getchar();
3. b = getchar();
4. if (a>b){
5.   a = a*b;
6.   print(a);
7. }
8. else {
9.   a = a/b;
10.   print(a);
11. }
12. ### if/else

复制代码

代码56行与910行两个代码块有不同的进入条件，下一个执行代码块的选择取决于第4行的判断条件

1. int a,b;
2. a = getchar();
3. b = getchar();
4. while (a>b){
5.   a = a*b;
6.   print(a);
7. }
8. # while

复制代码

第4行代码while语句包含第5行代码，该行代码与其他行代码分开，执行条件是第4行的判断语句

1. int a,b,c;
2. a = getchar();
3. b = getchar();
4. for (;a,b;a++){
5.   c = a+b;
6. }
7. print(c);
8. ### for

复制代码

第4行代码for语句包含第5行代码，该行代码与其他行代码分开，执行条件是第4行的判断语句
控制流图CFG

当程序被划分为基本块后，如果将基本块视为一个基本单元节点，基本块之间在程序执行流程上互为前驱和后继的关系可以视为两个基本块村子一条边，则整个程序可以转换为一个有向图，称为控制流图（Control Flow Graph）

1. int max(int x, int y){
2.   int tmp = 0;        -----0
3.   if (x>y){           -----0
4.     tmp =x;           -----1
5.   }
6.   else{
7.     tmp = y;          -----2
8.   }
9.   return tmp;         -----3
10. }

复制代码

节点0是节点1和2的严格直接前必经节点，而节点3是节点1和2的严格直接后必经节点。
根据基本块构造的有向图G可以表示为四元组G = {V, E, Entry, Exit}，其中
V是基本块节点的集合
E是基本块之间边的集合
Entry表示入口基本块节点
Exit表示结束基本块节点
程序执行时，从Entry代表的基本块开始执行，沿着控制边遍历执行基本块，最后到Exit代表的基本块时执行结束。

数据流分析

到达与可到达

针对变量x的一个定义语句s，称该语句对变量x的定义到达程序的某个代码位置P，当且仅当在程序控制流图(CFG)中存在从该定义对应的语句到位置P语句的一条路径，并且该路径上没有变量x的其他定义。
称语句s是代码位置P的一个可到达定义。

第2条语句对变量b赋值，在该语句执行后变量b的值被算术表达式a+1的值所替代。
另外，每条语句前后都有对应的代码位置标识，分别为P1, P2, P3, P4, P5, P6，程序执行时可能的路径为或者。
第二条语句对变量b赋值，在该语句执行后变量b的值被算术表达式a+1的值所替代。

语句3对变量a进行定义，且语句4和5均未对变量a进行定义，那么，语句3就是代码位置P4、P5和P6的一个可到达定义
简单一点来说，一个赋值语句a在他的赋值被更改前运行的所有语句的有一个可到达定义a。

变量定义和引用概念

定义概念Def(x)假定某个变量为x，则x有定义集Def(x)，表示定义x的所有语句的集合，该集合包含任何使x的值发生变化的语句(例如，简单的或者经过运算后的赋值语句等)。Use(x)Use(x)表示变量x的引用集，即，任何使用x的语句的集合。分别将基本块内所有变量的定义集和引用集做并集，即可得到对应基本块的定义集和引用集Gen(s)产生集Gen(s)
表示所有由s给出的变量定义所在的语句构成的集合。
假定某条语句用s表示，s包含的变量定义和引用可以引入Kill(s)杀死集Kill(s)
若s重新定义变量x，而x此前由语句s’定义，则称s消灭定义s’。
所有由s消灭的定义的集合称为s的消灭集。In(s)表示所有在语句s之前仍然有效(没有被消灭)的定义语句的集合。Out(s)表示所有离开语句s的定义语句的集合，添加s产生的语句，同时去掉语句s所消灭的定义语句。程序切片

程序切片通常包括3个步骤
1、程序依赖关系提取
主要是从程序中提取各类信息，包括控制流和数据流信息，形成程序依赖图。
2、切片规则制定
主要是依据具体的程序分析需求设计切片准则。
3、切片生成
主要是依据切片准则选择相应的程序切片方法，然后对提取的依赖关系进行分析处理，从而生成程序切片。

程序切片的分类
按照是否在切片中考虑程序的具体输入，可以划分为静态切片和动态切片。
按照切片要提取的是对关注变量有影响的代码片段还是被关注变量所影响，可以划分为前向切片和后向切片。
按照提取的切片是否为可执行程序，可以划分为可执行的切片和不可执行的切片等。
静态切片

目前，静态程序切片主要有两种方法
基于数据流方程的切片方法
基于程序依赖图可达性的切片方法
静态程序切片方法均是利用数据依赖和控制依赖关系进行分析以获得程序切片。

静态程序切片方法
基于数据流方程的切片方法
基于图可达性算法的切片方法

基于数据流方程进行切片的方法主要是通过迭代计算控制流图中每个节点的相关变量集合，迭代分析语句间的数据依赖关系和控制依赖关系，最终获得每条语句中与切片准则相关的变量的集合。
基于图可达性算法的切片方法

基于图可达性进行切片的方法与图遍历方法基本相同。
首先需要计算出目标程序的控制依赖和数据依赖关系，构建程序依赖图。
然后从切片准则所对应的节点出发，沿着数据依赖边和控制依赖边进行图遍历，所有遍历可达的节点均加入到切片中
这边其实最重要的一步是画出程序依赖图，这是静态切片的关键：
[code]int main(){  int x=0, y, z;  int i = 0;  z = 0;  y = getchar();  for(;i