1. SMS介紹
? SMS(Swing Modulo Scheduling, 搖擺模調(diào)度)是一個基于循環(huán)的與架構(gòu)無關(guān)的SWP(software pipelining)指令調(diào)度框架, 其目的是通過將當(dāng)前迭代的指令與上一迭代同時發(fā)射來提升并行度. 考慮以下偽代碼:

1 BB1: 2 A0 = A1 (1) 3 A2 = A1 (2) 4 A3 = A2 (3) 5 b BB1 if cond

? 不考慮跳轉(zhuǎn)指令, 該循環(huán)需要獨立發(fā)射三條指令(指令之間相互依賴). 但如果將其改變?yōu)橐韵路绞?

1 A0 = A1 2 BB1: 3 A2 = A1 4 A3 = A2; A0 = A1; 5 b BB1 if cond 6 A2 = A1 7 A3 = A2

? 指令1與指令3間無直接依賴, 因此可以將本次迭代的指令3與下次迭代的指令1放在同一時刻發(fā)射, 提高并行度.

? 關(guān)于SMS原理的更多了解, 參見include/llvm/CodeGen/MachinePipeliner.h中涉及的三篇論文.
? 1. "Swing Modulo Scheduling: A Lifetime-Sensitive Approach"
? 2."Lifetime-Sensitive Modulo Scheduling in a Production Environment"
? 3. "An Implementation of Swing Modulo Scheduling With Extensions for Superblocks"

2. SMS實現(xiàn)分析
? SMS算法由三部分組成. 首先, 計算出最小初始間隔(MII, minimal initiation interval). 第二步建立dependence graph, 計算每條指令的相關(guān)信息(ASAP ALAP MOV Height Depth ...). 最后使用論文中提及的方式為節(jié)點排序.

3. 常見概念
? MII(minimal initiation interval)指完成循環(huán)所需的最小間隔, 它等于ResMII與RecMII兩者的較大值, MII是理想的調(diào)度結(jié)果. ResMII(Resource MII)是根據(jù)一次循環(huán)所需的功能單元(FU, function unit)去除以機器所有功能單元的結(jié)果, 即如果一個循環(huán)包含4條指令而芯片只有兩個運算單元則(不考慮指令間依賴)最少需要2 cycle才能完成一次循環(huán). 更進一步, 如果循環(huán)中包含多類FU的使用(且每類FU之間相互無法替換), 則ResMII是分別對每一類FU計算ResMII后的最大值. RecMII(Recurrence MII)是循環(huán)中環(huán)路完成一次迭代所需的最小間隔, 如果循環(huán)存在多條數(shù)據(jù)鏈路則分別計算后取其最大值.
? Prolog / Epilog分別指實現(xiàn)SWP后被提前到循環(huán)之前/放到循環(huán)之后執(zhí)行的代碼塊. Kernel指實現(xiàn)SWP后的循環(huán)代碼塊.
? Dependence Graph指指令間存在的依賴關(guān)系, 具體分為對寄存器的依賴與對內(nèi)存的依賴. 對寄存器的依賴又分三種: 先寫后讀(RAW, read after write, 數(shù)據(jù)依賴, 又稱真依賴)在LLVM中用SDep::Data表示, 先讀后寫(WAR, write after read, 反依賴)在LLVM中用SDep::Anti表示, 先寫后寫(WAW, write after write, 輸出依賴)在LLVM中用SDep::Output表示. 對同一地址的讀寫也會產(chǎn)生依賴, 在LLVM中統(tǒng)一使用SDep::Order表示(不論是laod-store還是store-load還是store-store), 另外特殊指令帶有side-effect屬性時也使用順序依賴表示. 順序依賴又分為Barrier, AliasMem, Artificial, Weak等多個子類型, 其具體定義見include/llvm/CodeGen/ScheduleDAG.h.

