Compiler -- Codegen

发表于 2023-11-19 分类于 note ，编译原理

概述

在代码生成步骤中，编译器会将中间代码或 AST 翻译为目标语言，通常是汇编语言，供后续程序处理或运行。

这篇文章所描述的代码生成指的是由 AST 直接生成汇编语言的步骤。由 AST 生成 IR 的过程简单修改该过程即可，而由 IR 生成汇编语言的步骤将会在代码优化中讨论。

运行时组织

一个程序需要先被操作系统加载才能运行。具体有以下几个步骤：

操作系统为程序分配内存空间；
操作系统将程序的代码以及静态的数据装载到内存中为程序分配的空间中；
切换至用户态并跳转到程序的入口处，开始运行程序。

在内存中，程序将会被划分为许多的段（segment）。通俗来讲，一个段是一块拥有相同功能的内存区域。通常内存中段的布局大致如下：

其中堆和栈的大小是根据运行情况动态调整的，其它部分的大小则是由可执行文件指定的，大小固定。

编译器需要完成的事情包括代码的生成以及数据段的编排。

堆栈机

堆栈机（stack machine）是一种计算模型，该模型中只有一个栈作为数据存储。

对于每条指令： \[r = F(a_1,\cdots,a_n)\] 机器会从栈中弹出 \(n\) 个操作数，进行操作后将结果 \(r\) 推入栈顶。

不同于寄存器机（register machine）每条指令需要指定操作数和返回的寄存器，堆栈机的操作数和返回位置均在栈顶，因此使用堆栈机作为虚拟机的模型可以得到更小的可执行文件，这也是 JVM 选择堆栈机作为其计算模型的一个原因。

对于堆栈机来说，由于操作都在栈顶执行，其它的数据是保持不变的，因此堆栈机十分适合用于模拟子程序的进入和返回。

通常，现代计算机执行程序的模式可以看作是含有多个寄存器的堆栈机，大致可以看作将栈顶位置使用寄存器代替了。

现在考虑带有一个寄存器的堆栈机，该寄存器通常称为累加器（accumulator）。对于每条指令： \[r = F(a_1,\cdots,a_n)\] 机器会从栈中弹出 \(n-1\) 个操作数，与累加器中的数据一起进行操作后将结果 \(r\) 放入累加器中。

同样地，执行完操作后结果在累加器，而栈中的数据保持不变。

栈帧

对于子程序的调用，我们希望能在子程序运行完成后能够恢复到调用前的状态，这样便保持了程序的正确性；同时由堆栈机的特性，事实上我们只需要保存寄存器即可。

一个简单的方法是在调用时直接将寄存器的内容和调用完返回的地址保存到栈中，返回时将这些内容从栈中取出来即可。事实上这些内容便构成了一个栈帧（stack frame）；或者称作活动记录（activation）。

通常栈帧的结构如图所示：

其中 fp 称为栈帧指针（Frame Pointer），指向栈帧开始的地址；sp 称为栈指针（stack pointer），指向栈顶后一个单元。

对于寄存器的保存，其中一些寄存器的值会保留在调用该子程序的栈帧中，称为调用者保存寄存器（caller saved register），还有一部分寄存器是不需要保留的，具体那些寄存器属于被调保存寄存器（callee saved register）是由 ABI 指定的。

通常 fp 指针是可选的，保留 fp 指针主要为了方便调试工具读取栈帧内容，有时因为性能需求也会将储存 fp 的寄存器当作普通寄存器来使用。

临时变量

代码生成时追踪临时变量的个数是很重要的，这样我们便可以尽可能地将临时变量储存在寄存器中，从而优化生成的代码的运行速度。

为此我们可以在 AST 结点上新增一个属性 \(T(e)\)，表示求值该表达式所需的临时变量的数量。例如对于表达式 \(e_1 + e_2\)，有： \[T(e_1 + e_2) = \max\{ T(e_1), T(e_2 + 1) \}\]

对象布局

对于面向对象的语言来说，对象的内存布局也是需要在代码生成步骤中考虑的。

设计对象布局的原则同样也是里氏替换原则，如下是一个简单可行的对象布局：

其中类标签为一个整数，在代码生成时需要为每个类生成一个合适的类标签以在运行时获取对象所属类的信息；方法指针指向一个只读数据区的列表，该列表中包含该类方法的入口地址，该列表的编排也需要先储存基类方法再储存子类的方法；基类属性是嵌套的，也即储存直接基类之前需要先储存直接基类的基类属性。

可以发现如果使用该布局，指向该对象的指针同样也是一个合法的指向该对象所属类基类的指针，因此该布局是可行的。

堆内存管理

除了全局变量和栈中的局部变量以外，内存中还有许多变量需要使用变量中的指针或引用进行间接访问，这类变量通常储存在堆（heap）中。

