石河子大学：《编译原理》课程教学资源（PPT课件）第十一章 代码优化

参考文献 11.1 优化概述 《程序设计语言编译原理》 (第二版) 陈火旺等国防工业出版社 第9章第1节 《编译原理和技术》 (第一版) 陈意云 中国科学技术大学出版社 第9章第1节、第9章第2节 《编译原理和技术》 (第二版) 陈意云 中国科学技术大学出版社 第9章第1节、第9章第2节 《编译原理及实践》 Kenneth C.Louden(美) 冯博琴等译机械工业出版社 第8章第9节

《程序设计语言 编译原理》（第二版） 陈火旺等 国防工业出版社 第9章 第1节 《编译原理和技术》（第一版） 陈意云 中国科学技术大学出版社 第9章 第1节、第9章 第2节 《编译原理和技术》（第二版） 陈意云 中国科学技术大学出版社 第9章 第1节、第9章 第2节 《编译原理及实践》 Kenneth C. Louden (美) 冯博琴 等 译 机械工业出版社 第8章 第9节

11.1 优化概述 参考文献 Compilers principles,techniques,and tools (2001) Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman. 第11章第1节、第11章第2节 Crafting a Compiler with C (1991), Charles N.Fischer,Richard J.LeBlanc Jr. 第16章第1节 《现代编译程序设计》 冯博琴等译 第4章第2节第11小节

Compilers :principles, techniques, and tools （2001）, Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. 第11章 第1节、第11章 第2节 Crafting a Compiler with C（1991）, Charles N. Fischer, Richard J. LeBlanc Jr. 第16章 第1节 《现代编译程序设计》 冯博琴等译 第4章 第2节 第11小节

11.1 优化概述 本节内容 一.代码优化概念、目的与原则 二.代码优化器的地位和结构 三.代码优化分类 四.代码优化涉及的各个环节 五.四元式的改写 六.引例：优化主要方法简介

一. 代码优化概念、目的与原则 二. 代码优化器的地位和结构 三. 代码优化分类 四. 代码优化涉及的各个环节 五. 四元式的改写 六. 引例：优化主要方法简介

代码优化既念、目的与原贝 对程序进行各种等价变换，使得从变换后的程序出发，能 生成更有效的目标代码，我们通常称这种变换为优化。 优化的目的是为了产生更高效的代码。 优化的原则： (1)等价原则 应尽可能以较低的代价 取得较好的优化效果。 (2)有效原则 (3)合算原则

优化的目的是为了产生更高效的代码。 对程序进行各种等价变换，使得从变换后的程序出发，能 生成更有效的目标代码，我们通常称这种变换为优化。 优化的原则： (1)等价原则 (3)合算原则 (2)有效原则 经过优化后不应改变 程序运行的结果。 使优化后所产生的目标 代码运行时间较短，占 用的存储空间较小。 应尽可能以较低的代价 取得较好的优化效果

二。个代预马允匕署器的地立乔回肯勾 1编译前端 伐码优化器下代码生成！ 控制流分析 数据流分析 代码变换

编译前端 代码优化器 代码生成 控制流分析 数据流分析 代码变换

三。代码优化分类 1.按所处阶段分类 最主要一类优化是在目标代码生成以前，对语法分析后 的中间代码进行的。这类优化不依赖于具体的计算机。 另一类重要的优化是在生成目标代码时进行的这 类优化很大程序上依赖于具体的计算机。 优化可在编译的各个阶段进行

另一类重要的优化是在生成目标代码时进行的这 类优化很大程序上依赖于具体的计算机。 优化可在编译的各个阶段进行 最主要一类优化是在目标代码生成以前，对语法分析后 的中间代码进行的。这类优化不依赖于具体的计算机。 1. 按所处阶段分类

三。代码优化分类 2.按所涉及范围 局部优化 单个基本块内 循环优化 可能涉及多个基本块 全局优化 涉及所有代码

单个基本块内 局部优化 2. 按所涉及范围 循环优化 涉及所有代码 全局优化 可能涉及多个基本块

四。代码优化涉及的各个环节 源代码 考虑产生更加高效的 设计语义 有效地利用寄存器 及，进 动作时 选择指令 中间代码 作 本章讨论的重点 目标代码 窥孔优化

选择适当的算法 源代码 安排适当的实现语句 源代码的优化很重要 设计语义 动作时 考虑产生更加高效的 中间代码 为后面的优化阶段做一些 中间代码 可能的预备工作 安排专门的优化阶段，进 行各种等价变换 本章讨论的重点 目标代码 有效地利用寄存器 选择指令 窥孔优化

五。四元式的改写 (:=,B,,A) 改写成 A:=B (op,B,,A) 改写成 A:=op B (op,B,C,A) 改写成 A:=B op C (=□，B,C,A) 改写成 A:=B[C] (]=,B,,D[C]) 改写成 D[C]=B (jrop,B,C,L) 改写成 if B rop C goto L (j L) 改写成 goto L

( := , B, , A) 改写成 A:=B (op , B, , A) 改写成 A:=op B (op , B, C, A) 改写成 A:=B op C (=[], B, C, A) 改写成 A:=B[C] ([]=,B, ,D[C]) 改写成 D[C]:=B (jrop, B, C, L) 改写成 if B rop C goto L (j , , , L) 改写成 goto L

六。引例：优化主要 T6=T11=4*灯 1.快速排序子程序：C语言-〉 x :a x:=a[Tl void quicksort (m,n); T7T12=4*1 int m,n; x=ali]; T8=T13=4*n int t x ali]; T14=aT1] f( a叮=a[n]i a[T]a[T2:=T14 i=m B1 while a[n]x; T1三T15=4*n B2 B3] aT]aTsl=× if(i> B4 goto E x=a B5 x=ali doj=j-1; 4*灯 while (a[j]v); Ts :a[T4] if Ts>v goto B3

1. 快速排序子程序： C语言-〉原始中间代码 B6 B1 B2 B3 B4 B5 i = m -1; j = n; v = a[n]; i := m-1 j := n T1 := 4*n v := a[T1] do i = i + 1; while (a[i] v); j := j-1 T4 := 4*j T5 := a[T4 ] if T5>v goto B3 if (i >= j) break; if i>=j goto B6 x = a[i]; a[i] = a[j]; a[j] = x; T6 := 4*i x := a[T6 ] T7 := 4*i T8 := 4*j T9 := a[T8 ] a[T7 ] := T9 T11 := 4*j a[T11] := x goto B2 x = a[i]; a[i] = a[n]; a[n] = x; T11 := 4*j x := a[T11] T12 := 4*i T13 := 4*n T14 := a[T13] a[T12] := T14 T15 := 4*n a[T15] := x