第十一章优化 ■简介 ■局部优化（重点） ■循环优化（难点) ■数据流分析（不介绍） ■作业 2025/4 课程目绿国回 1
2025/4/2 1 第十一章 优 化 ◼简介 ◼局部优化（重点） ◼循环优化（难点） ◼数据流分析(不介绍） ◼作业 课程目录
什么是代码优化p249 ■ 含义 ◆是指对程序进行各种等价变换，使得从变换后的程序出 发，能生成更有效的目标代码 ■代码优化器的地位和结构 编译前端 代码优化器 鸭产生 代码产生 控制流分析 数据流分析 代码变换 ◆优化可在编译的各个阶段进行 ◆最主要的一类优化是在目标代码生成之前，对语义分析 后的中间代码进行 2025/472 国回 2
2025/4/2 2 什么是代码优化 p249 ◼ 含义 ◆是指对程序进行各种等价变换，使得从变换后的程序出 发，能生成更有效的目标代码 ◼ 代码优化器的地位和结构 ◆优化可在编译的各个阶段进行 ◆最主要的一类优化是在目标代码生成之前，对语义分析 后的中间代码进行 编译前端 代码优化器 代码产生 控制流分析 数据流分析 代码变换
11.1优化技术简介 优化的目的和原则p249 ■优化目的 ◆产生更高效的目标代码 ◆合理利用计算机资源 ■优化原则 ◆等价一 不改变程序的运行结果 ◆高效一运行时间较短，占用存储空间较小 ◆合算—以较低的代价取得较好的优化效果 ◆例如优化算法虽然使最后生成的目标代码的运行时间 缩短，占用空间减少，但是若优化算本身运行是浪费了 过多的时间和空间，则从总上说就不一定合算 201 国 3
2025/4/2 3 11.1 优化技术简介 优化的目的和原则 p249 ◼ 优化目的 ◼ 优化原则 ◆产生更高效的目标代码 ◆合理利用计算机资源 ◆等价——不改变程序的运行结果 ◆高效——运行时间较短，占用存储空间较小 ◆合算——以较低的代价取得较好的优化效果 ◆例如 优化算法虽然使最后生成的目标代码的运行时间 缩短，占用空间减少，但是若优化算本身运行是浪费了 过多的时间和空间，则从总上说就不一定合算
■按阶段分成 优化的分类 ◆与机器无关的优化，对中间代码进行 ◆依赖于机器的优化，生成目标代码时进行 ■根据优化时所涉及的程序范围分成 ◆局部优化在基本块内部进行优化 ◆循环优化对循环中的代码进行优化 ◆全局优化大范围的优化，涉及整个程序 ■优化工作的基础 ◆控制流分析(data-flow analysis) ◆数据流分析(control-f1 ow analysis) ●变换(transformations) 进入下一环节 2025/4/2 国
2025/4/2 4 ◼ 按阶段分成 优化的分类 ◼ 根据优化时所涉及的程序范围分成 进入下一环节 ◆与机器无关的优化，对中间代码进行 ◆依赖于机器的优化，生成目标代码时进行 ◆局部优化 在基本块内部进行优化 ◆循环优化 对循环中的代码进行优化 ◆全局优化 大范围的优化，涉及整个程序 ◼ 优化工作的基础 ◆控制流分析(data-flow analysis) ◆数据流分析(control-flow analysis) ◆变换(transformations)
程序举例P249 例如 进入循环前 1)P:=0 (2）I:=1 P:=0; 一增1 for①1to20do (3)T1:=4*IA的可变 P:=P+A[I]*B[I] 4)T2:=A-4A的不变 (5)T3:=T2[T1]T3存A[I] 循 (6)T4:=4*I 翻译成三地址代码是： 环 (7)T5:=B-4 元素A[I]的地址 体 (8)T6:=T5[T4] T6存B[I] =base+(I-1)*w (9)T7:=T3*T6 =I*w+A-w 10)P:=P+T7 11)I:=I+1 =4*I+A-4 (12)ifI<=20goto(3) 问题：可采取哪些优化技术？ 202 5
2025/4/2 5 程序举例P249 例如 P:=0； for I:=1 to 20 do P:=P+A[I]* B[I]； 翻译成三地址代码是： (1)P:=0 (2)I:=1 元素A[I]的地址 =base+(I-1)*w =I*w+A-w =4*I+A-4 (3)T1:=4*I A的可变 (4)T2:=A-4 A的不变 (5)T3:=T2[T1] T3存A[I] (6)T4:=4*I (7)T5:=B-4 (8)T6:=T5[T4] T6存B[I] (9)T7:=T3*T6 (10)P:=P+T7 增1 (11)I:=I+1 (12)if I<=20 goto(3) 进入循环前 循 环 体 问题：可采取哪些优化技术？
优化技术举例P250 ↓ (①)P:=0 (1)P:=0 ■代码外提p276 (2)I:=1 (2)I:=1 (4)T2:=A-4 每次循环结果 (3)T1:=4*I (7)T5:=B-4 不改变的代码 4)T2=A-4 ■删除公共子 (⑤)T3:=T2T1] (3)T1:=4*I (6)T4:=4*I (5)T3:=T2[T1] 表达式p273 (7)T5:=B-4 (6)T4:=T1 删除多余运算 (8)T6:=T5T4] (8)T6:=T5[T4] (9)T7:=T3*T6 (9)T7:=T3*T6 避免重复计算 (10)P:=P+T7 (10)P:=P+T7 (11)I:=I+1 11)I:=I+1 (12)ifI<=20 (12)ifI<=20 goto(3) goto(3) 2025/472 ✉ 6
2025/4/2 6 优化技术举例P250 (1)P:=0 (2)I:=1 (3)T 1:=4*I (4)T 2:=A - 4 (5)T 3:=T 2[T 1 ] (6) T 4:=4*I (7)T 5:=B - 4 (8)T 6:=T 5[T 4 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (12)if I<=20 goto(3) ◼ 代码外提p276 每次循环结果 不改变的代码 (1)P:=0 (2)I:=1 (4)T 2:=A - 4 (7)T 5:=B - 4 ◼ 删除公共子 表达式 p273 删除多余运算 避免重复计算 (3)T 1:=4*I (5)T 3:=T 2[T 1 ] (6) T 4:= (8)T 6:=T 5[T 4 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (12)if I<=20 goto(3) T1
优化技术举例P250 (1)P:= )P:=0 ■强度削弱p277 (2)①：=1 (2)I:=1 (4)T2:=A-4 例如将循环中 (4)T2:=A-4 (7)T5:=B-4 (7)T5:=B-4 的*变换为+， (3)T1:=4*I 提高运算速度 (3)T1:=4*I I每次增1 5)T3:=T2T1] (5)T3:=T2[T1] (6)T4:=T1 T1每次增4 (6)T4:=T1 (8)T6:=T5[T4] (8)T6:=T5[T4] 外提(3) (9)T7:=T3*T6 (9)T7:=T3*T6 给T1赋初值 (10)P:=P+T7 (10)P:=P+T7 新增(3) (11)I:=I+1 (11)I:=I+1 (3)T1:=T1+4 给T1增4 (12)ifI<=20 goto(3) (12)ifI<=20 goto(5) 202 国回 7
2025/4/2 7 优化技术举例P250 ◼ 强度削弱p277 例如 将循环中 的*变换为+， 提高运算速度 (1)P:= (2)I:=1 0 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4*I (5)T 3:=T 2[T 1 ] (6)T 4:=T 1 (8)T 6:=T 5[T 4 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (12)if I<=20 goto(3) I每次增 1 T 1每次增 4 外提(3) 给T1赋初值 新增(3 ’ ) 给 T 1 增 4 (1)P:=0 (2)I:=1 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4*I (5)T 3:=T 2[T 1 ] (6)T 4:=T 1 (8)T 6:=T 5[T 4 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (3 ’)T 1:=T 1+4 (12)if I<=20 goto( 5 )
优化技术举例P251 TP:=0 DP:=0 ■复写传播p275 (2)L=1 (2)I:=1 例T6:=T2 (4)T2:=A-4 (4)T2:=A-4 (7)T5:=B-4 (7)T5:=B-4 (3)T1:=4米) (3)T1:=4*1 x:=T2 (5)T3:=T2[T1] (5)T3:=T2[T1] 目的：使对某 (6)T4:=T1 (6)T4:=T1 些变量的赋 (8)T6:=TT (8)T6:=T5[T] 值变为无用 (9)T7:=T3*T6 (9)T7:=T3*T6 (6)T4无用 (10)P:=P+T7 (10)P:=P+T7 (11)I:=I+1 (11)I:=I+1 (3)T1:=T1+4 (3)T1:=T1+4 (12)ifI<=20 (12)ifI<=20 goto(5) goto(5) 2025/42 国 8
2025/4/2 8 优化技术举例P251 ◼ 复写传播p275 例 T6:=T2 . x:= T 6 (1)P:=0 (2) I:= 1 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4* I (5)T 3:=T 2[T 1 ] (6) T 4:= T 1 (8)T 6:=T 5 [ T 4 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (3 ’)T 1:=T 1+4 (12)if I<=20 goto(5) 目的：使对某 些变量的赋 值变为无用 (6)T 4无用T 2 (1)P:=0 (2) I:= 1 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4* 1 (5)T 3:=T 2[T 1 ] (6) T 4:= T 1 (8)T 6:=T 5 [ T 1 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (3 ’)T 1:=T 1+4 (12)if I<=20 goto(5)
优化技术举例P251 (1)P:=0 ■删除归纳变量p277 (2)I:=1 例(11)I:=I+1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=T1+4T1:=4*I (3)T1:=4*1 T1与循环变量I保持线性关系 T1称为归纳变量 (5)T3:=T2[T1] (6)T4:=T1 因为I在其它地方没有引用 (8)T6:=T5[T] 所以(12)中条件可变换为 (9)T7:=T3*T6 (12)ifT1<=80goto(5) (10)P:=P+T7 (11)I:=I+1 故(2)I（11)I的赋值无用 3)T1:=T1+4 (12)ifT1=80 goto(5) 2025/4 国回 9
2025/4/2 9 优化技术举例P251 ◼ 删除归纳变量p277 例(11)I:=I+1 (3 ’)T 1:=T 1+4 T 1:=4*I T 1与循环变量 I保持线性关系 T 1称为归纳变量 因为 I在其它地方没有引用 所以(12)中条件可变换为 (12)if T 1<=80 goto(5) 故(2)I (11) I 的赋值无用 (1)P:=0 (2)I:=1 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4*1 (5)T 3:=T 2[T 1 ] (6)T 4:=T 1 (8)T 6:=T 5[T 1 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (3 ’)T 1:=T 1+4 (12)if I<=20 goto(5) T1<=80
优化技术举例P251 (①)P:=0 ■删除无用代码p276 ®1 例(2)I(6)T4(11)I (4)T2:=A-4 赋值无用 (7)T5:=B-4 (3)T1:=414 相应代码也无用，删除 ■合并已知量 (5)T3:=T2[T1] ① 例(3)直接计算 E中+ ■优化后，循环体内代 (8)T6:=T5[T1] 码从10条减少到6条 (9)T7:=T3*T6 (10)P:=P+T7 ④ 1&⊙-H (3)11:=T1+4 (12)if T1<=80 goto(5) 2025/4/2 国 10
2025/4/2 10 优化技术举例P251 ◼ 删除无用代码p276 例 (2) I 赋值无用 (1)P:=0 (2)I:=1 (4)T 2:=A - 4 (7)T 5:=B - 4 (3)T 1:=4*1 (5)T 3:=T 2[T 1 ] (6)T 4:=T 1 (8)T 6:=T 5[T 1 ] (9)T 7:=T 3*T 6 (10)P:=P+T 7 (11)I:=I+1 (3 ’)T 1:=T 1+4 (12)if T1<=80 goto(5) ◼ 合并已知量 例(3)直接计算 4 ◼ 优化后，循环体内代 码从10条减少到 6 条 相应代码也无用，删除 (6) T 4 (11) I ①②③④⑤⑥