4. 代碼分析
? MachinePipeliner類的入口為MachinePipeliner::swingModuloScheduler(), 函數(shù)首先檢查循環(huán)是否僅包含一個BB(即沒有change of flow). SwingSchedulerDAG是ScheduleDAGInstrs的子類, 父類的startBlock()/enterRegion()/exitRegion()/finishBlock()都是virtual的, 用于特定調(diào)度器的initial/clean up. SwingSchedulerDAG::schedule()(defined in lib/CodeGen/MachinePipeliner.cpp)實現(xiàn)swing modulo調(diào)度算法.
? 4.1. 建立dependence graph
? 為建立依賴圖首先需要獲取alias分析結(jié)果(否則無法分析order dependence), 再調(diào)用公共框架接口ScheduleDAGInstrs::buildSchedGraph()(defined in lib/CodeGen/ScheduleDAGInstrs.cpp)建立依賴圖(關(guān)于ScheduleDAGInstrs類后文分析). 注意公共框架返回的依賴圖是基于順序執(zhí)行的代碼塊的, 由于SWP的特殊性我們還要加上跨迭代的依賴(loop carried dependence, 即本次迭代的指令與下次迭代間的依賴).
? 由于在SSA模式下跨迭代的寄存器使用必然存在phi node, 因此我們只需為phi node添加依賴. SwingSchedulerDAG::updatePhiDependences()(defined in lib/CodeGen/MachinePipeliner.cpp)會為phi node添加data dep如果存在指令引用該phi, 并為該指令添加anti dep(在本次迭代的引用指令與下次迭代的phi指令間存在先讀后寫的關(guān)系).
? 對于跨迭代的內(nèi)存訪問間依賴交給SwingSchedulerDAG::addLoopCarriedDependences()(defined in lib/CodeGen/MachinePipeliner.cpp)處理. 該接口會遍歷循環(huán)內(nèi)所有l(wèi)oad/store指令, 對每條load指令如果存在由alias關(guān)系的store則檢查是否能通過load指令reach到store指令(一般是順序load后store的情況, 不需要額外dep), 如果不能reach則為該sotre添加barrier dep. 再調(diào)用ScheduleDAGTopologicalSort::InitDAGTopologicalSorting()(defined in lib/CodeGen/ScheduleDAG.cpp)為節(jié)點排序方便之后處理, 至此依賴圖基本建立完畢.
? 當(dāng)前框架下還有兩個針對依賴圖的優(yōu)化, SwingSchedulerDAG::changeDependences()會嘗試轉(zhuǎn)換指令使用前次迭代的值來降低RecMII(主要針對pre-inc/post-inc的load/store, 縮短dep chain). SwingSchedulerDAG::postprocessDAG()用來調(diào)用一些基于特定目的實現(xiàn)的Mutation的hook, 當(dāng)前框架實現(xiàn)一個名為CopyToPhiMutation, 這個沒看懂干嘛的, 為什么延后COPY的調(diào)度可以獲得更好的性能?

? 為更具象的描述代碼, 這里以一個testcase為例:

1 [23:34:53] hansy@hansy:~$ cat test.c 2 void test(int * __restrict in, int * __restrict out, int cnt) 3 { 4 int i; 5 #pragma nounroll 6 for (i = 0; i < cnt; i++) { 7 *in = *out; 8 in++; 9 out++; 10 } 11 } 12 [23:34:59] hansy@hansy:~$ ~/llvm/llvm_build/bin/clang test.c -w -O2 -S -mllvm -debug-only=pipeliner --target=hexagon -mllvm -print-after-all 2>1.ll 13 [23:35:03] hansy@hansy:~$

? 其中__restrict是c99引入的關(guān)鍵字, 在這里用以減少內(nèi)存訪問依賴, #pragma nounroll是llvm的pragma, 保證循環(huán)不被展開優(yōu)化, 用在這里減少循環(huán)內(nèi)指令數(shù)(變相減少打印), 也可以去掉以上語法糖來觀察SMS的變化. 篇幅有限, 這里截取部分打印.

? loop block before SMS

448B bb.4.for.body (address-taken):; predecessors: %bb.4, %bb.6successors: %bb.5(0x04000000), %bb.4(0x7c000000); %bb.5(3.12%), %bb.4(96.88%) 464B %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4 480B %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4 496B %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2) 512B %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2) 528B ENDLOOP0 %bb.4, implicit-def $pc, implicit-def $lc0, implicit $sa0, implicit $lc0 544B J2_jump %bb.5, implicit-def dead $pc

? dependence graph

SU(0): %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4# preds left : 0# succs left : 2# rdefs left : 0Latency : 0Depth : 0Height : 1Successors:SU(3): Data Latency=0 Reg=%2SU(3): Anti Latency=1 SU(1): %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4# preds left : 0# succs left : 2# rdefs left : 0Latency : 0Depth : 0Height : 1Successors:SU(2): Data Latency=0 Reg=%3SU(2): Anti Latency=1 SU(2): %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2)# preds left : 2# succs left : 1# rdefs left : 0Latency : 1Depth : 1Height : 0Predecessors:SU(1): Data Latency=0 Reg=%3SU(1): Anti Latency=1Successors:SU(3): Data Latency=0 Reg=%15 SU(3): %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2)# preds left : 3# succs left : 0# rdefs left : 0Latency : 1Depth : 1Height : 0Predecessors:SU(2): Data Latency=0 Reg=%15SU(0): Data Latency=0 Reg=%2SU(0): Anti Latency=1 ExitSU: ENDLOOP0 %bb.4, implicit-def $pc, implicit-def $lc0, implicit $sa0, implicit $lc0# preds left : 0# succs left : 0# rdefs left : 0Latency : 0Depth : 0Height : 0

