Machine Outliner簡(jiǎn)介

在嵌入式領(lǐng)域，代碼體積（code size）優(yōu)化能夠減少內(nèi)存的使用，對(duì)產(chǎn)品的競(jìng)爭(zhēng)力至關(guān)重要。對(duì)當(dāng)代產(chǎn)品而言， code size優(yōu)化可以為產(chǎn)品放入更多特性，增強(qiáng)競(jìng)爭(zhēng)力；對(duì)下一代產(chǎn)品而言，code size優(yōu)化能夠帶來(lái)產(chǎn)品功耗和成本的競(jìng)爭(zhēng)力提升。LLVM Machine Outliner是一種編譯器優(yōu)化技術(shù)，可以識(shí)別重復(fù)代碼片段，將其提取出來(lái)并轉(zhuǎn)換成一個(gè)獨(dú)立的函數(shù)，從而降低程序code size。

示例

通過(guò)以下代碼示例，描述是否開(kāi)啟Machine Outliner優(yōu)化的效果：

int div(int x) {
    int a = x / 2;
    int b = x;
    return b / a;
}

int sub(int x) {
    int a = x / 2;
    int b = x;
    return b - a;
}

以上代碼片段由div和sub兩個(gè)函數(shù)組成，通過(guò)函數(shù)參數(shù)x，對(duì)變量a和b賦值，然后分別返回b和a相除，以及b和a相減的結(jié)果。其中，關(guān)于變量a、b賦值部分為重復(fù)代碼片段。

是否開(kāi)啟Machine Outliner優(yōu)化，在匯編層面的區(qū)別如下表所示：

如果不開(kāi)啟Machine Outliner優(yōu)化，則會(huì)分別在標(biāo)簽div和sub下生成相關(guān)的重復(fù)匯編指令。開(kāi)啟Machine Outliner優(yōu)化，則會(huì)將重復(fù)指令提取為單獨(dú)的函數(shù)，并且在重復(fù)指令初始位置添加函數(shù)調(diào)用，從而降低程序code size。在編譯階段，可以通過(guò)使用 -mllvm -enable-machine-outliner=always 選項(xiàng)開(kāi)啟Machine Outliner優(yōu)化，提取出的函數(shù)統(tǒng)一以“OUTLINED_FUNCTION_n”的形式命名。

后綴樹(shù)

Machine Outliner優(yōu)化依靠后綴樹(shù)（Suffix Tree）的形式進(jìn)行重復(fù)指令序列的識(shí)別，后綴樹(shù)的構(gòu)造和重復(fù)字符串查詢操作均可在線性時(shí)間復(fù)雜度內(nèi)完成，從而實(shí)現(xiàn)了Machine Outliner優(yōu)化的效率提升。

后綴樹(shù)是一種將字符串所有后綴存儲(chǔ)在一棵樹(shù)中的數(shù)據(jù)結(jié)構(gòu)，目的是用來(lái)支持快速搜索和大量字符串匹配和查詢，能高效解決很多關(guān)于字符串的問(wèn)題[2]。字符串S對(duì)應(yīng)的后綴樹(shù)，也就是由該字符串所有后綴所共同構(gòu)成的壓縮字典樹(shù)。

字典樹(shù)（Trie）是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)，其中每條邊用來(lái)表示一個(gè)字符，且每個(gè)節(jié)點(diǎn)出邊對(duì)應(yīng)的字符都不相同，將根節(jié)點(diǎn)到某一節(jié)點(diǎn)路徑上所經(jīng)過(guò)的字符拼接起來(lái)，即為該節(jié)點(diǎn)所表示的字符串。壓縮字典樹(shù)（Compressed Trie）由字典樹(shù)演變而來(lái)，將字典樹(shù)中的單節(jié)點(diǎn)鏈條壓縮為一個(gè)節(jié)點(diǎn)，即將相鄰的具有相同前綴的節(jié)點(diǎn)合并，可得到對(duì)應(yīng)的壓縮字典樹(shù)。字符串“ABD$0”對(duì)應(yīng)的字典樹(shù)和壓縮字典樹(shù)如下所示：

后綴樹(shù)的構(gòu)建需要經(jīng)過(guò)字符串后綴生成和壓縮字典樹(shù)構(gòu)建兩步：

