编译技术：目标代码生成

目标代码生成设计

编码前的设计

需求分析

读取生成的 LLVM IR 中间代码，生成对应的 MIPS 目标代码，输出至 mips.txt。

文件组织

新建目录 src\backend\mips，该部分存储 MIPS 的数据结构，其中包含若干目录：

DataAssembly：data 段语句，主要是全局变量和字符串等。
TextAssembly：text 段语句，各种函数的实际语句。
Register：寄存器的枚举类型。

新建类 src\backend\Backend.java，这是后端的“主函数”。

主要思想

完全由中间代码指令对指令翻译过来，这样后续优化只需要对中间代码部分进行，无需考虑目标代码。

编码完成之后的修改

完整文件组织

backend
├── Backend.java
└── mips
    ├── Asm.java // mips顶层模块
    ├── Assembler.java // “主函数”
    ├── Register.java
    └── assembly
        ├── Assembly.java // 汇编指令父类
        ├── data
        │   ├── Align.java // 对齐
        │   ├── Asciiz.java // 字符串
        │   ├── DataAssembly.java
        │   ├── Space.java // 未初始化数组
        │   └── Word.java // 全局变量
        └── text
            ├── Annotation.java // 注释
            ├── Label.java // 跳转标签
            ├── TextAssembly.java
            ├── basic // 基本指令
            │   ├── Alu.java
            │   ├── Branch.java
            │   ├── Compare.java
            │   ├── Jump.java
            │   ├── Lsu.java
            │   ├── Mdu.java
            │   └── Syscall.java
            └── extended // 扩展指令
                ├── La.java
                ├── Li.java
                └── Move.java

栈空间

在 Assembler 中，有一系列处理栈的函数：

public static int allocateStack(int offset)：分配栈，因为规范栈管理是函数头部向 sp 负数处开辟栈空间，后续用正数偏移定位，因此这一步也是减法。

public static Integer hashStack(Value value)：查找栈偏移，在生成代码前首先对所有 LLVM 的虚拟寄存器给了一个栈偏移，这一步就是查找。

public static int getCorrectOffset(int offset)：获取正数偏移，因为 offset 存的都是负的，减去一个正的页框大小即为正偏移。

全局变量转 MIPS

这里的全局变量指的是中间代码生成的 GlobalVariable、StringLiteral。这些类都继承于 DataAssembly。

Word：全局变量或初始化的全局数组，会在前面加上一个 align。

Space：全局未初始化数组，会在前面加上一个 align。

Asciiz：字符串字面量。

Function 转 MIPS

会对整个函数扫描两遍，第一遍：

首先给参数开栈

if (paramValues != null) {  
    for (Value arg : paramValues) {  
        int offset = Assembler.allocateStack(4);  
        Assembler.addStack(arg, offset);  
    }  
}

为返回地址 ra 预留栈空间，main 函数不用

1
2
3

if (!name.equals("main")) {  
    Assembler.allocateStack(4);  
}

每一条有虚拟寄存器的指令都要分配栈空间，如果是 alloca 了一个数组要考虑数组长度

for (BasicBlock basicBlock : basicBlocks) {  
    for (Instruction inst : basicBlock.getInstList()) {  
        if (!inst.getType().equals(ValueType.VOID)) {  
            int size = 4;  
            if (inst instanceof AllocateInst) {  
                AllocateInst alloc = (AllocateInst) inst;  
                size = alloc.getLength() >= 0 ? alloc.getLength() * 4 : size;  
            }  
            int offset = Assembler.allocateStack(size);  
            Assembler.addStack(inst, offset);  
        }  
    }  
}

第一次对整个函数遍历完了之后，现在可以得到页框大小（正数）

1 2	int stackSize = Assembler.getStackOffset(); int frameSize = -stackSize;

第二遍：

添加函数标签

1	new Label(name);

函数开头显式开栈，sp 减小

1
2
3

if (frameSize > 0) {  
    new Alu(Alu.AluType.ADDIU, Register.SP, Register.SP, -frameSize);  
}

参数保存在栈里面，前四个参数在寄存器 a0，a1，a2，a3，多的寄存器在栈帧（当前 sp 的上方），此时并不知道偏移量，需要最后回填偏移量。

