编译原理——基本块、流图、基本块优化、循环优化（代码优化）

向上的yyy

已于 2022-12-27 16:40:00 修改

阅读量6.9k

点赞数 30

分类专栏：编译原理文章标签：编译原理

于 2022-12-27 16:38:05 首次发布

本文链接： https://blog.csdn.net/weixin_51995229/article/details/128454552

版权

编译原理专栏收录该内容

5 篇文章 6 订阅

订阅专栏

一、划分基本块、画流图

找基本块的入口：一共有三类入口：①代码段的第一个指令；②条件跳转和无条件跳转的目标语句；③条件跳转语句的下一条语句；
根据划分的入口画流图，一个基本块的区间：从入口开始，至到遇到下一个入口结束；

例题1

分析

首先根据上面的3类找基本块入口的方法，把基本块入口找出来；
根据划分的入口画流图，一个基本块从入口开始，至到遇到下一个入口结束；

例题2

分析

首先根据上面的3类找基本块入口的方法，把基本块入口找出来；一共5个基本块：B1、B2、B3、B4、B5；
根据划分的入口画流图，一个基本块从入口开始，至到遇到下一个入口结束；

二、基本块优化

例题1

（一）、删除公共子表达式

删除前面已经计算过得、公共子表达式；由于A+C、A*C已经计算过，故将H=D，I=E；

（二）、复制传播

把后面用的H、I的换为根（源头），H的源头是D，那么把下面用到H的换成D；I的源头是E，那么把下面用到I的换成E；

（三）、删除死代码

把没用的代码直接删掉；H、I已经没用任何用处了

（四）、根据题目要求再优化

常量B，可以直接删掉，把用到B的都替换成3即可；然后只写G、L、M用到的基本块，其余的不用写；

例题2

图片来源于： Bilibili 中间代码优化习题讲解，讲的挺不错的，可以去看看；

三、循环优化

例题1

这个例题就是从 Bilibili 中间代码优化习题讲解里截取的，挺经典；

（一）、代码外提

把循环中，一直不变的量（常量）移出循环，可以放在循环的上一个基本块中；

（二）、归纳变量强度削弱

通过循环结束if判断条件（i<=10），以及代码块（ i 每次+1），可以发现 i 就是基本归纳变量；那么与i（基本归纳变量）相关的t2、t10就是归纳变量；
注意基本归纳变量 和 归纳变量是两个东西；
然后削弱归纳变量（把 i 通过别的方式替换掉），t2=4*i，乘法可以削弱为加法变为 ==》t2=t2+4；然后那么t2就需要初始化，所以在B1将有一个t2=4 * i（i起始为1）的初始化；

（三）、删除基本归纳变量

上面已经削弱了归纳变量，那么现在可以删除基本归纳变量 i，以及更换或删除和 i 相关的条件；
由于循环结束条件是i<=10，那么就是t2加10次4，那不就是t2=40为临界条件，所以把i<=10改为t2<=40；
所有与基本归纳变量 i 相关的t10也可以删了（t10的作用理解为for循环的i++）；
并且B1中把常量1代入4*i，可以理解为：合并已知量；

例题2

分析

首先观察四元式程序，发现不用进行基本块优化，那么就可以直接通过上面的循环优化的步骤来做这个题；

（一）、归纳变量强度削弱

可以发现循环体没有常量，所以省去第一步，直接进行第二步，归纳变量的削弱；
然后一个比较重要的规律：像 A=K*I 都可以转化为自身+=一个非I的数；比如此题的A=K*I，可以转换为A=A+K，因为K * I就相当于 I个K的和赋给A，等价于 A自身+=K，这样+= I次即可；需要记得初始化那些削弱后的归纳变量；

（二）、删除基本归纳变量 I

关于新的循环结束条件，最简单的方法就是看原程序的目的；所以循环结束条件可以是A<K * 100，也可以是B<J * 100；
由于此题仅仅要求对循环进行优化，所以最后I=1的初始值还保留着，也可以像上面把常量I=1代入K*I，这里就不画蛇添足了；
然后我把K*100封装一个变量T了，然后代码外提部分我直接放在基本块1了，答案那样新开一个基本块也是一样的；

例题3

分析

首先观察四元式程序，发现不用进行基本块优化，那么就可以直接通过上面的循环优化的步骤来做这个题；

（一）、代码外提

B=J+1与循环无关，那么直接提出去即可；

（二）、归纳变量强度削弱

