? ? ? ? 這一部分，我們將基于之前創(chuàng)建好的抽象語法樹為源代碼生成具體的匯編語言代碼。在這之前，我們先來看看下面這段源代碼對應生成的匯編代碼的內(nèi)容：

int foo(
                             _foo:
                                  push   %rbp                                     
                                  mov    %rsp,%rbp  
        int a,                    mov    %edi,-0x4(%rbp)  
        int b                     mov    %esi,-0x8(%rbp) 
)     
{                        
                                  mov    -0x4(%rbp),%edx                          
                                  mov    -0x8(%rbp),%eax                          
    return a + b;                 add    %edx,%eax   
                                  pop    %rbp
                                  retq
}                                             
 

int main()
{
                            _main:
                                  push   %rbp                                     
                                  mov    %rsp,%rbp                                     
    int a;                        sub    $0x10,%rsp 
    a = 1;                        movl   $0x1,-0x4(%rbp)
                                  mov    -0x4(%rbp),%eax 
    return foo(  
        a,                        mov    %eax,%edi 
        2                         mov    %0x2,%esi
    );                            callq  _foo
                                  leaveq                                          
                                  retq
}

這里使用的是OnlineGDB在線編譯器，然后將源代碼和匯編語言代碼一一對應起來。每一行匯編代碼的意義，大家可以參考匯編語言指令的詳細介紹。接下來，將以左邊的源代碼代碼為例，開始實現(xiàn)一個匯編語言生成器，生成右邊的匯編代碼。
? ? ? ? 我們還是需要遍歷這棵抽象語法樹。為此，首先定義一個這樣的類：

class CodeGenVisitor(NodeVisitor):
    def __init__(self):
        self.curr_str = ""

    def output(self, op, left_reg, left_type, right_reg=None, right_type=None):
        _str = f"\t{op.to_str(left_type, right_type)} {left_reg.to_str(left_type)}"
        if right_reg is not None:
            if right_type is not None:
                _str += f", {right_reg.to_str(right_type)}"
            else:
                _str += f", {right_reg.to_str(left_type)}"

        self.curr_str += _str + "\n"

這里的curr_str用來存儲遍歷過程中生成的匯編語言代碼。只要獲得當前操作對應的操作指令和操作數(shù)，就可以利用output函數(shù)生成具體的匯編代碼。由于操作指令的后綴對應著操作數(shù)的大小，即操作指令具體的變種類型，就需要通過操作數(shù)具體的類型進行綜合判斷。例如，數(shù)據(jù)傳送指令就有4個變種：傳送字節(jié)的movb，傳送字的movw和傳送雙字的 movl以及傳送4字的 movq。
? ? ? ? 剩下的，就是仿照前面語義分析所用到的方法：定義節(jié)點函數(shù)。

8.1 函數(shù)定義

? ? ? ? 對于main和foo這樣的函數(shù)，在定義的過程中，它們對應的節(jié)點函數(shù)如下：

    def visit_FunctionDefn(self, node):
        self.stack = RegistersManager(self)
        # head
        self.output(Push, Rbp, PointerType())
        self.output(Mov, Rsp, PointerType(), Rbp)
        # parameters and local variables
        stack_frame_size = self.calc_function_var_addrs(node.scope_symbol, -8)
        self.stack.set_base_fp(stack_frame_size)

        previous_str = self.curr_str
        self.curr_str = ""

        node.body.visit(self)

        function_str = self.curr_str
        self.curr_str = previous_str

        left_reg = ImmediateFreme(f"${-self.stack.get_max_fp()}")
        self.output(Sub, left_reg, PointerType(), Rsp)
        # callee saves registers
        self.stack.save_callee_saves()
        self.curr_str += function_str
        self.stack.restore_callee_saves()
        
        if not self.stack.get_max_fp() == 0:
            self.output(Mov, Rbp, PointerType(), Rsp)
        self.output(Pop, Rbp, PointerType())

    def calc_function_var_addrs(self, scope_symbol, last_fp_loc):
        self.calc_function_arg_addrs(scope_symbol)
        return self.calc_local_var_addrs(scope_symbol.children[0], last_fp_loc)

