指令調度簡介

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

根據指令調度發生的階段，可以把其分為靜態調度和動態調度^[2]^。

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

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

現代計算機的指令并行方案

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

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

   • 使能流水線之前
     

   • 使能流水線之后
     

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

對于如下原始指令序列

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

在指令調度之前，耗時17個cycle：

在指令調度之后，耗時13個cycle：

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

1. 超標量
   具備超標量結構的CPU在一個內核上集成了多個譯碼器、ALU等單元。相比于具備普通流水線技術的CPU，具備超標量技術的CPU可以在同一個階段執行多條處在相同階段的指令。
   
   超標量流水線：
   

   指令調度與寄存器分配的關系

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

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

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

所以說兩者相互約束。可以知道，將指令調度問題和寄存器分配問題作為兩個約束條件進行聯合求解得到的解決方案是相對更優的，但由于無論是指令調度還是寄存器分配，都是很復雜的NP完全問題，綜合考慮下，編譯器一般會分別處理二者^[1]^。

在LLVM編譯器的設計中，寄存器分配之前和寄存器分配之后都會執行指令調度。

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