不同于全局变量与局部变量，堆中的变量的多少以及生存期在编译期是不确定的，因此需要在运行期管理堆中内存的手段。通常有三种方式：

使用函数或关键字在代码中手动申请和释放内存，例如 C 中的 malloc/free 和 C++ 中的 new/delete；
手动申请内存，使用运行时系统定期自动回收内存，例如 Java 与 C# 等语言中的垃圾回收机制（Garbage Collection, abbr. GC）；
将堆内存的申请与释放与某个变量的生存期关联起来，在变量的生存期开始与结束时自动对堆中的变量进行申请与释放，也称 RAII 机制（Resource Acquisition Is Initialization），例如 C++ 与 Rust 中的智能指针。

三种方式各有优缺点。手动管理的优点在于内存管理比较灵活，适用于系统编程等较底层的编程；缺点在于经常会由于疏忽造成各类难以复现与定位的内存 bug，如内存泄露、悬垂指针等。GC 机制则很少出现类似的 bug，但代价是较大的性能损失，通常作用相同的代码在 Java 上的实现其运行时间是 C 语言实现的两倍及以上。RAII 机制结合了两者的优点，但有一些内存结构无法处理，例如循环引用。

垃圾回收

在程序中，只有能被 “找到” 的变量是能够被使用的；无法被 “找到” 的变量则无法使用，称为垃圾（garbage），这类变量所占据的内存可以被回收用于后续的内存申请。

这种能否被 “找到” 的属性称为变量的可达性（reachable）。若符合如下两个条件则称变量为可达的：

该变量是全局变量、局部变量或者是在寄存器上的临时变量；
有某个可达变量拥有该变量的指针或引用。

符合第一个条件的变量称为根变量（root）。有了可达性的概念则可以使用如下的算法进行垃圾回收：

从根变量出发，标记所有的可达变量；
若堆中某变量标记为可达则清除标记，否则将该变量所占内存空间回收。

该算法称为标记 - 清除算法（mark and sweep），即第一步为标记，第二步为清除。

空闲空间的管理通常是由空闲链表（free list）来完成的：内存回收时将该内存空间以空闲块的形式插入空闲链表中，分配内存时遍历空闲链表，找到大小足够的块便分配该块，将该块移除空闲链表，如果有剩余空间还需将剩余空间重新插入空闲链表当中。

实际执行该算法时仍有一些需要注意的地方：GC 通常是在可用空间不足时触发的，然而标记时可能需要辅助的内存空间来标记可达变量（例如栈），而且辅助的内存空间大小是未知的。

一个想法是将变量内部的指针用作辅助内存。具体来讲，进行标记的同时可以将整个链进行翻转，到达链的终点时再沿着翻转的链回溯并将链重新翻转回去。这便是指针翻转（pointer reversal）算法。

这样在标记的过程中只需要记录两个指针：当前标记的指针与链中前一个变量的指针。

另外的一个问题是标记 - 清除算法容易产生内存碎片（memory fragment），即内存中的空闲空间大于申请的空间，但没有可用的大于申请空间的空闲内存块。

一种方法是在清除后再加一步整理（compact），将可达变量复制到空闲内存的起始位置并重置变量中的指针。这种算法称为标记 - 清除 - 整理算法（mark-sweep-compact）。这样剩余的空闲内存就变成了一整块，消除了内存碎片。这样做的缺点在于重新进行复制消耗的运行时间较大。

另一种方法是将堆分为两块相同大小的块，若一个块满了标记可达变量并连续复制到另一个块中，并将原先的块标记为空块。这种算法称为标记 - 复制算法（mark and copy）。这样标记和复制可以同时进行，缺点在于需要一个额外的预留空间。

在 Java 的实现中，堆中的数据分为两个部分：新生代和老年代；新生代经常会发生垃圾回收，因此新生代使用标记 - 复制算法进行 GC；老年代较少发生 GC，因此使用标记 - 清除 - 整理算法。

引用计数

不同于垃圾回收，引用计数（Reference Counting, abbr. RC）会为每个堆中的变量设置一个计数器记录有多少指针指向该变量，若计数器变为 0，则立刻清除该变量。

C++11 中引入了三种智能指针，其中 shared_ptr<T> 即为使用引用计数的智能指针。使用 make_shared<T>() 可以创建一个智能指针和一个与指针绑定的堆上变量，此时会申请变量的空间和一个储存计数器的空间；当智能指针被拷贝时计数器加 1，当指针被释放时（超出作用域或在堆中被释放）或更改了指针位置（赋值或调用 shared_ptr<T>::reset()）计数器减 1，若计数器为 0 则释放变量和计数器。

