機器碼生成
，是編譯階段的倒數第二個環節了。它把
三地址碼
序列轉化為
機器指令
序列，屬於編譯器裡的
機器相關
部分。
生成了機器碼之後，只要按照
elf
檔案的格式，把它寫成
可重定位
檔案，就可以讓
聯結器
去連線了。
連線和編譯是兩個步驟，連線相對要容易處理，速度也比編譯快得多，它主要處理各種全域性函式和變數（連線時叫
符號
）的
實際
地址。
編譯則要經過很多步驟，比連線複雜
得
多。
接下來說說編譯中最關鍵的一步，機器碼生成。
編譯器後端的實現，C語言
機器碼是依賴於具體的CPU型別的，生成的程式碼只能在某一類CPU上執行。要移植到其他CPU上，就要
重新編譯
對應的機器碼。
gcc就有很多平臺的工具鏈，來保證C程式碼在不同處理器之間的移植。
不同的CPU，指令集不一樣，暫存器不一樣，定址方式不一樣，在生成機器碼
時多少
有一些不同。
例如intel平臺上，乘法、除法都會使用rax和rdx，移位會使用rcx，在生成機器碼時就要注意運算元與這幾個暫存器的衝突。
ARM平臺的載入儲存指令比較強大，就儘量使用stmfd， ldmfd這類指令一次載入多個暫存器，以節省指令條數。
但總的來說，暫存器分配主要依賴於
變數之間的活躍情況
。即，
同時活躍
的變數
不能使用相同
的暫存器。
變數的活躍情況分析，在之前的文章裡提到過。就是從後往前查詢，如果某個變數在以後還使用，它在當前就是活躍的。
如果
現在
就要使用它
佔據的暫存器
（例如乘法，它現在佔據著rax，必須騰出來），就要先把它
儲存到記憶體
，以防
資料丟失
。
暫存器裡存的是什麼，變數到底在記憶體還是在暫存器裡，變數以後還用不用，是機器碼生成時的主要問題。
指令選擇
，我們暫時就為某個功能選擇固定的指令，這樣會大大
的
簡化機器碼生成的難度。要是指令選擇和暫存器分配糾結在一起，那程式碼就寫不下去了（捂臉）。
這個問題屬於NP完全問題，目前在數學上沒有最優解，所以咱們把指令就選成固定的，只做暫存器分配，一樣是
可行解
（笑）。
暫存器分配，使用的還是
圖的著色
演算法。
相鄰的節點表示同時活躍（即
衝突
的），不能使用同一個暫存器。
每一種顏色表示一個暫存器，其中rsp和rbp不能分配，只能當作棧指標。
暫存器分配使用的圖，屬於
無向圖
。它的邊只是表示兩個節點之間有連線，即兩個變數有衝突，沒有方向。
這個圖的節點資料結構還是很簡單的：
neighbors，表示節點的鄰居節點陣列，與它衝突的變數都是它的鄰居。
color，表示為節點分配的顏色，即分配的是哪個暫存器。
data，用來表示使用者自定義資料，例如存放變數的DAG節點。
圖的總體結構，就是一個大陣列，由所有節點組成。
各個節點之間複雜的
鄰居關係
，就反映了程式碼中的變數
活躍
情況。對這個圖進行
K著色
（K是可用的暫存器個數），就可以為各個變數分配暫存器。
分配完暫存器之後，就可以根據選好的指令去生成機器碼了。
這個用來給變數分配暫存器的圖，叫
暫存器衝突圖
，register conflict graph，縮寫成rcg。
機器碼的生成，是以函式為基本單位的。一個函式一個函式的處理。
函式內部劃分為多個迴圈，迴圈之間的程式碼劃分為一個個的組。然後以
迴圈
或
組
為單位，統一分配暫存器。
統一分配暫存器的
程式碼範圍越大
，越容易在全域性上給出
更最佳化的解法
。
因為暫存器
個數有限
，而函式的
程式碼量可以很大
，所以
暫存器溢位
是必不可少的。
即：把某個
以後還使用
的變數
儲存到記憶體
，騰出暫存器給
其他變數
使用一下，以後用到時再載入回暫存器。
intel早期的32位CPU，只有eax，ebx，ecx，edx，esi，edi，這6個暫存器。
現在的x64，多了r8-r15，但是相對於程式碼裡的變數個數來說，也是很少的。
所以，暫存器的溢位不可避免，也是很影響程式速度的一個地方。
在為
迴圈語句
生成機器碼時，要儘量避免在
內層迴圈
裡溢位暫存器。
不過對初學者來說，生成的機器碼能在電腦上跑起來就不錯了（汗）。
生成機器碼的步驟
如下：
1
，先根據三地址碼的指令序列構造暫存器衝突圖。
上圖是個函式指標陣列，存放為每種三地址碼構造暫存器衝突圖的函式。
遍歷三地址碼的序列，然後查詢這個陣列，就可以構造衝突圖了。
2
，給這個圖著色，完成暫存器分配。
著色演算法的程式碼還是很長的，不過主要思路依然是
編譯原理（龍書）
上的。
假設暫存器個數是K，如果某個節點的鄰居數量小於K，只要把它和鄰居分別著不同顏色就行。
即，為它和鄰居（表示與它衝突的變數）使用不同的暫存器。
不相鄰的變數互相不衝突，可以分配相同的暫存器。
其他情況，就要考慮暫存器的溢位了。
3
，為每條三地址碼生成機器指令序列。
這一步也是個指標陣列，存放為每種三地址碼生成指令的函式。
根據三地址碼和分配的暫存器，按照intel的機器指令格式，編成機器指令就可以了。
4
，把機器指令寫入elf可重定位檔案，編譯完成。
這個環節的程式碼還是很多的，但步驟比較清晰簡單。
程式碼細節以後再寫，先放一張圖：
左邊是生成的機器碼，右邊是objdump列印的彙編碼。
想了解更多精彩內容，快來關注
閒聊程式碼