2024-06-23 编译原理实验5——目标代码生成

文章目录

- 一、实验要求
- 二、实验设计
- 三、实验结果
- 四、附完整代码

补录与分享本科实验，以示纪念。

一、实验要求

在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C−−源代码翻译为MIPS32指令序列（可以包含伪指令），并在 SPIM Simulator上运行。
当你完成之后，你就拥有了一个自己独立编写、可以实际运行的编译器。

基本要求
将中间代码正确转化为MIPS32汇编代码。
“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。
附加要求
1. 对寄存器分配进行优化，如使用局部寄存器分配办法等。
2. 对指令进行优化
化简要求
1. 寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的正常运行，可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。
2. 栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。甚至可以使用栈以外的方式对过程调用间各种数据的传递进行管理，前提是输出的目标代码“正确”。

本实验只实现了基本要求，没有实现附加要求。

二、实验设计

此次实验在原先的基础上新增加了dst_code.c和dst_code.h文件，用于将中间代码转换成目标代码。

1、程序的数据结构

typedef struct Variable {char name[32];int offset;
} Variable;static IrNode *head;
FILE *fp;
static int argCount = 0;
static int size = 0;
static int count = 0;
// 变量表
static Variable table[1024];

可以看出，我们定义了IR的变量结构，使用数组的形式进行存储（table）。同时使用全局变量记录当前正在处理的函数参数个数argCount，大小size和变量个数count。

2、getOffset
根据变量名获取偏移位置。

/*** 常数返回-1* *&开头，不看开头* 在table里找名字，返回offset* @param name* @return*/
int getOffset(char *name) {if (name[0] == '#')return -1;if (name[0] == '*' || name[0] == '&')name++;for (int i = 0; i < count; i++) {if (strcmp(name, table[i].name) == 0)return table[i].offset;}return -1;
}

3、addVar
往变量表table里加一个变量variable

/*** 往table里加一个variable* @param name* @param sz*/
void addVar(char *name, int sz) {if (name[0] == '#')return;if (name[0] == '*' || name[0] == '&')name++;if (getOffset(name) != -1)return;table[count].offset = size;size += sz;strcpy(table[count].name, name);count++;
}

4、prepareReg
根据不同情况准备一个寄存器。