引用计数同样会产生内存碎片，同时引用计数无法处理循环引用。一个方法是在空间不足时仍然使用 GC 回收内存。另一个方法是使用另一种智能指针 weak_ptr<T>，该指针只能通过 shared_ptr<T> 或其它的 weak_ptr<T> 构造，且不会增加对象的引用计数，访问变量时需使用 weak_ptr<T>::lock() 方法尝试创建一个 shared_ptr<T> 再访问，若指向的对象引用计数为 0 则 weak_ptr<T>::lock() 方法将返回空指针。

一个比较经典的例子是对于树状的数据结构，可以使用 shared_ptr<T> 构建指向子结点的指针，使用 weak_ptr<T> 构建指向父节点的指针。

引用循环本质上是变量所有权（ownership）的问题，shared_ptr<T> 代表指针拥有变量的所有权，而 weak_ptr<T> 则没有。这样引用循环的问题就变为了代码设计的问题。

操作语义

一些编译器可能需要跨平台工作，不适合直接使用汇编来描述表达式的求值过程，因此需要一个尽量准确且与某个特定的实现无关的方式来描述求值过程。

从数学的角度来讲，程序是一个由一个 “状态” 到另一个 “状态” 的映射，可以使用命题逻辑的方式来描述某个表达式的语义：若机器起始状态符合 X，则经过表达式求值后机器的状态符合 Y。因此可以使用和类型检测相同的方式来描述求值的过程。

例如，对于赋值操作，有如下操作语义：

\[ \frac{ \begin{gathered} so, E, S \vdash e: v, S_1 \\ E(\mathrm{id}) = l_{\mathrm{id}} \\ S_2 = S_1[v/l_{\mathrm{id}}] \end{gathered} }{ so, E, S \vdash (\mathrm{id} \leftarrow e):v,S_2 } \]

与类型检查规则类似，\(\vdash\) 前面的 \(so, E, S\) 是语义上下文。其中 \(so\) 代表当前的 self 对象（Self Object）；\(E\) 代表变量环境（Environment），是由标识符到变量内存位置的一个映射；\(S\) 代表存储（Storage），是由 \(E\) 给出的变量位置到变量值的映射。

从这个例子中可以看出操作语义与类型检查的区别主要在于最终结果。冒号后面的 \(v\) 代表的是该表达式求值的结果，后面的 \(S_2\) 代表求值前后 \(S\) 发生了变化，代表了求值的副作用（side-effect）。

Lab

作业五需要使用 C++ 或 Java 通过之前生成的 AST 来生成 MIPS 汇编代码。

个人感觉手册中给出的信息相对较少，一个解决办法是逆向标准的 coolc 生成的汇编代码。

首先在头文件中添加代码生成的函数：

class CgenClassTable : public SymbolTable<Symbol,CgenNode> {
private:
  /*...*/
   void code_global_data();
   void code_global_text();
   void code_bools(int);
   void code_select_gc();
   void code_constants();

   void code_class_nametab();
   void code_disptable();
   void code_prot();
   void code_init(int&);
   void code_method(int&);

  /*...*/
};

同样地，在 CgenNode 中添加代码生成的函数：

class CgenNode : public class__class {
private: 
   CgenNodeP parentnd;                        // Parent of class
   List<CgenNode> *children;                  // Children of class
   Basicness basic_status;                    // `Basic' if class is basic
                                              // `NotBasic' otherwise
   StringEntryP p_str;
   int classtag;
   int attr_size;
   int meth_size;
   int ub_child_tag;
   SymbolTable<Symbol, MemAddr>* varenv;
   CgenClassTableP clsenv;
   SymbolTable<Symbol, int>* dispidx;

   void code_disptable_items(ostream&, CgenNode*);
   void code_prot_items(ostream&, CgenNode*);

public:
   CgenNode(Class_ c,
            Basicness bstatus,
            CgenClassTableP class_table
   );

   void add_child(CgenNodeP child);
   List<CgenNode> *get_children() { return children; }
   void set_parentnd(CgenNodeP p);
   CgenNodeP get_parentnd() { return parentnd; }
   int basic() { return (basic_status == Basic); }
   StringEntryP get_p_str() { return p_str; }
   int get_classtag() { return classtag; }
   int get_ub_child() { return ub_child_tag; }
   CgenClassTableP get_clsenv() { return clsenv; }
   SymbolTable<Symbol, int>* get_disp() { return dispidx; }
   void code_class_nametab(ostream&);
   void code_disptable(ostream&);
   void code_prot(ostream&);
   void code_init(ostream&, int&);
   void code_method(ostream&, int&);
   int get_attr_size() { return attr_size; }
   void init_nd(int&);
};

其中的 varenv 即为变量名到内存地址的映射，MemAddr 的定义如下：

struct MemAddr {
  char* reg;
  int offset;
};

然后是初始化 CgenNode，主要是指定类标签以及计算对象的大小：

