编译原理讲义 第八章代码优化) 南京大学计算机系 赵建华
编译原理讲义 (第八章 代码优化) 南京大学计算机系 赵建华
优化的概念 编译时刻为改进目标程序的质量而进行的各项工 作 空间效率 时间效率 空间效率和时间效率有时是一对矛盾,有时不能 兼顾。 优化的要求: 必须是等价变换 为优化的努力必须是值得的 有时优化后的代码的效率反而会下降
优化的概念 • 编译时刻为改进目标程序的质量而进行的各项工 作。 – 空间效率 – 时间效率 • 空间效率和时间效率有时是一对矛盾，有时不能 兼顾。 • 优化的要求： – 必须是等价变换 – 为优化的努力必须是值得的。 – 有时优化后的代码的效率反而会下降
优化的分类 机器相关性: 机器相关优化:寄存器优化,多处理器优化,特殊 指令优化,无用指令消除等 无关的优化: 优化范围: 局部优化:当个基本块范围内的优化,合并常量优 化,消除公共子表达式,削减计算强度和删除无用 代码。 全局优化:主要是基于循环的优化:循环不变式优 化,归纳变量删除,计算强度削减。 优化语言级 优化语言级:针对中间代码,针对机器语言
优化的分类 • 机器相关性： – 机器相关优化：寄存器优化，多处理器优化，特殊 指令优化，无用指令消除等。 – 无关的优化： • 优化范围： – 局部优化：当个基本块范围内的优化，合并常量优 化，消除公共子表达式，削减计算强度和删除无用 代码。 – 全局优化：主要是基于循环的优化：循环不变式优 化，归纳变量删除，计算强度削减。 – 优化语言级： • 优化语言级：针对中间代码，针对机器语言
代码优化程序的结构 控制流分析 数据流分析「代码变换 控制流分析的主要目的是分析出程序的循环结 构。循环结构中的代码的效率是整个程序的效 率的关键。 数据流分析进行数据流信息的收集,主要是变 量的值的获得和使用情况的数据流信息。 到达-定值分析;活跃变量;可用表达式; 代码变换:根据上面的分析,对内部中间 代码进行等价变换
代码优化程序的结构 • 控制流分析的主要目的是分析出程序的循环结 构。循环结构中的代码的效率是整个程序的效 率的关键。 • 数据流分析进行数据流信息的收集，主要是变 量的值的获得和使用情况的数据流信息。 – 到达-定值分析；活跃变量；可用表达式； • 代码变换：根据上面的分析，对内部中间 代码进行等价变换。 控制流分析 数据流分析 代码变换
基本块和流图 基本块中,控制流是由第一个四元式进 入,到达最后一个四元式离开。 ·流图:把一个程序的中间表示中所有的 基本块作为节点集合。有边从节点n到节 点n当且仅当控制流可能从n的最后的 个四元式到达n?的第一个四元式 首节点:对应的基本块的第一个四元式 是程序的第一个四元式
基本块和流图 • 基本块中，控制流是由第一个四元式进 入，到达最后一个四元式离开。 • 流图：把一个程序的中间表示中所有的 基本块作为节点集合。有边从节点n到节 点n’当且仅当控制流可能从n的最后的一 个四元式到达n’的第一个四元式。 • 首节点：对应的基本块的第一个四元式 是程序的第一个四元式