# 基本块

在数据流分析和优化之前需要先将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`。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mashplant.gitbook.io/decaf-doc/pa4/ji-ben-kuai.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.