CgenClassTable::CgenClassTable(Classes classes, ostream& s) : nds(NULL) , str(s)
{
   stringclasstag = 3 /* Change to your String class tag here */;
   intclasstag =    1 /* Change to your Int class tag here */;
   boolclasstag =   2 /* Change to your Bool class tag here */;

   enterscope();
   if (cgen_debug) cout << "Building CgenClassTable" << endl;
   install_basic_classes();
   install_classes(classes);
   build_inheritance_tree();
   if (cgen_debug) cout << "CgenNodes initializing" << endl;
   init_nd();

   code();
   exitscope();
}
void CgenClassTable::install_classes(Classes cs)
{
  for(int i = cs->first(); cs->more(i); i = cs->next(i)) {
    install_class(new CgenNode(cs->nth(i),NotBasic,this));
  }

  // reverse cgen nd list
  List<CgenNode>* tmp = this->nds;
  this->nds = NULL;
  while(tmp) {
    nds = new List<CgenNode>(tmp->hd(), nds);
    List<CgenNode>* nd = tmp->tl();
    delete tmp;
    tmp = nd;
  }
}
void CgenClassTable::init_nd() {
  int tag_cnt = 0;
  this->root()->init_nd(tag_cnt);
}
void CgenNode::init_nd(int& tag_cnt) {
  if(!this->name->equal_string("Object", 6)) {
    this->attr_size = this->parentnd->attr_size;
    this->meth_size = this->parentnd->meth_size;
  }
  for(int i = this->features->first(); this->features->more(i); i = this->features->next(i)) {
    if(this->features->nth(i)->is_attr()) {
      ++this->attr_size;
    } else {
      ++this->meth_size;
    }
  }

  // reverse child to get proper order
  List<CgenNode>* rev = this->children;
  this->children = NULL;
  while(rev) {
    this->children = new List<CgenNode>(rev->hd(), this->children);
    rev = rev->tl();
  }
  // set class tag
  this->classtag = tag_cnt++;
  for(List<CgenNode>* l = this->children; l; l = l->tl()) {
    l->hd()->init_nd(tag_cnt);
  }
  this->ub_child_tag = tag_cnt;
}

类标签是按照 dfs 序指定的，这样某个类的子类的类标签是一个区间，方便后面生成 case 语句的代码。

然后是代码生成：

void CgenClassTable::code()
{
  if (cgen_debug) cout << "coding global data" << endl;
  code_global_data();

  if (cgen_debug) cout << "choosing gc" << endl;
  code_select_gc();

  if (cgen_debug) cout << "coding constants" << endl;
  code_constants();

//                 Add your code to emit
//                   - prototype objects
//                   - class_nameTab
//                   - dispatch tables
//

  if (cgen_debug)  cout << "coding class name table" << endl;
  code_class_nametab();

  if (cgen_debug)  cout << "coding dispatch tables" << endl;
  code_disptable();

  if (cgen_debug) cout << "coding prototype objs" << endl;
  code_prot();

  if (cgen_debug) cout << "coding global text" << endl;
  code_global_text();

//                 Add your code to emit
//                   - object initializer
//                   - the class methods
//                   - etc...

  int label_cnt = 0;
  if (cgen_debug) cout << "coding object inits" << endl;
  code_init(label_cnt);

  if (cgen_debug) cout << "coding class methods" << endl;
  code_method(label_cnt);

}

首先按照运行时系统的要求，需要在数据段生成类名表、方法分配表和对象原型。

void CgenClassTable::code_class_nametab() {
  str << "class_nameTab:\n";
  this->root()->code_class_nametab(this->str);
}
void CgenNode::code_class_nametab(ostream& s) {
  s << WORD; stringtable.lookup_string(this->name->get_string())->code_ref(s); s << endl;
  for(List<CgenNode>* l = this->children; l; l = l->tl()) {
    l->hd()->code_class_nametab(s);
  }
}

void CgenClassTable::code_disptable() {
  for(List<CgenNode>* l = this->nds; l; l = l->tl()) {
    l->hd()->code_disptable(this->str);
  }
}
void CgenNode::code_disptable(ostream& s) {
  emit_disptable_def(this->name, s);
  dispidx->enterscope();
  this->code_disptable_items(s, this);
}
void CgenNode::code_disptable_items(ostream& s, CgenNode* anc_nd) {
  int idx = 0;
  if(anc_nd->parentnd) {
    this->code_disptable_items(s, anc_nd->parentnd);
    idx = anc_nd->parentnd->meth_size;
  }
  for(int i = anc_nd->features->first(); anc_nd->features->more(i); i = anc_nd->features->next(i)) {
    Feature f = anc_nd->features->nth(i);
    if(f->is_attr()) continue;
    method_class* meth = dynamic_cast<method_class*>(f);
    dispidx->addid(meth->name, new int(idx));
    s << WORD; emit_method_ref(anc_nd->name, meth->name, s); s << endl;
    ++idx;
  }
}

