编译原理第九章复习.docVIP

第9章 代码 代码生成阶段以中间代码为输入，输出与源程序等价的目标代码。 目标代码的生成依赖于所设计的目标代码结构、运行时刻环境的结构、目标机器的特点。 代码生成输出的目标程序有如下形式： 目标机器上的机器指令 目标机器上的汇编语言指令 抽象机代码 1．简单的代码生成算法 涉及存储管理，指令选择，寄存器分配和计算次序选择等基本问题 依次考虑基本块的每个语句，为其产生代码 假定三地址语句的每种算符都有对应的目标机器算符 假定计算结果留在寄存器中尽可能长的时间, 除非： 该寄存器要用于其它计算，或者 到基本块结束 代码生成阶段以中间代码为输入，输出与源程序等价的目标代码。 2．指令的选择 目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素 指令的速度和机器特点是另一些重要的因素 若不考虑目标程序的效率，指令的选择是直截了当的。 逐个语句地产生代码，常常得到低质量的代码 3．寄存器分配问题 运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些 4．寄存器分配 选择驻留在寄存器中的一组变量 寄存器指派 挑选变量要驻留的具体寄存器 6．计算次序的选择 某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果 7．目标机器的指令系统 8．指令的代价 指令代价取成1加上它的源和目的地址模式的附加代价 9．基本块 连续的语句序列，控制流从它的开始进入，并从它的末尾离开，除最后外中间没有分支的可能 10．控制流程图（流图）：具有唯一首结点的有向图 一个基本块是流图的一个结点，一个程序的所有基本块是程序流图的结点集。程序的第一个语句所在的基本块成为程序流图的首结点。把各基本块之间的控制流向作为结点之间的有向边集合，就得到程序的控制流图 11．构造流图算法 （1）输入的基本块集即为结点集N； （2）含程序的第一个语句的基本块为首结点n0； （3）设Bi, Bj∈N，若满足下列条件之一： （a）Bj紧跟在Bi之后， Bi的出口语句不是无条件转向或停语句； （b）Bi的出口语句为转向语句，其转向点恰 为Bj的入口语句。 则Bi与Bj之间有有向边Bi→Bj。结点间的所有有向边便是集合E。 11．划分基本块 首先确定所有的入口语句 序列的第一个语句是入口语句 能由条件转移语句或无条件转移语句转到的语句是入口语句 紧跟在条件转移语句后面的语句是入口语句 然后确定每一个基本块 对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除 12．基本块的变换 一个基本块可以通过一系列变换转化成与之等价的另一个基本块。它们包括： 合并常量计算 消除公共子表达式 削减计算强度 删除无用代码 三地址语句x : y + z引用y和z并对x定值 一个名字的值在基本块的某一点以后还要引用的话，我们说这个名字在该点是活跃的 13．基本块的等价 两个基本块计算一组同样的表达式 这些表达式的值分别代表同样的活跃名字的值 或者 两个基本块 和 ‘等价当且仅当两个基本块有相同的输入和输出变量，且对应的输出变量的值相同。 有很多等价变换可用于基本块 局部变换（局部优化） 全局变换（全局优化） 14．变换的形式 删除局部公共子表达式 删除死代码 定值x : y + z以后不再引用，则称x为死变量 交换相邻的独立语句 t1 : b + c t2 : x + y t2 : x + y t1 : b + c 当且仅当x和y都不是t1，b和c都不是t2 代数变换 x : x + 0 可以删除 x : x * 1 可以删除 x : y **2 改成x : y * y 15．寄存器描述和地址描述 例：对a : b + c 如果寄存器Ri含b，Rj含c，且b此后不再活跃 产生ADD Rj, Ri，结果a在Ri中 如果Ri含b，但c在内存单元，b仍然不再活跃 产生ADD c, Ri，或者 MOV c, Rj ADD Rj, Ri 若c的值以后还要用,第二种代码比较有吸引力 16．在代码生成过程中，需要跟踪寄存器的内容和名字的地址 寄存器描述记住每个寄存器当前存的是什么 在任何一点，每个寄存器保存若干个 包括零个 名字的值 名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合 这些信息可以存于符号表中 这两个描述在代码生成过程中是变化的。 17．代码生成算法 对