9编译009.ppt.ppt

第7章 代码优化 学习目标： 掌握：基本块的划分、基本块的DAG优化 理解：什么是局部优化、循环优化、全局优化 了解：循环优化技术 7.1 优化技术简介 什么是优化： 所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之） 优化可在编译的不同阶段进行，最主要的优化有 中间代码优化（不依赖具体计算机） 目标代码优化（依赖于具体计算机） 优化的分类： 根据优化涉及的程序范围，分为： 局部优化：在只有一个入口、一个出口的基 本块上进行优化 循环优化：对循环中的代码进行优化 全局优化：在整个程序范围内进行的优化 中间代码优化常用技术 1.? 删除多余运算（删除公共子表达式） 如果子表达式E在前面计算过，且之后E中的变量值都未改变，那么E的重复出现称为公共子表达式，可避免重复计算 2. 合并已知量与复写传播 如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量 若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。 3. 删除无用赋值 有些变量的赋值从未被引用，称为无用赋值，应删除。 无用赋值分三种情况： 变量被赋值，但在程序中从未被引用（在局部范围内难判定） ?变量赋值后未被引用又重新赋值，则前面赋值是无用的 ?变量的赋值只被计算变量自己引用，其他变量都不引用它 例 （1） I:=1 （2）T1:=4 （3）T3:=T2[T1] （4）T4:=T1 （5）I:=I+1 （6）T1:=T1+4 （7）if T1≤80 goto (3) 4. 其他优化技术 以下优化技术将在循环优化中介绍： 代码外提 强度削弱 变换循环控制条件（删除归纳变量） 7.2 局部优化 局部优化是指基本块内的优化 基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出 7.2.1 基本块的划分 把程序（中间代码形成）划分成基本块的算法： 1.??求基本块的入口语句，它们是： 程序的第一个语句；或者 条件转移或无条件转移语句的转移目标语句；或者 紧跟在条件转移语句后面的语句。 2．对每一入口语句，构造其所属的基本块: 它是由该入口语句到下一入口语句(不包括下一入口语句); 或到一转移语句(包括该转移语句); 或到一停止语句(包括该停止语句) 之间的语句序列组成的。 3．凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除。 例： read X read Y R:=X mod Y if R=0 goto (8) X:=Y Y:=R goto (3) write Y halt 7.2.2 基本块的DAG表示 DAG(Directed Acyclic Graph)是无环路有向图的简称 1. 基本块的DAG是一种其结点带有标记或附加信息的DAG： 叶结点(无后继的结点)以一标识符或常数作标记，表示该结点代表该变量或常数的值 内部结点(有后继的结点)以一运算符作标记，表示该结点代表用该算符对其后继结点所代表的值进行运算的结果 各结点都可以附加上一个或多个标识符，表示这些变量具有该结点所代表的值 基本块的DAG的例子 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R－r B:=T5*T6 2. 四元式及其相应的DAG结点形式 3 构造基本块的DAG的算法 算法准备： 假定DAG各结点信息将用适当的数据结构来存放，并设有一个标识符（包括常数）与结点的对应表。NODE(A)是描述这种对应关系的函数，它的值或为n（表示结点n上有A作为标记或附加标识符），或无定义。 算法： 首先DAG为空，对基本块的每一四元式，按其类型分别处理： 对0型（A:= B） 对1型（A:= op B） 对于2型（A:= B op C） 7.2.3 DAG的应用 在一个基本块被构造成相应的DAG的过程中，进行了如下基本的优化工作： 合并已知量 在DAG构造算法中，如果运算量都是已知量，则不生成计算该结点值的内部结点，而执行该运算，将计算结果生成一个叶结点，实现了合并已知量优化 删除多余运算 对具有公共子表达式的所有四元式，只生成一个计算该表达式的内部结点，所有被赋值的变量都作为该结点的附加标识符，实现了删除多余运算的优化 删除无用赋值 如果变量被赋值后，在它被引用前又被重新赋值，则变量被从具有前一个值的结点上删除 利用DAG进行优化 删除在基本块后不被引用变量的