编译原理课件-优化.pptxVIP

优化;10.1 概述;10.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); };中间代码程序段 ;中间代码程序段 ;公共子表达式;删除公用子表达式后;i:=m-1 j:=n T1:=4*n v:=a[T1];删除公用子表达式后;i:=m-1 j:=n T1:=4*n v:=a[T1];删除公用子表达式后;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;复写传播;删除无用赋值;删除无用赋值后 ;强度削弱 ;强度削弱后 ;删除归纳变量;删除归纳变量后;中间代码程序段 （优化前） ;中间代码程序段 （优化后）;10.2 局部优化;10.2 局部优化;划分四元式程序为基本块的算法: 1.求出四元式程序中各个基本块的入口语句: 1) 程序第一个语句，或 2) 能由条件转移语句或无条件转移语句转移到的语句，或 3) 紧跟在条件转移语句后面的语句。;划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句) 之间的语句序列组成的。 ;划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句) 之间的语句序列组成的。 ;划分四元式程序为基本块的算法: 2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句) 、或一停语句(包括该停语句)之间的语句序列组成的。 ;例：划分基本块 (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 (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 (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;10.2 局部优化;优化措施;优化措施;10.2.2 基本块的DAG表示及其应用;7.1.2 图表示法; a:=b*(-c)+b*(-c)的图表示法 ;DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 ;描述计算过程的DAG是一种带有下述标记或附加信息的DAG:;10.2.2 基本块的DAG表示及应用;