编泽原理 第十章代码优化 2005/6/12
编译原理 第十章 代码优化 2005/6/12
编译原理 444444444“ 编译前端 代码优化器 代码产生 控制流分析 数据流分析 代码变换 图10,1 代码优化器的地位和结构 第2页
编译原理 第2页
编泽原理 主要内容 优化概述， 局部优化， 基本块的DAG表示及其应用， 控制流分析和循环查找算法， 到达定值与引用定值链， 墨循环优化 第3觉
编译原理 第3页 主要内容 优化概述， 局部优化， 基本块的DAG表示及其应用， 控制流分析和循环查找算法， 到达定值与引用定值链， 循环优化
编泽原理 第十章 代码优化 墨概述 墨三条优化原则 售局部优化 基本块的划分 基本块的变换 基本块优化的实现(DAG的使用） 墨流图（控制流程图】 循环 循环查找 马前置结点 可归纳流图 墨循环优化常用方法 第贡
编译原理 第4页 第十章 代码优化 概述 三条优化原则 局部优化 基本块的划分 基本块的变换 基本块优化的实现（DAG的使用） 流图 (控制流程图) 循环 循环查找 前置结点 可归纳流图 循环优化常用方法
编泽原理 第一节 概述 墨优化的定义：对程序进行各种等价变换，使得 变换后的代码运行结果与变换前代码运行结果 相同，而运行速度加大，或占用存储空间减少， 或两者都有。 空间效率和时间效率有时是一对矛盾，有时 不能兼顾。 第5页
编译原理 第5页 第一节 概 述 优化的定义:对程序进行各种等价变换，使得 变换后的代码运行结果与变换前代码运行结果 相同，而运行速度加大，或占用存储空间减少， 或两者都有。 空间效率和时间效率有时是一对矛盾，有时 不能兼顾
编译原理 三条优化原侧 等价：是指不改变程序的运行结果； 有效：主要指优化后的目标代码运行时间较短， 以及占用的存储空间较小。 香合算：应尽可能以较低的代价取得较好的优化 效果。 第6页
编译原理 第6页 三条优化原则 等价:是指不改变程序的运行结果； 有效:主要指优化后的目标代码运行时间较短, 以及占用的存储空间较小。 合算:应尽可能以较低的代价取得较好的优化 效果
编泽原理 售优化的时机 优化可在编译的各个阶段进行。最主要的时 机是在语法、语义分析生成中间代码之后，在中 间代码上进行。这一类优化不依赖于具体的计算 机，而取决于语言的结构。另一类优化则是在生 成目标程序时进行的，它在很大程度上与具体的 计算机有关。 按所涉及的程序范围可分为三种级别： 1、局部优化： 2、 循环优化； 3、 全局优化。 第7负
编译原理 第7页 优化的时机 优化可在编译的各个阶段进行。最主要的时 机是在语法、语义分析生成中间代码之后，在中 间代码上进行。这一类优化不依赖于具体的计算 机，而取决于语言的结构。另一类优化则是在生 成目标程序时进行的，它在很大程度上与具体的 计算机有关。 按所涉及的程序范围可分为三种级别 ： 1、局部优化; 2、循环优化; 3、全局优化
编泽原理 1)局部优化（基本块内）： 是指在基本块内进行的优化。由于这类优化是在顺序执 行的线性程序段上进行的，不存在转进转出、分叉汇合等问 题。所以处理起来比较简单。，在基本块上可进行常数合并， 冗余子表达式的消除等优化处理。 2)循环优化（对循环中的代码进行优化）： 是对循环语句所生成的中间代码序列所进行的优化处理， 属这类优化的有循环展开，频度削弱和强度削弱。 3)全局优化大范围的优化)： 是在非线性程序段上的优化。因为程序段是非线性的， 因此需要分析程序的控制流和数据流，处理比较复杂。 第8觉
编译原理 第8页 1）局部优化(基本块内)： 是指在基本块内进行的优化。由于这类优化是在顺序执 行的线性程序段上进行的，不存在转进转出、分叉汇合等问 题。所以处理起来比较简单。在基本块上可进行常数合并， 冗余子表达式的消除等优化处理。 2）循环优化(对循环中的代码进行优化): 是对循环语句所生成的中间代码序列所进行的优化处理， 属这类优化的有循环展开，频度削弱和强度削弱。 3）全局优化(大范围的优化)： 是在非线性程序段上的优化。因为程序段是非线性的， 因此需要分析程序的控制流和数据流，处理比较复杂
编泽原理 变量的引用点和定值点 点：某一四元式的位置。 引用点（使用点）：在该点使用了该变量。 如：表达式中的变量。 定值点（定义点）：在该点变量被赋值或输入值。 如：赋值语句左部的变量。 例1：x:(定义点)=（⑤引用点）+1； 例2：x:=y+z称为对x定值并引用y和z。 第9负
编译原理 第9页 变量的引用点和定值点 点：某一四元式的位置。 引用点(使用点):在该点使用了该变量。 如:表达式中的变量。 定值点(定义点):在该点变量被赋值或输入值。 如：赋值语句左部的变量。 例1： x :(定义点)= x(引用点) + 1; 例2: x:＝y＋z称为对x定值并引用y和z
编译原理 第二节局部优化 慧基本块内的变换为局部优化。 墨基本块定义：程序中一顺序执行的语句序列：其中只 有一个入口语句第一条语句)，一个出口语句（最后一 条语句) 量执行时只能从入口语句进入，从出口语句退出，中 途没有停止或分枝。 第10页
编译原理 第10页 第二节 局部优化 基本块内的变换为局部优化。 基本块定义: 程序中一顺序执行的语句序列:其中只 有一个入口语句(第一条语句),一个出口语句(最后一 条语句)。 执行时只能从入口语句进入，从出口语句退出，中 途没有停止或分枝