基本块

在电脑编译器架构中，基本块（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）。满足以下任何一项的就是启始指令：

1. 第一个指令。
2. goto、无条件跳跃或有条件跳跃目的的指令。
3. 紧接在goto、无条件跳跃或有条件跳跃后面的指令。

步骤2：从启始指令开始，一直往下检查，直到找到下一个基本块的启始指令为止，从启始指令开始，到下一个基本块的启始指令之前的程式码就是对应启始指令的基本块。

每一个基本块都会有一个启始指令。

以下的程式码会结束一个基本块：

• 无条件或是有条件的分支指令，不论是直接的或是间接的都是。
• 函式的返回指令（英语：return statement）。
• 可能会丢出异常的指令。
• 函式呼叫若无法返回，也可能是基本块的结束，例如会产生异常的函式，或是像C语言中longjmp 指令及exit 指令。
• return指令本身。

以下的程式码会开始一个基本块：

• 程序或是函式的进入点。
• 跳跃或是分支指令的目标。
• 一些条件分支指令后的“贯穿”(fall-through）程式码（某一条件成立后，除了执行自身程式吗外，还会执行对应其他条件的程式码）
• 在丢出异常指令之后的程式码
• 异常处理程式。

因为流程控制无法越过基本块的结尾，在找到基本块之后，有些基本块边界可能要调整。特别是“贯穿”(fall-through）的条件分支需要改为传统二路的条件分支，丢出异常的函数后面需要加上无条件的跳跃。这些调整可能需要在其他基本块的开始处加上标记，表示是无条件跳跃的目标。

相关条目

• 计算机程序设计主题

• 块 (编程)
• 控制流图
• 决策到决策路径
• Extended basic block（英语：Extended basic block）
• 线性程式码顺序及跳转

参考资料

1. Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.
2. Daniel), Cooper, Keith D. (Keith. Engineering a compiler. Torczon, Linda. 2nd. Amsterdam: Elsevier/Morgan Kaufmann. 2012: 231. ISBN 978-0120884780. OCLC 714113472.
3. "Control Flow Analysis" by Frances E. Allen. [2020-07-07]. （原始内容存档于2020-05-26）.
4. Yousefi, Javad. Masking wrong-successor Control Flow Errors employing data redundancy. IEEE: 201–205. 2015. doi:10.1109/ICCKE.2015.7365827.
5. "Global Common Subexpression Elimination" by John Cocke
6. Modern Compiler Design by Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen p320
7. Compiler Principles, Techniques and Tools, Aho Sethi Ullman

外部链接

• Basic Blocks - GNU Compiler Collection（页面存档备份，存于互联网档案馆）
• Extended Basic Block - Wiktionary（页面存档备份，存于互联网档案馆）