编译原理 第十章优化 http://sei.nudt.edu.cn/cp 网上教学系统：070606302：编译原理
编译原理 第十章 优化 http://sei.nudt.edu.cn/cp 网上教学系统: 070606302: 编译原理
源程序 表 词法分析器 出 单词符号 语法分析器 格 语法单位 错 ←→中间代码生成器 管 四元式 处 优化段 理 四元式 理 目标代码生成器 目标代码 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 词法分析器 语法分析器 中间代码生成器 优化段 源程序 单词符号 语法单位 四元式 表 格 管 理 出 错 处 理 目标代码生成器 四元式 目标代码
第十章优化 优化：对程序进行各种等价变换，使得从 变换后的程序出发，能生成更有效的目标 代码。 口等价：指不改变程序的运行结果。 口有效： 指目标代码运行时间短，占用的存储空 间小。 编译前端 代码优化器 编译后端 控制流分析 数据流分析 代码变换 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 第十章 优化 ◼ 优化：对程序进行各种等价变换，使得从 变换后的程序出发，能生成更有效的目标 代码。 等价：指不改变程序的运行结果。 有效：指目标代码运行时间短，占用的存储空 间小。 编译前端 代码优化器 编译后端 控制流分析 数据流分析 代码变换
10.1概述 优化的目的是为了产生更高效的代码。由 优化编译程序提供的对代码的各种变换必 须遵循一定的原则： 口等价原则：经过优化后不应改变程序运行的 结果； ▣有效原则：使优化后所产生的目标代码运行° 时间较短，占用的存储空间较小； 口合算原则：应尽可能以较低的代价取得较好 的优化效果。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 10.1 概述 ◼ 优化的目的是为了产生更高效的代码。由 优化编译程序提供的对代码的各种变换必 须遵循一定的原则： 等价原则：经过优化后不应改变程序运行的 结果； 有效原则：使优化后所产生的目标代码运行 时间较短，占用的存储空间较小； 合算原则：应尽可能以较低的代价取得较好 的优化效果
10.1概述 ■优化的三个不同级别： ▣局部优化 口循环优化 ▣全局优化 优化的种类： 口删除多余运算（或称删除公用子表达式） 口代码外提 口强度消弱 口变换循环控制条件 口合并已知量 口复写传播 ▣删除无用赋值 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 10.1 概述 ◼ 优化的三个不同级别： 局部优化 循环优化 全局优化 ◼ 优化的种类： 删除多余运算(或称删除公用子表达式) 代码外提 强度消弱 变换循环控制条件 合并已知量 复写传播 删除无用赋值
void quicksort (m,n); int m,n; int i,j; int v,x; if (nv); if (i>=j)break; =a[];a[叮=a];a=x; } x=a[叮；af叮=a[n];a[n=x; /*fragment ends here*/ quicksort (m,j);quicksort (i+1,n); 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 void quicksort (m, n); int m, n; { int i, j; int v, x; if (nv); 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[Tl Br if i>=j goto B B4 i:=i+1 T6=4*1 T11=4*i T2=4*1 x:=a [Tol B2 B5 x:=a [Tul T7=4*i Bo T3:=a[T2l T12=4*i if T3v goto B3 ▣中间代码程序段 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ❑中间代码程序段 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 T6 :=4*i x:=a [T6 ] T7 :=4*i T8 :=4*j T9 :=a [T8 ] a [T7 ]=T9 T10:= 4*j a [T10]=x goto B2 B5 T11:=4*i x:=a [T11] T12:=4*i T13:=4*n T14:=a [T13] a [T12]=T14 T15:= 4*n a [T15]=x B6
i:=m-1 j:=n T1=4*n v:=a[Tl B if i>=j goto B i:=i+1 T6=4*i T1=4*i T2=4*1 x:=a [Tol B2 B5 x:=a [Tul T2:=4*i Bo Ta:=a[T2] T12=4*1 if T3y goto B3 ▣中间代码程序段 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ❑中间代码程序段 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 T6 :=4*i x:=a [T6 ] T7 :=4*i T8 :=4*j T9 :=a [T8 ] a [T7 ]=T9 T10:= 4*j a [T10]=x goto B2 B5 T11:=4*i x:=a [T11] T12:=4*i T13:=4*n T14:=a [T13] a [T12]=T14 T15:= 4*n a [T15]=x B6
i:=m-1 j:=n T1=4*n v:=a[Tl Bi if i>=j goto B B4 i:=i+1 T6=T2 Tu:=T T2=4*1 x:=a [Tol B2 B5 x:=a [Tul Bo T3:=a[T2l T:=T6 Tp=Tu if T3v goto B3 口删除公用子表达式后 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ❑删除公用子表达式后 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 T6 := T2 x:=a [T6 ] T7 := T6 T8 := T4 T9 :=a [T8 ] a [T7 ]=T9 T10:= T8 a [T10]=x goto B2 B5 T11:= T2 x:=a [T11] T12:= T11 T13:= T1 T14:=a [T13] a [T12]=T14 T15:= T13 a [T15]=x B6
i:=m-1 j:=n T1=4*n v:=a[Tl BI if i>=j goto B i:=i+1 T6=T2 Tu=T2 T2=4*i x:=a [Tol B2 Bs x:=a [Tul T-=To Bo Ta:=a[T2l Tp:=Tu if T3<v goto B2 Ts:=T4 T13=T1 T:=a [Tsl Tu:=a [Tl a [Tl=T9 a [Tpl-T1 Tio:=T8 Tis:=T13 j=j-1 B a [Tiol=x a [Tisl=x T4=4*j goto B2 Ts:=a[T4 ifTs≥v goto B3 口复写传播 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ❑复写传播 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 T6 := T2 x:=a [T6 ] T7 := T6 T8 := T4 T9 :=a [T8 ] a [T7 ]=T9 T10:= T8 a [T10]=x goto B2 B5 T11:= T2 x:=a [T11] T12:= T11 T13:= T1 T14:=a [T13] a [T12]=T14 T15:= T13 a [T15]=x B6