编译原理讲义 第八章代码优化) 南京大学计算机系 赵建华
编译原理讲义 (第八章 代码优化) 南京大学计算机系 赵建华
优化的概念 编译时刻为改进目标程序的质量而进行的各项工 作 空间效率 时间效率 空间效率和时间效率有时是一对矛盾,有时不能 兼顾。 优化的要求: 必须是等价变换 为优化的努力必须是值得的 有时优化后的代码的效率反而会下降
优化的概念 • 编译时刻为改进目标程序的质量而进行的各项工 作。 – 空间效率 – 时间效率 • 空间效率和时间效率有时是一对矛盾，有时不能 兼顾。 • 优化的要求： – 必须是等价变换 – 为优化的努力必须是值得的。 – 有时优化后的代码的效率反而会下降
优化的分类 机器相关性: 机器相关优化:寄存器优化,多处理器优化,特殊 指令优化,无用指令消除等 无关的优化: 优化范围: 局部优化:当个基本块范围内的优化,合并常量优 化,消除公共子表达式,削减计算强度和删除无用 代码。 全局优化:主要是基于循环的优化:循环不变式优 化,归纳变量删除,计算强度削减。 优化语言级 优化语言级:针对中间代码,针对机器语言
优化的分类 • 机器相关性： – 机器相关优化：寄存器优化，多处理器优化，特殊 指令优化，无用指令消除等。 – 无关的优化： • 优化范围： – 局部优化：当个基本块范围内的优化，合并常量优 化，消除公共子表达式，削减计算强度和删除无用 代码。 – 全局优化：主要是基于循环的优化：循环不变式优 化，归纳变量删除，计算强度削减。 – 优化语言级： • 优化语言级：针对中间代码，针对机器语言
代码优化程序的结构 控制流分析 数据流分析「代码变换 控制流分析的主要目的是分析出程序的循环结 构。循环结构中的代码的效率是整个程序的效 率的关键。 数据流分析进行数据流信息的收集,主要是变 量的值的获得和使用情况的数据流信息。 到达-定值分析;活跃变量;可用表达式; 代码变换:根据上面的分析,对内部中间 代码进行等价变换
代码优化程序的结构 • 控制流分析的主要目的是分析出程序的循环结 构。循环结构中的代码的效率是整个程序的效 率的关键。 • 数据流分析进行数据流信息的收集，主要是变 量的值的获得和使用情况的数据流信息。 – 到达-定值分析；活跃变量；可用表达式； • 代码变换：根据上面的分析，对内部中间 代码进行等价变换。 控制流分析 数据流分析 代码变换
基本块和流图 基本块中,控制流是由第一个四元式进 入,到达最后一个四元式离开。 ·流图:把一个程序的中间表示中所有的 基本块作为节点集合。有边从节点n到节 点n当且仅当控制流可能从n的最后的 个四元式到达n?的第一个四元式 首节点:对应的基本块的第一个四元式 是程序的第一个四元式
基本块和流图 • 基本块中，控制流是由第一个四元式进 入，到达最后一个四元式离开。 • 流图：把一个程序的中间表示中所有的 基本块作为节点集合。有边从节点n到节 点n’当且仅当控制流可能从n的最后的一 个四元式到达n’的第一个四元式。 • 首节点：对应的基本块的第一个四元式 是程序的第一个四元式
流图的构造 以所有的基本块为节点集合 有B1到B2的边(B2是B1的后继)当且仅 当: B1的最后一个四元式有条件或无条件地转移 到B2的第一个四元式。 B2是紧紧跟随在B1后面的四元式,且B1的 最后四元式不是无条件转向语句
流图的构造 • 以所有的基本块为节点集合。 • 有B1到B2的边（B2是B1的后继）当且仅 当： – B1的最后一个四元式有条件或无条件地转移 到B2的第一个四元式。 – B2是紧紧跟随在B1后面的四元式，且B1的 最后四元式不是无条件转向语句
流图的例子 BI B f B2 fftbi2 t2 10 B4 GO B2 B4 f fib ·在转移语句中,目标标号转变称为基本块的编号, 可以避免因为四元式的变动而引起的麻烦
流图的例子 • 在转移语句中，目标标号转变称为基本块的编号， 可以避免因为四元式的变动而引起的麻烦。 = 1 _ i = 1 _ f = 0 _ a >= i 10 B4 = f _ b + f a t1 = t1 _ f = b _ a + i 1 t2 = t2 _ i GO B2 = f fib B1 B2 B3 B4
基本块的优化 合并常量计算 消除公共子表达式 削减计算强度 删除无用代码
基本块的优化 • 合并常量计算 • 消除公共子表达式 • 削减计算强度 • 删除无用代码
合并常量计算 例子:1=2*3.14* 23.14t1 ·2*3.1415926的值在编译时刻就可以确定 6.28r
合并常量计算 • 例子：l = 2*3.14*r – * 2 3.14 t1 – * t1 r t2 – = t2 l • 2*3.1415926的值在编译时刻就可以确定。 – * 6.28 r t2 – = t2 l
消除公共子表达式 + d b 显然,第2和4个四元式计算的是同一个值,所以第四 个四元式可以修改称为=b 对于第1和3个四元式,虽然都是计算b+c,但是他们 的值其实是不同的,所以不能完成处理。 ·公共表达式:如果某个表达式先前已经计算,且从上 次计算到现在,E中的变量的值没有改变。那么E的这 次出现称为公共子表达式。 利用先前的计算结果,可以避免对公共子表达式的重 复计算
消除公共子表达式 • + b c a - a d b • + b c c - a d d • 显然，第2和4个四元式计算的是同一个值，所以第四 个四元式可以修改称为 = b _ d。 • 对于第1和3个四元式，虽然都是计算b+c，但是他们 的值其实是不同的，所以不能完成处理。 • 公共表达式：如果某个表达式先前已经计算，且从上 次计算到现在，E中的变量的值没有改变。那么E的这 次出现称为公共子表达式。 • 利用先前的计算结果，可以避免对公共子表达式的重 复计算