README

这是北航编译原理课程的课设分享

如果是不打算采取SSA的同学可以参考本人的设计

该编译器性能与采用了SSA的同学性能不相上下甚至略高

采用了直接且暴力的手段进行了性能优化

中间代码翻译阶段问题汇总

• 函数如何调用？如何传回返回值？
  1. 函数调用前，先将参数依次放入当前栈帧，然后跳转到函数开头位置。
  2. 为被调用函数过程创建新的栈帧，存储所有调用者的S寄存器及$ra寄存器，保存现场。
  3. 被调用函数执行自己的功能。
  4. 被调用函数完成自己的功能。
  5. 被调用函数清除自己的栈帧，并且清除调用者传入的参数栈，恢复调用者现场，将结果放在寄存器中返回。
  6. 一个函数的栈帧通常存储的都是该函数声明的变量
  7. 函数调用的参数传递用不用专用寄存器$a1、$a2、$a3、$a4？
  8. 保存和恢复现场的时候是否只需要保存和恢复该函数所用到的寄存器即可？如何在进入函数前就预测到？
     • 显然不能预知，等优化吧（笑
• 数组变量如何处理？一维数组，二维数组……
  • 对于变量类型匹配，只考虑维度
  • 对于数组类型，其存储的值为其初始化时的首地址、维度信息、名称
  • 数组变量初始化声明时，在当前栈中申请对应长度的空间
  • 初始化和赋值不完全相同，初始化时支持用数组赋值，赋值时仅支持Exp。因此在初始化时考虑数组整体赋值，而在赋值时仅考虑用Exp进行数组元素的赋值。
  • 在赋值语句中，将多维数组看作一维数组处理，这意味着操作数分别为数组对象和其一维化后的偏移总量
  • 将数组传入函数时，传递的实际是其首地址。
  • 对数组对象进行操作时，可以发现我们均仅需其首地址即可。
• printf如何处理？
  • printf中传入的字符串可以以%d为分割符，将其分为多段，每一段均存储在静态变量区。当调用printf语句时，分别间隔答应每一段，并在其中穿插输出参数值。
• getint()如何处理？
  • 提前将getint()函数的实现放在开头，然后将其当作普通函数处理
• 在从中间代码向汇编代码生成时，比如Add a b c，如何把a、b、c替换为合适的寄存器？
  • 记录一个类似符号表的栈帧记录器，其中记录了当前作用域下每个变量的存储地址
  • 记录一个全局的变量-寄存器字典和一个局部的变量-寄存器字典
  • 对变量a，先在全局找a，如果找到a对应寄存器，就用；如果没找到，则从栈帧记录器中提取出变量地址后，申请一个寄存器存放。

数组的若干问题

1. 程序中的数组是什么？
   • 是符号项的类型，符号项的类型就是变量的类型
     • 操作集合：判断类型是否一致，甄别不同四元组操作
     • ArrayType是DataType的子类
     • ArrayType需要指明基本类型和维度情况
   • 一个数组的符号项有以下特点：
     • pos：指向的空间只有一个整型大小，该位置存储一个指向数组实际空间的值。
     • 注意pos指向的是该变量存储的位置，而其值指向的是该数组实际存储的位置。
     • 实际上和普通符号项VarEntry基本结构一致，只是存储的值从语义上有区别
   • 是物理存储结构，即数组如何在汇编程序中存储
     • 操作集合：全局初始化赋值，全局赋值，局部赋值，局部取值，全局取值
     • NArray承担的角色是，将程序AST中的语法元素解析为接近物理存储结构的数组对象的中介类型
     • NArray包含一个ArrayType对象用于指示其维度类型
     • NArray中以线性方式存储一个空间
     • 全局初始化赋值时，先按照初始化值生成一个NArray对象，然后将该NArray对象映射到栈中指定位置（语法中只允许在初始化时使用数组赋值），然后生成一个数组符号项，将其值设置为该空间的起始地址。NArray的元素存在以下情况，要么是常数，要么是变量表达式
     • 局部赋值时，数组对象不能作为左值，因此左值一定是数组的最底层元素，即基本类型的普通变量，使用的value值一定也是普通变量或常数（实际转变为临时变量）。用一个四元式能够将指定变量赋值给数组中指定位置的元素。VarEntry -> ArrayEntry[Pos]
     • 局部取值时，按照读取时的指示变量，创建一个新的符号项tmp并返回。注意数组对象局部取值时生成的tmp对象，做一个局部变量处理，即完整地进行变量声明、变量初始化。如果取值得到的是基本元素，那么得到的变量是一个普通变量，其pos，其值即为其真正值，是从原数组空间复制过来的；如果取值得到的是一个数组变量，其值为数组的对应物理起始地址。这里需要一个四元式能够完成从数组中取出一个数组变量，一个四元式能够从数组中取出一个普通变量。AbsVarEntry <- ArrayEntry[Pos]
     • 数组对象传递时，直接传递符号项。对于局部取值传递，传递的符号项是tmp变量
     • 全局取值时，直接返回当前符号项