1. 生成字符串S的所有后綴，以“ABCAB$0”(“$0”是結(jié)束字符）為例，該字符串的所有后綴為：

   ABCAB$0
   BCAB$0
   CAB$0
   AB$0
   B$0
   $0
   

2. 為以上所有后綴生成字典樹(shù)，并且合并節(jié)點(diǎn)生成相應(yīng)的壓縮字典樹(shù)：

令字符串S的長(zhǎng)度為n，通過(guò)構(gòu)建字符串S所對(duì)應(yīng)的后綴樹(shù)，即可在O(n)時(shí)間復(fù)雜度內(nèi)，完成字符串重復(fù)次數(shù)，以及重復(fù)字符串長(zhǎng)度的檢索[3]。

重復(fù)次數(shù)搜索： 假設(shè)字符串T在字符串S中重復(fù)次數(shù)為m，則字符串S應(yīng)有m個(gè)后綴以字符串T為前綴，即字符串T所對(duì)應(yīng)節(jié)點(diǎn)的葉節(jié)點(diǎn)數(shù)量為其重復(fù)次數(shù)。

重復(fù)字符串長(zhǎng)度搜索： 由于重復(fù)字符串出現(xiàn)次數(shù)大于1，所以字符串T在后綴樹(shù)中一定以非葉節(jié)點(diǎn)的形式表示，字符串T的長(zhǎng)度為該非葉節(jié)點(diǎn)到根節(jié)點(diǎn)所經(jīng)過(guò)的字符總數(shù)。

編譯器實(shí)現(xiàn)

LLVM對(duì)于Machine Outliner的實(shí)現(xiàn)在寄存器分配之后，主要集中在MachineOutliner.cpp中，基于機(jī)器指令表示（MIR）進(jìn)行函數(shù)的分析和提取，以實(shí)現(xiàn)程序code size優(yōu)化。

編譯器側(cè)的實(shí)現(xiàn)過(guò)程可劃分為指令映射、后綴樹(shù)構(gòu)建和函數(shù)提取三個(gè)階段：

1. 將指令映射成特定的無(wú)符號(hào)數(shù)，并以指令-無(wú)符號(hào)數(shù)對(duì)的形式存儲(chǔ)在Map中；
2. 以無(wú)符號(hào)數(shù)組為輸入構(gòu)建指令序列對(duì)應(yīng)的后綴樹(shù)，并且找出所有長(zhǎng)度大于2的重復(fù)指令序列；
3. 遍歷后綴樹(shù)并進(jìn)行收益計(jì)算，從而得到包含正收益序列的候選列表，對(duì)于具備收益的候選項(xiàng)進(jìn)行函數(shù)外提。

指令映射

首先需要遍歷源文件對(duì)應(yīng)的所有指令，將所有合法指令映射為無(wú)符號(hào)數(shù)（InstrNumber），并以指令-無(wú)符號(hào)數(shù)對(duì)的形式存儲(chǔ)在Map中，如果兩條指令的操作碼和操作數(shù)均相同，則認(rèn)為兩條指令相同。對(duì)于所訪問(wèn)的每條指令，首先應(yīng)該在Map中查詢是否已經(jīng)存儲(chǔ)了相同的指令，如果是，則返回對(duì)應(yīng)的InstrNumber；否則，將該指令插入到Map中，InstrNumber自加。

至此，所有指令均以無(wú)符號(hào)數(shù)的形式進(jìn)行唯一標(biāo)識(shí)，以作為構(gòu)建后綴樹(shù)的輸入。而對(duì)于讀寫棧指針、PC相關(guān)，以及其他與call、ret指令有數(shù)據(jù)依賴的指令，將被判定為非法指令，為保證程序運(yùn)行的正確性，這些指令不參與上述映射過(guò)程。

后綴樹(shù)構(gòu)建

假定將無(wú)符號(hào)數(shù)以字符形式表示，以指令映射輸出的無(wú)符號(hào)數(shù)組為輸入，通過(guò)添加終結(jié)符和構(gòu)建后綴樹(shù)，即可在線性時(shí)間復(fù)雜度內(nèi)，完成字符串S的所有重復(fù)子字符串長(zhǎng)度、重復(fù)次數(shù)和起始下標(biāo)的計(jì)算，這些重復(fù)字符串將以候選列表的形式輸出。

1. 以第2節(jié)所示匯編指令為例，經(jīng)過(guò)指令映射和添加終結(jié)符后可得到字符串S： ABCDEFG$0ABCDEH$1，其中添加終結(jié)符可避免跨函數(shù)指令序列提取。

2. 以字符串S為輸入，構(gòu)建后綴樹(shù)：

令A(yù)BCDE所指向的節(jié)點(diǎn)為P，單個(gè)字符所表示的距離為1，則節(jié)點(diǎn)P到根節(jié)點(diǎn)的距離為5，大于其他非葉節(jié)點(diǎn)到根節(jié)點(diǎn)的距離，因此ABCDE為字符串S中的最長(zhǎng)重復(fù)子字符串T。節(jié)點(diǎn)P有兩個(gè)子節(jié)點(diǎn)，因此字符串T的重復(fù)次數(shù)為2，且T在S中的起始下標(biāo)分別為[0,4]，[8,12]。

函數(shù)提取

完成后綴樹(shù)構(gòu)建和重復(fù)字符串解析后，還需要對(duì)提取該重復(fù)字符串對(duì)應(yīng)的指令序列進(jìn)行code size收益計(jì)算，計(jì)算公式如下：

codesize_benefit = codesize_before - codesize_after
codesize_before = 指令序列重復(fù)次數(shù) * 指令序列codesize
codesize_after = 插入call指令的codesize + 指令序列codesize + 插入ret指令的codesize

如果收益大于1，則提取同一重復(fù)字符串對(duì)應(yīng)的所有指令序列，以構(gòu)造outline函數(shù)，并在函數(shù)末尾額外添加ret指令。而對(duì)于重復(fù)字符串指向的下標(biāo)位置，需要?jiǎng)h除初始指令序列，并且通過(guò)call指令增加對(duì)outline函數(shù)的調(diào)用。

總結(jié)

本文對(duì)Machine Outliner的基本概念和實(shí)現(xiàn)方法進(jìn)行了簡(jiǎn)單介紹，通過(guò)將所有指令映射成為無(wú)符號(hào)數(shù)，并且以后綴樹(shù)的形式對(duì)重復(fù)指令序列進(jìn)行高效識(shí)別，最后提取具有正收益的指令序列作為outline函數(shù)，實(shí)現(xiàn)程序code size優(yōu)化，從而提高代碼的可讀性并且減少程序的內(nèi)存占用。

在源碼中大量使用宏、模板，以及循環(huán)展開(kāi)的場(chǎng)景下，開(kāi)啟Machine Outliner優(yōu)化將會(huì)獲得明顯的code size收益；而對(duì)于程序本身code size很小、結(jié)構(gòu)化設(shè)計(jì)良好，或者包含大量違反外提約束的情況，Machine Outliner對(duì)code size的優(yōu)化效果不顯著。此外，在LLVM14及更高版本上，完成了多次outline的實(shí)現(xiàn)，相比于本文所述的單次outline，能夠進(jìn)一步實(shí)現(xiàn)code size提升。