# AssemblyProject **Repository Path**: heiffeli/assembly-project ## Basic Information - **Project Name**: AssemblyProject - **Description**: No description available - **Primary Language**: C++ - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2022-04-20 - **Last Updated**: 2022-06-08 ## Categories & Tags **Categories**: Uncategorized **Tags**: Cpp ## README # **MASM汇编生成** ## **目前存在的问题** **** - 寄存器分配(变量的下次引用信息) - 符号表的调用？或重新生成？ - 需要对基本块重新生成子表？ - temp量 - 分辨其值是否为地址 - 当temp地址作为非 `result` 时，需要取出该地址中的数据参与运算 - 当temp地址作为 `result` 时 - 一是数组下标或记录域的访问，获取元素的所在地址，并存入temp中 - 二是将新的数据存放在该temp所指地址单元中 - 由于三地址代码中已经引入了temp量，优化了后续对寄存器的分配 - 将temp增加到符号表中，并添加下次引用信息 - 遇到temp即为其分配寄存器即可，需要用到寄存器分配算法，类似于书 P308 的getreg()函数，但temp不为其分配实地址？ - 局部变量 - 全局变量 - 变量的控制流传递(作用域) - 在符号表中增加变量的控制流(作用域)，包括temp以防出现temp跨基本块引用的情况 ## **目标代码生成概述** **** ### **代码生成程序的输入输出** - 输入：三地址中间代码、符号表 - 输出：MASM汇编代码 - 输入 - 三地址中间代码 由 `OP arg1 arg2 result` 的形式构成的一组中间形式的代码，具体见`三地址代码解析` `https://fsbupteducn.feishu.cn/docs/doccnMai638PEOyln0I0WHXgyjc` - 符号表 >目前不知道符号表的具体实现、以及如何调用符号表 ### **寄存器分配** - 运算对象在寄存器中的指令通常比运算对象在内存中的指令短且执行速度快，因此就要充分利用目标机器的寄存器，尽量生成寄存器寻址的指令 - 设计寄存器分配的 **问题** - 确定在程序的某一点需要使用寄存器的变量集合（基本块的划分以及对块中每个变量的下次引用信息分析） - 寄存器指派，将变量指派到具体的寄存器（对每个寄存器的当前存储内容分析） - 特殊寄存器的用法 >具体见《INTEL汇编语言程序设计》 寄存器部分 - 8个通用寄存器 - `EAX` 在乘法和除法指令中被自动使用，通常为扩展累加寄存器 - `EBX` - `EXC` 在某些指令中，CPU自动使用其作为循环计数器 - `EDX` - `ESI` `EDI` 由高速内存数据传送指令使用，通常称为*扩展源指针*和*扩展目的指针寄存器* - `EBP` 高级语言使用其引用堆栈上的函数参数和局部变量，**一般不应该用于普通算术运算和数据传送**，通常称为*扩展帧指针寄存器* - `ESP` 寻址堆栈上的数据，**极少用于普通算术运算和数据传送**，通常称为*扩展堆栈指针寄存器* - 6个段寄存器 - 指令指针 `EIP` 存放下一条要执行的指令的地址 - `EFLAGS` 寄存器 - 系统寄存器 - **设计原则** - 生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配为止 ## **基本块划分** **** ### **基本块** - **基本块** 是具有原子性的连续的语句序列，控制流从第一条语句（称为进口）进入，从最后一条语句（称为出口）流出，中途没有停止或分支 - 基本块 **划分规则** >书上的规则，实际实现时可能会做一些改动 - 代码序列的第一条语句是一个入口语句 - 任何一个条件或无条件转移语句转移到的目标语句是一个入口语句 >对应到具体的三地址代码中可以理解为所有的 > >`LABEL labelName null null` > >都是一个入口语句 - 任何紧跟在一个条件或无条件转移语句之后的那条语句是一个入口语句 >对应到具体的三地址代码中可以理解为所有的 > >`GOTO ...` > >之后紧跟的任意语句都是入口语句 ## **下次引用信息** **** ### **符号表的扩充** - 增加记录下次引用信息的域 - 增加记录活跃信息的域 ### **下次引用信息算法(基本块内)** >以下为书中对形如 `x := y op z` 的三地址代码的下次引用信息计算算法，实际在程序开发过程中，由于已知的三地址代码已做了形式上的优化 `op arg1 arg2 result`，应对如下算法进行改动和优化 - 初始化。把基本块中个变量的符号表想的下次引用信息域置为“无下次引用”、活跃信息置为“活跃” - 计算各变量的下次引用信息。按照从基本块的出口语句到入口语句的顺序，一次处理每一条三地址语句，针对语句`(i) x := y op z`，依次执行下列步骤： - 把当前符号表中记录的变量 x 的下次引用信息和活跃信息附加到语句上 - 把符号表中的x的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃” - 把当前符号表中记录的变量 y 和 z 的下次引用信息和活跃信息附加到语句上 - 把符号表中 y 和 z 的下次引用信息均置为 i，活跃信息置为“活跃” >严格按照次序执行，因为 y 和 z 也可能是x ### **下次引用信息算法(优化)** >算法总体上和以上相同，在个别地方做修改 - 三地址语句为 `op arg1 arg2 result`，result对应 x ，arg1 和 arg2 对应 y 和 z - 三个操作数都有可能为生成的 temp 值，同样加入到符号表中，加入两个信息域 - 待续... ## **目标代码生成** **** ### **内存 / 寄存器分配算法** - 寄存器描述符 - 记录每个寄存器当前保存的是那些名字的值 - 地址描述符 - 记录一个名字的当前值的存放位置，它有可能是一个寄存器、一个栈单元、一个存储单元，或者是这些地址的集合 - 名字的地址描述符可以存放在符号表中，在代码生成时，通过查找符号表可以确定对一个名字的寻址方式 - 教材书上 `getreg()` 算法 P308 ``` 算法9.2 函数getreg(s)。 输人:三地址语句x:=y op z。 输出:地址L(L或者是一个寄存器,或者是一个存储单元地址)。 主要数据结构:寄存器描述符和名字的地址描述符。 方法:依次执行以下步骤。 (1) switch 参数语句{ (2) case形如x:=y op z的赋值语句: (3) case形如x:=op y的赋值语句: (4) 查看名字y的地址描述符; (5) if (y的值存放在寄存器R中){ (6) 查看R的寄存器描述符; (7) if (R中仅有名字y的值){ (৪) 查看名字y的下次引用信息和活跃信息; (9) if(名字y无下次引用,且非活跃) return R; (10) } (11) } (12) else if (存在空闲寄存器R) return R; (13) else { (14) 查看名字x的下次引用信息; (15) if(x有下次引用I op需要使用寄存器) { (16) 选择一个已被占用的寄存器R; (17) for(R寄存器描述符中记录的每一个名字n) (18) if(名字n的值仅在寄存器R中) { (19) outcode ('MoV' Mn, R); (20) 更新名字n的地址描述符为Mn; //Mn表示名字n的存储单元地址 (21) } (22) return R; (23) } (24) else return Mx; //Mx表示名字x的存储单元地址 (25) } (26) } ``` ### **算法优化** - 针对目前的三地址代码 `op arg1 arg2 result` 做算法改进优化 - 对 temp 量的内存分配只考虑寄存器 - 由于 `result` 为非temp量名字的情况仅出现在 `ASSING` 语句中，可以对其进行简化 - 待续... ### **目标代码生成算法** - 教材 P309 ``` 算法9.3 目标代码生成算法。 输入:基本块的三地址语句序列。 输出:基本块的目标代码。 方法:从入口语句开始,依次处理基本块中的每一条三地址语句。 (1) for (基本块中的每一条三地址语句) (2) switch当前处理的三地址语句( (3) case 形如x:=y op z的赋值语句: (4) L= getreg(i: x:=y op z); (5) 查看名字y的地址描述符,取得y值的当前存放位置y'; (6) if (y'!= L) outcode('Mov' L, y'); (7) else将L从y的地址描述符中删除; (৪) 查看名字z的地址描述符,取得z值的当前存放位置z'; (9) outcode (op L, z'); (10) 更新x的地址描述符以记录x的值仅在L中; (11) if (L是寄存器) 更新L的寄存器描述符以记录L中只有x的值; (12) 查看y/z的下次引用信息和活跃信息,以及y/z的地址描述符; (13) if (y/z没有下次引用,在块出口处非活跃,且当前值在寄存器R中){ (14) 从y/z的地址描述符中删除寄存器R; (15) 从R的寄存器描述符中删除名字y/z; } (16) break; (17) case 形如x:=op y的赋值语句: (18) L=getreg (i: x:=Op y'); (19) 查看名字y的地址描述符,取得y值的当前存放位置y'; (20) if (y'!=L) outcode ('Mov' L, y'); (21) else 将L从y的地址描述符中删除; (22) outcode (op L) ; (23) 更新x的地址描述符以记录x的值仅在L中; (24) if (L是寄存器)更新L的寄存器描述符以记录L中只有x的值; (25) 查看y的下次引用信息和活跃信息,以及y的地址描述符; (26) if (y没有下次引用,在块出口处非活跃,且当前值在寄存器R中)( (27) 从y的地址描述符中删除寄存器R; (28) 从R的寄存器描述符中删除名字y; (29) break; (30) case 形如x:=y的赋值语句: (31) 查看名字y的地址描述符; (32) if (y的值在寄存器R中){ (33) 在R的寄存器描述符中增加名字x; (34) 更新名字x的地址描述符为R; } (35) else { (36) L= getreg (i: x:=y); (37) if (L是寄存器)( (38) outcode ('Mov' L, y'); //y'为y值的当前存放位置 (39) 更新L的寄存器描述符为名字x和y; (40) 更新名字x的地址描述符为L; (41) y的地址描述符中增加寄存器L; (42) } (43) else { //此时,L是名字x的存储单元地址Mx (44) outcode ('Mov' L, y'); //y'为y值的当前存放位置 (45) 更新名字x的地址描述符为Mx; (46) } (47) }// end of if-else (48) break; (49) } // end of switch (50) } // end of for,基本块中的所有语句已经处理完毕 (51) for (在出口处活跃的每一个变量x){ (52) 查看x的地址描述符; (53) if (x值的存放位置只有寄存器R) (54) outcode ('Mov'Mx, R); //将x的值存人它的内存单元中 (55)} // end of for ``` ### **指令翻译** - **程序模板** ``` TITLE Programe QuickSort (QuickSort.asm) ; 程序的描述: ; 作者: ; 创建日期: ; 修改: ; 日期: 修改者: INCLUDE Irvine32.inc .data ;(在此插入变量) .code main PROC ;(在此插入可执行代码) exit main ENDP ;(在此插入其它子程序) END main ``` - 代码块翻译 - 数据声明块(变量、常量) >具体见《INTEL汇编语言程序设计》第三、九章内容 - 类型声明块 - 记录(对应结构？) >具体见《INTEL汇编语言程序设计》第十章内容 - 程序体 >具体见《INTEL汇编语言程序设计》第五、八章内容 - 主程序 - 子过程 / 函数 - 具体操作指令翻译 >具体见《INTEL汇编语言程序设计》第四、六、七章内容 - 单操作数 - 双操作数 - 三操作数 - 多操作数 - CALL >具体见《INTEL汇编语言程序设计》第五章内容 - 库函数 - I/O >具体见《INTEL汇编语言程序设计》第十一章内容 - 自定义函数 / 过程 >具体见《INTEL汇编语言程序设计》第五、八章内容