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