目录
4.2 程序的启动
相信各位同学已经编写了不少高级语言的程序，我们可以理解自己编写代码的含义，但是计算机是如何理解并准确无误地执行我们的代码的。这一过程并不是一个启动按钮，或是一行指令。
实际上，程序的启动是一个相当复杂的过程，对于C语言而言，涉及了四个相对独立的功能模块，分别是：编译器（Compiler），汇编器（Assembler），链接器（Linker），加载器（Loader）。他们按照一定的次序工作，上一层的输出产物成为下一层的输入，逐步将程序转换成与实际计算机系统硬件相关的，计算机可以理解执行的程序（C.A.L.L.过程）。如下图所示：
- 为了确定文件类型UNIX使用文件的后缀，
x.c表示C源文件，x.s表示汇编文件，x.o表示目标文件，x.a表示静态链接库，x.so表示动态链接库。默认情况下，a.out表示可执行文件。 - MS-DOS使用
.C, .ASM, .OBJ, .LIB, .DLL, .EXE来完成相同功能。
4.2.1 代码编译
编译器将C程序转换成一种机器可以理解的符号形式的汇编语言程序，它能够被进一步翻译成二进制机器语言。
4.2.2 代码汇编
由编译器生成的汇编程序中，存在着简化程序转换和编程的一些实际硬件不支持的指令，这类指令称为伪指令(pseudoinsruction)。
例如，MIPS硬件确保寄存器$zero保持0。即一旦使用该寄存器，它都能提供0，而且程序员不能修改寄存器$zero的值。寄存器$zero用于生成汇编语言指令move。move的功能是将一个寄存器中的内容复制到另一个中。因此即使MIPS体系结构不存在这条指令，MIPS汇编器依然可以识别它。
move $t0, $t1 # 寄存器$t0得到寄存器$t1的值
汇编器将这条汇编语言指令转换成等价的机器语言指令：
add $t0, $zero, $t1
总的来说，伪指令使得MIPS拥有比硬件所实现的更为丰富的汇编语言指令集。唯一的代价是保留了$at寄存器。本次实验中也存在着将伪指令扩展成通用指令的任务。
汇编器的主要任务是汇编成机器代码。汇编器将汇编语言程序转换成目标文件(object file)，它包括机器语言指令，数据和指令正确放入内存所需要的信息。
为了产生汇编语言程序每条指令对应的二进制表示，汇编器必须处理所有标号对应的地址，汇编器将分支和数据传输指令中用到的标号都放入一个**符号表(Symbol Table)**中。这个表由标号和地址组成。
UNIX系统中的目标文件通常包括以下6个不同部分：
- 目标文件头，描述目标文件其他部分的大小和位置
- 代码段，包含机器语言代码
- 静态数据段，包含在程序生命周期内分配的数据
- 重定位信息，标记了一些在程序加载进内存时依赖于绝对地址的指令和数据
- 符号表，包含未定义的剩余标记，如外部引用
- 调试信息，包括了一份说明目标模块如何编译的简明描述
4.2.3 代码链接
到目前为止我们描述的所有内容表明，对源程序的任意一行代码的修改都需要重新编译和汇编整个程序，全部的编译和汇编效率是低下的，尤其对于标准库而言。因而出现了另一种方法，即单独编译和汇编每个过程，使得某一行代码的修改只需要编译和汇编一个过程，这种方法需要一个新的系统程序，称为链接器(Linker)。它把所有独立汇编的机器语言程序拼接在一起。
链接器的工作分为三个步骤：
- 将代码和数据模块象征性地放入内存
- 决定数据和指令标签的地址
- 修补内部和外部引用
链接器使用每个目标模块中的重定位信息和符号表，来解析所有未定义标签，这种引用发生在分支指令，跳转指令和数据寻址处。它的工作非常像一个编辑器，寻找所有旧地址并用新地址加以代替。 如果所有外部引用都解析完成，链接器接着要确定每个模块将要占用的内存位置。因为文件是单独汇编的，所以汇编器不可能知道该模块指令和数据相对于其他模块而言的位置，因此也就无从确定他们的内存位置。当链接器将一个模块放到内存中的时候，所有的绝对引用（与寄存器无关的内存地址），必须重定位来反映它们的真实地址。 链接器将产生一个可执行文件(Executable file)，它可以在一台计算机上运行，通常，这个文件与目标文件具有相同的格式，但是它不包含未解决的引用。
4.2.4 代码加载
现在可执行文件已经存在于磁盘中，操作系统就可以将其读入内存并启动执行该程序，在UNIX系统中，**加载器(Loader)**按照以下步骤工作：
- 读取可执行文件头来确定代码段和数据段的大小
- 为正文和数据创建一个足够大的地址空间
- 将可执行文件中的指令和数据复制到内存中
- 把主程序的参数复制到栈顶
- 初始化机器寄存器，将栈指针指向第一个空位置
- 跳转到启动例程，它将参数复制到参数寄存器并且调用程序的main函数，当main函数返回时，启动例程通过系统调用exit终止程序
接下来，就让我们一起构造我们自己的汇编器和链接器！
4.3 汇编器
4.3.1 汇编器原理详解
正如上文所述，汇编器将汇编语言文件翻译成二进制机器指令和二进制数据组成的文件，我们将在下文阐述MIPS汇编器的实现细节。 首先我们先来看看汇编器在处理过程中可能面临的一些情况：
- 简单情况：
- 计算和逻辑指令，例如
等；addu rd, rs, rt mult rs, rt lw rt, offset(rs)- 为将其汇编成二进制指令所需要的所有信息都已经包含在了指令中。
- 分支指令(Branch)：
- 分支指令中的
imm字段代表的是相对当前指令地址的偏移量，即需要的是相对地址； - 一旦将所有的伪指令解析成实际的机器代码以后，由于MIPS是定长指令，因此通过简单的计算我们便可以得到实际的地址偏移量。
- 分支指令中的
- 前向引用：汇编语言允许标签在定义之前就被使用，如下图所示：
beq $zero, $zero, Label
Label:
汇编器在看到指令beq时，它不知道标签Label在哪里，因此也就无从得知相对地址偏移量了。
为解决这个问题，我们首先引入一个概念——遍(Pass)。它指的是对源程序（包括源程序的中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称为遍。
汇编器通常采用两遍的方式来处理可能出现的前向引用：
第一遍，汇编器将汇编文件的每一行读入，如果一行以标签作为开始，汇编器在他的符号表中记录标签的名字以及在文件中的位置。
第二遍，汇编器使用整个文件的符号表中的信息，在这一遍产生机器代码，若依然有未决的引用，将由链接器来进行解析：
跳转指令：例如
j, jal指令，这类跳转指令需要跳转的绝对地址，汇编器对于单一文件的操作，不可能得到最终的绝对地址。数据引用：例如
la指令，la指令将由汇编器处理为lui和ori指令，同样需要32位的绝对地址。外部引用：
jal指令可能跳转到外部文件的函数（就如C语言引用库函数），汇编器处理单一文件无法获取外部引用。
可以看到，我们对于需要绝对地址的指令以及外部引用都是无法解析的，因此汇编器将创建两张表。
符号定义表(Symbol Table)：每个文件都有一个符号定义表，用来记录该文件中定义的标签，这些标签可能被其他文件引用：
- 文本段标签： 1. 跳转标签，如循环时定义的 For/Loop/End 等标签； 2. 函数定义，如 main/add 等自行定义的函数；
- 数据段标签：出现在文件
.data段的数据标签。
重定位表(Relocation Table)：该文件中暂时无法确定的，需要在之后的过程中得到地址的标签：
j, jal等指令的跳转标签，一般都是在文本段中定义的，无论是文件内定义的还是文件以外定义的；- 任何可能的数据标签，例如所有被
la指令引用的数据标签。
4.3.2 汇编器具体实现
汇编器实现概述
本次实验，我们的汇编器将实现一个MIPS指令的子集。同时我们的汇编器是一个如上文描述的**“两遍”**汇编器，实现汇编.data和.text段。它将按照以下流程工作：
第一遍：读取输入的.s文件
举例如下：
.data
num: .space 8
num2: .space 16
.text
add:
lw $s5, -4($sp)
lw $s6, -8($sp)
addu $t0, $s5, $s6
move $v0, $t0
jr $ra
main:
la $v1, num
li $s1, 10
li $s2, 20
sw $ra, 0($a3)
sw $s1, -4($a3)
sw $s2, -8($a3)
move $sp, $a3
jal add
lw $ra, 0($sp)
move $t0, $v0
beq $t0, $0, end
j end
end:
- 剔除文件注释（在.s文件中，注释为#开头的单行注释）；
- 扩展伪指令，如
li,la等； - 记录文件符号，构建相应的符号定义表；
- 注意：在我们的处理中，为了区分符号是来自
.data段还是来自.text段，我们为来自.data段中的符号，在符号名最开始追加一个%用于在符号定义表中区分。
- 注意：在我们的处理中，为了区分符号是来自
- 标签（是否重复定义）和伪指令（是否合法）将被检查确认；
- 输出：中间文件（.int），对于
.data段，只需要输出.data段所占据的字节数即可，按照如下格式：
.data
24
.text
lw $s5 -4 $sp
lw $s6 -8 $sp
addu $t0 $s5 $s6
addu $v0 $0 $t0
jr $ra
lui $at num@Hi
ori $v1 $at num@Lo
addiu $s1 $0 10
addiu $s2 $0 20
sw $ra 0 $a3
sw $s1 -4 $a3
sw $s2 -8 $a3
addu $sp $0 $a3
jal add
lw $ra 0 $sp
addu $t0 $0 $v0
beq $t0 $0 end
j end
第二遍：读取.int中间文件
4.4 链接器
4.4.1 链接器原理详解
链接器读取我们汇编器输出的数个.o文件，利用目标文件中的信息，进行符号解析，最终输出可执行的机器代码，例如（a.out）。
链接器能够得到每个文件的text和data段的大小以及它们的顺序。利用这些，链接器便可以计算每个符号的绝对地址。
为了解析符号，链接器首先搜索每个文件的符号表（即每个文件定义的符号），如果没有找到，将继续在库文件中搜索(例如printf)。一旦获取到符号的定义位置，链接器就会填入实际的地址，完善机器代码。最终链接器输出的可执行文件包括.text和.data段（加上ELF文件头）。
对于我们的链接器而言，有四类地址：
- PC相对地址(
beq, bne)：不需要重定位，在汇编器汇编阶段已经确定了地址； - 绝对地址(
j, jal)：需要重定位，对应文本段中的跳转标签； - 外部引用(
jal)：需要重定位，对应文本段中的函数标签； - 数据引用(
la)：在汇编器中我们将其拆分为lui-ori指令对，需要重定位，对应数据段标签。
4.4.2 链接器具体实现
链接器实现概述
我们在汇编器中，解析了.data和.text段，因此我们在这里也将实现一个简化过的链接器，它将把一个或多个.o文件的.data和.text合并在一起来创建可执行的机器代码，但是我们不会为其添加ELF文件头，因此你可以认为我们的输出是可执行文件去掉ELF文件头以后的二进制bin文件。
具体的链接步骤如下：
- 创建一个空的全局符号定义表，这里将存储所有文件中符号（定义位置）的绝对地址，因此每个符号至多出现一次；
- 对于每个目标文件都创建一个独立的重定位表，将包含每个需要重定位符号的相对地址；
- 打开每个目标文件，分别读取它的
.data,.text,.symbol,.relocation段：- 如果是
.data段，读取该文件.data段的大小，用于计算上述提到的绝对地址； - 如果是
.text段，计算指令数目，得到该文件的指令将会占用多少字节（MIPS 的每条指令固定为 4 字节）； - 如果是
.symbol段，将其读入，将相对地址转换为绝对地址（怎么做？），并合并进第 1 步创建的全局符号表； - 如果是
.relocation段，将其读入进该文件的重定位表，保留其相对地址。
- 如果是
- 打开输出文件；
- 再次打开每个目标文件，读取
.text段，通过查找重定位表判断每条指令是否需要重定位，如果需要，使用符号表查找符号的绝对地址，并填入指令的相应字段，最终输出重定向后的指令即可。
链接器实现
链接器整体调用关系如下：
我们在汇编器的重定位表中引入新的结构体RelocData(定义在linker_utils.h)，主要是在重定位表中加入：
- 字段
text_size用于记录该文件的.text段需要占据的字节数； - 字段
data_size用于记录该文件的.data段需要占据的字节数；
typedef struct {
SymbolTable *table; //重定位表
int text_size; //相应文件.text段大小
int data_size; //相应文件.data段大小
} RelocData;
测试样例
为了便于理解，提供以下样例以供参考：
有以下两个.s文件需要进行处理：
main.s:
.data
num: .space 8
.text
main:
la $v1, num
li $s1, 10
li $s2, 20
sw $ra, 0($a3)
sw $s1, -4($a3)
sw $s2, -8($a3)
move $sp, $a3
jal add
lw $ra, 0($sp)
move $t0, $v0
beq $t0, $0, end
j end
end:
add.s:
4.5 测试环境及提交说明
提交说明
本次实验需要提交的文件只有my_assembler_utils.c和my_linker_utils.c。
测试说明
测试步骤
- 实验提供的代码里有针对各平台的辅助文件，将对应的
Makefile和libP4.a(Windows系统下为libP4.lib)文件复制到主目录下（即与assembler.c文件同一目录）； - 在主目录下通过命令行执行
make assembler可以得到汇编器可执行文件，执行make linker可以得到链接器可执行文件，或执行make可以一起编译汇编器和链接器。 - 创建输入文件，并写入你希望测试的
MIPS汇编代码，之后调用汇编器和链接器完成MIPS代码到机器码的转换，举例如下：
Linux系统与Mac系统下：
./assembler main.asm main.int main.out
./assembler add.asm add.int add.out
./linker main.out add.out main.o
Windows系统下：
assembler.exe main.asm main.int main.out
assembler.exe add.asm add.int add.out
linker.exe main.out add.out main.o
- 我们提供了各平台下的标准汇编器和链接器文件，以供大家作为参考。
- 我们还提供了CPU处理器用于运行机器码并观察结果，使用指南在下一章节。
测试环境
- Windows: 可以通过这篇教程安装
MinGW-64来执行make，注意需要配置系统变量，并拷贝一个mingw32-make.exe的副本命名为make.exe。 - Linux: 直接安装
gcc即可。 - Mac: 直接安装
gcc即可。
4.6 CPU使用指南
前言
这个CPU大体上和理论课讲过的单周期CPU差不多，就多一些细节，相信大家看一眼就知道怎么用，多看几眼就看明白结构了。
注意使用本次实验提供的2.16版logisim来打开，据测试jdk8也是能跑的，助教本地的jdk15也可以，要是jdk17、18就更没问题了。用logisim2.7可能CPU不能正常运行。
CPU支持的指令与指导书同步，因此不要测试超出的指令，可能会导致CPU无法识别而出现问题。
对于syscall系统调用，CPU仅支持用其停止程序，不支持任何输入输出，因此为了在CPU里调试，需要对MIPS代码进行一些修改：
- 对于简单的数字输入，可以直接使用
li指令写入寄存器； - 对于数字输出，可以将其存储到RAM的某一地址，在CPU停机后进行观察。 如下所示：
.data
.text
main:
li $a0, 100200
li $a1, -209
jal add
sw $v0, 0($zero)
li $v0, 10
syscall
add:
add $v0, $a0, $a1
jr $ra
如果你的汇编链接器实现正确，那么导入机器码并运行CPU停机后，会在内存地址第0行看到0x00018697。
如何使用
使用CPU的操作可以概括为：
- 编写汇编程序，用MARS或者自己的汇编链接器生成机器码；
- 向CPU中的指令rom加载机器码；
- 用
ctrl+k连续运行，或者用ctrl+t单步运行； - 停机后，查看内存中的运行结果。
导入机器码
用MARS导出机器码
在MARS编写好代码并汇编完成之后，选择上方工具栏Dump功能，如下所示：
之后在Dump Format里选择Hexadecimal Text并导出，就可以得到与我们的汇编链接器输出的同样格式的十六进制机器码了。
将机器码导入ROM
为了使用CPU处理器，我们需要将机器码导入ROM，也就是指令存储器。
首先，在我们自己的汇编链接器生成的机器码文件或者MARS导出的机器码文件的开头，加上一行v2.0 raw，如下所示：
v2.0 raw
3c010000
34230000
2411000a
24120014
acff0000
acf1fffc
acf2fff8
0007e821
0c000c0d
8fbf0000
00024021
11000001
08000c0d
8fb5fffc
8fb6fff8
02b64021
00081021
03e00008
然后找到ROM，右键点击并选择’加载数据镜像’，最后选择刚刚的机器码文件即可。
Logisim使用指导
Logisim使用指导
学习软件开发，你可能第一时间想到的是：C 语言、Java、Python、数据结构、前端后端、算法等等，没错，这些技术都是软件开发的关键技术，这些将来大家都会学习。然而，想成为一名优秀的软件工程师，仅仅掌握软件方面的知识， 是完全不够的。