Assembler Lab

ICS Lab6: Y86-64 Assembler

我Coding + Debugging的总耗时约13小时（Wakatime统计）

代码量：

本篇文章将从整体上拆解一下代码框架和实现思路，以及Debug的时候容易遇到的错误，不涉及具体的实现细节（无代码剧透）。

在Lab6，我们继续深入认识Y86-64指令集架构，实现一个Assembler将Y86-64汇编代码转化为Y86-64二进制代码。

Skeleton Code

在开始Coding之前，一定要先阅读并梳理代码框架！这里我简单讲解一下：

我们的Assembler需要负责将y86-64汇编源代码转化为机器能够直接执行的二进制代码。也就是说，Assembler的input是一个y64汇编文件（.ys），output是一个y64二进制文件。

那么如何做到呢？观察main函数，代码框架处理的思路如下：

1. 按行扫描并解析input .ys file，存储每一行汇编代码对应的字节码
2. 重定位第一遍扫描未解析的symbol
3. 将解析完成的结果（字节流）写入output file中

具体来说：

assemble函数负责解析input file，一行行读取y64汇编代码。每读取一行，交给parse_line对这一行汇编代码进行分词与解析。然后将该行的解析结果（字节码）存入一个line_t结构，加入到line table中。

assemble会按行将input file从头到尾扫描一遍，将每一行汇编代码转化成字节码存在line_t中，但是可能会留有未解析的symbol。代码框架的策略是当扫描到一个label时，将这个label的内存地址和名字存储在symbol_t结构中，加入到全局的symbol table。当扫描到一个无法解析的symbol时，将该行未完整解析的字节码和symbol的名字存储在reloc_t中，加入到relocation table。

在assemble扫描完一遍input file过后，relocate会被调用。relocate负责遍历relocation table，对每一个未解析symbol的行，在symbol table中找到这个symbol，用这个symbol的内存地址对应的字节码替换该行字节码中的符号占位。

assemble和relocate结束，就说明整个input .ys file全部解析完成，所有行的字节码都存在了line table中。这时候binfile会被调用。binfile会遍历line table，将每行的字节码写入到ouput file中。

Implementation

扫描，分词和解析

我们核心要实现的是parse_line，也就是对一行汇编代码进行分词和解析的工作。

一行汇编代码可能包含几个部分：注释、标签、指令、汇编器伪指令。你的parse_line需要能识别出这几部分。框架代码提供了很多宏和parse_xxx函数来帮助你解析。

我在这里梳理一些主要的实现逻辑：

1. 解析指令

注释和标签都不需要解析为字节码，因此我们关注的重点在解析指令上：

根据指令的类型（icode），需要不同的parse逻辑。因此需要一个switch语句分类parse不同类型的指令。可以思考的是哪些指令可以合并parse，查看下图的Y86-64指令集：

相同字节码格式的指令可以在switch里面合并处理。因为我们关心的只是字节码，与不同指令的执行行为和op code都没有关系。比如rrmovq, cmovXX, OPq可以合并，因为都是只需要解析rA和rB两个寄存器。

2. 解析汇编器伪指令

汇编器伪指令（assembler directives）其实不是真正的指令，但是可以统一当作指令一样处理。因为我们关心的只是翻译成的字节码而已。其中.pos和.align这两条伪指令很特殊，他们并不会翻译成字节码，但是可能会改变当前的内存地址。**想一想这会对我们的字节流的输出产生什么影响？**如果你现在想不到，可以到Debug的时候再处理。

3. 处理symbol占位

有三处位置可能会有symbol占位，在最后relocate部分需要用symbol对应的地址（字节码）替换：

1. irmovq中的立即数可能是symbol
2. jXX和call后面的Dest可能是symbol
3. 汇编器伪指令.byte, .word, .long, .quad后面的data可能是symbol

