# 基本块

在数据流分析和优化之前需要先将tac划分成基本块：大家应该是默认地接受了这个设定，其实这不是必要的。之后提到的所有的数据流分析和优化的算法都可以直接在tac语句级别进行，对于每条语句都可以计算出相应的集合，并且在语句间进行传播。将tac划分为基本块可以看做是一种**加速**手段：每个基本块从进入到退出，对于数据流信息的处理是固定的，而因为这些分析和优化方法都是迭代的算法，划分为基本块就可以避免每个迭代步重复计算了。

> 很多参考文献中为了简化算法的描述，会假定每个基本块都由单条语句组成。从这也可以看出划分基本块是不必要的，不过在实际的编译器中为了编译速度考虑，一般还是要进行划分基本块的操作。

原理课中对于基本块的定义如下：

* 程序中一个顺序执行的语句序列
* 只有一个入口语句和一个出口语句
* 除入口语句外其他语句均不可以带标号
* 除出口语句外其他语句均不能是转移或停止语句

也就是说，除非执行过程中发生意料之外的错误，一个基本块总能够从开头执行到结尾，且不可能从除开头外的任何一个中间点开始执行。

基本块的划分方法是先标记"首语句"，也就是可以成为基本块的第一条语句的语句。它可以是：

* 程序的第一条语句
* 转移语句的目标语句
* 紧跟在条件转移语句后面的语句

容易证明基本块就是被首语句划分的一系列语句块。因此一个直白的划分基本块的方法是先标记所有首语句，然后遍历一遍语句，将两条首语句之间的语句划分给一个基本块。不过实现的时候没有必要分成这样两趟的过程，只需要一趟遍历就可以划分出基本块。具体可以参考框架已经提供好的代码。

> 事实上为了获取基本块的划分，不一定要像现在的实验框架和课堂中讲的一样对线性的ir进行划分，也可以直接从ast构造出cfg，只是会让这个翻译阶段(pa3)麻烦一些而已。也许明年的框架中就没有划分基本块这一步了。

基本块之间的连接关系由基本块的最后一条语句决定：

* 返回/停止：没有出边
* 无条件转移：一条出边指向转移的标号所在的基本块
* 条件转移：一条出边指向转移的标号所在的基本块，一条出边指向下一个基本块

实现的时候，以下几个点需要注意：

1. 这个"最后一条语句"没有被包含在基本块的tac链表中，它的其它信息(例如返回值，条件)保存到了表示出边的enum中
2. 在遇到tac中的条件转移语句时，不是直接把它对应到条件转移，而是判断条件是否是一个常量，如果是则把它转化成无条件转移
3. tac语句中没有"停止指令"，但是有对功能为停止的intrinsic函数的调用，对它按照停止语句处理

容易看出，因为有第二条的"优化"的存在(其实主要目的不是优化，而是让本阶段的后续实现更简单)，如果在本阶段通过图的可达性来检查一个函数是否不返回就结束，可以对pa2中提到的循环条件为常量`true`且没有作用于它的`break`的循环做出正确的判断。事实上，在之前的某个版本中，我基本实现了java规范要求的这类错误的检测，但是结果只能在划分基本块这个阶段才能给出，而且需要依赖pa3中进行一定程度的常量折叠，但是其它的框架都希望能在pa2这个阶段就检查出这类错误，所以我也只能简化成现在这个样子了。

按照现在的实现，可以保证pa4中处理的所有函数都满足不会不返回就结束(不仅限于返回值非空的函数，而是所有函数)，`tacopt::bb::simplify`函数依赖于这个条件，如果违反的话可能会出现下标越界。这样的设计是完全合适的，按照rust的错误处理的理念，这样的不可恢复，而且是因为输入没有满足约定而导致的错误，就应该`panic`。