基本块
复习
- 三地址码：每条指令最多一个运算
- 控制流：顺序执行与跳转
- 图：用节点和边表示关系
TL;DR
- 基本块是一段“只能从开头进、从结尾出”的顺序指令
- 块内没有跳转进入，也没有中途跳出去
- 划分基本块是分析控制流的第一步
- 它把长长的指令序列切成便于分析的单位
正文
三地址码是一长串指令，其中既有顺序执行的运算，也有跳转。要分析程序“可能怎么走”，得先给它分段。分出来的每一段，叫基本块（basic block）。
一个入口，一个出口
基本块的定义很讲究：它是一段连续的指令，只能从第一条进入，只能从最后一条离开。
换句话说：
- 块内不会中途跳进来（不会有跳转指向块的中间）
- 块内也不会中途跳出去（除了最后一条，块内没有跳转）
所以，基本块内部的指令，一定是老老实实顺序执行的。它是一个“不可分割”的直线执行段。
怎么划分
怎么把一串指令切成基本块？规则也很直接：
- 第一条指令是一个新块的开头
- 任何跳转的目标，是一个新块的开头
- 任何跳转指令的下一条，是一个新块的开头
- 任何条件跳转的下一句（即“不跳”的那条路），也是一个新块的开头
按这些规则切下去，每一段都满足“单入口、单出口”。
一个很形象的类比：基本块就像没有岔路的一段直路。岔路（跳转）只出现在路口（块的边界），段中间不会突然冒出岔口。
为什么要这样切
因为顺序执行的指令，分析起来简单又可靠。把它切成基本块之后：
- 块内的行为是确定的、线性的
- 块与块之间的“流向”才是复杂的部分
于是，分析程序的控制流，就变成了“分析基本块之间怎么连”。这让问题一下子清楚了很多。先分块、再连线，正是下一章控制流图的做法。
思考题 1
基本块为什么要求“只能从开头进入”？
思考题 2
为什么要先把程序切成基本块，再谈控制流分析？
小结
知识点
- 基本块是单入口、单出口的顺序指令段
- 块内不跳入、不中途跳出
- 划分依据：跳转目标、跳转的下一句等
- 基本块是控制流分析的基本单位
参考资料
- Wikipedia(zh)：基本块：单入口单出口的直线指令段
- Wikipedia(zh)：控制流分析：以基本块为基础的分析
思考题答案（仅供参考）
思考题 1
因为只有保证不能从中间进入，块内的执行才一定是顺序的、行为确定的。若允许从中间跳入，块内指令就可能在前置状态未知的情况下执行，分析就不再可靠，基本块的意义也就失去了。
思考题 2
因为基本块内部是确定顺序执行的，把它单独拿出来分析简单又可靠；复杂之处只在于块与块之间的跳转关系。先分块，就把“顺序部分”和“控制流向”分离开，控制流分析只需关注块的连接即可。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