代码优化文档

乘法优化

有如下几种情况：

• 乘以0 rd寄存器直接赋0
• 乘以1 把rs寄存器move到rd寄存器
• 乘以2的幂：改为sll语句
• 其他按普通乘法处理

关键代码：

if (m == 1) {
    if (rd != reg1) {
        new MoveText(rd, reg1);
    }
} else if (m == 0) {
    new LiText(rd, 0);
} else if ((m & (m - 1)) == 0) { // 2的幂
    int k = 0;
    while ((m & (1 << k)) == 0) {
        k++;
    }
    new ALUText(ALUText.Op.SLL, rd, reg1, k);
} else {
    new LiText(reg2, m); // 重新加载operand2
    new MDText(MDText.Op.MULT, reg1, reg2);
    new MFText(MFText.MFType.MFLO, rd);
}

除法优化

不能简单地把2的幂翻译成srl（会有溢出问题），因此我按照讲座里给出的公式来算

关键代码：

if (d == 1) {
    if (rd != reg1) {
        new MoveText(rd, reg1);
    }
} else if ((d & (d - 1)) == 0){ // 2的幂
    // 使用公式：reg1/d= SRA(reg1 + SRL(SRA(reg1, k − 1), 32 − k), k)
    int k = 0;
    while ((d & (1 << k)) == 0) {
        k++;
    }
    new ALUText(ALUText.Op.SRA, reg2, reg1, k - 1);
    new ALUText(ALUText.Op.SRL, reg2, reg2, 32 - k);
    new ALUText(ALUText.Op.ADDU, reg2, reg2, reg1);
    new ALUText(ALUText.Op.SRA, rd, reg2, k);
} else {
    // 处理一般情况 d > 0 且非 2 的幂
    int N = 31; // 假设常量位数为 32 位
    long m = 0;
    int l = 0;
    // 确定 m 和 l
    while (true) {
        l++;
        m = (long) Math.ceil((double) (1L << (N + l)) / d);
        if (m * d <= (1L << (N + l)) + (1L << l)) {
            break; // 满足条件，退出循环
        }
    }
    if (m < (1L << N)) {
        // 使用公式: SRA(MULSH(m, n), l − 1) + SRL(n, 31)
        new LiText(reg2, (int) m);
        new MDText(MDText.Op.MULT, reg1, reg2);
        new MFText(MFText.MFType.MFHI, reg2);

        new ALUText(ALUText.Op.SRA, reg2, reg2, l - 1);
        new ALUText(ALUText.Op.SRL, reg1, reg1, 31);
        new ALUText(ALUText.Op.ADDU, rd, reg2, reg1);
    } else {
        // 使用公式: SRA(n + MULSH(m − 2^32, n), l − 1) + SRL(n, 31)
        m -= (1L << 32);
        new LiText(reg2, (int) m);
        new MDText(MDText.Op.MULT, reg1, reg2);
        new MFText(MFText.MFType.MFHI,reg2);

        new ALUText(ALUText.Op.ADDU, reg2, reg2, reg1);
        new ALUText(ALUText.Op.SRA, reg2, reg2, l - 1);
        new ALUText(ALUText.Op.SRL, reg1, reg1, 31);

        new ALUText(ALUText.Op.ADDU, rd, reg2, reg1);
    }
}

基本块合并

若一个基本块无条件跳转到它的下一个基本块，且下一个基本块只有一个前驱，那么可以直接合并这两个基本块，省去跳转指令。

关键代码：

while (bbIter.hasNext()) {
    BasicBlock curBB = bbIter.next();
    if (prevBB.getInstrs().getLast() instanceof BR br && br.isUncondition() && br.getDest() == curBB
            && curBB.getUsers().size() == 1) { // curBB只有preBB一个前驱
        prevBB.removeInstr(br);
        for (Instruction instr : curBB.getInstrs()) {
            prevBB.addInstr(instr);
            instr.setItsBB(prevBB);
        }
        bbIter.remove();
    } else {
        prevBB = curBB;
    }
}