if (paramValues != null) {  
    for (int i = 0; i < paramValues.size(); i++) {  
        Value arg = paramValues.get(i);  
        Integer offset = Assembler.hashStack(arg);  
        int trueOffset = Assembler.getCorrectOffset(offset);  
  
        if (i < 4) {  
            new Lsu(Lsu.LsuType.SW, getArgReg(i), Register.SP, trueOffset);  
        } else {  
            Lsu loadFromCaller = new Lsu(Lsu.LsuType.LW, Register.T0, Register.SP, 0);  
            stackParamLoads.add(loadFromCaller);  
            new Lsu(Lsu.LsuType.SW, Register.T0, Register.SP, trueOffset);  
        }  
    }  
}

参数之后是 ra 返回地址

if (!name.equals("main")) {  
    int raOffset = -((paramValues.size() * 4) + 4);  
    int raTrueOffset = Assembler.getCorrectOffset(raOffset);  
    new Lsu(Lsu.LsuType.SW, Register.RA, Register.SP, raTrueOffset);  
    Assembler.setRaOffset(raOffset);  
}

接下来处理具体函数语句

1
2
3

for (BasicBlock basicBlock : basicBlocks) {  
    basicBlock.toMips();  
}

最后回填参数偏移量，这个 16 就是最开始 4 个参数

for (int i = 0; i < stackParamLoads.size(); i++) {  
    Lsu loadInst = stackParamLoads.get(i);  
  
    int offsetInCaller = frameSize + 16 + (i * 4);  
    loadInst.setOffset(offsetInCaller);  
}

Alloca 转 MIPS

什么也不做。

Alu 转 MIPS

都是二元操作，因此将栈内数据移至 t0 和 t1。

1 2	Assembler.loadValueToRegister(op1, Register.T0); Assembler.loadValueToRegister(op2, Register.T1);

这里的函数如下：

public static void loadValueToRegister(Value value, Register target) {  
    if (value instanceof IntConst) {  
        new Li(target, ((IntConst) value).getValue()); // 常数直接 li 到寄存器
    }  
    else if (value instanceof GlobalVariable) {  
        // addr  
        String label = value.getName().substring(1);  
        new La(target, label); // 全局变量是用 label 的地址获取的，需要 la 
    }  
    else if (isDirectAddressing(value)) { // 直接寻址
        int offset = Assembler.getCorrectOffset(Assembler.hashStack(value));  
        new Alu(Alu.AluType.ADDIU, target, Register.SP, offset);  
    }  
    else {  
        // lw  
        int offset = Assembler.getCorrectOffset(Assembler.hashStack(value));  
        new Lsu(Lsu.LsuType.LW, target, Register.SP, offset); // 一般情况，从栈内 lw 
    }  
}

将结果存入 t2，同时乘除模指令还涉及 mflo、mfhi。

Branch 转 MIPS

有条件跳转，首先将 cond 的结果放进 t0，然后跳转至对应的基本块：

String trueLabel = ((BasicBlock) trueBlock).getLabel();  
new Branch(Branch.BranchType.BNE, Register.T0, Register.ZERO, trueLabel);  
String falseLabel = ((BasicBlock) falseBlock).getLabel();  
new Jump(Jump.JumpType.J, falseLabel);

Call 转 MIPS

首先保存参数，开头四个放进 a 寄存器，后面的放进 sp 栈空间。

然后跳转目标函数基本块。

最后把 v0 的返回值移到栈上。

Compare 转 MIPS

和 alu 几乎是一模一样的，也是二元操作，t0 和 t1，结果放 t2。

Extend 转 MIPS

这里在 llvm 中的行为是将一个虚拟寄存器的内容移到了另一个，因此这里也需要链接一下，但是 mips 中并没有清晰的数据类型，所以实际上可以不生成指令，直接在 map 中映射一下。后期可以优化。

Gep 转 MIPS

基地址存在 t0，偏移存在 t1，真实地址存在 t2。然后 t2 存进对应的结果的栈空间。

Jump 转 MIPS

直接使用 j 指令。

Load 转 MIPS

结果 lw 进 t0，t0 存进对应栈空间。

Return 转 MIPS

如果是 main 函数，syscall 一下。

普通函数，返回值移到 v0，返回地址移到 ra，把 sp 加上页框大小，再 jr 回 ra 的地址。

Store 转 MIPS

需要将实际目标地址存进 t1，把值存进 t0，然后 sw。

BaconToast's Shop