if-then-else、loop控制語句的後端實現

 

本文是通過程式碼而來，主要記錄了在SIMD指令集上，編譯器後端對控制語句（if-then-else、loop）的指令生成方法。

 

引言：

“A unique feature of most GPU』s is that they are designed to run many different instances of the same program in lock step in order to reduce the size of the scheduling hardware by sharing it between many different 「cores.」 When control flow diverges, meaning that when two different instances (fragments, vertices, etc.) branch in different directions, then the GPU will take both sides of the branch. For example, if both thread 1 and thread 2 are currently in block A, and thread 1 wants to branch to block B while thread 2 wants to branch to block C, then the GPU will first branch to block B with thread 1 enabled and thread 2 disabled, and then when execution reaches a predefined 「merge block,」 the GPU will jump back to block C while flipping the enabled threads and run until the merge block is reached, at which point the control flow has converged and both thread 1 and thread 2 can be enabled.“

 

 

進入到if-then-else語句塊，轉換為branch指令時，因為使用的是SIMD指令，所以各個channel的跳轉控制流程可能會出現分歧。

在此我們先假設condition等於true，執行if-then語句塊；condition等於false，執行else語句。

當各個channel的condition相同時，各個channel不會出現分歧，各個channel的跳轉地址（程式碼塊）也是相同的，這種情況下，當condition等於true時，所有channel執行if-then語句塊，反之，condition等於false，所以channel執行else語句。

當各個channel的condition條件不一樣，那麼各個channel就會出現分歧，if、else兩個語句塊都需要被按條件被執行一次。對於condition等於1的channel，需要執行if-then語句塊，而不能執行else語句；對於condition等於false的channel，要執行else語句，而不能執行if-then語句塊。

最後，進入到匯合點後，所有的channel又可以並行的執行相同的指令了。

 

如何處理上述的兩種情況呢？

首先這需要機器指令級別上的支援，不同的處理器有不同的實現。

來看看VC4提供的指令方案：

1.每個channel有獨立的標誌位，比如，N、Z、C

2.運算指令的執行結果能設置每個channel的標誌位

3.指令支援條件執行

4.branch指令支援跳轉條件，且支援各個channel標誌位間的邏輯運算

 

具體來看.

 

偽程式碼：

 

 

偽程式碼中condition表示if的條件「if(condition)」，而execute實時記錄了各個channel的執行條件。

 

當各個channel的condition相等時，這種情況相對簡單些，各個channel執行的流程是相同的，要麼執行if-then語句塊，那麼執行else語句。

當各個channels的condition值不相等時，「if-then」「else」兩個語句塊，均要被執行一次，但是，不是每個channel都要執行，只有在進入到語句塊中execute等於零的channel才能執行其中的指令，而非零值的channel不能執行語句塊中的指令（非零值是等於else語句塊的index號，指向執行完當前語句塊後，接下來要進入執行的語句塊）。具體來看，執行流程首先（PC指針）進入到「if」基本塊中，對於execute值等於0的channel會執行基本塊中的指令，非0的要跳過基本塊中的所有指令。在if-then語句塊執行後，執行過「if」語句的channel，就不能再執行else語句的指令，所以在if-then語句塊結束後需要對execute更新，在執行if-then語句塊時execute等於0的channel，需要把execute更新為after block index，即執行完else基本塊後的基本塊的index號，非0的channel的execute需要更新為0，表明在接下來的else基本塊中需要執行指令，所以在執行流程（PC指針）進入else基本塊中後，同樣的execute等於零的channel才會執行指令，非零不執行.

 

進入某個語句塊前，需要對execute進行測試，進入某個語句塊前execute保存了各個channel的將要執行的語句塊的地址。

對滿足if語句塊的channel的退出if語句塊時，需要將execute更新為下一個執行的語句塊地址，即@after_block。

 

回到偽程式碼：

 

當我們開始處理if-then-else語句時，我們先判斷執行條件，以取得下一句指令的入口，這時可能出現3種情況：

1.所有channel的condition等於0，則跳轉到else_block

2.所有channel的condition不等於0，則執行if_block，並且在if_block執行完畢後，要跳過else_block。

3.各個channel的condition不全為零，按標誌位，先執行if_block，再執行else_block。

 

1.將execute初始化為0，execute保存了各個channel的執行條件，在進入if-then語句塊後，對execute等於0的channel，要執行if-then語句塊中的指令，在進入else語句後，這些channel就不能再執行其中的else語句中的指令了。對不執行if-then語句塊的channel，對應的execute值等於@else_block。

