Register Allocation in GCC : Reload / LRA

這篇文主要是想簡短介紹一下邪惡的 Reload 以及目前 LRA 的一些狀況, 這部份大概是 GCC 最棘手的部份, 其中缺乏文件且程式碼又跟漿糊一樣, 一直到了近年來才有 Vladimir Makarov@redhat 在幫忙加註解兼整理, 這篇大致上是根據其 Wiki 頁面及 LRA 簡報再加上一些個人經驗所匯集而成的東西.

Reload

在介紹 Reload 前一定要提下 GCC reload 的 Wiki 頁面[1]頁面上的經典介紹, 其中第一段第一句

"Reload is the GCC equivalent of Satan."

在強而有力的開場白後, 接著就來介紹 Reload 到底做了甚麼事？

• 產生 Spill Code
• 想辦法符合 Instruction constraint
• CSE (common subexpression elimination)
• 融合 Frame Point 及 Stack Point (-fomit-frame-pointer)
• 想辦法把所有 non-strict RTL 弄成 strict RTL
• 蓋 Constant pool

所以在 Reload 完後, 基本上所有 insn 都已經符合  Instruction constraint, 言下之意就是可以輸出成組合語言了, 也因此 Reload 在 GCC backend 裡面是一個非常重要的里程碑, 而 reload_completed 這個變數則可以查詢目前使在 reload 前還是後, 亦或是正在 reload (variable:reload_in_progress).

雖然 Reload 很強大, 但問題就在於太強大太貪心作太多事了, 模組也沒切的很好, reload.c + reload1.c 大概超過一萬六千多行左右, 缺乏註解, 並且可怕的是其中的函數參數都很多, 而其中的一些 assertion 的邏輯也沒說明的很清楚, 導致目前沒多少人有膽去動...在 GCC 的程式碼堆裡面一直是個黑暗角落...而其中最大的問題是引入過多不必要的 Target Marco , 其中有相當程度的資訊基本尚可由 md 檔中推導而出, 導致 Porting 難度的增加.

LRA : Local Register Allocation

在一片混沌多年後, IRA 的主要作者 Vladimir Makarov@redhat 跳出來試著想要把 Reload 換掉, 當然如同 Register Allocation 一樣, 不是第一個跳出來挑戰的人, 但 Vladimir Makarov@redhat 卻是第一個成功將 Register Allocation 換掉的人, 也因此 LRA 這個計畫相當的令人期待.

大致了解 LRA 的使命後接著來介紹他所設定的幾個設計目標

• 盡可能的將各個模組切開
• 盡可能的將資訊反應到 RTL 上, Reload 則是偏好在 RTL 串上一堆 note
• 將 MD 中 Insn 的 Constraint 作為主要資訊來源, 減少額外 Target Marco 的需要

接著是來看他內部的架構圖, 大致上是採用 Iterative pass 的方式來處理

其中比較要注意的是 Virtual Register 跟 Pseudo Register , 各家的 Register Allocation 皆有各自的定義, 而這邊的定義則是

1. Hard Register : 代表目標機器的實體暫存器
2. Virtual Register : 代表一些特殊的暫存器如 Argument  pointer, Frame pointer 及 Stack pointer, 但為何稱為  Virtual , 則是有些機器並無保留特定的 Register, 通常用 Stack pointer 加上 offset 來表示.
3. Pseudo Register : 則是代表每一個可被分配暫存器的最小單位,  Pseudo Register 僅用於 Compiler 內部使用, 且數目可無限多個不被  Hard Register 的數目限制, 但最終經過 Register Allocation 後, IR 內部將不會有任何 Pseudo Register.

另外補上一些名詞說明

1. Coalesce : 看到類似 mov a, b 的指令時, 試著強制合併 a, b 藉此分配到相同暫存器或記憶體空間(如 LRA 中的Memory-memory move), 以此消除搬移指令
2. Inheritance : 這個是在 LRA 中的專有名詞, 跟 Coalesce 的概念有點類似, 但主要差別在於其作用範圍在 EBB
3. Spill : 當暫存器不足以使用時, 將變數暫時存回 Memory, 這個行為稱為 Spill
4. Constraint : 指 gcc 在每道 insn pattern 中對於每個 Operand 的規範, 通常寫在 md 檔裡面

目前 LRA 還尚在開發當中, 在 gcc 4.7 中尚無計畫合併進來, 但仍然是個相當令人期待的專案, 若 LRA 發展順利則可降低 Porting 難度, 以及實作 Register allocator 的難度, 否則現在卡了個 Reload 改 Register allocator 相當容易吃鱉還不知道真正錯誤原因而無從 debug 起...


參照連結
[1] http://gcc.gnu.org/wiki/reload
[2] http://vmakarov.fedorapeople.org/LRA.html