Loading AI tools
来自维基百科,自由的百科全书
在电脑编译器架构中,基本块(basic block)是一段线性的程式码,只能从这段程式码开始处进入这段程式,没有其他程式码会跳跃进入这段程式,只能从这段程式码最后一行离开这段程式,中间没有其他程式码会跳跃离开这段程式[1][2]。这种程式的限制使得基本块非常好分析[3]。编译器处理程式时,会在分析程序中,将程式分解为所有基本块的组合。在控制流图中,基本块是控制流图中的节点。
此条目需要补充更多来源。 (2020年7月) |
以下是一段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]。
以下是更型式化的定义一串的指令属于基本块的方式:
此定义会比一开始较直观定义的范围更广。例如,此定义可以允许程式码中间有无条件的跳跃,只要跳跃目的的程式码不是其他跳跃的目的即可。使用此定义,在产生基本块的演算法中,会比较容易产生基本块。
在执行某一基本块最后一行之后,可能会执行的基本块称为“后继”(Successor),而执行此基本块之前,可能会执行的基本块称为“前驱”(Predecessor)。会跳到基本块启始程式的程式码可能不止一处。
若要由一串的指令中产生基本块,其演算法如下:程式先分析指令,找到“基本块的边界”,基本块的边界是指可能会开始一个基本块(因为是其他流程控制指令的跳跃目标)或是结束一个基本块的指令(因为有流程控制指令,可能会跳跃到其他的基本块)。因此,指令列表会因为这些“基本块的边界”而切割成几段,这几段就是基本块。
上述方式不一定能找到(在型式化定义下)最大的基本块,不过多半而言都已足够了(最大的基本块是指基本块无法在不违反规则的情形下,和邻近基本块合并,形成更大的基本块[6])。
输入:一串指令(多半是三位址码)[7]。 输出:一串的基本块,其中每一个三位址码都恰好在一个基本块内。
步骤1:找到程式码中的启始指令(leader)。满足以下任何一项的就是启始指令:
步骤2:从启始指令开始,一直往下检查,直到找到下一个基本块的启始指令为止,从启始指令开始,到下一个基本块的启始指令之前的程式码就是对应启始指令的基本块。
每一个基本块都会有一个启始指令。
以下的程式码会结束一个基本块:
longjmp
指令及exit
指令。以下的程式码会开始一个基本块:
因为流程控制无法越过基本块的结尾,在找到基本块之后,有些基本块边界可能要调整。特别是“贯穿”(fall-through)的条件分支需要改为传统二路的条件分支,丢出异常的函数后面需要加上无条件的跳跃。这些调整可能需要在其他基本块的开始处加上标记,表示是无条件跳跃的目标。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.