1. 區間圖：用于局部寄存器分配，基本塊內的每個活躍范圍看作一個區間（最早定義位置+最新使用位置），所有活躍范圍構成區間圖。區間圖是一種不精確的沖突圖（因為高估了活躍范圍的范圍而導致偽沖突，比如認為一個復制操作連接的或兩個源相同目標不同的復制操作產生重疊的兩個活躍范圍沖突，但實際沒有沖突），優勢在于著色是P（復雜度O(|V|)或O(|E|)）而非NP問題。llvm早期的線性掃描分配器是基于區間圖在全局的擴展，比較適用于JIT編譯（減少編譯時間）
2. 一般圖：用于全局寄存器分配，是一種精確的沖突圖（由一組定義與一組使用構成的網絡）。優勢在于努力最小化溢出活躍范圍而生成高效執行的代碼，但會犧牲編譯時間。llvm的greedy寄存器分配是基于一般圖的代表。編譯器使用的沖突圖可能會將機器約束條件比如多寄存器值/調用約定編碼進去而存在重復邊，導致不滿足圖論中的簡單圖定義，故這里采用一般圖
3. 弦圖：定義詳見
https://oi-wiki.org/graph/chord。基于靜態單賦值形式名建立的沖突圖是弦圖。優勢在于可以做到最佳著色（復雜度O(|V|+|E|)）而非啟發式（基于一般圖的全局寄存器分配使用啟發式），利于減少寄存器壓力。劣勢在于必須將指派寄存器后的仍然為靜態單賦值代碼轉換為機器碼，而這種轉換可能增加寄存器壓力，以及插入一些可能非必要的復制操作，若復制操作實現的數據流與ssa phi函數對應，則分配器無法合并這種復制，這將破壞弦圖的性質
4. 沖突圖拆分：查找其中的團分割即連通子圖，移除它劃分得到不相交的一些子圖，這樣一來，各子圖可獨立著色（有點類似活躍范圍拆分）而利于減少寄存器壓力，另外實現上還能節省下三角布爾矩陣（用于快速判斷兩結點是否沖突）的規模
#############################
寄存器分配與圖論的染色理論相關。其它的比如常量傳播與格代數及不動點相關，循環優化與多面體、矩陣相關。這三方面是我目前看到的編譯器所用數學理論
posted on 2023-10-04 13:08
春秋十二月 閱讀(3881)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler