编译原理

Lab3 Report

2020-05-14 00:00 CST
2020-05-22 14:10 CST
CC BY-NC 4.0

1. 文件结构

本次新增的内容如下:

  • ir.c:中间代码翻译器,名称前缀IR
  • opt.c:中间代码优化器,名称前缀OC

2. 中间代码生成

中间代码的存储采用线性三地址代码,用双向链表串起来。

由于上次实验采用了Functional Style,因此一旦在语法分析过程中离开了CompSt,当前局部作用域的符号表就会被弹出销毁,所以我采取了如下的翻译方案:

  • 首先按顺序遍历语法树,先完成符号表的生成;
  • CompSt结尾处即将弹出符号表时,翻译这一段CompSt的代码,并将代码的首尾地址注入到语法树中;
  • 显然深层的代码先被翻译,而当递归回溯到上层的CompSt时,可以直接从语法树中提取处下层的CompSt代码连接到上层的代码中去;
  • 最后回溯到最上层的FunDec,直接在头部加上声明函数和参数的中间代码,最后再加上一个防止错误的RETURN #0,挂到全局代码链表中去就可以了。

2.1 函数接口

IRCodePair IRTranslateExp(STNode *exp, IROperand place, bool deref);
  • 函数参数:
    • STNode *exp:当前语法树结点;
    • IROperand place:将运算得到的结果保存到哪里(如果为IR_OP_NULL就不保存了);
    • bool deref:是否需要对结果进行解引用(仅限数组/结构体)。
  • 函数返回值:
    • struct IRCodeList list:翻译得到的代码段;
    • struct SEType *typeplace中的值的类型或其所指内存单元中的类型;
    • bool addr:放入place的是一个地址还是值。

2.2 内存访问

不支持将内存作为操作数进行运算(仿mips特性?),所以有单独的加载/保存中间代码类型,必须先把操作数读出来在进行运算/运算完再保存。在优化时非常的保守,只对LOAD指令进行一点点优化。

2.3 数组拷贝

给每个运算分量都记录了类型和内存大小,以此实现了一个简陋的memcpy(在ir.c的227行附近),就是插入了如下的中间代码:

iter = 0
LABEL loop:
temp = *t1
*addr = temp
t1 += 4
addr += 4
iter += 4
if iter < size GOTO loop

3. 中间代码优化

代码优化共分为四步:

  1. 首先替换所有的常量,如下面的t1 := 2 + 3可以直接替换成t1 := 5
  2. 然后替换所有的变量,如下面的t1 := v1可以在之后的代码中把t1直接替换成v1
  3. 接着反向遍历所有的中间代码,对一些重要的变量(跳转条件、存储地址等)做出标记,防止这些代码在优化时被删除;
  4. 最后再次反向遍历所有的中间代码,删除所有不活跃变量的计算。

在实现代码优化时采用了比较保守的方式,前两步中每遇到一个FUNCTIONLABEL,所有可替换的常量/变量值都会失效(通过时间戳实现了$O(1)$操作);第三步中会被使用的变量都被标记为重要,且重要变量的依赖也是重要的,具有传递性,防止误删关键变量导致程序出错。

4. 实验中遇到的困难与致谢

遇到的困难:被迫内卷,卷不动了,我放弃

致谢:董杨静同学的测试仓库、欧先飞大佬的C++ IRSim和大家贡献的测试样例。