void CgenClassTable::code_prot() {
  for(List<CgenNode>* l = this->nds; l; l = l->tl()) {
    l->hd()->code_prot(this->str);
  }
}
void CgenNode::code_prot(ostream& s) {
  s << WORD << "-1" << endl;
  emit_protobj_ref(this->name, s); s << LABEL
    << WORD << this->classtag << endl;
  int attr_cnt = 0;
  
  // size
  s << WORD << (this->attr_size + DEFAULT_OBJFIELDS) << endl
    << WORD; emit_disptable_ref(this->name, s); s << endl;
  varenv->enterscope();
  this->code_prot_items(s, this);
}
void CgenNode::code_prot_items(ostream& s, CgenNode* anc_nd) {
  if(anc_nd->name->equal_string("Int", 3) || anc_nd->name->equal_string("Bool", 4)) {
    s << WORD << "0" << endl;
  } else if(anc_nd->name->equal_string("String", 6)) {
    s << WORD; inttable.lookup_string("0")->code_ref(s); s << endl;
    s << WORD << "0" << endl;
  } else {
    int offset = DEFAULT_OBJFIELDS;
    if(anc_nd->parentnd) {
      this->code_prot_items(s, anc_nd->parentnd);
      offset += anc_nd->parentnd->attr_size;
    }
    for(int i = anc_nd->features->first(); anc_nd->features->more(i); i = anc_nd->features->next(i)) {
      Feature f = anc_nd->features->nth(i);
      if(!f->is_attr()) continue;
      attr_class* attr = dynamic_cast<attr_class*>(f);
      varenv->addid(attr->name, new (MemAddr){ SELF, offset });
      
      if(attr->type_decl->equal_string("Int", 3)) {
        s << WORD; inttable.lookup_string("0")->code_ref(s); s << endl;
      } else if(attr->type_decl->equal_string("Bool", 4)) {
        s << WORD; BoolConst(0).code_ref(s); s << endl;
      } else if(attr->type_decl->equal_string("String", 6)) {
        s << WORD; stringtable.lookup_string("")->code_ref(s); s << endl;
      } else { // Object
        s << WORD << 0 << endl;
      }
      ++offset;
    }
  }  
}

然后生成代码段，首先是根据运行时系统的要求生成每个类的初始化函数：

void CgenNode::code_init(ostream& s, int& label_cnt) {
  emit_init_ref(this->name, s); s << LABEL;
  if(this->basic_status == Basic) {   // Basic classes, which don't need init
    emit_return(s);
    return;
  }
  emit_enter_frame(s);
  s << JAL; emit_init_ref(this->get_parent(), s); s << endl;
  int offset = DEFAULT_OBJFIELDS + this->parentnd->attr_size;
  for(int i = this->features->first(); this->features->more(i); i = this->features->next(i)) {
    if(!this->features->nth(i)->is_attr()) continue;
    attr_class* attr = dynamic_cast<attr_class*>(this->features->nth(i));
    if(typeid(*(attr->init)) == typeid(no_expr_class)) {
      ++offset;
      continue;
    }
    int _ = -3;
    attr->init->code(s, label_cnt, this, this->varenv, _);  // code gen for init expr
    emit_store(ACC, offset, SELF, s); // store value from init expr to var in proper offset
    ++offset;
  }
  emit_move(ACC, SELF, s);
  emit_exit_frame(s);
}

其中的 emit_enter_frame 和 emit_exit_frame 为自定义的函数，用于生成进出栈帧的代码：

void emit_enter_frame(ostream& s) {
  // Push stack
  emit_addiu(SP, SP, -12, s);
  // Save reg states
  emit_store(FP, 3, SP, s);
  emit_store(SELF, 2, SP, s);
  emit_store(RA, 1, SP, s);
  // set frame pointer
  emit_addiu(FP, SP, 12, s);
  // set self pointer
  emit_move(SELF, ACC, s);
}
void emit_exit_frame(ostream& s) {
  // Recover reg states
  emit_load(RA, -2, FP, s);
  emit_load(SELF, -1, FP, s);
  // Pop stack
  emit_move(SP, FP, s);
  // Recover fp
  emit_load(FP, 0, FP, s);

  emit_return(s);
}

然后是生成类中各成员方法：

void CgenNode::code_method(ostream& s, int& label_cnt) {
  if(this->basic_status == Basic) {   // basic classes, already implemented intrinsically
    return;
  }
  for(int i = this->features->first(); this->features->more(i); i = this->features->next(i)) {
    if(this->features->nth(i)->is_attr()) continue;
    method_class* m = dynamic_cast<method_class*>(this->features->nth(i));
    m->code(s, label_cnt, this, this->varenv);
  }
}
void method_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv) {
  if (cgen_debug) { cout << "coding method "; emit_method_ref(so->name, this->name, cout); cout << endl; }
  emit_method_ref(so->name, this->name, s); s << LABEL;
  
  emit_enter_frame(s);

  // establish ref for formal args
  varenv->enterscope();
  int offset = this->formals->len();
  for(int i = this->formals->first(); this->formals->more(i); i = this->formals->next(i)) {
    formal_class* farg = dynamic_cast<formal_class*>(this->formals->nth(i));
    varenv->addid(farg->name, new (MemAddr){ FP, offset });
    --offset;
  }
  
  varenv->enterscope();
  int sp = -3;
  this->expr->code(s, label_cnt, so, varenv, sp);

  varenv->exitscope(); varenv->exitscope();
  emit_exit_frame(s);
  if (cgen_debug) { cout << "method "; emit_method_ref(so->name, this->name, cout); cout << " successfully coded. " << endl; }
}