2.將condition與0做比較，並且運算結果會設置各個channel的標誌位，如果condition等於0，會將對應channel的 Z標誌位設置為0，否則設置為1。

3.語句3中，mov會利用語句2中對Z標誌位的設置結果，更新各個channel的execute值。如果Z標誌位等於0，則將@else_block的地址跟新到execute中。

4.語句4，根據execute的值，更新Z標誌位

5.語句5根據以上4句的運算結果，如果全部channel的execute都不等於0，則跳轉到@else_block地址。

   具體的說，如果全部channel的condition等於0，那麼所有channel的execute都等於@else_block，所以語句4的執行後，所有channel的Z標誌位都不為零，語句5滿足跳轉條件，跳轉到@else_block；

   如果全部channel的condition都等於1，那麼所有channel的execute等於0，所以語句4的執行後，所有channel的Z標誌位都為零，語句5的跳轉條件不滿足，進入@then_block；

   如果各個channel的condition不全相等，那麼，對於condition等於0的channel的execute值就等於@else_block；而對於1的channel，execute的值等於0，所以語句4的執行後，所有channel的Z標誌位不全為零，語句5的跳轉條件不滿足，進入@then_block。

 

6.從語句6開始是if-then語句塊。一旦能進入if-then語句塊中，就需要依據各個channel的execute值，來判斷指令能否被執行。所以每條指令執行前都要用execute更新一次Z標誌位（暫不考慮優化），且每條指令都要加上條件執行碼，例如：

    Mov.sf    null, execute
    Add.zs    tmp4, tmp3, tmp2
 
    Mov.sf    null, execute
    Sub.zs    tmp5, tmp3, tmp1

7.在if-then語句塊執行完畢後，離開if-then語句塊前，需要判斷執行流程的下一個入口。如5中所述，能進入到if-then語句塊中有兩種情況，分別對應不同的出口。

1. 如果是全部channel的condition等於1，這種情況下我們接下來不需要執行else語句了。因為各個channel的execute均等於0，所以語句8執行後會把每個channel的Z標誌位置位，緊接著語句9，也就把每個channel的execute值都更新為@after_block，在語句10測試跳轉條件，與@after_block相減，結果為0，所以各個channel的Z標誌位被置位，語句11的跳轉條件是全部Z標誌位置位，此時條件滿足，即跳轉到after_block，也就結束了if-then-else語句的處理。

    

2. 如果不是全部channel的condition都等於1，接下來我們需要進入到else語句，執行非零的channel。語句8會把execute等於0的channel的Z標誌位置位，語句9把Z標誌位置位的channel的execute更新為@after_blcok，其餘保存不變，語句10做條件測試的結果，不能滿足語句11的跳轉條件。接下進入else語句，並且這時各個channel的execute的值等於@else_blcok或@after_block。

8.能進入到else語句，也有兩種情況，並且else語句中的指令也需要做if-then語句塊中相同的處理，依據execute更新Z標準位，每條執行要交條件執行碼。

   在執行else語句中的指令前，我們需要更新execute的值。只有在進入else語句前execute值等於@else_block的channel才能執行else語句中的指令。所以語句14先對execute做測試，與@else_block相減，對於execute等於@else_block的channel的N標誌位會被置位，語句15據此更新execute的值，Z標誌位被置位的channel的execute被更新為0。這樣就能滿足我們前提到的，只有當execute等於0的channel才會執行指令。

 

當else語句執行完畢後，我們就退出了if-then-else語句的處理流程。

 

 

在SIMD指令下的loop語句塊實現，與if-then-else語句塊的實現方法類似。同樣的，在loop中也會因為各個channel的情況不同，可能會產生控制流程分歧。當控制流存在分歧時，同樣要依據各個channel的控制條件決定是否執行對應的指令，處理完分歧後，每個channel再匯合到一起。

 

這裡考慮一種一般的情況，示例程式碼如下：

 

 

如果沒有遇到break、continue語句loop會一直循環下去。而break中斷並結束循環，continue中斷本次循環，繼續下一次循環（與C語言的類似）。

從上面的示例程式碼可以看出，loop中會產生分歧主要是源自於其中的if-then-else語句。當各個channel在執行if-then-else語句出現分歧後，在執行loop中語句就channel的執行情況就不一樣了。

例如，當兩個channel出現執行if語句出現分歧，A滿足if語句塊執行條件，B不滿足，在if語句塊中有break語句，if語句按前文所述的if-then-else語句處理分歧，A執行，B不執行，執行完畢if語句塊後，A不再執行loop中的指令，B繼續執行loop中的語句，直到滿足推出loop的條件，最終與A匯合。

 

