第五章 代码优化

《第五章 代码优化》由会员分享，可在线阅读，更多相关《第五章 代码优化（56页珍藏版）》请在文档大全上搜索。

1、第五章代码优化5.1 局部优化局部优化5.2 循环优化循环优化优化的概念优化的概念v代码优化代码优化 对代码进行等价变换，使得变换后的代码具有更高对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。的时间效率和空间效率。v空间效率和时间效率有时是一对矛盾，有时不能兼空间效率和时间效率有时是一对矛盾，有时不能兼顾。顾。v优化要求优化要求必须是等价变换必须是等价变换( (保持功能保持功能) )为优化的努力必须是值得的为优化的努力必须是值得的v机器相关性机器相关性机器相关优化：寄存器优化，多处理器优化，特殊指机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。令优化，

2、无用指令消除等。机器无关优化：对中间代码的优化。机器无关优化：对中间代码的优化。v优化范围优化范围局部优化：单个局部优化：单个基本块基本块范围内的优化，包括常量合并、范围内的优化，包括常量合并、公共子表达式删除、计算强度削弱和无用代码删除等。公共子表达式删除、计算强度削弱和无用代码删除等。全局优化：主要是全局优化：主要是基于循环基于循环的优化，包括循环不变量的优化，包括循环不变量代码外提、删除归纳变量、计算强度削弱等。代码外提、删除归纳变量、计算强度削弱等。v优化语言级优化语言级优化语言级：针对中间代码，针对机器语言。优化语言级：针对中间代码，针对机器语言。代码优化的分类代码优化的分类v控制流

3、分析控制流分析的主要目的是分析出程序的循环结构。的主要目的是分析出程序的循环结构。 循环结构中的代码的效率是整个程序的效率的关键。循环结构中的代码的效率是整个程序的效率的关键。v数据流分析数据流分析进行数据流信息的收集，主要是变量的值进行数据流信息的收集，主要是变量的值 的获得和使用情况的数据流信息。的获得和使用情况的数据流信息。到达到达- -定义分析；活跃变量分析；可用表达式分析；定义分析；活跃变量分析；可用表达式分析；v代码变换代码变换：根据上面的分析，对内部中间代码进行等：根据上面的分析，对内部中间代码进行等 价变换。价变换。控制流分析控制流分析数据流分析数据流分析代码变换代码变换代码优

4、化主要完成的工作代码优化主要完成的工作5.1 局部优化局部优化v指基本块内的优化。指基本块内的优化。v基本块：基本块：是指程序（本课本中假设已经是四是指程序（本课本中假设已经是四元式表示的程序了）中一顺序执行的语句序元式表示的程序了）中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。列，其中只有一个入口语句和一个出口语句。5.1.1 基本块的划分基本块的划分v入口语句入口语句（1）四元式语句序列的第一个语句；）四元式语句序列的第一个语句；（2）条件转移语句或无条件转移语句转移到）条件转移语句或无条件转移语句转移到的目标语句；的目标语句；（3）紧跟在条件转移语句后面的语句。）紧跟在条件

5、转移语句后面的语句。v出口语句出口语句（1）下一个入口语句的前导语句；）下一个入口语句的前导语句；（2）转移语句（包括其自身）；）转移语句（包括其自身）；（3）停语句（包括其自身）。）停语句（包括其自身）。v基本块的划分基本块的划分1、求出四元式程序之中各个基本块的入口语句。、求出四元式程序之中各个基本块的入口语句。2、对每一入口语句，构造其所属的基本块。即由该、对每一入口语句，构造其所属的基本块。即由该入口语句到出口语句之间的语句序列。入口语句到出口语句之间的语句序列。3、凡未被纳入某一基本块的语句，都是程序中控制、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被

