编译原理-第十章-第一部分.ppt

编译原理——第十章 优化（第一部分） 王金伟 计算机与信息工程学院 天津师范大学 第10章 优化 优化：对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 10.1 概述 优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循一定的原则： 等价原则：经过优化后不应改变程序运行的结果； 有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小； 合算原则：应尽可能以较低的代价取得较好的优化效果 优化的三个不同级别： 局部优化 循环优化 全局优化 优化的种类： 删除公用子表达式 代码外提 强度消弱 变换循环控制条件 合并已知量 复写传播 删除无用赋值 一个例子：Ｃ语言写的快速排序子程序 将输入的序列a[m..n]划分成两个非空子序列a[m..k]和a[k+1..n]，使a[m..k]中任一元素的值不大于a[k+1..n]中任一元素的值。 递归求解：通过递归调用快速排序算法分别对a[m..k]和a[k+1..n]进行排序，直至序列长度为1。 一个例子：Ｃ语言写的快速排序子程序 void quicksort (m, n); int m, n; { int i, j; int v, x; if (n=m) return; /* fragment begins here*/ i=m-1; j=n; v=a [n]; while (1) { do i=i+1; while (a [i]v); do j=j-1; while (a [j]v); if (i=j) break; x=a [i]; a[i]=a [j]; a[j]=x; } x=a[i]; a[i]=a [n]; a [n]=x; /*fragment ends here*/ quicksort (m, j); quicksort (i+1, n); } 代码外提 对于循环中的有些代码，如果它产生的结果在循环中是不变的，就可以把它提到循环外来，以避免每循环一次都要对这条代码进行运算。 例如： while(i=limit-2)… 如果在循环中limit的值是不变的，就可以把它变换为： t:=limit-2; while(i=t)… 10.2 局部优化 一、基本块： 指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。执行时只能从其入口进入，从其出口退出 局限于基本块范围内的优化称为基本块内的优化，或称局部优化。 在一个基本块内通常可以实行下面的优化: 删除公共子表达式 删除无用赋值 合并已知量 临时变量改名 交换语句的位置 代数变换 二、划分四元式程序为基本块的算法: 1.求出四元式程序中各个基本块的入口语句: 1) 程序第一个语句，或 2) 能由条件转移语句或无条件转移语句转移到的语句，或 3) 紧跟在条件转移语句后面的语句。 划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句) 之间的语句序列组成的。 划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句) 之间的语句序列组成的。 划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句) 、或一停语句(包括该停语句)之间的语句序列组成的。 划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。 3. 凡未被纳入某一基本块中的语句，可以从程序中删除。 例：划分基本块 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt 例：划分基本块 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt 例：划分基本块 (1) read X (2) read Y