2. 数组的物理存储结构：
   • 初始化定义时分配空间
   • 符号项中存储的值是其起始位置

函数调用

1. 函数的定义一定在全局块中

2. 函数如何调用？

   • 直接跳转：jump后从v寄存器取出值

3. 函数如何传值？

   • 先push参数，将其按次序放进栈中
   • 然后Call函数跳转到函数内部
   • 函数内部首先需要Def所有参数，即在符号表中建立对应变量并在栈中申请空间，然后通过传入的实参完成赋值。

4. 函数如何返回值？

   • 返回值一定是VarEntry

   • 将VarEntry赋值到v寄存器

翻译中间代码时

每进入一个函数Scope，则将通过移动$sp将所有需要的局部变量的空间alloc出来

• 所有变量，包括数组空间和中间变量空间
• 之后的一切操作，均从内存中获取变量。寄存器仅在单个语句范围中使用。
• 对于每个Scope记录其局部变量名称到其偏移的映射关系。
• 对于每个局部变量，其同时需要记录名称和其对应的Scope名称

移动sp后，还需要将指定的数组符号项进行赋值，即将数组符号项的内容赋值为申请的空间的地址。

函数定义时，在解析参数时，将参数放入当前函数的Scope符号表时，注意其处在$ra之前，$ra之后才是函数内部的其他局部变量和临时变量。

函数传递参数时，通过push方式向当前栈指针$sp的下方压入值（而不改变$sp）。跳转后，由函数自己扩展栈。

一个函数的栈如何管理？

• 在进行FuncDef时，记录所有该函数内的Scope中的符号表项，并且加上函数参数列表中的符号表项，形成属于这个Func的栈帧对象。
• 在生成目标代码时，统一通过Func的栈帧对象初始化栈帧空间。
• 当进入某个Scope后，我们遇到一个变量a，首先查Scope表，找到a的对应符号表项ae，然后用ae去当前栈帧空间内找到对应地址。
• 栈帧对象需要记录符号表项到偏移的映射，因此上一步中，我们进一步获得了a相对于栈帧的偏移量。
• 栈帧在初始化后，$sp就是指着该栈帧的最底部，因此可以通过偏移+$sp来获得a的实际地址

使用FuncRegion来同时描述当前函数的栈帧和相对于的所有中间代码。每个FuncRegion无法相互访问，然而同时共享一个全局变量声明块。

全局变量的声明有异于其他所有变量，其不从属于任何FuncRegion，而是由全局所共用。

当任意语句访问到某个变量声明时，首先检查其是否是全局变量，如果是，则从全局块进行加载；否则，则从该语句所属的FuncRegion的Frame对象加载。

判断一个变量是否是全局变量的依据是其符号表项所属的Scope的level = 0

运行时栈和寄存器管理

生成目标代码时，我们需要将中间代码翻译为实际目标代码。

当我们遇到一个未分配寄存器的变量时，我们从空闲寄存器中向其分配一个寄存器，并记录下来（RegMap）。

如果此时没有空闲寄存器，则触发替换。假设我们随机选中一个寄存器R，其已经被分配给变量V，我们建立一个MemMap，然后将寄存器R的值存入栈中，然后将栈中地址和变量V放入MemMap中，然后将寄存器R空出来。如果我们后续又访问到V中取值，则向其分配一个寄存器，然后根据MemMap将其取出。

RegMap和MemMap都是针对一个栈帧而言的。每个栈帧维护着自己的两个Map。

一个栈帧对应一个{}，即我们的Scope。注意以下情况：

int main() {
  int a = 10;
  int b = 10;
  {
    int a;
    a = 100;
    b = 100;
  }
  return 0;
}

上述在内层Scope中，存在两个a定义。实际上，我们区分两个变量是否是同一个，需要同时考虑其所属的Scope和其名称。

考虑上述代码分析过程，我们首先中外层scope定义了ab两个变量，然后进入内层后，再一次定义了a。在a=100时找到的是内层Scope的a而不是外层Scope的a。

当我们遇到一个已经被分配了寄存器的普通变量时，我们认为赋值和取值都是针对它进行。

优化阶段工作

主要采用的优化方式为流图分析，其主要优化逻辑写在improve.component.FlowGraph中

• 全局优化

  • 局部常量传播

  • 全局公共表达式消除

  • 全局复制传播

• 窥孔优化

  • 条件跳转优化

  • 死代码优化

  • 立即赋值优化

• 循环优化

  • 删除无效循环

目标代码生成时采用了图着色算法进行寄存器分配，其逻辑位于improve.component.regpool下，其对性能提升影响显著

目标代码生成关键在于除法优化，其优化逻辑位于imcode.imexp.DivExp，其对性能提升影响显著