基于C语言的局部优化程序的实现.zip

# 局部优化程序的实现 # 一、设计概览 ## 1.1 课程设计目的和要求 目的 《编译原理》是计算机专业的一门重要课程，其中包含大量软件设思想。大家通过课程设计，实现一些重要的算法或个完整编译序模型能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要意义[1]。 要求 按照《编译原理课程设计指导书（含参考选题）》（2016 版）的有关要求完成算法设计、代码编写与调试以及课设报告的撰写。 ## 1.2 课程设计任务 题目：局部优化程序的实现 设计内容及要求：根据基本块转换成 DAG 的算法，实现：对于任意输入的一个基本块（四元式程序），将其转换为 DAG；然后按照 DAG 节点构造顺序，重构基本块四元式代码。以 P.283 例 10.4 为输入，完成并输出局部优化。 # 二、开发环境 硬件：Dell G3579 笔记本电脑； 软件：Visual Studio Enterprise 2019、gcc、Notepad++。 # 三、相关原理及算法 ## 3.1 基本原理 代码优化是指编译程序为了生成高质量的目标程序而做的各种加工和处理。而高质量的目标程序是指对同一源程序在运行时所占的内存空间较小，且在同一台机器上运行时间也较短的目标程序。代码优化并不能保证得到的目标代码是最优的，而只能是相对较优的。优化的原则是在编译阶段能计算的量绝不留到运行时刻去做，能在外层循环中计算的量绝不放到内层去做，能够共用存储单元(寄存器)的尽量共用。 优化可在编译的各个阶段进行，最主要的时机是在语法、语义分析生成中间代码之后，在中间代码上进行。这一类优化不依赖于具体的计算机，而取决于语言的结构。代码优化有以下三种类型： 局部优化：是指在只有一个入口和一个出口，且语句为顺序执行的程序段上所进行的优化。这种程序段，称为基本块。将基本块作为优化要考虑的主要范围为优化决策提供了基础，在一般情况下，将会产生更高质量的代码。 循环优化：是对循环语句所生成的中间代码序列所进行的优化处理，这类优化包括外提不变表达式、强度削弱和删除归纳变量。 全局优化：是在非线性程序段上的优化。因为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂。 其中，局部优化是指局部范围内的优化。这个“局部范围”是指基本块，即只有一个入口和一个出口且语句为顺序执行的程序段。局部优化就是把程序划分为若干个“基本块”，优化的工作分别在每个基本块内进行。下面介绍有关概念。 ### 3.1.1 基本块的相关概念 所谓基本块，是指程序中一组顺序执行的语句序列，其中只有一个入口和一个出口。执行时只能从其入口进入，从其出口退出。基本块内的语句要么都被执行，要么都不执行。入口语句的定义如下： 程序的第一个语句；或者， 条件转移语句或无条件转移语句的转移目标语句； 紧跟在条件转移语句后面的语句。 有了入口语句的概念之后，就可以给出划分中间代码（四元式程序）为基本块的算法，其步骤如下： 求出四元式程序中各个基本块的入口语句。 对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。 在一个基本块内通常可以实行下面的优化： 删除公共子表达式：如果一个表达式 E 已经计算过了，并且从先前的计算到现在 E 中所有变量的值都没有发生变化，那么 E 的这次出现就成为了公共子表达式。对于这种表达式，没有必要花时间再对它进行计算，只需直接用前面计算过的表达式结果代替 E 即可。 删除无用赋值：删除无用赋值或删除无用代码是指在程序中有些变量的赋值对程序运行结果没有任何作用，对这些变量赋值的代码可以删除。 合并已知量：也称为常数合并，是指将能在编译时计算出值的表达式用其相应的值替代。如果在编译时，编译程序能知道一个表达式的所有操作数的值，则此表达式就可由其计算出的值替代。 临时变量改名：总可以将一个基本块变换城等价的另一个基本块，使其中定义临时变量的语句改成定义新的临时变量。 交换语句的位置：在交换语句位置不影响基本块值的情况下，有时通过改变其次序可产生更高效的代码。 代数变换：对基本块中求值的表达式，用代数上等价的形式变换，以期使复杂运算变成简单运算。 ### 3.1.2 基本块的 DAG 表示 一个基本块的 DAG 是一种其结点带有下述标记或附加信息的 DAG。 图的叶结点(没有后继的结点)以一标识符(变量名)或常数作为标记，表示该结点 代表该变量或常数的值。如果叶结点用来代表某变量 A 的地址，则用 addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标 0，以表示它是该变量的初值。 图的内部结点(有后继的结点)以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 ### 3.1.3 中间代码类型 一般地，中间代码有 4 中类型，具体示例与说明如图 3.1.3.1 所示。  接下来介绍与本设计有关的算法。 ## 3.2 有关算法 对于仅含 0、1、2 型中间代码的基本块的 DAG 构造算法描述如下[2]。 开始，DAG 为空。 对基本块中的每一条中间代码式，依次执行以下步骤。 如果 NODE（B）无定义，则构造一标记为 B 的叶结点并定义 NODE（B）为这个结点； 如果当前四元式是 0 型，则记 NODE（B）的值为 n，转 4。 如果当前四元式是 1 型，则转 2.（1）。 如果当前四元式是 2 型，则：（ⅰ）如果 NODE（C）无定义，则构造一标记为 C 的叶结点并定义 NODE（C）为这个结点，（ⅱ）转 2.（2）。 2． 如果 NODE（B）是标记为常数的叶结点，则转 2.（3），否则转 3.（1）。 如果 NODE（B）和 NODE（C）都是标记为常数的叶结点，则转 2.（4），否则转 3.（2）。 执行 op B（即合并已知量），令得到的新常数为 P。如果 NODE（B）是处理当前四元式时新构造出来的结点，则删除它。如果 NODE（P）无定义，则构造一用 P 做标记的叶结点 n。置 NODE（P）＝n，转 4。 执行 B op C(即合并已知量)，令得到的新常数为 P。如果 NODE（B）或 NODE（C）是处理当前四元式时新构造出来的结点，则删除它。如果 NODE（P）无定义，则构造一用 P 做标记的叶结点 n。置 NODE（P）＝n，转 4。 3． 检查 DAG 中是否已有一结点，其唯一后继为 NODE（B），且标记为 op（即找公共子表达式）。如果没有，则构造该结点 n，否则就把已有的结点作为它的结点并设该结点为 n，转 4。 检查 DAG 中是否已有一结点，其左后继为 NODE（B），右后继