指令調(diào)度簡(jiǎn)介

指令調(diào)度是指對(duì)程序塊或過程中的操作進(jìn)行排序以有效利用處理器資源的任務(wù)^[1]^。指令調(diào)度的目的就是通過重排指令，提高指令級(jí)并行性，使得程序在擁有指令流水線的CPU上更高效的運(yùn)行。指令調(diào)度優(yōu)化的一個(gè)必要前提就是CPU硬件支持指令并行，否則，指令調(diào)度是毫無(wú)意義的。

根據(jù)指令調(diào)度發(fā)生的階段，可以把其分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度^[2]^。

• 靜態(tài)調(diào)度：發(fā)生在程序編譯時(shí)期。靜態(tài)調(diào)度由編譯器完成，在生成可執(zhí)行文件之前通過指令調(diào)度相關(guān)優(yōu)化，完成指令重排。
• 動(dòng)態(tài)調(diào)度：發(fā)生在程序運(yùn)行時(shí)期。需要提供相應(yīng)的硬件支持，比如亂序執(zhí)行（OoOE: out-of-order execution），此時(shí)指令的發(fā)射順序和執(zhí)行順序可能是不一致，但CPU會(huì)保證程序執(zhí)行的正確性。

無(wú)論是靜態(tài)調(diào)度還是動(dòng)態(tài)調(diào)度，都是通過指令重排以提高指令流水，進(jìn)而提高程序執(zhí)行性能。靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度二者相輔相成，可以彌補(bǔ)對(duì)方的一些天然不足，協(xié)同完成指令流水優(yōu)化，提高程序性能。本文主要介紹靜態(tài)調(diào)度，如無(wú)特殊說(shuō)明，后續(xù)指令調(diào)度均指靜態(tài)指令調(diào)度。

現(xiàn)代計(jì)算機(jī)的指令并行方案

現(xiàn)代計(jì)算機(jī)的三種并行模式：流水線、超標(biāo)量、多核。其中流水線和超標(biāo)量與指令調(diào)度相關(guān)性更強(qiáng)，下面簡(jiǎn)單介紹一下這兩種模式。

1. 流水線
   將指令執(zhí)行過程分成多個(gè)階段，每個(gè)階段使用不同的硬件資源，從而使得多條指令的執(zhí)行時(shí)間可以重疊。
   經(jīng)典五段式流水線：IF（取指）、ID（譯碼）、EX（執(zhí)行）、MEM（訪存）、WB（回寫）。在五段式流水線中將一條指令的執(zhí)行過程分成了5個(gè)階段。
   

   • 使能流水線之前
     

   • 使能流水線之后
     

     在最優(yōu)情況下，一個(gè)cycle中，由于指令執(zhí)行的每個(gè)階段使用不同的硬件資源，不存在競(jìng)爭(zhēng)關(guān)系，從而可以使每個(gè)指令執(zhí)行在不同的階段。而由于數(shù)據(jù)依賴等原因的存在，流水線的并行程度一般很難達(dá)到最優(yōu)，具體的并行程度需要依賴于指令調(diào)度的效果。

對(duì)于如下原始指令序列

ldr    x1, [x2, x3]
add    x1, x1, #1
ldr    x5, [x2, x4]
sub    x5, x5, #1
mul    x6, x1, x5

在指令調(diào)度之前，耗時(shí)17個(gè)cycle：

在指令調(diào)度之后，耗時(shí)13個(gè)cycle：

ldr    x1, [x2, x3]
ldr    x5, [x2, x4]
add    x1, x1, #1
sub    x5, x5, #1
mul    x6, x1, x5

1. 超標(biāo)量
   具備超標(biāo)量結(jié)構(gòu)的CPU在一個(gè)內(nèi)核上集成了多個(gè)譯碼器、ALU等單元。相比于具備普通流水線技術(shù)的CPU，具備超標(biāo)量技術(shù)的CPU可以在同一個(gè)階段執(zhí)行多條處在相同階段的指令。
   
   超標(biāo)量流水線：
   

   指令調(diào)度與寄存器分配的關(guān)系

講到指令調(diào)度，不可避免的會(huì)想到寄存器分配，而指令調(diào)度和寄存器分配之間可以說(shuō)具有相互約束、相互作用的關(guān)系。

指令調(diào)度通過重排指令順序，降低指令間依賴，提高程序的并行度，相應(yīng)的，改變指令的執(zhí)行時(shí)機(jī)也會(huì)改變指令所使用的寄存器的生命周期；而寄存器分配又是挖掘程序的局部性，盡量縮短寄存器的生命周期，以能夠讓更多的數(shù)據(jù)直接存儲(chǔ)在寄存器中。

寄存器分配同樣也會(huì)影響指令調(diào)度，例如當(dāng)對(duì)寄存器的需求超過寄存器數(shù)量時(shí)，會(huì)選擇增加一些訪存指令，這些指令也需要納入到指令調(diào)度的考慮范疇之內(nèi)。

所以說(shuō)兩者相互約束?？梢灾?，將指令調(diào)度問題和寄存器分配問題作為兩個(gè)約束條件進(jìn)行聯(lián)合求解得到的解決方案是相對(duì)更優(yōu)的，但由于無(wú)論是指令調(diào)度還是寄存器分配，都是很復(fù)雜的NP完全問題，綜合考慮下，編譯器一般會(huì)分別處理二者^[1]^。

在LLVM編譯器的設(shè)計(jì)中，寄存器分配之前和寄存器分配之后都會(huì)執(zhí)行指令調(diào)度。

• 寄存器分配之前執(zhí)行指令調(diào)度：當(dāng)前LLVM IR中分配的寄存器為虛擬寄存器，寄存器數(shù)量不受限制，此時(shí)指令調(diào)度受到的約束最小，可以更大程度上提高指令并行度。但是在寄存器分配階段，使用物理寄存器替換虛擬寄存器，由于物理寄存器數(shù)量有限，寄存器壓力增大，可能產(chǎn)生寄存器spill場(chǎng)景影響程序性能。
• 寄存器分配之后執(zhí)行指令調(diào)度：寄存器分配階段由于寄存器復(fù)用等情況會(huì)增加指令間依賴，破壞在寄存器分配之前做好的指令調(diào)度優(yōu)化，所以在寄存器分配之后還要再次執(zhí)行指令調(diào)度。