第10章（1)代码优化 n简介 n10.1基本块流图和循环 n 10.3代码优化技术 n10.3.2局部优化（重点） n10.3.3循环优化（难点） n 数据流分析（不介绍） n 作业 2023/2/28 课程目录国②115
2023/2/28 第10章（1）代码优化 n 简介 n 10.1 基本块、流图和循环 n 10.3 代码优化技术 n 10.3.2 局部优化（重点） n 10.3.3 循环优化（难点） n 数据流分析（不介绍） n 作业 课程目录 1/15
什么是代码优化 p255 n含义 u等价变换，生成更有效的目标代码 n编译的优化工作阶段 源代码.前端中间代码代码产生目标代码 中间代码优化 目标代码优化 u优化可在编译的各个阶段进行 最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行 2023/2/28 国 2/15
2023/2/28 什么是代码优化 p255 n 含义 u 等价变换，生成更有效的目标代码 n 编译的优化工作阶段 u优化可在编译的各个阶段进行 u最主要的一类优化是在目标代码生成之前，对 语义分析后的中间代码进行 前端 中间代码 代码产生 中间代码优化 目标代码优化 源代码 目标代码 2/15
优化的目的和原则 n优化目的 u产生更高效的目标代码一一时间空间 u合理利用计算机资源一一指令寄存器 n 优化原则 u等价 不改变程序的运行结果 u 高效 运行时间较短，占用存储空间较小 u合算— 以较低的代价取得较好的优化效果 例如：优化算法生成目标代码运行时间缩短， 占用空间减少，但若优化算法本身运行是浪费 了过多的时间和空间，则不一定合算 2023/2/28 ☒2315
2023/2/28 优化的目的和原则 n 优化目的 n 优化原则 u 产生更高效的目标代码——时间 空间 u 合理利用计算机资源——指令 寄存器 u 等价——不改变程序的运行结果 u 高效——运行时间较短，占用存储空间较小 u 合算——以较低的代价取得较好的优化效果 u 例如：优化算法生成目标代码运行时间缩短， 占用空间减少，但若优化算法本身运行是浪费 了过多的时间和空间，则不一定合算 3/15
优化的分类 n按阶段分成 ù与机器无关的优化，对中间代码进行 u依赖于机器的优化，生成目标代码时进行 n根据优化时所涉及的程序范围分成 u局部优化在基本块内部进行优化 ù循环优化对循环中的代码进行优化 全局优化大范围的优化，涉及整个程序 n优化工作的基础 u控制流分析(data-flow analysis) u 数据流分析(control-f1 ow analysis) u变换(transformations) 2023/2/28 章节目绿☒ 4/15
2023/2/28 优化的分类 n 按阶段分成 n 根据优化时所涉及的程序范围分成 u 与机器无关的优化，对中间代码进行 u 依赖于机器的优化，生成目标代码时进行 u 局部优化 在基本块内部进行优化 u 循环优化 对循环中的代码进行优化 u 全局优化 大范围的优化，涉及整个程序 章节目录 4/15 n 优化工作的基础 u 控制流分析(data-flow analysis) u 数据流分析(control-flow analysis) u 变换(transformations)
例如下基本块 基本块的定义和性质p255 一(1)T1:=AB 入▣ (2)T2:=3/2 n基本块的定义 语句 (3)T3:=T1-T2 u是指程序中一顺序执行的 (4)X:=T3 语句序列，其中只有一个 (5)C:=2 入口语句和一个出口语句 (6)T4:=A*8 n基本块的性质 (7)T5:=18+℃ 出▣ (8)T6:=T4*T5 语句 (9)Y:=T6 基本块内的语句要么全执行， 要么全不执行，而不能只执行一部分 2023/2/28 D515
2023/2/28 基本块的定义和性质 p255 n 基本块的定义 u 是指程序中一顺序执行的 语句序列，其中只有一个 入口语句和一个出口语句 例如下基本块 (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 入口 语句 出口 语句 n 基本块的性质 基本块内的语句要么全执行， 要么全不执行，而不能只执行一部分 5/15
n合并常数和已知量 常用局部优化技术p270 (2)编译时计算(2) (1)T1:=A*8 (1)T1:=A*B (7)编译时计算(7) n删除多余运算 2)T2.=3/2 2T2=1. (1)(6)AB公共子表达式 8)3.=1T23')①3：=T1- 只需计算一次(6) n复写传播 (4)X:-③ (2)X:=T1-1.5 (3)引用T2(3) 5)C.=2 (8)引用T4,T5(8) （6)T4.=*8 6T4:=T一 n删除无用赋值 设所有临时变量T和C在以后无 (7分T5.-18+e 7T5.=2 用，则除了计算x,Y时要用到8)T6:-4*508'6:=T1*20 的变量保留外，删除其它赋值 (9)Y:-6 (2)(5)(6)(7) (3)Y:=T1*20 优化后只有5条代码 进一步优化后只有3条代码，如何实现？ 2023/2/28 1D6/15
2023/2/28 常用局部优化技术 p270 n 删除无用赋值 设所有临时变量T和C在以后无 用，则除了计算X，Y时要用到 的变量保留外，删除其它赋值 (2)’(5)’(6)’(7)’ (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 优化后只有5条代码 n合并常数和已知量 (2) 编译时计算(2’) (7) 编译时计算(7’) (2’)T2:=1. 5 (7’)T5:=2 0 n复写传播 (3)引用T2 (3’) (8)引用T4，T5 (8’) n删除多余运算 (1)(6) A*B公共子表达式 只需计算一次 (6’) (6’)T4:=T 1 (3’)T3:=T1- 1.5 (8’)T6:=T1*20 进一步优化后只有3条代码,如何实现？ (1)T1:=A*B (2)X:=T1-1.5 (3)Y:=T1*20 6/15
基本块的DAG表示及其应用 p27110.3.2 n基本块的DAG构造算法部分优化 n 基本块的DAG应用进一步优化 2023/2/28 ☒D715
2023/2/28 基本块的DAG表示及其应用 p271 10.3.2 n 基本块的DAG构造算法 部分优化 n 基本块的DAG应用 进一步优化 7/15
基本块的DAG表示举例 n有向无环图 DAG结点建立顺序 三地址代码 DAG表示 重建代码 过程 及结点对应表 (1)c:=a+b (1)c:=a+b 别除 (2)a:=cd (2)a:=c-d 多余 编结点 附加 (3)b:=a+b (3)d:=a 运算 针针 标记 (4)d:=c-d (4)b:=a+b 1 2c 附加标记（右边） n3/ n4 do do √5 3 4a,d 6+ 5 2b 标记（下边） ao 2023/2/28 ☒> 8/15
2023/2/28 基本块的DAG表示举例 n 有向无环图 三地址代码 (1)c:=a+b (2)a:=c-d (3)b:=a+b (4)d:=c-d 编 号 结点 标记 左 指 针 右 指 针 附加 标记 n1 a0 1 a0 b0 2 b0 n3 + 标记(下边) 附加标记(右边) c 3 + 1 2 c DAG结点建立顺序 及结点对应表 n4 d0 4 d0 n5 - a 5 - 3 4 a n6 + b 6 + 5 2 b ,d ,d DAG表示 过程 删除 多余 运算 重建代码 √ √ √ (1)c:=a+b √ √ (2)a:=c-d (3)d:=a √ (4)b:=a+b n2 8/15
基本块的DAG表示 n 基本块的DAG u结点带有标记或附加标记的DAG nk b ni附加标记 ni op n叶结点 标记 3 800 u标记是一个标识符（变量名）或常数 u代表该变量或常数的值举例 变量a的初帽0 n内部结点 n附加标安 表b:=3ta 块外无但) u标记是一个运算符 一个或多美量的当 u u代表其直接后继结点值 可以附加到蘑索 进行该运算的结果举例 u表示这些变量持有该 结点所代表的值举例 2023/2/28 9115
2023/2/28 基本块的DAG表示 n 基本块的DAG u 结点带有标记或附加标记的DAG ni 标记 附加标记 n 叶结点 u 标记是一个标识符(变量名)或常数 u 代表该变量或常数的值 举例 ni 3 nj a0 变量a的初值 表示该值由 块外定值， 以免与a的当 前值混淆 n 内部结点 u 标记是一个运算符 u 代表其直接后继结点值 进行该运算的结果 举例 ni nj nk op n 附加标记 u 一个或多个变量 u 可以附加到各个结点 u 表示这些变量持有该 结点所代表的值举例 b:=3+a 3 a0 + b 9/15
基本块的DAG构造举例p273~274 原代码 对应表 DAG构造过程 (1)To:=3.14 标 加 号 左佑 标记 删除 一(2)T1:=2*T0 1 3.14 To 其它B (3)T2:=R+r 26.28 TL Ts 一(4)A:=T1*T2 3 Ro 4 ro n6 一(5)B:=A 5 3 4T2,T4 一(6)T3:=2*T0 6 米 2 5A,R, 3 n5 一(7)T4:=R+r 4T6 8 米 6 一(8)T五=①*T4 一(9)T6:=R-rA=6.28* n2 n3 n4 12 (10)B:=T5*T6 3.14 6.28 Ro 合并已知量 删除无用赋值 删除多余运算 复写传播 2023/2/28 10/15
2023/2/28 基本块的DAG构造举例 p273～274 原代码 (1)T0:=3.14 (2)T1:=2*T0 (3)T2:=R+r (4)A:=T1*T2 (5)B:=A (6)T3:=2*T0 (7)T4:=R+r (8)T5:=T3*T4 (9)T6:=R-r (10)B:=T5*T6 对应表 编 号 标 记 左 右 附加 标记 DAG构造过程 n1 3.14 T0 1 3.14 T0 n2 2 n2 6.28 T1 2 6.28 T1 n3 R0 3 R0 n4 r0 4 r0 n5 + T2 5 + 3 4 T2 n6 * A 6 * 2 5 A ,B ,B n7 2 ,T3 ,T3 ,T4 ,T4 ,T5 ,T5 n7 － T6 7 - 3 4 T6 n8 * B 删除 其它B 8 * 6 7 B 合并已知量 删除多余运算 删除无用赋值 复写传播 A=6.28*T2 10/15