? NodeFunction & NodeSets

Node 0:ASAP = 0ALAP = 0MOV = 0D = 0H = 1ZLD = 0ZLH = 1Node 1:ASAP = 0ALAP = 0MOV = 0D = 0H = 1ZLD = 0ZLH = 2Node 2:ASAP = 0ALAP = 0MOV = 0D = 1H = 0ZLD = 1ZLH = 1Node 3:ASAP = 0ALAP = 0MOV = 0D = 1H = 0ZLD = 2ZLH = 0Rec NodeSet Num nodes 2 rec 1 mov 0 depth 1 col 0SU(0) %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4SU(3) %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2)Rec NodeSet Num nodes 2 rec 1 mov 0 depth 1 col 0SU(1) %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4SU(2) %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2)NodeSet Num nodes 2 rec 1 mov 0 depth 1 col 0SU(0) %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4SU(3) %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2)NodeSet Num nodes 2 rec 1 mov 0 depth 1 col 0SU(1) %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4SU(2) %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2)NodeSet size 2Bottom up (default) 3 0Switching order to top down Done with Nodeset NodeSet size 2Bottom up (preds) 2 1Switching order to top down Done with Nodeset

? Schedule

Try to schedule with 1 Inst (3) %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2)es: -2147483648 ls: 2147483647 me: 2147483647 ms: -2147483648insert at cycle 0 %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2) Inst (0) %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4es: 0 ls: 0 me: 2147483647 ms: -2147483648insert at cycle 0 %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4 Inst (2) %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2)es: -2147483648 ls: 0 me: 2147483647 ms: -2147483648insert at cycle 0 %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2) Inst (1) %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4es: 0 ls: 0 me: 2147483647 ms: -2147483648insert at cycle 0 %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4 Schedule Found? 1 (II=2) cycle 0 (0) (0) %2:intregs = PHI %7:intregs, %bb.6, %5:intregs, %bb.4cycle 0 (0) (1) %3:intregs = PHI %8:intregs, %bb.6, %6:intregs, %bb.4cycle 0 (0) (2) %15:intregs, %6:intregs = L2_loadri_pi %3:intregs(tied-def 1), 4 :: (load 4 from %ir.out.addr.07, !tbaa !2)cycle 0 (0) (3) %5:intregs = S2_storeri_pi %2:intregs(tied-def 0), 4, %15:intregs :: (store 4 into %ir.in.addr.08, !tbaa !2)

? 先來看下dependence graph, 循環(huán)內(nèi)總共四條Machine IR, 其中兩條為PHI, 另外兩條分別為load與store. 先看第一條PHI, 因為它的def-reg %2被store指令使用(先寫后讀)所以存在真依賴, 同理它的use-reg %5被store指令定義所以又存在反依賴. 另一條PHI與load指令間依賴關(guān)系類似. 最后load定義的%15被store使用, 所以兩者間還有一個真依賴. 注意雖然PHI與store之間都存在反依賴, 但其含義不同: PHI指令的反依賴表示PHI不能調(diào)度到本迭代的store后, store的反依賴表示不能調(diào)度到下次迭代的PHI之后.

? 4.2. 計算ResMII/RecMII
? ResMII比較容易計算(最簡單的辦法是指令數(shù)除以功能單元數(shù), 當(dāng)然代碼中使用更復(fù)雜的DFA做更精確的評估), SwingSchedulerDAG::calculateResMII()基于DFA實現(xiàn)了ResMII的計算.
? RecMII的計算則復(fù)雜許多, 首先我們要找到所有的關(guān)鍵路徑(critical path). SwingSchedulerDAG::findCircuits()會首先查找循環(huán)中所有的環(huán)路并將其記錄到NodeSets中. 思路是首先交換反依賴(否則跨迭代環(huán)路不結(jié)束), 然后構(gòu)建一個依賴矩陣, 依賴矩陣的作用是記錄所有backedge, 判斷回邊的依據(jù): 到phi的反依賴(必然是回邊), 順序的輸出依賴鏈上第一個與最后一個(最后一個不能調(diào)度到下個迭代的第一個之前), 以及讀寫之間的順序依賴(為什么寫寫之間的順序依賴不算回邊? 我的猜測是如果循環(huán)中只有寫寫那么相對順序就不重要了, 只要保證最后一次寫正確即可?). 最后通過索引改矩陣查找從每個節(jié)點出發(fā)回到該節(jié)點為止的一條鏈路.
? 可以看到例子中一共找到兩條環(huán)路, 第一條phi到store指令的基址, store指令基址再到phi, 第二條類似phi到load指令再到phi. 找到所有環(huán)路后即可計算RecMII, 對每條環(huán)路計算所需的latency總和取最大值即可.