void prepareReg(char *name, int num) {char temp[8];sprintf(temp, "$t%d", num);if (name[0] == '*') {// 第一步：把相对栈顶偏移loc的位置的值赋给tempfprintf(fp, "  lw %s, %d($sp)\n", temp, getOffset(name));// 第二步：将temp的值与$sp地址相加结果存入tempfprintf(fp, "  add %s, %s, $sp\n", temp, temp);// 第三步：使用temp中的最终地址找到实际要找的值fprintf(fp, "  lw %s, 0(%s)\n", temp, temp);}else if (name[0] == '&') {// 将name的地址存到t寄存器中fprintf(fp, "  li %s, %d\n", temp, getOffset(name));}else if (name[0] == '#') {// 存常数fprintf(fp, "  li %s, %s\n", temp, &name[1]);}else {// 普通变量从栈里拿fprintf(fp, "  lw %s, %d($sp)\n", temp, getOffset(name));}
}

5、genOneFunction
处理每一个函数的步骤，在这里我们以函数为单位进行处理

void genOneFunction(IrNode *begin, IrNode *end) {count = 0;size = 0;argCount = 0;// 输出函数fprintf(fp, "\n%s:\n", begin->args[1]);// 第一次处理，产生变量表IrNode *p = begin->next;while (p != end) {switch (p->argsNum) {case 2: {if (strcmp("GOTO", p->args[0]) != 0)addVar(p->args[1], 4);break;}case 3: {if (strcmp(p->args[1], ":=") == 0) {addVar(p->args[0], 4);addVar(p->args[2], 4);}else if (strcmp(p->args[0], "DEC") == 0) {int a = strtol(p->args[2], NULL, 10);addVar(p->args[1], a);}break;}case 4: {addVar(p->args[0], 4);break;}case 5: {addVar(p->args[0], 4);addVar(p->args[2], 4);addVar(p->args[4], 4);break;}case 6: {addVar(p->args[1], 4);addVar(p->args[3], 4);break;}default:break;}p = p->next;}// 更改栈顶指针位置fprintf(fp, "  addi $sp, $sp, -%d\n", size);// 第二次处理，生成代码p = begin->next;while (p != end) {switch (p->argsNum) {case 2: {// GOTO xif (strcmp(p->args[0], "GOTO") == 0) {fprintf(fp, "  j %s\n", p->args[1]);}// RETURN xelse if (strcmp(p->args[0], "RETURN") == 0) {prepareReg(p->args[1], 0);fprintf(fp, "  move $v0, $t0\n");fprintf(fp, "  addi $sp, $sp, %d\n", size);fprintf(fp, "  jr $ra\n");}// ARG xelse if (strcmp(p->args[0], "ARG") == 0) {prepareReg(p->args[1], 0);fprintf(fp, "  move $a%d, $t0\n", argCount);argCount++;}// PARAM xelse if (strcmp(p->args[0], "PARAM") == 0) {int para_count = 0;IrNode *q = p;while (strcmp(q->next->args[0], "PARAM") == 0) {q = q->next;para_count++;}fprintf(fp, "  sw $a%d, %d($sp)\n", para_count, getOffset(p->args[1]));}// READ xelse if (strcmp(p->args[0], "READ") == 0) {// 保存上下文环境fprintf(fp, "  addi $sp, $sp, -4\n");fprintf(fp, "  sw $ra, 0($sp)\n");fprintf(fp, "  jal read\n");fprintf(fp, "  lw $ra, 0($sp)\n");fprintf(fp, "  addi $sp, $sp, 4\n");if (p->args[1][0] == '*') {// 类似 prepareRegfprintf(fp, "  lw $t0, %d($sp)\n", getOffset(p->args[1]));fprintf(fp, "  add $t0, $t0, $sp\n");fprintf(fp, "  sw $v0, 0($t0)\n");}elsefprintf(fp, "  sw $v0, %d($sp)\n", getOffset(p->args[1]));}// WRITE xelse if (strcmp(p->args[0], "WRITE") == 0) {prepareReg(p->args[1], 0);// 获取参数fprintf(fp, "  move $a0, $t0\n");// 保存上下文环境fprintf(fp, "  addi $sp, $sp, -4\n");fprintf(fp, "  sw $ra, 0($sp)\n");fprintf(fp, "  jal write\n");fprintf(fp, "  lw $ra, 0($sp)\n");fprintf(fp, "  addi $sp, $sp, 4\n");}break;}case 3: {// x := yif (strcmp(p->args[1], ":=") == 0) {prepareReg(p->args[2], 0);if (p->args[0][0] == '*') {// 同 prepareRegfprintf(fp, "  lw $t1, %d($sp)\n", getOffset(p->args[0]));fprintf(fp, "  add $t1, $t1, $sp\n");fprintf(fp, "  sw $t0, 0($t1)\n");}else {fprintf(fp, "  sw $t0, %d($sp)\n", getOffset(p->args[0]));}}// DEC x [size]else if (strcmp(p->args[0], "DEC") != 0) {fprintf(fp, "%s:\n", p->args[1]);}break;}case 4: {// x := CALL fargCount = 0;fprintf(fp, "  addi $sp, $sp, -4\n");fprintf(fp, "  sw $ra, 0($sp)\n");fprintf(fp, "  jal %s\n", p->args[3]);fprintf(fp, "  lw $ra, 0($sp)\n");fprintf(fp, "  addi $sp, $sp, 4\n");if (p->args[0][0] == '*') {fprintf(fp, "  lw $t0, %d($sp)\n", getOffset(p->args[0]));fprintf(fp, "  add $t0, $t0 ,$sp\n");fprintf(fp, "  sw $v0, 0($t0)\n");}elsefprintf(fp, "  sw $v0, %d($sp)\n", getOffset(p->args[0]));break;}case 5: {prepareReg(p->args[2], 0);prepareReg(p->args[4], 1);// x := y + z    x := y - z    x := y * z    x := y / zswitch (p->args[3][0]) {case '+': {fprintf(fp, "  add $t0, $t0, $t1\n");break;}case '-': {fprintf(fp, "  sub $t0, $t0, $t1\n");break;}case '*': {fprintf(fp, "  mul $t0, $t0, $t1\n");break;}case '/': {fprintf(fp, "  div $t0, $t1\n");fprintf(fp, "  mflo $t0\n");break;}default:;}if (p->args[0][0] == '*') {fprintf(fp, "  lw $t1, %d($sp)\n", getOffset(p->args[0]));fprintf(fp, "  add $t1, $t1, $sp\n");fprintf(fp, "  sw $t0, 0($t1)\n");}elsefprintf(fp, "  sw $t0, %d($sp)\n", getOffset(p->args[0]));break;}case 6: {// if x [relop] y GOTO zchar temp[4];if (strcmp(p->args[2], "==") == 0)strcpy(temp, "beq");else if (strcmp(p->args[2], "!=") == 0)strcpy(temp, "bne");else if (strcmp(p->args[2], ">") == 0)strcpy(temp, "bgt");else if (strcmp(p->args[2], "<") == 0)strcpy(temp, "blt");else if (strcmp(p->args[2], ">=") == 0)strcpy(temp, "bge");else if (strcmp(p->args[2], "<=") == 0)strcpy(temp, "ble");prepareReg(p->args[1], 0);prepareReg(p->args[3], 1);fprintf(fp, "  %s $t0, $t1, %s\n", temp, p->args[5]);break;}default:break;}p = p->next;}
}

6、genDstCode
首先生成read函数和write函数的目标代码，然后使用genOneFunction处理每一个函数。

void genDstCode(IrNode *h, FILE *f) {head = h;fp = f;fprintf(fp, "%s\n", ".data");fprintf(fp, "%s\n", "_prompt: .asciiz \"Enter an integer:\"");fprintf(fp, "%s\n", "_ret: .asciiz \"\\n\"");fprintf(fp, "%s\n", ".globl main");fprintf(fp, "%s\n", ".text");fprintf(fp, "%s\n", "read:");fprintf(fp, "  %s\n", "li $v0, 4");fprintf(fp, "  %s\n", "la $a0, _prompt");fprintf(fp, "  %s\n", "syscall");fprintf(fp, "  %s\n", "li $v0, 5");fprintf(fp, "  %s\n", "syscall");fprintf(fp, "  %s\n", "jr $ra");fprintf(fp, "\n");fprintf(fp, "%s\n", "write:");fprintf(fp, "  %s\n", "li $v0, 1");fprintf(fp, "  %s\n", "syscall");fprintf(fp, "  %s\n", "li $v0, 4");fprintf(fp, "  %s\n", "la $a0, _ret");fprintf(fp, "  %s\n", "syscall");fprintf(fp, "  %s\n", "move $v0, $0");fprintf(fp, "  %s\n", "jr $ra");IrNode *p = head, *q;do {// 定位函数q = p->next;while (1) {if (strcmp(q->args[0], "FUNCTION") == 0 || q == head) break;q = q->next;}// 分析函数genOneFunction(p, q);p = q;} while (p != head);
}

三、实验结果

test1.c

int main()
{int a = 0, b = 1, i = 0, n;n = read();while (i < n) {int c = a + b;write(b);a = b;b = c;i = i + 1;}return 0;
}

执行目标代码生成：

目标代码：

.data
_prompt: .asciiz "Enter an integer:"
_ret: .asciiz "\n"
.globl main
.text
read:li $v0, 4la $a0, _promptsyscallli $v0, 5syscalljr $rawrite:li $v0, 1syscallli $v0, 4la $a0, _retsyscallmove $v0, $0jr $ramain:addi $sp, $sp, -20li $t0, 0sw $t0, 0($sp)li $t0, 1sw $t0, 4($sp)li $t0, 0sw $t0, 8($sp)addi $sp, $sp, -4sw $ra, 0($sp)jal readlw $ra, 0($sp)addi $sp, $sp, 4sw $v0, 12($sp)
label0:lw $t0, 8($sp)lw $t1, 12($sp)blt $t0, $t1, label1j label2
label1:lw $t0, 0($sp)lw $t1, 4($sp)add $t0, $t0, $t1sw $t0, 16($sp)lw $t0, 4($sp)move $a0, $t0addi $sp, $sp, -4sw $ra, 0($sp)jal writelw $ra, 0($sp)addi $sp, $sp, 4lw $t0, 4($sp)sw $t0, 0($sp)lw $t0, 16($sp)sw $t0, 4($sp)lw $t0, 8($sp)li $t1, 1add $t0, $t0, $t1sw $t0, 8($sp)j label0
label2:li $t0, 0move $v0, $t0addi $sp, $sp, 20jr $ra

目标代码执行结果（输入 2）：

test2.c

int fact(int n)
{if (n == 1){return n;}elsereturn (n * fact(n - 1));
}int main()
{int m, result;m = read();if (m > 1)result = fact(m);elseresult = 1;write(result);return 0;
}

执行目标代码生成：

目标代码：

.data
_prompt: .asciiz "Enter an integer:"
_ret: .asciiz "\n"
.globl main
.text
read:li $v0, 4la $a0, _promptsyscallli $v0, 5syscalljr $rawrite:li $v0, 1syscallli $v0, 4la $a0, _retsyscallmove $v0, $0jr $rafact:addi $sp, $sp, -16sw $a0, 0($sp)lw $t0, 0($sp)li $t1, 1beq $t0, $t1, label0j label1
label0:lw $t0, 0($sp)move $v0, $t0addi $sp, $sp, 16jr $raj label2
label1:lw $t0, 0($sp)li $t1, 1sub $t0, $t0, $t1sw $t0, 4($sp)lw $t0, 4($sp)move $a0, $t0addi $sp, $sp, -4sw $ra, 0($sp)jal factlw $ra, 0($sp)addi $sp, $sp, 4sw $v0, 8($sp)lw $t0, 0($sp)lw $t1, 8($sp)mul $t0, $t0, $t1sw $t0, 12($sp)lw $t0, 12($sp)move $v0, $t0addi $sp, $sp, 16jr $ra
label2:main:addi $sp, $sp, -8addi $sp, $sp, -4sw $ra, 0($sp)jal readlw $ra, 0($sp)addi $sp, $sp, 4sw $v0, 0($sp)lw $t0, 0($sp)li $t1, 1bgt $t0, $t1, label3j label4
label3:lw $t0, 0($sp)move $a0, $t0addi $sp, $sp, -4sw $ra, 0($sp)jal factlw $ra, 0($sp)addi $sp, $sp, 4sw $v0, 4($sp)j label5
label4:li $t0, 1sw $t0, 4($sp)
label5:lw $t0, 4($sp)move $a0, $t0addi $sp, $sp, -4sw $ra, 0($sp)jal writelw $ra, 0($sp)addi $sp, $sp, 4li $t0, 0move $v0, $t0addi $sp, $sp, 8jr $ra

目标代码执行结果（输入 5）：

四、附完整代码

github 链接：https://github.com/zheliku/byyl---Target-Code-Generation。