在函數(shù)體內(nèi)部，我們首先初始化了一個操作數(shù)管理器。接下來的兩句和最后的輸出可以對應匯編語言代碼中處理函數(shù)的“標準”格式，在進入函數(shù)和退出函數(shù)的時候，一般都是：

push   %rbp                                     
mov    %rsp,%rbp  
...
pop    %rbp

8.1.1 函數(shù)參數(shù)

? ? ? ? 定義函數(shù)入口之后，我們首先處理函數(shù)的參數(shù)：

    def calc_function_arg_addrs(self, scope_symbol):
        Arg_regs = [Rdi, Rsi, Rdx, Rcx, R8, R9]

        arg_index = 0
        arg_size = 0
        for symbol in scope_symbol._symbols.values():
            if arg_index > 5:
                arg_size += FrameManager.WORD_SIZE
                symbol.compile_loc = MemoryFrame(f"(%rbp)", arg_size)
            else:
                symbol.compile_loc = Arg_regs[symbol.parms_index]
                self.stack.remove_free_reg(symbol.compile_loc)

            arg_index += 1

這里，我們用到了在語義分析中聲明檢查時得到的產(chǎn)物：作用域和變量表。具體地，對函數(shù)的前六個參數(shù)，我們使用對應的寄存器進行保存，避免了先轉(zhuǎn)換為存儲器，實際運算時可能再轉(zhuǎn)換為寄存器的麻煩，使生成的代碼更加簡潔。剩下的函數(shù)參數(shù)，我們則向上（棧幀地址增大的方向）開辟出具體的空間來存儲它們。值得注意的是，這里我們并沒有關心參數(shù)的具體類型，統(tǒng)一用4字來存儲。

8.1.2 局部變量

? ? ? ? 接著，我們處理函數(shù)體中的局部變量：

    def calc_local_var_addrs(self, scope_symbol, last_fp_loc):
        """calculate local variable address in function body"""
        for symbol in scope_symbol._symbols.values():
            if not symbol.is_used:
                continue
          
            next_fp_loc = last_fp_loc - self.calc_var_size(symbol.type)
            last_fp_loc = self.calc_var_align(self.calc_var_size(symbol.type), next_fp_loc)
            symbol.compile_loc = MemoryFrame(f"(%rbp)", last_fp_loc + self.calc_var_size(symbol.type))

        max_last_fp = last_fp_loc
        # recursive calculate local variables inside the scope
        for kid in scope_symbol.children:
            curr_last_fp = self.calc_local_var_addrs(kid, last_fp_loc)
            if curr_last_fp < max_last_fp:
                max_last_fp = curr_last_fp

        max_last_fp = self.calc_var_align(FrameManager.WORD_SIZE, max_last_fp)

        return max_last_fp

同樣地，函數(shù)體內(nèi)部的變量我們都存儲在了變量表中，并且保存在作用域中。在聲明檢查中，我們提到過，由于大括號對會引入新的作用域，因此，還需要遍歷子一層作用域進行類似的操作。為了節(jié)約使用寄存器，我們會為每個使用過的變量向下（棧幀地址減小的方向）開辟出新的地址來存儲它們。

8.1.2.1 數(shù)據(jù)對齊

? ? ? ? 許多計算機系統(tǒng)都要求某種類型對象的地址必須是某個值（通常是2，4或8）的倍數(shù)。因此，我們需要使用last_fp_loc來動態(tài)跟蹤最小地址的位置。這里，用到了幾個輔助函數(shù)：

    @staticmethod
    def calc_var_size(self, _type):
        type_str = _type.get_string()
        if type_str == 'char':
            return FrameManager.CHAR_SIZE
        elif type_str == 'int':
            return FrameManager.INT_SIZE
        elif type_str == 'pointer':
            return FrameManager.WORD_SIZE

    @staticmethod
    def calc_var_align(align, next_fp_loc):
        bytes_overboard = (-next_fp_loc) % align
        if not bytes_overboard == 0:
            last_fp_loc = next_fp_loc - (align - bytes_overboard)
        else:
            last_fp_loc = next_fp_loc

        return last_fp_loc

calc_var_size用來計算變量對應的類型大小，決定分配多大的地址。而calc_var_align則用來進行數(shù)據(jù)對齊。這方面的知識大家可以查閱其它資料進行獲得完全的認識，這里就忽略了。