? 4.3. 計算NodeFunction與NodeOrder
? 為了方便之后的調(diào)度還需要計算節(jié)點的一些特殊屬性, SwingSchedulerDAG::computeNodeFunctions()代碼注釋已經(jīng)很好的說明這些屬性的作用. 如字面意思ASAP指該節(jié)點最早調(diào)度時機, ALAP值該節(jié)點最晚調(diào)度時機, MOV指該節(jié)點可調(diào)度空間(等于ALAP - ASAP), D指節(jié)點深度, H指節(jié)點高度. 注意由于有zero latency指令的存在(一般是各類phi copy reg_sequence等偽指令), ASAP/ALAP與D/H存在區(qū)別.
? 計算NodeOrder(TODO).

? 4.4. 調(diào)度
? SwingSchedulerDAG::schedulePipeline()按NodeOrder順序排序. 節(jié)點所插入的cycle是由NodeFunction與已排序的節(jié)點間的依賴決定的. SMSchedule::computeStart()用來計算當(dāng)前節(jié)點最早與最晚插入時機, 如果計算的earlystart > latestart則調(diào)度失敗, 一般情況是NodeOrder順序非最優(yōu)順序. 否則調(diào)用SMSchedule::insert()嘗試插入節(jié)點(注意偽指令一般視作zerocost指令無需排序), 由于NodeOrder過程中只考慮了順序的依賴, 因此這里還要考慮跨迭代的依賴(即不光考慮當(dāng)前cycle是否能插入該節(jié)點, 還要考慮(cycle + II * stage)中的節(jié)點是否與該節(jié)點沖突, 否則最后無法將later stage中指令折疊到當(dāng)前cycle). 所有節(jié)點排序完成后就得到順序依賴的指令調(diào)度, 此時調(diào)用SMSchedule::finalizeSchedule()將later stage指令往前折疊. 該接口分為三步, 第一將later stage指令拷貝到first stage, 第二步建立每個stage的寄存器映射, 最后為每個cycle內(nèi)的指令重新排序(包括zerocost指令). 第三步通過SMSchedule::orderDependence()實現(xiàn).

? 4.5. 生成pipelined loop
? finalizeSchedule()產(chǎn)生了并行的循環(huán)代碼, 但這還不是最終的kernel, 期間還需要完成三件事: 重新計算寄存器(對應(yīng)不同迭代), 重新生成phi節(jié)點, 生成prolog與epilog. 這些任務(wù)由SwingSchedulerDAG::generatePipelinedLoop()完成. 主要接口updateInstruction()根據(jù)VRMap與stage為寄存器重命名, generateExistingPhis()替換之前的phi節(jié)點, generatePhis生成新的phi節(jié)點. 這塊是詬病最多的代碼, 像reduceLoopCount()這些為Hexagon實現(xiàn)的hack, 最近社區(qū)還有討論重構(gòu)這塊代碼(http://lists.llvm.org/pipermail/llvm-dev/2019-July/134002.html).

5. 優(yōu)化&問題定位
? SMS是比較復(fù)雜的后端優(yōu)化模塊, 問題定位主要抓以上幾個流程點: 首先看依賴圖是否有問題, MII的計算是否正確, NodeFunction與NodeOrder計算, 排序結(jié)果是否有問題, prolog/epilog是否有誤. 每個流程的問題不能影響下一流程. e.g. SMS流程后出現(xiàn)use before def問題, 如果覺得排序有誤就不用看寄存器映射是否有問題, 先分析排序是否正確, 因為finalizeSchedule()后指令就不能重排序, 而VRMap是依據(jù)當(dāng)前指令排序生成的, 排序不正確后面修改phi也不能解決問題.

轉(zhuǎn)載于:https://www.cnblogs.com/Five100Miles/p/11223493.html

總結(jié)

以上是生活随笔為你收集整理的LLVM笔记(5) - SMS的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。