具體的實現與if-then-else語句類似，使用一個變數execute來記錄執行條件，當channel的execute等於0時表示，該channel需要執行當前指令；對於不需要執行當前指令的channel，execute的值等於下一個需要執行的語句塊的入口地址。

 

偽程式碼：

 

進入loop語句，首先對各個channel的execute進行測試，等於0的channel可以執行loop語句塊中的指令。

同樣loop語句塊中的指令依然需要通過在每條語句執行前添加「mov.sf null, execute」來設置Z標誌位（贊不考慮優化），每條指令添加條件執行碼。

語句1，對execute初始化。

語句3，對execute測試，在進入loop前如果execute等於@loop_block，表示該channel會遭loop中執行，Z標誌位被置位，然後語句4將對應channel的execute更新為0，反之，保存execute原值不變（初次進入時execute保持為0值）。

這樣loop中的指令語句就能根據execute的值，判斷是否被執行。

 

當遇到if語句時，if語句的處理與前文所述的不變，只是在進入if-then-else語句塊前不再將各個channel的execute初始化為0。

 

當if語句中存在break指令時，並能執行break指令，對於滿足if語句塊執行條件的channel，將在break執行完畢後，結束loop語句塊的執行，這些channel的下一個執行語句塊是@break_loop（即退出loop語句塊的指令語句地址）。而不滿足if語句塊執行條件的channel將繼續執行loop中的指令語句。

語句6、7首先完成對break的channel的execute進行更新，這些channel下一個要執行的語句塊地址為@break_loop，這樣在接下來的循環體中，如果沒有發生共同跳轉，那麼剩下的loop語句塊中的條件執行指令，均不能滿足執行條件。

語句8、9是為應對當所有channel均執行了break指令的情況，這時所有channel同時結束loop語句塊的執行。具體來看，首先對更新後的execute進行測試，語句8與jump_block（break_block）相減，其結果會影響Z標準位，如果所有channel均置位了Z標誌位，語句9的跳轉條件滿足，所有channel將共同跳轉到break_block（break_block），也就跳出了loop語句塊。

break指令是loop的唯一出口，所以各個channel一定會從某個break語句結束循環（死循環除外）。

 

當if語句中存在continue指令時，並且continue指令能被執行，對於滿足if語句塊執行條件的channel，在執行完continue指令後，中斷本次循環的執行，重新跳轉到loop的開始處@loop_block，繼續執行下一次的循環。

與break的情況類似，同樣可以通過偽程式碼的語句6-8來處理continue指令，語句6置位測試條件，語句7根據測試結果設置新的跳轉地址 @loop_block，語句8、9同樣會判斷是否所有channel的執行情況相同，相同時時直接開始下一次循環。

當各個channel的情況不一樣時，還會接著loop語句塊往下執行，同樣的執行了continue的channel的execute已被更新，且不為0，loop語句塊中剩餘的程式碼也不會被這些channel執行了。

在完成一次loop語句塊中程式碼的執行後，後開始新的一次循環前（如1中所述），均要做條件測試。

 

執行完一次loop後，語句11根據execute當前的值對Z標誌位進行更新，語句12是條件執行指令，並且滿足執行條件的channel會更新Z標誌位，而不滿足語句12執行條件的channel的Z標誌位保存會不變（處於Z標誌位置位狀態）。

滿足Z標誌位未被置位的channel，會將execute與@loop_block相減，並更新Z標誌位，對於執行過continue的channel，Z標誌位會被置位，語句13，branch的跳轉條件是任意channel為Z標誌位被置位，就會回到loop的開頭處@loop_block，繼而進行下一循環.

這裡能滿足語句13跳轉條件的channel，來至兩種情況，一種是在循環體中未執行過break和continue指令的channel，execute一直保持為0，在語句11中置位Z標誌位，且語句12不會清除Z標誌位；另一種是執行了continue指令的channel。

所以在執行下一次循環前，各個channel的execute的值可能是0或@loop_block，且一定有某個channel的值為其中之一。

重新開始循環後，會先按上述1中的方式更新execute，然後就是再一次的循環體程式碼執行了。

 

總結一下：

1.控制語句塊中，執行每條程式碼前必須做條件測試（不考慮優化），每條程式碼必須按條件執行。

2.進入控制語句塊前需做語句塊執行條件測試

3.退出控制語句前，需要更新各個channel的跳轉地址

 

參考資料：

mesa：src/gallium/drivers/vc4/vc4_program.c