然后就是各个表达式的代码生成，根据手册给出的操作语义书写即可，其中一些方法是由运行时系统实现的，在手册中有调用说明。

唯一需要注意的是 case 表达式的代码生成，这里的类型判断需要判断动态类型，因此需要在运行时对类标签进行判断。由于前面说过类标签是由 dfs 序指定的，因此只需要判断是否在其子树区间即可。

其它的判断方式也许可以但几乎肯定运行时开销会更大。

void assign_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->expr->code(s, label_cnt, so, varenv, sp);
  MemAddr* ma = varenv->lookup(this->name);
  emit_store(ACC, ma, s);
}

void static_dispatch_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  SymbolTable<Symbol, CgenNode>* clsenv = so->get_clsenv();
  // evaluate actual args
  int orig_sp = sp;
  for(int i = this->actual->first(); this->actual->more(i); i = this->actual->next(i)) {
    this->actual->nth(i)->code(s, label_cnt, so, varenv, sp);
    emit_push(ACC, s);
    --sp;
  }

  if(typeid(*(this->expr)) == typeid(no_expr_class)) {
    emit_move(ACC, SELF, s);
  } else {
    this->expr->code(s, label_cnt, so, varenv, sp);
  }
  int lbl_tbr = label_cnt++;
  emit_bne(ACC, ZERO, lbl_tbr, s);
  // dispatch on void, abort
  s << LA << ACC << " "; stringtable.lookup_string(so->filename->get_string())->code_ref(s); s << endl;
  emit_load_imm(T1, this->line_number, s);
  emit_jal("_dispatch_abort", s);

  emit_label_def(lbl_tbr, s);
  CgenNodeP ty;
  if(this->type_name->equal_string("SELF_TYPE", 9)) {
    ty = so;
  } else {
    ty = clsenv->lookup(this->type_name);
  }

  int idx = *(ty->get_disp()->lookup(this->name));
  emit_load(T1, 2, ACC, s);   // load disp tab
  emit_load(T1, idx, T1, s);  // search meth
  emit_jalr(T1, s);
  emit_addiu(SP, FP, orig_sp * WORD_SIZE, s);
  sp = orig_sp;
}

void dispatch_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  SymbolTable<Symbol, CgenNode>* clsenv = so->get_clsenv();
  if (cgen_debug) {
    cout << "dispatch at line #" << this->line_number << endl;
    cout << "  type = " << this->expr->type->get_string() << ", name = " << this->name->get_string() << endl;
  }
  // evaluate actual args
  int orig_sp = sp;
  for(int i = this->actual->first(); this->actual->more(i); i = this->actual->next(i)) {
    this->actual->nth(i)->code(s, label_cnt, so, varenv, sp);
    emit_push(ACC, s);
    --sp;
  }

  if(typeid(this->expr) == typeid(no_expr_class*)) {
    emit_move(ACC, SELF, s);
  } else {
    this->expr->code(s, label_cnt, so, varenv, sp);
  }
  int lbl_tbr = label_cnt++;
  emit_bne(ACC, ZERO, lbl_tbr, s);
  // dispatch on void, abort
  s << LA << ACC << " "; stringtable.lookup_string(so->filename->get_string())->code_ref(s); s << endl;
  emit_load_imm(T1, this->line_number, s);
  emit_jal("_dispatch_abort", s);

  emit_label_def(lbl_tbr, s);
  CgenNodeP ty;
  if(this->expr->type->equal_string("SELF_TYPE", 9)) {
    ty = so;
  } else {
    ty = clsenv->lookup(this->expr->type);
  }

  int idx = *(ty->get_disp()->lookup(this->name));
  emit_load(T1, 2, ACC, s);   // load disp tab
  emit_load(T1, idx, T1, s);  // search meth
  emit_jalr(T1, s);
  emit_addiu(SP, FP, orig_sp * WORD_SIZE, s);
  sp = orig_sp;
  if (cgen_debug) {
    cout << "dispatch at line #" << this->line_number << " successfully coded. " << endl;
  }
}

