♻️ 资源
大小：2.90MB
➡️资源下载：https://download.csdn.net/download/s1t16/87450308
局部优化程序的实现
一、设计概览
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），右后继为 NODE（C），且标记为 op(即找公共子表达式)。如果没有，则构造该结点 n，否则就把已有的结点作为它的结点并设该结点为 n。转 4。
4．
如果 NODE（A）无定义，则把 A 附加在结点 n 上并令 NODE（A）＝n；否则先把 A 从 NODE（A）结点上的附加标识符集中删除（注意，如果 NODE（A）是叶结点，则其标记 A 不删除），把 A 附加到新结点 n 上并令 NODE（A）＝n。转处理下一四元式。
上述构造 DAG 算法的流程图如图 3.2.1 所示。
据图 3.2.1 所示流程图所得的伪代码描述如下所示。
DAG = NULL; for exp in blocks: If node (b) is not defined, a leaf node marked b is constructed and node (b) is defined as this node; If the current quaternion is type 0, mark the value of node (b) as N and turn to 4. If the current quaternion is type 1, turn to 2. (1). If the current quaternion is type 2, then: (I) if node (c) has no definition, then construct a leaf node marked as C and define node (c) as this node, (II) turn to 2. (2).2．
If node (b) is a leaf node marked as a constant, turn to 2. (3), otherwise turn to 3. (1). If node (b) and node (c) are leaf nodes marked as constants, turn to 2. (4), otherwise turn to 3. (2). Execute OP B (i.e. merge known quantities) and make the new constant P. If node (b) is a newly constructed node when processing the current quaternion, delete it. If node (P) is undefined, a leaf node n marked with P is constructed. Set node (P) = n and turn to 4. Execute B OP C (i.e. merge known quantities) so that the new constant obtained is p. If node (b) or node (c) is a newly constructed node when processing the current quaternion, delete it. If node (P) is undefined, a leaf node n marked with P is constructed. Set node (P) = n and turn to 4. Check whether there is a node in DAG whose unique successor is node (b) and marked as op (i.e. find common subexpression). If not, the node n is constructed. Otherwise, the existing node is regarded as its node and the node is set as N, then turn to 4. Check whether there is a node in DAG, whose left successor is node (b), right successor is node (c), and marked as op (that is to find common subexpression). If not, the node n is constructed, otherwise the existing node is regarded as its node and the node is set as n. Turn to 4. If node (a) has no definition, a is attached to node n and node (a) = n; otherwise, a is deleted from the set of additional identifiers on node (a) (note that if node (a) is a leaf node, its mark a is not deleted), and a is attached to the new node n and node (a) = n. Turn to the next quaternion. endfor return DAG四、设计的输入和输出形式
本设计所构建局部优化程序不单是将四元式代码优化后输出，而是可以对完整的 C 语言文件进行词法分析、语法分析、语义分析、中间代码生成与中间代码优化，故程序支持对 C 语言程序的直接读入与处理。
4.1 程序输入内容与格式
本设计所构建局部优化程序的输入内容为一 TXT 格式的文本文件，文件里包含了一段待处理的 C 语言程序。输入文件的形式如图 4.1.1 所示。
值得一提的是，本设计所构建的程序支持 C 语言的 14 个关键词及有关语句：int、char、void、if、else、switch、case、default、scanf、printf、main 和 return。
4.2 程序输出内容与格式
本设计所构建局部优化程序的输出内容分两部分：1）输出到控制台的信息，包括对程序每一行语句的判断、语法错误提示、程序所含变量和优化后的四元式代码；2）写入到 TXT 格式的文本文件包括程序所含变量与函数以及优化后的四元式代码。输出到控制台的内容如图 4.2.1 所示，写入文本的内容如图 4.2.2 所示（所用测试用例为 P.283 例 10.4 的四元式代码）。
五、程序运行的主要界面和结果截图
5.1 程序运行界面
本设计所构建局部优化程序的程序运行界面如图 5.1.1 至图 5.1.3 所示（所用测试样例在附录中給出）。
5.2 程序运行结果
本设计所构建局部优化程序的程序运行结果如图 5.2.1 至图 5.2.3 所示。
六、总结和感想体会
本次设计让我加深了对基本块优化和编译器的理解：对于一个給定的程序，我们可以把它划分为一系列的基本块。在各个基本块范围内，分别进行优化。最终的优化结果不仅减少了冗余代码，还降低了对内存的消耗与运行时间，时空都得到了优化。
所谓代码优化是指对程序代码进行等价（指不改变程序的运行结果）变换。程序代码可以是中间代码（如四元式代码），也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短（运行时间更短、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机[3]。简而言之，在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加高效的目标代码[4]。
七、参考文献
李宏芒. 编译原理课程设计指导书（含参考选题）（2016 版）[M]. 合肥：合肥工业大学， 2016.
陈火旺，刘春林，谭庆平，赵克佳，刘越. 程序设计语言编译原理[M]. 北京：国防科技大学出版社，1999.
https://baike.baidu.com/item/%E4%BB%A3%E7%A0%81%E4%BC%98%E5%8C%96/571727?fr=aladdin陈英. 编译原理[M]. 北京：清华大学出版社，2009.