8.1.3 其它

? ? ? ? 得到的last_fp_loc指出了存儲數(shù)據(jù)地址的范圍。那么，在操作數(shù)管理器中，臨時變量的區(qū)域我們就選擇開辟在這之外，即向下（棧幀地址減小的方向）開辟存儲區(qū)域。并將棧指針放置到當前位置。
? ? ? ? 接下來，我們會訪問函數(shù)體內(nèi)部的其它節(jié)點，我們會在后面詳細定義。在外部看來，當前函數(shù)就是被調(diào)用函數(shù)，因此，我們需要保存對應的被調(diào)用保存寄存器。這樣，就完成了生成函數(shù)定義的匯編語言的實現(xiàn)。整個過程，其實就是按照上一部分，對棧幀結(jié)構(gòu)實現(xiàn)的過程。

8.2 函數(shù)調(diào)用

? ? ? ? 說完了函數(shù)定義的過程，我們看看函數(shù)調(diào)用如何處理：

    def visit_FunctionOp(self, node):
        self.stack.save_caller_saves()

        node.args.nodes.reverse()
        arg_num = len(node.args.nodes)
        for arg in node.args.nodes:
            arg_reg = self.visit_and_pop(arg)
            if arg_num > 6:
                offset = (8 - arg_num) * FrameManager.WORD_SIZE
                if not offset == 0:
                    right_reg = ImmediateFreme(f"{-offset}(%rsp)")
                else:
                    right_reg = ImmediateFreme(f"(%rsp)")
            else:
                right_reg = Arg_regs[arg_num-1]

            self.output(Mov, arg_reg, arg.type, right_reg)

            arg_num -= 1

        node.args.nodes.reverse()
        self.comment(f"callq {node.expr.symbol.compile_loc}")

        self.stack.done()
        result_reg = self.stack.push(preferred_reg=Rax)
        if not result_reg == Rax:
            self.output(Mov, Rax, node.type, result_reg)

        arg_stack_size = ((len(node.args.nodes) - 6) * WORD_SIZE)
        if arg_stack_size > 0:
            left_reg = ImmediateFreme(f"${arg_stack_size}")
            self.output(Add, left_reg, PointerType(), Rsp)

正如在棧幀結(jié)構(gòu)中所說的那樣，在調(diào)用函數(shù)時，調(diào)用者需要保存對應的寄存器，然后，再處理函數(shù)參數(shù)傳遞相關的工作。這里需要注意的是，由于函數(shù)參數(shù)是按照向上（往棧幀地址增大的方向）順序排布的，為了方便起見，我們先將函數(shù)參數(shù)順序翻轉(zhuǎn)再進行操作。此外，按照規(guī)定，結(jié)果寄存器%rax用來存儲返回值。因此，如果得到的最終寄存器不是%rax，則需要進行轉(zhuǎn)換。函數(shù)調(diào)用結(jié)束之后，就需要移動棧指針，回收函數(shù)參數(shù)分配的地址空間。

8.3 四則運算

? ? ? ? 函數(shù)體內(nèi)的節(jié)點包含著具體的語句，我們首先從最基本的四則運算過程說起。定義賦值操作節(jié)點函數(shù)如下：

    def visit_BinOp(self, node):
        if node.op == '=':
            self.binop_assign(node)

    def binop_assign(self, node):
        node.left.visit(self)
        right_reg = self.visit_and_pop(node.right)
        left_reg = self.stack.pop()

        self.output(Mov, right_reg, node.type, left_reg)
        self.stack.done()

    def visit_and_pop(self, node):
        if node.is_const():
            return ImmediateFreme(f"${node.expr}")
        else:
            node.visit(self)
            return self.stack.pop()

在賦值運算操作過程中：

• 首先訪問賦值運算符左邊節(jié)點，將對應的操作數(shù)存儲在堆棧中。
• 其次，訪問賦值運算符右邊節(jié)點。如果是立即數(shù)，則直接返回；否則訪問節(jié)點得到具體的操作數(shù)。
• 再從堆棧中得到存放的賦值運算符左邊節(jié)點對應的操作數(shù)。
• 輸出具體的操作指令代碼，釋放所有當前使用的寄存器。

