基本塊
 | 此條目需要補充更多來源。 (2020年7月) |
在電腦編譯器架構中，基本塊（basic block）是一段線性的程式碼，只能從這段程式碼開始處進入這段程式，沒有其他程式碼會跳躍進入這段程式，只能從這段程式碼最後一行離開這段程式，中間沒有其他程式碼會跳躍離開這段程式[1][2]。這種程式的限制使得基本塊非常好分析[3]。編譯器處理程式時，會在分析程序中，將程式分解為所有基本塊的組合。在控制流圖中，基本塊是控制流圖中的節點。
以下是一段QuickBASIC程式，程式中的前二行（DO之前的程式碼）即為基本塊。
INPUT "What is your name: ", UserName$
PRINT "Hello "; UserName$
DO
INPUT "How many stars do you want: ", NumStars
Stars$ = STRING$(NumStars, "*")
PRINT Stars$
DO
INPUT "Do you want more stars? ", Answer$
LOOP UNTIL Answer$ <> ""
Answer$ = LEFT$(Answer$, 1)
LOOP WHILE UCASE$(Answer$) = "Y"
PRINT "Goodbye "; UserName$
定義
[編輯]基本塊的程式有以下特點：
因為上述特點，基本塊中的程式，只要執行了第一行，後面的程式碼就會依序執行，每一行程式都會執行一次[4][5]。
以下是更型式化的定義一串的指令屬於基本塊的方式：
- 程式碼中的每一個指令都支配（dominate）位置在較後面的指令，也就是位置在較後面的指令一定會比較晚執行。
- 這串程式中的連續兩個指令之間，不會再執行其他的指令。
此定義會比一開始較直觀定義的範圍更廣。例如，此定義可以允許程式碼中間有無條件的跳躍，只要跳躍目的的程式碼不是其他跳躍的目的即可。使用此定義，在產生基本塊的演算法中，會比較容易產生基本塊。
在執行某一基本塊最後一行之後，可能會執行的基本塊稱為「後繼」（Successor），而執行此基本塊之前，可能會執行的基本塊稱為「前驅」（Predecessor）。會跳到基本塊啟始程式的程式碼可能不止一處。
產生基本塊的演算法
[編輯]若要由一串的指令中產生基本塊，其演算法如下：程式先分析指令，找到「基本塊的邊界」，基本塊的邊界是指可能會開始一個基本塊（因為是其他流程控制指令的跳躍目標）或是結束一個基本塊的指令（因為有流程控制指令，可能會跳躍到其他的基本塊）。因此，指令列表會因為這些「基本塊的邊界」而切割成幾段，這幾段就是基本塊。
上述方式不一定能找到（在型式化定義下）最大的基本塊，不過多半而言都已足夠了（最大的基本塊是指基本塊無法在不違反規則的情形下，和鄰近基本塊合併，形成更大的基本塊[6]）。
輸入：一串指令（多半是三位址碼）[7]。 輸出：一串的基本塊，其中每一個三位址碼都恰好在一個基本塊內。
步驟1：找到程式碼中的啟始指令（leader）。滿足以下任何一項的就是啟始指令：
- 第一個指令。
- goto、無條件跳躍或有條件跳躍目的的指令。
- 緊接在goto、無條件跳躍或有條件跳躍後面的指令。
步驟2：從啟始指令開始，一直往下檢查，直到找到下一個基本塊的啟始指令為止，從啟始指令開始，到下一個基本塊的啟始指令之前的程式碼就是對應啟始指令的基本塊。
每一個基本塊都會有一個啟始指令。
以下的程式碼會結束一個基本塊：
- 無條件或是有條件的分支指令，不論是直接的或是間接的都是。
- 函式的返回指令。
- 可能會丟出異常的指令。
- 函式呼叫若無法返回，也可能是基本塊的結束，例如會產生異常的函式，或是像C語言中
longjmp指令及exit指令。 - return指令本身。
以下的程式碼會開始一個基本塊：
- 程序或是函式的進入點。
- 跳躍或是分支指令的目標。
- 一些條件分支指令後的「貫穿」(fall-through）程式碼（某一條件成立後，除了執行自身程式嗎外，還會執行對應其他條件的程式碼）
- 在丟出異常指令之後的程式碼
- 異常處理程式。
因為流程控制無法越過基本塊的結尾，在找到基本塊之後，有些基本塊邊界可能要調整。特別是「貫穿」(fall-through）的條件分支需要改為傳統二路的條件分支，丟出異常的函數後面需要加上無條件的跳躍。這些調整可能需要在其他基本塊的開始處加上標記，表示是無條件跳躍的目標。
相關條目
[編輯].gif){kind=small}
參考資料
[編輯]- ^ Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.
- ^ Daniel), Cooper, Keith D. (Keith. Engineering a compiler. Torczon, Linda. 2nd. Amsterdam: Elsevier/Morgan Kaufmann. 2012: 231. ISBN 978-0120884780. OCLC 714113472.
- ^ "Control Flow Analysis" by Frances E. Allen. [2020-07-07]. （原始內容存檔於2020-05-26）.
- ^ Yousefi, Javad. Masking wrong-successor Control Flow Errors employing data redundancy. IEEE: 201–205. 2015. doi:10.1109/ICCKE.2015.7365827.
- ^ "Global Common Subexpression Elimination" by John Cocke
- ^ Modern Compiler Design by Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen p320
- ^ Compiler Principles, Techniques and Tools, Aho Sethi Ullman
外部連結
[編輯]- Basic Blocks - GNU Compiler Collection（頁面存檔備份，存於網際網路檔案館）
- Extended Basic Block - Wiktionary（頁面存檔備份，存於網際網路檔案館）