第10章（1)代码优化 n简介 n优化程序举例 n10.1基本块流图和循环 n10.3代码优化技术 n10.3.2局部优化（重点） n10.3.3循环优化（难点） n 数据流分析（不介绍） 作业 n 2023/2/28 课程目录②6
2023/2/28 第10章（1）代码优化 n 简介 n 优化程序举例 n 10.1 基本块、流图和循环 n 10.3 代码优化技术 n 10.3.2 局部优化（重点） n 10.3.3 循环优化（难点） n 数据流分析（不介绍） n 作业 课程目录 1/36
什么是代码优化p255 n含义 u是指对程序进行各种等价变换，使得从变换 后的程序出发，能生成更有效的目标代码 n编译的优化工作阶段 源代码.前端→中间代码代码产生.目标代码 中间代码优化 目标代码优化 u优化可在编译的各个阶段进行 最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行° 2023/2/28 国D 2/36
2023/2/28 什么是代码优化 p255 n 含义 u 是指对程序进行各种等价变换，使得从变换 后的程序出发，能生成更有效的目标代码 n 编译的优化工作阶段 u优化可在编译的各个阶段进行 u最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行 前端 中间代码 代码产生 中间代码优化 目标代码优化 源代码 目标代码 2/36
优化的目的和原则 n优化目的 u产生更高效的目标代码 u 合理利用计算机资源 n优化原则 等价 不改变程序的运行结果 u高效 运行时间较短，占用存储空间较小 u合算— 以较低的代价取得较好的优化效果 u例如 优化算法虽然使最后生成的目标代码的 运行时间缩短，占用空间减少，但是若优化算 本身运行是浪费了过多的时间和空间，则从总 上说就不一定合算 2023/2/28 ☒> 3136
2023/2/28 优化的目的和原则 n 优化目的 n 优化原则 u 产生更高效的目标代码 u 合理利用计算机资源 u 等价——不改变程序的运行结果 u 高效——运行时间较短，占用存储空间较小 u 合算——以较低的代价取得较好的优化效果 u 例如 优化算法虽然使最后生成的目标代码的 运行时间缩短，占用空间减少，但是若优化算 本身运行是浪费了过多的时间和空间，则从总 上说就不一定合算 3/36
n按阶段分成 优化的分类 u与机器无关的优化，对中间代码进行 u依赖于机器的优化，生成目标代码时进行 n根据优化时所涉及的程序范围分成 u局部优化在基本块内部进行优化 u循环优化对循环中的代码进行优化 u全局优化大范围的优化，涉及整个程序 n优化工作的基础 u控制流分析(data-flow analysis) u数据流分析(control-flow analysis) 变换(transformations)) 2023/2/28 章节目录国> 4/36
2023/2/28 n 按阶段分成 优化的分类 n 根据优化时所涉及的程序范围分成 u 与机器无关的优化，对中间代码进行 u 依赖于机器的优化，生成目标代码时进行 u 局部优化 在基本块内部进行优化 u 循环优化 对循环中的代码进行优化 u 全局优化 大范围的优化，涉及整个程序 n 优化工作的基础 u 控制流分析(data-flow analysis) u 数据流分析(control-flow analysis) u 变换(transformations) 章节目录 4/36
程序举例 (①)P:=0 例如 进入循环前 (2)I:=1 P增 fof○：=1to20do (3)T1:=4*灯A的可变 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) 问题：可采取哪些优化技术？ 2023/2/28
2023/2/28 程序举例 例如 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) 进入循环前 循 环 体 问题：可采取哪些优化技术？ 5/36
优化技术举例 (①)P:=0 (1)P:=0 n代码外提 (2)I:=1 (2)I:=1 (4)T2:=A-4 每次循环结果 (3)T1:=4*I (7)T5:=B-4 不改变的代码 (4)T2:=A-4 (⑤)T3:=T2Ti] (3)T1:=4*I n删除公共子 (6)T4:=4*I (5)T3:=T2[T1] 表达式 (7)T5:=B-4 (6)T4:=T1 删除多余运算 8)T6:=15T4] (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) 2023/2/28 I区 6/36
2023/2/28 优化技术举例 (1)P:=0 (2)I:=1 (3)T1:=4*I (4)T2:=A-4 (5)T3:=T2[T1] (6)T4:=4*I (7)T5:=B-4 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3) n 代码外提 每次循环结果 不改变的代码 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 n 删除公共子 表达式 删除多余运算 避免重复计算 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:= (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3) T1 6/36
优化技术举例 (1)P:=0 (1)P:=0 n强度削弱 (2)I:=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*T I每次增1 (⑤)T3:=T2IT1] (5)T3:=T2[T1] (6)T4:=T1 (6)T4:=T1 T1每次增4 (8 T6:=T5[T4] (8)T6:=T5[T4] 外提(3) (9)T7:=T3*T6 (9)T7:=T3*T6 给T赋初值 (10)P:=P+T7 (10)P:=P+T7 新增(3) (11)I:=I+1 (11)I:=I+1 3)T1:=T1+4 给T增4 12)ifI<=20 goto(3) (12)1fI<=20 goto (5) 2023/2/28 7/36
2023/2/28 优化技术举例 n 强度削弱 例如 将循环中 的*变换为+， 提高运算速度 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3) I每次增1 T1每次增4 外提(3) 给T1赋初值 新增(3’) 给T1增4 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if I<=20 goto(5) 7/36
优化技术举例 (1P:=0 (1)P:=0 n复写传播 (2)I:=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:=T5①4 (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) 2023/2/28 ☒28/36
2023/2/28 优化技术举例 n 复写传播 例 T6:=T2 . x:=T6 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if I<=20 goto(5) 目的：使对某 些变量的赋 值变为无用 (6)T4无用 T2 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*1 (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T1] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if I<=20 goto(5) 8/36
优化技术举例 (1)P:=0 n删除归纳变量 (2)I:=1 例(11)I:=I+1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=T1+4T1:=4*灯 (3)T1:=4*1 T1与循环变量I保持线性关系 T称为归纳变量 (5)T3:=T2[T] (6)T4:=T1 因为I在其它地方没有引用 (8)T6:=T5[T1] 所以(12)中条件可变换为 (9)T7:=T3*T6 (12)ifT1=80goto(5) (10)P:=P+T7 (11)I:=I+1 故(2)I(11)II的赋值无用 (3)T1:=T1+4 (12)ifT1<=80 goto (5) 2023/2/28 9/36
2023/2/28 优化技术举例 n 删除归纳变量 例(11)I:=I+1 (3’)T1:=T1+4 T1:=4*I T1与循环变量I保持线性关系 T1称为归纳变量 因为I在其它地方没有引用 所以(12)中条件可变换为 (12)if T1<=80 goto(5) 故(2)I (11) I 的赋值无用 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*1 (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T1] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if I<=20 goto(5) T1<=80 9/36
优化技术举例 (1)P:=0 n删除无用代码 €士 例(2)I(6)T4(11)I (4)T2:=A-4 (7)T5:=B-4 赋值无用 (3)T1:=*14 相应代码也无用，删除 n合并已知量 (5)I3:=T2[T1] ① 例(3)直接计算 6T+ n优化后，循环体内代 (8)T6:=T5[T1] 码从10条减少到6条 (9)T7:=T3*T6 (10)P:=P+T7 ④ ®+H (3)1:=T1+4 (12)ifT1<=80 ⑥ goto (5) 2023/2/28 ☑D10/36
2023/2/28 优化技术举例 n 删除无用代码 例 (2) I 赋值无用 (1)P:=0 (2)I:=1 (4)T2:=A-4 (7)T5:=B-4 (3)T1:=4*1 (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T1] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if T1<=80 goto(5) n 合并已知量 例(3)直接计算 4 n 优化后，循环体内代 码从10条减少到6条 相应代码也无用，删除 (6) T4 (11) I ① ② ③ ④ ⑤ ⑥ 10/36