基本块

程序领域术语

基本块，是指程序—顺序执行的语句序列。

定义

基本块，其中只有一个入口和一个出口，入口就是其中的第—个语句，出口就是其中的最后一个语句。对一个基本块来说，执行时只从其入口进入，从其出口退出。

具体而言：

1. 只有一个入口，表示程序中不会有其它任何地方能通过jump跳转类指令进入到此基本块中。

2. 只有一个出口，表示程序只有最后一条指令能导致进入到其它基本块去执行。

所以，基本块的一个典型特点是：只要基本块中第一条指令被执行了，那么基本块内所有执行都会按照顺序仅执行一次。

基本块可以用源代码、汇编、指令等表示。

基本块的划分

寻找入口语句

1、程序的第一条语句

2、转移语句的目标语句

3、紧跟在条件转移语句后面的语句

·划分基本块的算法：

1、求出所有入口语句

2、一个入口语句对应一个基本块，入口语句对应的基本块方法是：该基本块由该入口语句到下一入口语句（不含下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的代码序列组成

3、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，可以删除

GCC中的表示

在GCC中，基本块使用basic_block数据类型来表示。

结构体basic_block的两个指针成员是指针next_bb和prev_bb，用来构造和内在的指令流顺序相同的基本块双向链表。基本块的链接由操作CFG的API来更新。宏FOR_EACH_BB可以用来按照lexicographical顺序来访问所有基本块。也可以使用walk_dominator_tree，来进行dominator遍历。给出两个基本块A和B，块A支配（dominate）块B，如果A总是在B之前被执行。

数组BASIC_BLOCK按照未指定的顺序包含了所有的基本块。每一个basic_block结构体都有一个域，包含了一个唯一的整数标识符index，其为该块在BASIC_BLOCK数组中的索引。函数中基本块的总数为n_basic_blocks。由于过程可以重排，创建，复制和销毁基本块，所以基本块的索引和总数在编译过程中都可能改变。任何块的索引都不应该比last_basic_block的大。

一些特定的基本块用来表示一个函数的可能的入口和出口。这些块被称作ENTRY_BLOCK_PRT和EXIT_BLOCK_PTR。这些块不包含任何代码，并且不是BASIC_BLOCK数组的成员。因此它们被赋予了唯一的负数索引。

每个basic_block还包含了指向基本块中的第一个指令（head）和最后一条指令（tail），或者指令流的结尾。实际上，由于basic_block数据类型在GCC的两个主要中间表示（tree和RTL）中都被用来表示块，因此具有针对这两种表示的指向基本块的头和尾的指针。

对于RTL，这些指针是rtx头和尾。在RTL函数表示中，头指针总是指向NOTE_INSN_BASIC_BLOCK或者CODE_LABEL。在RTL函数表示中，指令流不仅包含“真正”的指令，而且还有注解。任何移动或者复制基本块的函数都需要注意更新这些注解。许多这些注解都期望指令流由线性区域组成，这使得难以更新。NOTE_INSN_BASIC_BLOCK注解是唯一类型的，可以出现在基本块内包含的指令流中。一个基本块的指令流总是跟随一个NOTE_INSN_BASIC_BLOCK，但是块注解之前可以有0个或多个CODE_LABEL节点。基本块结束于控制流指令，或者最后一条指令后面跟随CODE_LABEL或者NOTE_INSN_BASIC_BLOCK。CODE_LABEL不能出现在基本块中的指令流里。

除了注解之外，跳转表向量还被表示为insn流中的“伪指令”。这些向量从不出现在基本块中，并且应该总是放在跳转指令引用它们的表后面。在移除table-jump之后，通常很难消除计算地址和引用向量的代码，所以对这些向量的清除工作被推迟到活跃分析之后。这样跳转表向量可能会在insn流中出现未被引用，并且无用的情况。在任何边成为fall-thru之前，关于现存的构架，需要调用can_fallthru函数来检测。

对于树的表示，基本块的头和尾由stmt_list域指向，但是，决不要直接引用这些特定的树。相反的，在树级别上，使用抽象容器和迭代器来访问基本块中的语句和表达式。这些迭代器被称作块语句迭代器（BSI）。可以在各种tree-*文件中使用grep查找^bsi。下面的摘抄可以很好的打印使用GIMPLE表示的程序的所有语句。

basic_block bb;

FOR_EACH_BB (bb)

{

gimple_stmt_iterator si;

for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))

{

gimple phi = gsi_stmt (si);

print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);

}

for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))

{

gimple stmt = gsi_stmt (si);