6、执行到的流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。语句，可以把它们删除。(1) read (C)(2) A= 0(3) B= 1(4) L1: A=A + B(5) if B= C goto L2(6) B=B+1(7) goto L1(8) L2: write (A)(9) halt为其划分基本块。为其划分基本块。【例】有四元式代码程序如下：【例】有四元式代码程序如下：5.1.2 基本块的基本块的DAG表示表示vDAG 指有向无环图（指有向无环图（ Directed Acyclic Graph ），），常用来对基本块进行优化。常用来对基本块进行优化。v基本块的基本块的

7、DAG 是是在结点上带有标记在结点上带有标记的的 DAG。 叶结点叶结点 代表名字的初值，以唯一的标识符（变量代表名字的初值，以唯一的标识符（变量名字或常数）标记。通常用名字或常数）标记。通常用x0表示变量名字表示变量名字x的初的初值。值。 内部结点内部结点 用运算符作为标记。用运算符作为标记。 所有结点所有结点都可有都可有一个或多个一个或多个附加标识符，表示这些附加标识符，表示这些变量具有该结点所代表的值。变量具有该结点所代表的值。 （其他四元式的其他四元式的 DAG 结点形式参见教材结点形式参见教材P131图图5-1）DAG 结点结点 A BAop Bop n1 n2BCn1n2n1n3n

8、1n2四元式四元式A=BA=op BA= B op CA运算符标记运算符标记四元式和与其对应的四元式和与其对应的DAGDAG结点形式结点形式 基本块基本块 DAG 表示的构造算法表示的构造算法 设设 A=B, A=op B, A=B op C分别为第分别为第0、1、2型四元式，设型四元式，设函数函数 Node(name) 返回最近创建的关联于返回最近创建的关联于 name 的结点。的结点。 首先，置首先，置 DAG 为空。为空。 对基本块的每一个四元式，依次执行下列步骤：对基本块的每一个四元式，依次执行下列步骤： v若若 Node(B) 无定义，则创建一个标记为无定义，则创建一个标记为 B 的

9、叶结点，并令的叶结点，并令Node(B) 为这个结点；为这个结点； (1) 对于对于2型四元式型四元式，v若若Node(C) 无定义，再创建标记为无定义，再创建标记为C 的叶结点，并令的叶结点，并令 Node(C) 为这个结点。为这个结点。v若若 Node(B)和和 Node(C)都是标记为常数的叶结点，都是标记为常数的叶结点，执行执行B op C，令得到的新常数为，令得到的新常数为p。 若若Node(p) 无定义，则构造一个用无定义，则构造一个用 p 做标记的叶结做标记的叶结点点 n,置置Node(p)=n。 若若 Node(B) 或或 Node(C)是处是处理当前语句时新构造出来的结点，则

10、删除它。理当前语句时新构造出来的结点，则删除它。 （这一步有（这一步有合并已知量合并已知量的作用）的作用）v若若 Node(B) 或或 Node(C)不是标记为常数的叶结点，不是标记为常数的叶结点，则检查是否存在某个标记为则检查是否存在某个标记为 op 的结点，其左孩的结点，其左孩子是子是 Node(B) ，而右孩子是，而右孩子是Node(C) ？ 若无，则创建这样的结点。若无，则创建这样的结点。 若有，则把已有的结点作为它的结点并且若有，则把已有的结点作为它的结点并且 无论有无，都令该结点为无论有无，都令该结点为 n。（这一步有（这一步有删除多余运算删除多余运算的作用）的作用）(2)对于对于

11、1型四元式型四元式v若若 Node(B) 是标记为常数的叶结点，则执行是标记为常数的叶结点，则执行 op B，令得到的新常数为，令得到的新常数为p. 若若 Node(p)无定义，则无定义，则构造一个用构造一个用 p 做标记的叶结点做标记的叶结点 n，置，置node(p)=n。 若若Node(B) 是处理当前语句时新构造出来的结点，是处理当前语句时新构造出来的结点，则删除它。（这一步有则删除它。（这一步有合并已知量合并已知量的作用）的作用）v若若 Node(B) 不是标记为常数的叶结点，则不是标记为常数的叶结点，则检查是否存在某个标记为检查是否存在某个标记为 op 的结点，其的结点，其唯一的孩子