需注意此题的归纳变量C，C=B+I，这里是加法，就不能像上面例题1、2直接转化本身 +=K；
可以发现每次C=B+I，每次的值都是，也就是C在B的基础上，每次加个1，所以 C赋个初值C=B+1，然后每次C=C+1，正好可以把I=I+1替换掉；

（三）、删除基本归纳变量 I

通过分析原程序，新的循环结束条件，是C=B+100；封装一个T=B+100，那循环结束就是C=T；

向上的yyy

关注关注

30
点赞
踩
127

收藏

觉得还不错? 一键收藏
打赏
0
评论
编译原理——基本块、流图、基本块优化、循环优化（代码优化）

把后面用的H、I的换为根（源头），H的源头是D，那么把下面用到H的换成D；I的源头是E，那么把下面用到I的换成E；常量B，可以直接删掉，把用到B的都替换成3即可；然后只写G、L、M用到的基本块，其余的不用写；由于A+C、A*C已经计算过，故将H=D，I=E；把循环中，一直不变的量（常量）移出循环，可以放在循环的上一个基本块中；把没用的代码直接删掉；B=J+1与循环无关，那么直接提出去即可；首先观察四元式程序，发现不用进行。，讲的挺不错的，可以去看看；，那么就可以直接通过上面的。，那么就可以直接通过上面的。
复制链接

扫一扫

专栏目录

程序设计语言编译原理 (陈火旺)

03-22

编译原理经典教材目录第一章引论 1.1什么叫编译程序 1.2编译过程概述 1.3编译程序的结构 1.3.1编译程序总框 1.3.2表格与表格管理 1.3.3出错处理 1.3.4遍 1.3.5编译前端与后端 1.4编译程序与程序设计环境 1.5编译程序的生成第二章高级语言及其语法描述 2.1 程序语言的定义 2.1.1语法 2.1.2 语义 2.2 高级语言的一般特性 2.2.1 高级语言的分类 2.2.2程序结构 2.2.3数据类型与操作 2.2.4语句与控制结构 2.3程序语言的语法描述 2.3 上下文无关文法 2.3.2语法分析树与二义性 2.3.3 形式语言鸟瞰练习第三章词法分析 3.1 对于词法分析器的要求 3.1.1词法分析器的功能和输出形式 3.1.2词法分析器作为一个独立子程序 3.2词法分析器的设计 3.2.1输入、预处理 3.2.2 单词符号的识别：超前搜索 3.2.3状态转换图 3.2.4状态转换图的实现 3.3正规表达式与有限自动机 3.3.1正规式与正规集 3.3.2确定有限自动机（DFA） 3.3.3非确定有限自动机（NFA） 3.3.4正规文法与有限自动机的等价性 3.3.5 正规式与有限自动机的等价性 3.3.6确定有限自动机的化简 3.4词法分析器的自动产生 3.4.1语言LEX的一般描述 3.4.2超前搜索 3.4.3 LEX的实现练习第四章语法分析——自上而下分析 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL（1）分析法 4.3.1左递归的消除 4.3.2消除回溯、提左因子 4.3.3 LL（1）分析条件 4.4递归下降分析程序构造 4.5预测分析程序 4.5.1预测分析程序工作过程 4.5.2预测分析表的构造 4.6 LL（1）分析中的错误处理练习第五章语法分析——自下而上分析 5.1 自下而上分析基本问题 5.1.1 归约 5.1.2规范归约简述 5.1.3符号栈的使用与语法树的表示 5.2算符优先分析 5.2.1算符优先文法及优先表构造 5.2.2算符优先分析算法 5.2.3优先函数 5.2.4算符优先分析中的出错处理 5.3LR分析法 5.3.1 LR分析器 5.3.2LR（O）项目集族和LR（O）分析表的构造 5.3.3 SLR分析表的构造 5.3.4规范LR分析表的构造 5.3.5 LALR分析表的构造 5.3.6 二义文法的应用 5.3.7LR分析中的出错处理 5.4语法分析器的自动产生工具YACC 练习第六章属性文法和语法制导翻译 6.1属性文法 6.2基于属性文法的处理方法 6.2.1 依赖图 6.2.2树遍历的属性计算方法 6.2.3 一遍扫描的处理方法 6.2.4抽象语法树 6.3 S－属性文法的自下而上计算 6.4 L－属性文法和自顶向下翻译 6.4.1 翻译模式 6.4.2自顶向下翻译 6.4.3递归下降翻译器的设计 6.5自下而上计算继承属性 6.5.1 从翻译模式中去掉嵌入在产生式中间的动作 6.5.2分析栈中的继承属性 6.5.3模拟继承属性的计算 6.5.4 用综合属性代替继承属练习