指令調度的問題與約束

指令調度受到多方面的約束，如數據依賴約束、功能部件約束、寄存器約束等^[3]^，在這些約束下，尋找到最優解，降低指令流水間的stall，就是指令調度的終極目標。

指令流水間的stall主要由數據型冒險、結構性冒險、控制型冒險導致。

• 數據型冒險：當前指令的執行依賴與上一條指令執行的結果。數據型冒險共有三種：寫后讀（RAW）、讀后寫（WAR）、寫后寫（WAW）。數據冒險可能產生數據流依賴。
• 結構型冒險：多條指令同時訪問一個硬件單元的時候，由于缺少相應的資源，導致結構型冒險。
• 控制型冒險：存在分支跳轉，無法預測下一條要執行的指令，導致其產生的控制型冒險。

編譯器解決上述冒險的方法就是通過插入 NOP 指令，增加流水間的stall來化解冒險。

下面簡單介紹一下三種數據型冒險（即數據依賴）：

1. 寫后讀（RAW）：一條指令讀取前一條指令的寫入結果。寫后讀是最常見的一種數據依賴類型，這種依賴被稱為真數據依賴（true dependence）。

   x = 1;
   y = x;
   

2. 讀后寫（WAR）：一條指令寫入數據到前一條指令的操作數。這種依賴被稱為反依賴或反相關（anti dependence）。

   y = x;
   x = 1;
   

3. 寫后寫（WAW）：兩條指令寫入同一個目標。這種依賴被稱為輸出依賴（output dependence）。

   x = 1;
   x = 2;
   

指令調度算法之表調度（List Scheduling）

表調度是一種貪心+啟發式方法，用以調度基本塊中的各個指令操作，是基本塊中指令調度的最常見方法。基于基本塊的指令調度不需要考慮程序的控制流，主要考慮數據依賴、硬件資源等信息。

表調度的基本思想：維護一個用來存儲已經準備執行的指令的ready列表和一個正在執行指令的active列表，ready列表的構建主要基于數據依賴約束和硬件資源信息；根據調度算法以周期為單位來執行具體的指令調度，包括從列表中選擇及調度指令，更新列表信息。

基本的表調度算法大致分為以下三步：

1. 根據指令間依賴，建立依賴關系圖。
2. 根據當前指令節點到根節點的長度以及指令的latency，計算每個指令的優先級。
3. 不斷選擇一個指令，并調度它，
   • 使用兩個隊列維護ready的指令和正在執行的active的指令；
   • 在每個周期：選擇一個滿足條件的ready的指令并調度它，更新ready隊列；檢查active的指令是否執行完畢，更新active列表。

指令調度案例^[4]^

本案例選自卡內基梅隆大學（Carnegie Mellon University）的Compiler Design課程。

假設當前CPU有兩個計算單元（即每個周期可以執行兩條指令）；加法指令的latency為 2 cycles，其他指令為 1 cycle。

1. 根據數據依賴關系構建出依賴關系圖。
   
2. 計算指令節點優先級
   優先級計算公式如下：
   其中，表示當前指令節點，表示的子節點，表示 "true dependency" ，表示 "anti-dependency" 。
   
   其中 I10 為葉節點，優先級為其latency，故結果為1；I4 為非葉節點，優先級為當前節點latency（I4 為加法指令，latency為2）+ 子節點的優先級，故結果為3。本例中無反依賴（anti-dependency）情形。
3. 執行調度
   
   在實際執行調度時，對于同等優先級的指令，由于具體調度方案的不同，會出現不同的情況，例如本例中出現的場景，可以通過添加其他度量標準進一步優化優先級計算方案。盡管表調度方法不能保證得到最優調度結果，但它是接近最優解的。

本文只是簡單介紹了最基本的表調度方法，在實際應用中，存在各種基于該方法的改進方案。關于LLVM編譯器中的表調度算法，可以先自行閱讀其源碼，更多相關介紹，敬請期待。

結語

本文簡單介紹了指令調度的基本概念，指令調度的原因與影響以及基本的指令調度算法。

指令調度作為NP完全問題目前依舊尚未有一個完美的解決方案，對指令調度算法的探索與優化尚有很大的發展空間。

LLVM之父Chris Lattner認為“編譯器的黃金時代”已經降臨^[5]^。隨著計算機架構的復興，未來的N年里將是每一位編譯器工程師大顯身手的時代。

參考

1. Keith D. Cooper, Linda Torczon. Engineering a Compiler (Second Edition).
2. https://zhuanlan.zhihu.com/p/360364235
3. Andrew W.Apple, Maia Ginsburg. Modern Compiler Implementation in C.
4. https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L18-Instruction-Scheduling-pre-class.pdf
5. https://zhuanlan.zhihu.com/p/502730940