void cond_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->pred->code(s, label_cnt, so, varenv, sp);
  // get slot of bool
  emit_load(T1, 3, ACC, s);
  int lbl_fbr = label_cnt++;
  int lbl_end = label_cnt++;
  emit_beqz(T1, lbl_fbr, s);
  this->then_exp->code(s, label_cnt, so, varenv, sp);
  emit_branch(lbl_end, s);
  emit_label_def(lbl_fbr, s);
  this->else_exp->code(s, label_cnt, so, varenv, sp);
  emit_label_def(lbl_end, s);
}

void loop_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  int lbl_beg = label_cnt++;
  int lbl_end = label_cnt++;
  emit_label_def(lbl_beg, s);
  this->pred->code(s, label_cnt, so, varenv, sp);
  emit_load(T1, 3, ACC, s);
  emit_beqz(T1, lbl_end, s);
  this->body->code(s, label_cnt, so, varenv, sp);
  emit_branch(lbl_beg, s);
  emit_label_def(lbl_end, s);
  emit_move(ACC, ZERO, s);
}

void typcase_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  SymbolTable<Symbol, CgenNode>* clsenv = so->get_clsenv();

  this->expr->code(s, label_cnt, so, varenv,sp);
  int lbl_beg = label_cnt++;
  int lbl_end = label_cnt++;

  emit_bne(ACC, ZERO, lbl_beg, s);
  // case on void
  s << LA << ACC << " "; stringtable.lookup_string(so->filename->get_string())->code_ref(s); s << endl;
  emit_load_imm(T1, this->line_number, s);
  emit_jal("_case_abort2", s);

  // sort branch with their size of inheritance tree
  // so that when branch matches, it is the closest ancestor
  struct sort_t { CgenNodeP nd; branch_class* br; };
  std::vector<sort_t> v;
  for(int i = this->cases->first(); this->cases->more(i); i = this->cases->next(i)) {
    branch_class* br = dynamic_cast<branch_class*>(this->cases->nth(i));
    CgenNodeP nd = clsenv->lookup(br->type_decl);
    v.push_back({nd, br});
  }
  std::sort(v.begin(), v.end(), [](sort_t a, sort_t b) -> bool {
    return (a.nd->get_ub_child() - a.nd->get_classtag())
      < (b.nd->get_ub_child() - b.nd->get_classtag());
  });

  emit_label_def(lbl_beg, s);
  emit_load(T1, 0, ACC, s);
  int lbl_nxt;
  for(auto a: v) {
    if (cgen_debug) {
      cout << "branch in case at line #" << this->line_number << endl;
      cout << "  type = " << a.nd->name->get_string() << endl;
    }
    lbl_nxt = label_cnt++;
    emit_blti(T1, a.nd->get_classtag(), lbl_nxt, s);
    emit_bgti(T1, a.nd->get_ub_child(), lbl_nxt, s);
    varenv->enterscope();
    varenv->addid(a.br->name, new (MemAddr){ FP, sp });
    --sp;
    emit_push(ACC, s);
    a.br->expr->code(s, label_cnt, so, varenv, sp);
    emit_addiu(SP, SP, 4, s);
    ++sp;
    varenv->exitscope();
    emit_branch(lbl_end, s);
    emit_label_def(lbl_nxt, s);
  }
  // mismatch, abort
  emit_jal("_case_abort", s);
  emit_label_def(lbl_end, s);
  if (cgen_debug) { cout << "case at line #" << this->line_number << " successfully coded. " << endl; }
}

void block_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  for(int i = this->body->first(); this->body->more(i); i = this->body->next(i)) {
    Expression expr = this->body->nth(i);
    expr->code(s, label_cnt, so, varenv, sp);
  }
}

void let_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  if (cgen_debug) { cout << "let at line #" << this->line_number << endl; }
  this->init->code(s, label_cnt, so, varenv, sp);
  varenv->enterscope();
  varenv->addid(this->identifier, new (MemAddr){ FP, sp });
  --sp;
  emit_push(ACC, s);
  this->body->code(s, label_cnt, so, varenv, sp);
  emit_addiu(SP, SP, 4, s);
  ++sp;
  varenv->exitscope();
  if (cgen_debug) { cout << "let at line #" << this->line_number << " successfully coded. " << endl; }
}

void plus_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_jal("Object.copy", s);
  emit_move(T2, ACC, s);
  emit_load(ACC, &tmp, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);

  emit_load(T1, 3, ACC, s);
  emit_move(ACC, T2, s);
  emit_load(T2, 3, T2, s);
  emit_add(T1, T1, T2, s);
  emit_store(T1, 3, ACC, s);
}

void sub_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_jal("Object.copy", s);
  emit_move(T2, ACC, s);
  emit_load(ACC, &tmp, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);
  
  emit_load(T1, 3, ACC, s);
  emit_move(ACC, T2, s);
  emit_load(T2, 3, T2, s);
  emit_sub(T1, T1, T2, s);
  emit_store(T1, 3, ACC, s);
}

