- 1、本文档共36页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
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进行优化 删除在基本块后不被引用变量的
文档评论(0)