> For the complete documentation index, see [llms.txt](https://mashplant.gitbook.io/decaf-doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mashplant.gitbook.io/decaf-doc/pa3/zhong-jian-dai-ma.md).

# 中间代码

## 中间代码

中间代码有很多形式，例如三元式，四元式，树形中间代码(虎书的示例中采用这种格式)，静态单赋值形式(ssa，single static assignment)等。jvm的byte code也可以看成是一种中间代码，由前端的javac产生，交由后端的jvm进行执行和优化，它是一种基于栈的中间代码，例如一条`iadd`指令弹出栈顶的两个整数，将它们的和压入栈中。

我们使用的中间代码格式为三地址码(tac)，即四元式(quad)。一条典型的tac包含四个组成成分(所以称四元式)：`dest = operand1 op operand2`，其中`dest`和`operand1/2`都是虚拟寄存器。

除了这些相对底层，目标主要是翻译和优化的中间代码之外，还有一些中间代码的目标是进行程序分析和检查。例如rust采用了hir(high-level ir)和mir(mid-level ir)两级中间代码，在这些中间代码中进行诸如类型检查(与之不同，实验框架中类型检查在ast层次进行)，类型推导，借用检查等工作，虽然也会进行一定程度的优化，但是主要的翻译和优化还是直接交给llvm进行。

## tac

实验框架中的每种tac并不都符合典型的tac的格式，例如对于单目操作符则只有一个operand，对于加载整数和字符串等则没有operand而有一个常量值，对于函数调用可能没有dest。

此外，我们的框架对tac做了一定的拓展：每个operand不一定是一个虚拟寄存器，也有可能是一个常量值，定义如下：

```rust
pub enum Operand {
  Reg(u32),
  Const(i32),
}
```

限定常量只能是`i32`常量似乎有点局限，不过在我们的编译器里已经足够了。这样定义的主要是为了pa4做准备：假设我们通过某种方法手段确定一个虚拟寄存器是常量，自然会希望把所有对它的引用都转化成对常量的引用，然而如果限定tac的operand只能是虚拟寄存器的话，就没法直接做这种转化了(如果要做，又得定义新的数据结构来存放结果，反而更麻烦)。

本阶段生成的tac由tac模拟器[tacvm](https://github.com/MashPlant/tacvm)来执行，后续章节中有关于tac格式的文档。

## 存储tac的数据结构

只看pa3这个阶段，为了把tac序列组织起来，显然性能最好也最自然的方法就是`Vec<Tac>`，但是我们没有使用`Vec`，而是使用了链表。这是因为后序的处理会频繁地对tac序列做插入和删除操作，`Vec`显然不适合这种使用。

具体怎么实现链表在rust中似乎是一件很有挑战性的事情：首先我们不会使用标准库的`LinkedList`，这很好理解，只要稍微查一下它的api，就会发现它(几乎)什么api也没有。迭代器的自由性让c++的`std::list`和`std::set`非常好用，但是这是以牺牲安全为代价换来的。倒不能说这种取舍一定是不好的，但是现在既然我们选择了(安全)rust，就等于接受我们没有这种选择了。

我们选择的实现方案是使用在pa1/2中都用到了的`Arena`，链表节点定义为：

```rust
pub struct TacNode<'a> {
  pub tac: Cell<Tac>,
  pub prev: Cell<Option<&'a TacNode<'a>>>,
  pub next: Cell<Option<&'a TacNode<'a>>>,
}
```

此外，还需要借助一个独立于链表的外部的`Arena`来为节点分配内存。

关于这个实现方案，需要承认的有两点：第一，它的底层肯定也还是不安全的rust，只是在我们关心的应用层面可以忽略这种不安全；第二，也是更重要的，这种实现方案下我们将**无法**再利用rust的借用检查等编译期机制来避免犯错，`Cell`可以在一定程度上避免可变性相关的错误，但是它的效果实际上是完全不够的，很容易就能写出能通过编译但是会破坏链表结构的代码。

也许有人会问为什么不使用`Rc`和`Weak`那一套呢?这是显然的：它们也不能通过编译时或者运行时的检查保证链表的结构被正确维护，唯一的"好处"在于一个链表节点不再被使用时可以及时释放。但是事实上不那么及时的释放事实上也是完全可以接受的，而且因为少了很多额外的维护操作，不及时释放的效率也会高一些。

很遗憾，在链表的实现上我们没能很好地利用rust优秀的语言特性来帮助编写代码，不过稍微想一下就会发现，这也只不过是退化到了和其它语言一样而已，并不是那么不能接受。当然，如果大家有更好的实现方案非常欢迎提出，以后的实验中也许会用上。