void mul_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_jal("Object.copy", s);
  emit_move(T2, ACC, s);
  emit_load(ACC, &tmp, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);
  
  emit_load(T1, 3, ACC, s);
  emit_move(ACC, T2, s);
  emit_load(T2, 3, T2, s);
  emit_mul(T1, T1, T2, s);
  emit_store(T1, 3, ACC, s);
}

void divide_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_jal("Object.copy", s);
  emit_move(T2, ACC, s);
  emit_load(ACC, &tmp, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);
  
  emit_load(T1, 3, ACC, s);
  emit_move(ACC, T2, s);
  emit_load(T2, 3, T2, s);
  emit_div(T1, T1, T2, s);
  emit_store(T1, 3, ACC, s);
}

void neg_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  emit_jal("Object.copy", s);
  emit_load(T1, 3, ACC, s);
  emit_neg(T1, T1, s);
  emit_store(T1, 3, ACC, s);
}

void lt_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_load(T2, 3, ACC, s);
  emit_load(ACC, &tmp, s);
  emit_load(T1, 3, ACC, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);

  int lbl_tbr = label_cnt++;
  int lbl_end = label_cnt++;
  emit_blt(T1, T2, lbl_tbr, s);
  // false branch
  emit_load_bool(ACC, BoolConst(0), s);
  emit_branch(lbl_end, s);
  // true branch
  emit_label_def(lbl_tbr, s);
  emit_load_bool(ACC, BoolConst(1), s);
  emit_label_def(lbl_end, s);
}

void eq_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_move(T2, ACC, s);
  emit_load(T1, &tmp, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);

  int lbl_end = label_cnt++;
  s << LA << ACC << " "; BoolConst(1).code_ref(s); s << endl;
  emit_beq(T1, T2, lbl_end, s);
  s << LA << A1 << " "; BoolConst(0).code_ref(s); s << endl;
  emit_jal("equality_test", s);
  emit_label_def(lbl_end, s);
}

void leq_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  // Save temp
  emit_push(ACC, s);
  MemAddr tmp = { FP, sp };
  --sp;
  this->e2->code(s, label_cnt, so, varenv, sp);
  emit_load(T2, 3, ACC, s);
  emit_load(ACC, &tmp, s);
  emit_load(T1, 3, ACC, s);
  // pop
  ++sp;
  emit_addiu(SP, SP, 4, s);

  int lbl_tbr = label_cnt++;
  int lbl_end = label_cnt++;
  emit_bleq(T1, T2, lbl_tbr, s);
  // false branch
  emit_load_bool(ACC, BoolConst(0), s);
  emit_branch(lbl_end, s);
  // true branch
  emit_label_def(lbl_tbr, s);
  emit_load_bool(ACC, BoolConst(1), s);
  emit_label_def(lbl_end, s);
}

void comp_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  emit_load(ACC, 3, ACC, s);
  int lbl_tbr = label_cnt++;
  int lbl_end = label_cnt++;
  emit_bne(ACC, ZERO, lbl_tbr, s);
  // false branch
  emit_load_bool(ACC, BoolConst(1), s);
  emit_branch(lbl_end, s);
  // true branch
  emit_label_def(lbl_tbr, s);
  emit_load_bool(ACC, BoolConst(0), s);
  emit_label_def(lbl_end, s);
}

void int_const_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp)  
{
  //
  // Need to be sure we have an IntEntry *, not an arbitrary Symbol
  //
  emit_load_int(ACC,inttable.lookup_string(token->get_string()),s);
}

void string_const_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp)
{
  emit_load_string(ACC,stringtable.lookup_string(token->get_string()),s);
}

void bool_const_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp)
{
  emit_load_bool(ACC, BoolConst(val), s);
}

void new__class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  s << LA << ACC << " "; emit_protobj_ref(this->type_name, s); s << endl;
  emit_jal("Object.copy", s);
  s << JAL << " "; emit_init_ref(this->type_name, s); s << endl;
}

void isvoid_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  this->e1->code(s, label_cnt, so, varenv, sp);
  int lbl_tbr = label_cnt++;
  int lbl_end = label_cnt++;
  emit_beqz(ACC, lbl_tbr, s);
  // false branch
  emit_load_bool(ACC, BoolConst(0), s);
  emit_branch(lbl_end, s);
  // true branch
  emit_label_def(lbl_tbr, s);
  emit_load_bool(ACC, BoolConst(1), s);
  emit_label_def(lbl_end, s);
}

void no_expr_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
}

void object_class::code(ostream& s, int& label_cnt, CgenNode* so, SymbolTable<Symbol, MemAddr>* varenv, int& sp) {
  if(this->name->equal_string("self", 4)) {
    emit_move(ACC, SELF, s);
  } else {
    MemAddr* ma = varenv->lookup(this->name);
    emit_load(ACC, ma, s);
  }
}