中间代码

tac

我们使用的中间代码格式为tac(Three Address Code)，即四元式(quad)。一条典型的tac包含四个组成成分(所以称四元式)：dest = operand1 op operand2，其中dest和operand1/2都是虚拟寄存器。具体实现的时候可以有一定的变化，例如对于单目操作符则只有一个operand，对于加载整数和字符串等则没有operand而有一个常量值，对于函数调用可能没有dest。

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

在具体实现的时候，我们对tac做了一定的拓展：每个operand不一定是一个虚拟寄存器，也有可能是一个常量值，定义如下：

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

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

java框架使用的tac.jar并不支持例如加法的某个操作数是常数这样的tac格式，不过没有关系，反正我们不会用它。我另外编写了一个tac的解释器tacvm，它支持这样的tac格式就够了。除此之外，二者在虚表的格式上也有一定差异，tacvm的功能更强一些，不过大家其实并不用关心这些不兼容性，我们生成的tac只需要符合tacvm的规范即可。

除了这些细节的不同之处外，tac的格式和语义可以直接参考其它框架的文档。

存储tac的数据结构

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

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

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

pub struct Tac<'a> {
  pub payload: RefCell<TacPayload>,
  pub prev: Cell<Option<&'a Tac<'a>>>,
  pub next: Cell<Option<&'a Tac<'a>>>,
}

借助一个独立于链表外部的Arena来为节点分配内存：

pub struct TacFunc<'a> {
  ...
  pub alloc: &'a Arena<Tac<'a>>,
  ...
}

impl<'a> TacFunc<'a> {
  pub fn push(&mut self, t: TacKind) -> &mut Self {
    let tac = self.alloc.alloc(Tac {
      payload: TacPayload { kind: t }.into(),
      prev: None.into(),
      next: None.into(),
    });
    ...
  }
}

关于这个实现方案，需要承认的有两点：第一，它的底层肯定也还是不安全的rust，只是在我们关心的应用层面可以忽略这种不安全；第二，也是更重要的，这种实现方案下我们将无法再利用rust的借用检查等编译期机制来避免犯错，RefCell可以在一定程度上通过运行时检查来帮助排查错误，但是它的效果实际上是完全不够的：如果链表的结构没有被正确维护，显然会让最终结果出错，但是这根本就不关payload的事，可以说这样的逻辑错误在这种实现方式下就是没法检查的。

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

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

decaf的运行时库函数

纯粹的表示运算，跳转，调用decaf函数等功能的tac是没办法实现诸如io，停止程序等需要和外部世界打交道的功能的。我们早在语法分析阶段就强行设定了几个"函数"，如ReadInteger()之类的，现在它们也不可能只用前面这些功能来实现，必须允许tac调用一些不属于decaf的函数，也就是decaf的运行时库函数，我们用Intrinsic来表示它们(在写文档的时候我发现，这种函数似乎叫外部函数或者内部函数都挺合理的，想表达的意思都是语言本身无法实现或无法高效实现的函数)：

pub enum Intrinsic { 
  _Alloc, _ReadLine, _ReadInt, _StringEqual, _PrintInt, _PrintString, _PrintBool, _Halt 
}

它们在生成的tac中的名字就是各个variant的名字。分别列举它们的功能如下：

• _Alloc

  • 功能：分配内存，如果失败则自动退出程序

  • 参数：为要分配的内存块大小(单位为字节)

  • 返回值：该内存块的首地址

• _ReadLine

  • 功能：读取一行字符串

  • 参数：无

  • 返回值：读到的字符串首地址

• _ReadInt

  • 功能：读取一个整数

  • 参数：无

  • 返回：读到的整数

• _StringEqual

  • 功能：比较两个字符串

  • 参数： 两个，分别为要比较的两个字符串的首地址

  • 返回值：表示两个字符串相等的bool值

• _PrintInt

  • 功能：打印一个整数

  • 参数：要打印的数字

  • 返回值：无

• _PrintString

  • 功能：打印一个字符串

  • 参数：要打印的字符串首地址

  • 返回值：无

• _PrintBool

  • 功能：打印一个布尔值

  • 参数：要打印的布尔变量

  • 返回值：无

• _Halt

  • 功能：结束程序

  • 参数：无

  • 返回值：无，且它会立即终止tacvm的运行