因此在遇到label的时候，需要将其存入symbol_t加入到symbol table。在遇到symbol的时候，需要先将该行的其余部分解析完成，将未完整解析的字节码和symbol的名字一起存入reloc_t，加入到relocation table。

4. 错误处理

当遇到解析错误时，需要err_print打印正确的错误信息。

assemble和binfile

在扫描完所有行汇编代码后，assemble还需要做一件事来确保你解析的汇编代码是正确的。这个在你实现的时候想不到很正常，可以留到Debug的时候再处理。

binfile需要遍历line table，将每行的字节码写入到ouput file中。这里的写法也有很容易忽略的点，前面其实我已经埋下了伏笔。

Debugging

在Coding的过程中，你应该会发现我们的Assembler实现细节非常琐碎，而且我前面也提到容易出错/忽略的点很多（我在下面会罗列出来），因此花费Debug的时间会比较多。

1. 在parse_line中不能移动line->y64asm指针，这个指针永远指向这一行汇编代码的开头。因为后面print_line需要用到这个指针来打印这一行的汇编代码；并且line->y64asm是在assemble中用malloc初始化的，因此在finit中需要传递同一个指针给free。

2. 注意symbol table和relocation table中的第一个entry是一个dummy head，你第一个向里面添加的symbol_t/reloc_t应该接在这个dummy head后面。

3. 只有标签(label)的行需要解析为instruction(TYPE_INS)类型，这样print_line才会打印标签行的内存地址。

4. parse_digit需要将*ptr指向的字符串数据解析为long类型的数据。注释里提示的strtoll是将数据解析成(signed) long long类型，因此如果字符串数据大于0x7FFFFFFF就会overflow，会返回signed long long的最大值0x7FFFFFFF。但是我们需要能够解析0 - 0xFFFFFFFF的任意字符串数据，那怎么办呢？可以用strtoull将字符串数据解析为unsigned long long，再cast成long。cast的过程不会改变bit pattern，只不过大于0x7FFFFFFF的数long类型会解析成负数。但只要不改变bit pattern，就不影响最终字节码的翻译。

5. .pos和.align directive可能会改变vmaddr，会有什么影响呢？这里就是伏笔回收。这两个汇编器指令的前一条指令和后一条指令间可能会空出来一段内存地址，需要向output binary file中添加padding zeros来填补前后两条指令间的空白。我的做法是不将.pos和.align翻译成字节码，但是在binfile中每次写入output file前检查当前output file中的位置是否等于当前要写入的指令的内存地址。如果不是，说明要向output file中添加padding zeros。

6. assemble里面parse完所有的行后还需要做什么？伏笔回收：需要检查JXX/call指令的destination address是否有效。如果这个destination address不等于整个文件中任一一条指令/标签的地址，说明这个destination address是无效的，需要报错。

Debug的时候用好y64asm和y64asm-base程序的-v功能，对照汇编源代码和（你的assembler和标准y64 assembler的）二进制输出，以及比较你的assembler和标准y64 assembler输出的.bin文件的区别。

Test

To test and evaluate your Assembler:

yat -h 
# Show help information of yat

yat -s <instruction> 
# Test correctness of single instruction in y64-ins directory

yat -s <error> 
# Test correctness of processing with specific error in y64-err directory

yat -S 
# Test correctness of processing all instructions and errors.

yat -a <program> 
# Test correctness of processing single .ys file in y64-app directory

yat -A 
# Test correctness of processing all .ys files provided in y64-app directory

yat -F 
# Test correctness of processing all instructions, error types and programs.

All tests pass!🤗

总结

总体来说，Assembler的实现思路代码框架还是提示的很完整的，也很简洁。但是具体实现起来琐碎的细节很多，需要有耐心慢慢地水磨功夫和Debug。

经过Lab6和Lab7，现在给我们一段汇编代码，我们的Assembler可以将其转化成二进制代码。我们的Simulator可以根据转化来的二进制代码，模拟硬件的行为执行这段汇编代码。