什么是指令調(diào)度（上）

指令調(diào)度簡介

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

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

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

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

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

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

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

   • 使能流水線之前
     

   • 使能流水線之后
     

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

對于如下原始指令序列

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

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

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

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

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

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

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

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

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

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

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

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