1. 作為指令高速緩層優(yōu)化的一種重要技術(shù)，它根據(jù)CFG流圖邊的執(zhí)行頻率將頻繁執(zhí)行的基本塊排列在一起，并布局那些基本塊在下降分支路徑，而不在一起的也就是很少執(zhí)行的基本塊布局在轉(zhuǎn)移分支路徑。這樣做一來可以使取到I-cache中的指令實際被執(zhí)行的比例較高，二來對于某些體系結(jié)構(gòu)上轉(zhuǎn)移和下降路徑延遲不等的分支指令，可以降低跳轉(zhuǎn)延遲
2. 實現(xiàn)過程內(nèi)代碼置放有以下幾個環(huán)節(jié)：
a）獲取剖析數(shù)據(jù)：編譯器可以先在基本塊出口處插入代碼以統(tǒng)計到其后繼基本塊的執(zhí)行次數(shù)，作為CFG流圖邊的權(quán)重，然后編譯生成可執(zhí)行文件，輸入代表性數(shù)據(jù)運行它，結(jié)果輸出一個數(shù)據(jù)文件，用于第二次編譯，這次編譯實施過程內(nèi)代碼置放優(yōu)化
b）以鏈的形式構(gòu)建熱路徑：熱路徑是CFG路徑的一個集合，其中包括頻繁執(zhí)行的那些邊，每條路徑是一個或多個基本塊按邊的方向構(gòu)成的鏈，每個鏈關(guān)聯(lián)一個優(yōu)先級，用于布局代碼的先后順序。初始時，每個基本塊構(gòu)成一個只有它本身的鏈，其優(yōu)先級為CFG流圖邊的數(shù)量或者更大值；接下來，在CFG中按權(quán)重降序遍歷每條邊<x,y>（x不等于y），若x是某個鏈a的尾結(jié)點且y是某鏈b的頭結(jié)點，則把b合并到a后面，更新a的優(yōu)先級為a原來優(yōu)先級、b優(yōu)先級、P三者的最小值，同時遞增P，其中P為鏈合并操作的計數(shù)器，用于決定鏈的相對次序由低到高排列，初值為0。當(dāng)遍歷結(jié)束時，所有熱路徑構(gòu)建完成
c）進(jìn)行代碼布局：經(jīng)過前一環(huán)節(jié)，就得到了鏈的集合。首先從鏈集合找出含有入口基本塊的鏈t，將t加入工作表WL；然后從WL移出一個優(yōu)先級最低的鏈c，按序（構(gòu)建鏈時加入基本塊的順序）遍歷c的每個基本塊x，把x放在過程可執(zhí)行代碼體的末端，對于邊<x,y>，將包含y的鏈t加入WL（若t不在WL中），重復(fù)該過程直至WL為空
posted on 2023-09-06 23:15
春秋十二月 閱讀(67)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler