第10章 代码优化 ■优化技术简介 ■局部优化（重点） ■光 循环优化 数据流分析（不介绍） ■ ■作业 2025/4/3 课程目录☒2
2025/4/3 1 第10章 代码优化 ◼优化技术简介 ◼局部优化（重点） ◼循环优化 ◼数据流分析(不介绍） ◼作业 课程目录
什么是代码优化 p255 ■含义 ◆是指对程序进行各种等价变换，使得从变换 后的程序出发，能生成更有效的目标代码 ■ 编译的优化工作阶段 源代码前端中间代码 代码产生 .目标代码 中间代码优化 目标代码优化 ◆优化可在编译的各个阶段进行 :Y ◆最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行 2025/4/3
2025/4/3 2 什么是代码优化 p255 ◼ 含义 ◆是指对程序进行各种等价变换，使得从变换 后的程序出发，能生成更有效的目标代码 ◼ 编译的优化工作阶段 ◆优化可在编译的各个阶段进行 ◆最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行 前端 中间代码 代码产生 中间代码优化 目标代码优化 源代码 目标代码
优化的目的和原则 ■优化目的 ◆产生更高效的目标代码 ◆合理利用计算机资源 ■优化原则 ◆等价 不改变程序的运行结果 ◆高效 运行时间较短，占用存储空间较小 ◆合算—以较低的代价取得较好的优化效果 ◆例如优化算法虽然使最后生成的目标代码的 运行时间缩短，占用空间减少，但是若优化算 本身运行是浪费了过多的时间和空间，则从总 上说就不一定合算 2025/4/3 ☒D 3
2025/4/3 3 优化的目的和原则 ◼ 优化目的 ◼ 优化原则 ◆产生更高效的目标代码 ◆合理利用计算机资源 ◆等价——不改变程序的运行结果 ◆高效——运行时间较短，占用存储空间较小 ◆合算——以较低的代价取得较好的优化效果 ◆例如 优化算法虽然使最后生成的目标代码的 运行时间缩短，占用空间减少，但是若优化算 本身运行是浪费了过多的时间和空间，则从总 上说就不一定合算
■按阶段分成 优化的分类 ◆与机器无关的优化，对中间代码进行 ◆依赖于机器的优化，生成目标代码时进行 ■根据优化时所涉及的程序范围分成 ◆局部优化在基本块内部进行优化 ◆循环优化对循环中的代码进行优化 ◆全局优化大范围的优化，涉及整个程序 ■优化工作的基础 ◆控制流分析(data-flow analysis) ◆数据流分析(control-flow analysis) ◆变换(transformations) 2025/4/3 章节目录国☑4
2025/4/3 4 ◼ 按阶段分成 优化的分类 ◼ 根据优化时所涉及的程序范围分成 ◆与机器无关的优化，对中间代码进行 ◆依赖于机器的优化，生成目标代码时进行 ◆局部优化 在基本块内部进行优化 ◆循环优化 对循环中的代码进行优化 ◆全局优化 大范围的优化，涉及整个程序 ◼ 优化工作的基础 ◆控制流分析(data-flow analysis) ◆数据流分析(control-flow analysis) ◆变换(transformations) 章节目录
11.2局部优化p251 ■定义 ◆局限于基本块范围内的优化 主要内容 ◆基本块及流图 ◆基本块的DAG表示及其应用 2025/4/3 章节目录5
2025/4/3 5 11.2 局部优化 p251 ◼定义 ◆局限于基本块范围内的优化 ◼主要内容 ◆基本块及流图 ◆基本块的DAG表示及其应用 章节目录
基本块的定义和性质p252 例如下基本块 (1)T1:=A*B ■基本块的定义 (2)T2:=3/2 ◆是指程序中一顺序执行的 语句 (3)T3:=T1-T2 语句序列，其中只有一个 (4)X:=T3 入口语句和一个出口语句 (5)C:=2 基本块的性质 (6)T4:=AB ■有唯一入口和唯一出口 (7)T5:=18+C ■块内各个操作按序执行， 出口 (8)T6:=T4*T5 不出现任何分叉 语句 (9)Y:=T6 基本块内的语句要么全执行， 要么全不执行，而不能只执行一部分 2025/4/3
2025/4/3 6 基本块的定义和性质 p252 ◼ 基本块的定义 ◆是指程序中一顺序执行的 语句序列，其中只有一个 入口语句和一个出口语句 例如下基本块 (1)T1:=A*B (2)T2:=3/2 (3)T3:=T1-T2 (4)X:=T3 (5)C:=2 (6)T4:=A*B (7)T5:=18+C (8)T6:=T4*T5 (9)Y:=T6 入口 语句 出口 语句 ◼ 基本块的性质 ◼ 有唯一入口和唯一出口 ◼ 块内各个操作按序执行， 不出现任何分叉 基本块内的语句要么全执行， 要么全不执行，而不能只执行一部分
基本块入口语句的确定p252 ■确定规则 规则1 1.程序的第一条语 8a号 句；或者 规则2 2.能由条件转移语 @或r0o goto (8) 句或无条件转移 规则3 语句转移到的语 @5X:= (6)Y:=R 句；或者 (7)goto (3) 3.紧跟在转移语句 后面的语句 规则2@8)ite (9)halt ■举例 共4个入口语句，对应4个基本块 2025/4/3 ☒D
2025/4/3 7 基本块入口语句的确定 p252 ◼ 确定规则 1.程序的第一条语 句；或者 2.能由条件转移语 句或无条件转移 语句转移到的语 句；或者 3.紧跟在转移语句 后面的语句 ◼ 举例 (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 共4个入口语句 规则2 规则1 规则2 规则3 ① ② ③ ④ ，对应4个基本块
划分基本块的算法p251 ■1.求出四元式程序中各个基本块的入口语句 ■2.对以上求出的每一个入口语句，构造其所 属的基本块。由该入口语句 (1)到另一入口语句（不包括该入口语句）或者 (2)到一转移语句（包括该转移语句）；或者 (3)到一停语句（包括该停语句） 之间的语句序列组成 ■3.凡未被纳入某一基本块的语句，都是程序 中控制流程无法到达的语句，从而也是不会 被执行到的语句，可把它们从程序中删除 2025/4/3
2025/4/3 8 划分基本块的算法 p251 ◼ 1.求出四元式程序中各个基本块的入口语句 ◼ 2.对以上求出的每一个入口语句，构造其所 属的基本块。由该入口语句 (1)到另一入口语句(不包括该入口语句)或者 (2)到一转移语句(包括该转移语句)；或者 (3)到一停语句(包括该停语句) 之间的语句序列组成 ◼ 3.凡未被纳入某一基本块的语句，都是程序 中控制流程无法到达的语句，从而也是不会 被执行到的语句，可把它们从程序中删除
划分基本块课堂练习 规则1I)read C (2)A:=0 (3)B:=1 规则2 @④A:=A+B (5)if B=C goto(8) 规则3 9迪 规则 2 (8)write A (9)halt 共4个入口语句，对应4个基本块 2025/4/3 ☒Dg
2025/4/3 9 划分基本块课堂练习 (1)read C (2)A:=0 (3)B:=1 (4)A:=A+B (5)if B=C goto(8) (6)B:=B+1 (7)goto(4) (8)write A (9)halt 共4个入口语句 规则2 规则1 规则2 规则3 ① ② ③ ④ ，对应4个基本块
程序流图构造举例 以基本块为结点，、以程序控制流为有向边的一张 有向图，用来描述程序 B1 B1(1)read x (1)read X (2)read Y (2)read Y B2f(3)R:=X mod Y B2 L(4)if R=0 goto(8) (3)R:=X mod Y B35)X:=Y (4)if R=0 goto(8) (6)Y:=R B3 B4 (7)goto(3) (5)X:=Y (8)write(Y) B4r(8)write Y (6)Y:=R (9)halt (9)halt (7)goto(3) 对应的程序流图 2025/4/3
2025/4/3 10 程序流图构造举例 ◼ 以基本块为结点，以程序控制流为有向边的一张 有向图，用来描述程序 (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 B1 (1)read X (2)read Y B2 (3)R:=X mod Y (4)if R=0 goto(8) B3 (5)X:=Y (6)Y:=R (7)goto(3) B4 (8)write(Y) (9)halt 对应的程序流图 B1 B2 B3 B4