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