实现简易的C语言编译器（part 10）
前面我们已经详细分析并实现了简易C语言的前处理、词法分析、语法分析和语义分析过程，最终得到了一棵没有语法错误、节点相互关系清晰的抽象语法树。这一部分，我们将继续遍历这棵树，生成汇编语言代码。
在进入这部分之前，有必要强调一下：出于简化的目的，我们这里定义的抽象语法树可能和教科书不甚相同。所以，大家可以看一看前面部分的内容，关键是记住这棵语法树的结构，便于接下来在遍历语法树时，定义节点函数和相关处理有清晰的认识。
除了一些对编译器实现相关的内容需要单独研究，我这里不打算详细介绍汇编代码其余的知识，这部分的内容完全可以上网或者从相关的书籍中获取。唯一说明的是，我们将采用AT&T格式的汇编代码，与之相对的是Intel格式。两者格式看似相差很大，但是主要的操作指令或者思路基本上是完全相同的。使用AT&T格式，在我看来，更有助于理解汇编指令操作过程，这是唯一的原因。
为了跟上时代的趋势，我们将实现自动生成64位的汇编代码，或者俗称x86-64汇编代码的过程。与传统的x86格式的相比，操作指令增加了对四字的扩展，指针类型从4个字节变成了8个字节；同时，新增加了若干寄存器，对函数参数有了支持。具体的差异可以参见官方文档，但可能需要科学上网。
生成汇编代码的过程相对来说稍显复杂，我们分成多个部分进行分析。
7.1 操作数
大多数操作指令都有一个或者多个操作数，指示出执行一个操作中要引用的源数据值，以及存放结果的目标位置。按照操作数的类别，可以分为：寄存器，寄存器和存储器引用。
7.1.1 寄存器
寄存器了表明某个寄存器的内容，AT&T格式的寄存器都是以%作为前缀的。先贴上一张主要的寄存器图：
图7-1 通用寄存器
这张图给出了我们将要使用的寄存器的功能和不同数据格式对应的寄存器名字，还有几个寄存器没有列出来，但仍然可以直接使用。C语言中，不同数据类型由于表示的字节长度不同，存储方式也不相同。例如，单字节的
char，4字节的int和8字节的指针类型。具体表现，就是对应的操作指令的后缀不相同；此外，我们也不需要为int类型的变量动用%rax这样的表示形式，转而应该使用%eax。为了表示这些寄存器以及得到变量类型对应的寄存器形态，定义如下的类：
class RegisterFrame:
byte_base_regs = ['%rax', '%rbx', '%rcx', '%rdx']
byte_index_regs = ['%rsi', '%rdi']
byte_extend_regs = ['%r8', '%r9', '%r10', '%r11']
stack_regs = ['%rbp', '%rsp']
def __init__(self, name):
self.name = name
def to_str(self, type_str):
if type_str == 'char':
output_str = self.reg_to_8()
elif type_str == 'int':
output_str = self.reg_to_32()
else:
output_str = self.name
if not output_str[0] == '%':
output_str = '%' + output_str
return output_str
def reg_to_8(self):
if self.name in self.byte_base_regs:
return self.name[2] + 'l'
elif self.name in self.byte_index_regs:
return self.name[2] + 'il'
elif self.name in self.byte_extend_regs:
return self.name[1:] + 'b'
else:
raise Exception(f"Register {self.name} is not byte-compatible!")
def reg_to_32(self):
if self.name in self.byte_base_regs or self.name in self.byte_index_regs:
return 'e' + self.name[2:]
elif self.name in self.byte_extend_regs:
return 'r' + self.name[2:] + 'd'
else:
raise Exception(f"Register {self.name} is not byte-compatible!")
通过传入64位寄存器的形态，我们将这12个寄存器按照名字的特点分成了4类，便于进行低位（8和32位）的转换。那么，这些寄存器用类表示，就是：
# the known register
Rax = RegisterFrame('%rax')
Rbx = RegisterFrame('%rbx')
Rcx = RegisterFrame('%rcx')
Rdx = RegisterFrame('%rdx')
Rsi = RegisterFrame('%rsi')
Rdi = RegisterFrame('%rdi')
R8 = RegisterFrame('%r8')
R9 = RegisterFrame('%r9')
R10 = RegisterFrame('%r10')
R11 = RegisterFrame('%r11')
Rbp = RegisterFrame('%rbp')
Rsp = RegisterFrame('%rsp')
# argument registers
Arg_regs = [Rdi, Rsi, Rdx, Rcx, R8, R9]
接下来，通过可以形如Rax.to_str('int')这种调用方式，就可以得到对应数据类型的寄存器形态。
7.1.2 立即数
立即数就是可以直接放在指令后面进行操作的整数，如movl $8, %eax中的$8。同样地，我们也可以定义一个立即数类来管理：
class ImmediateFreme:
def __init__(self, name):
self.name = name
7.1.3 存储器引用
存储器引用会根据计算出来的地址访问某个存储器位置。在AT&T格式的汇编代码中，通过括号来表示，如4(%eax)。具体的类可以定义为：
class MemoryFrame:
def __init__(self, name, offset):
self.name = name
self.offset = offset
def to_str(self, _type):
if self.offset == 0:
return self.name
return str(self.offset) + self.name
其中，offset就表示存储器偏移。
7.1.4 操作数管理
有了这些基本结构之后，我们定义一个类来管理这些操作数。
class FrameManager:
def __init__(self):
# A list of all registers
self.all_regs = [Rax, Rbx, Rcx, Rdx, Rsi, Rdi, R8, R9, R10, R11]
# A list of the registers currently free.
self.regs_free = self.all_regs[:]
# A list of all the registers that are "almost" free
self.regs_almost_free = []
self.stack = []
def get_free_reg(self, preferred_reg=None):
if len(self.regs_free) > 0:
reg = None
if preferred_reg is not None and preferred_reg in self.regs_free:
reg = preferred_reg
else:
for item in self.regs_free:
reg = item
break
if reg is not None:
self.regs_free.remove(reg)
return reg
def push(self, preferred_reg=None, is_reg=True):
if is_reg:
reg = self.get_free_reg(preferred_reg)
else:
reg = preferred_reg
self.stack.append(reg)
return reg
def pop(self):
if self.is_empty():
comment = f"stack is empty!"
raise CompilerError(comment)
loc = self.stack.pop()
if not loc.is_register():
return loc
if loc in self.all_regs:
self.regs_almost_free.append(loc)
return loc
def is_empty(self):
return len(self.stack) == 0
def done(self):
self.regs_free.extend(self.regs_almost_free)
self.regs_almost_free = []
这里我们使用了栈的结构来管理这些操作数，相比于采用其它的结构，它们将会在后面定义节点函数生成汇编代码时体会其优越性。值得注意的是，在弹出栈顶操作数的时候，我们并没有将其直接加入regs_free，而是先加入到regs_almost_free，直到调用done函数时，才加入到regs_free，我们也会在后面介绍这样做的原因。
7.2 操作指令
顾名思义，作用于具体寄存器、立即数或者存储器的运算符。通常，我们会在指令后面增加一个字符后缀，以表明操作数的大小。同样地，可以采用寄存器的形式来封装我们将要用到的操作指令：
class OperationFrame:
suffix_str = {'char': 'b', 'int': 'l', 'pointer': 'q'}
def __init__(self, name):
self.name = name
def to_str(self, type_str):
if type_str not in self.suffix_str.keys():
type_str = 'pointer'
output_str = self.suffix_str[type_str]
if output_str is not None:
output_str = self.name + output_str
else:
raise NotImplementedError('unexpected type')
return output_str
那么对应地，操作指令可以封装为：
Mov = OperationFrame('mov')
Add = OperationFrame('add')
Sub = OperationFrame('sub')
Mul = OperationFrame('imul')
Div = OperationFrame('idiv')
binop_arith_instrs = {'+': Add, '-': Sub, '*': Mul, '/': Div}
Push = OperationFrame('push')
Pop = OperationFrame('pop')
这部分主要研究了汇编语言的基本操作指令及其封装实现，为后面具体生成对应的代码提供方便。下一部分，我们开始分析汇编语言另一块非常重要的内容：栈帧结构。
实现简易的C语言编译器（part 0）
实现简易的C语言编译器（part 1）
实现简易的C语言编译器（part 2）
实现简易的C语言编译器（part 3）
实现简易的C语言编译器（part 4）
实现简易的C语言编译器（part 5）
实现简易的C语言编译器（part 6）
实现简易的C语言编译器（part 7）
实现简易的C语言编译器（part 8）
实现简易的C语言编译器（part 9）
实现简易的C语言编译器（part 11）