? ? ? ? 看起來，似乎可以采用直接訪問節(jié)點得到操作數(shù)的方法，完全不用堆棧先將左邊節(jié)點存儲起來，等右邊節(jié)點訪問結(jié)束才彈出節(jié)點對應的操作數(shù)。但是，不要忘了，我們這里定義的節(jié)點是廣義的節(jié)點，一個節(jié)點本身又可能是一個雙目操作符，采用堆棧結(jié)構(gòu)可以嚴格保證操作數(shù)的對應關系，這是由遍歷抽象語法樹的過程所決定的。那么，左右兩邊的節(jié)點到底去訪問什么呢？

    def visit_Id(self, node):
        if self.stack.last_is_memory():
            reg = self.stack.push()
            self.output(Mov, node.symbol.compile_loc, node.type, reg)
            return

        self.stack.push(node.symbol.compile_loc, is_reg=False)

通過訪問最終的標志符，就得到了具體的操作數(shù)，因為我們在函數(shù)定義中已經(jīng)給這些變量都分配了存儲空間，或者說都是存儲器引用。這里，我們使用了一點技巧來簡化匯編代碼：

class FrameManager:
    ...
    def last_is_memory(self):
        if self.is_empty():
            return False

        return self.stack[-1].is_memory()

由于在進行一個完整操作指令代碼生成之前，會有很多節(jié)點訪問到此，都會先存儲在操作數(shù)管理器的堆棧中。如果當前堆棧里面已經(jīng)存放了一個存儲器，由于匯編語言規(guī)定，操作指令中的兩個操作數(shù)不能同時為存儲器，必須將額外的存儲器先轉(zhuǎn)換成寄存器再進行操作。因此，在這里，我們先進行這樣的轉(zhuǎn)換。
? ? ? ? 有了賦值運算的操作流程，那么加減乘除也可以對應地實現(xiàn)：

    def visit_BinOp(self, node):
        ...
        if node.op in ('+', '-', '*', '/'):
            self.binop_arith(node)

    def binop_arith(self, node):
        binop_arith_instrs = {'+': Add, '-': Sub, '*': Mul, '/': Div}

        node.left.visit(self)
        right_reg = self.visit_and_pop(node.right)
        left_reg = self.stack.pop()

        self.output(binop_arith_instrs[node.op], right_reg, node.type, left_reg)
        self.stack.done()

        self.stack.push(left_reg)

唯一不同的是，需要將運算結(jié)果放到堆棧中，留作后面的運算使用。這樣，由于進行了轉(zhuǎn)換，這個結(jié)果就是寄存器，而不是存儲器引用，方便了后面運算的調(diào)用，而不用每次運算的時候都進行一次存儲器到寄存器的轉(zhuǎn)換。

? ? ? ? 將這之前我們實現(xiàn)的代碼整理一下，便可以對開頭那段源代碼生成對應的匯編語言代碼，結(jié)果如下：

    pushq %rbp
    movq %rsp, %rbp
    subq $8, %rsp
    addl %edi, %esi
    movl %esi, %eax
    movq %rbp, %rsp
    popq %rbp
                        
    pushq %rbp
    movq %rsp, %rbp
    subq $16, %rsp
    movl $1, -8(%rbp)
    movl $2, %esi
    movl -8(%rbp), %edi
    callq _foo
    movq %rbp, %rsp
    popq %rbp

看著還是比較清晰和簡潔，但還有一些細節(jié)沒有處理。此外，還有語句的實現(xiàn)，我們都會在下一部分繼續(xù)研究。

實現(xiàn)簡易的C語言編譯器（part 0）
實現(xiàn)簡易的C語言編譯器（part 1）
實現(xiàn)簡易的C語言編譯器（part 2）
實現(xiàn)簡易的C語言編譯器（part 3）
實現(xiàn)簡易的C語言編譯器（part 4）
實現(xiàn)簡易的C語言編譯器（part 5）
實現(xiàn)簡易的C語言編譯器（part 6）
實現(xiàn)簡易的C語言編譯器（part 7）
實現(xiàn)簡易的C語言編譯器（part 8）
實現(xiàn)簡易的C語言編譯器（part 9）
實現(xiàn)簡易的C語言編譯器（part 10）
實現(xiàn)簡易的C語言編譯器（part 11）