代码优化

由于时间因素，我只做了以下几种常见的优化。

中端优化

SSA

普通赋值语句通过重命名变量即可

对于较为复杂的，如控制流

引入phi指令实现，其只能放置在基本块开头，且并行执行，即其返回值取决于进入当前基本块时状态。例如：

1
2
3
4
5
6
7
8
9
10
11
12
...
1:
    %2 = icmp eq i32 %0, 42
    br i1 %1, label %3, label %4
3: 
    br label %6
4:
    %5 = add i32 %0, 2
    br label %6
6:
    %7 = phi i32 [1, %3], [%5, %4]
    ret i32 %7

mem2reg:内存引用提升为寄存器引用

理论

将仅被load和store引用的alloca提升为虚拟寄存器。
共分为两步:

  1. 插入phi函数，对某个变量v，原有的v定义和新插入的phi函数将程序分割为多个活跃区间。每个区间以v定义开始且仅有这个定义能到达活跃区间内v的引用。
  2. 变量重命名，对变量的每个活跃区间，重命名变量所有定义和使用，即拆分为不同的变量，其中的定义和使用都唯一对应于一处赋值，这也就是链和网的作用。
插入phi

为了确定哪些基本块需要插入phi函数，引入join node概念：

  • 对两个不同的基本块n1、n2，及基本块n3(可与前两者相同，也可不同)
  • 若控制流图中存在从n1->n3的路径和n2->n3，且路径至少经过一条控制流图边，且这两条路径仅有n3一个交点，则n3为前两个基本块的join node。

对于同一变量不同定义所在的两个不同基本块，两者的join node必须插入phi。
对于变量可能存在多个基本块都有定义，则这些基本块构成集合中任意两个基本块的join node都必插入phi，而这也就是join set。由于插入的phi也是对该变量的定义，因此这些phi所在的基本块集合与此前所有非phi基本块集合的并集都要两两求join node并插入phi，可证，实际上只需要求出所有非phi定义所在基本块的join set即可。
对于SSA形式中的变量v，(其中，基本块x为基本块y必经节点指1.若控制流图中从入口到基本块y的所有路径都经过x，则称x为y的必经节点或称x支配y；若x支配y，且x !=``y，则称x严格支配y。支配树：则让x成为y的祖先，通过这种方式能使支配关系唯一确定一个树状结构，即支配树，根节点为入口节点。若不存在被x严格支配同时严格支配y的节点，则x为y的直接支配者，节点y的直接支配着x即是y在支配树上的父节点):

  • 若v被基本块中一个phi(n:v,...)引用，则v的定义节点为n必经节点。
  • 若v被基本块中不是phi的语句引用，则v定义节点为当前基本块的必经节点。

通过迭代的方式计算支配关系：

  • 根据控制流图迭代计算支配关系，设支配x的点集为DOM(x)，
  • 对每个节点x初始化支配关系DOM(x) = {x}，
  • 对每个节点按DOM(x) = 将控制流图中x的所有前驱节点的DOM取交集后同{x}取并迭代计算，原因是支配x的节点一定也支配x的所有前驱，不然不能支配x
  • 重复迭代步骤直到所有节点支配关系都不变，实际实现中可使用bitset加速。

通过支配关系来得到支配树

  • 若x严格支配y，则x的祖先节点明显少于y，则|DOM(x)| < |DOM(y)|。
  • 则对于y来说，所有严格支配y的节点x中DOM(x)最大的即为y的直接支配者，也就是y在支配树上的父节点。

要在定义节点恰不能支配的节点处插入phi函数。
给出支配边界定义：

  • 若节点n不严格支配节点x，但严格支配x的一个前驱节点，则x在n的支配边界DF(n)中。
  • DF(n)为满足上述条件的所有点集
  • 节点集合S的支配边界为其中所有节点的支配边界的并集。
    由于phi函数定义的存在，此处仍需要去迭代求支配边界，最终得到DF+(Dv) = join-set(Dv∪{entry}) = join-set(Dv)
    相应计算方式：
    alt text

插入算法：
alt text

变量重命名

插入phi后，变量v的一个活跃区间含：1. 活跃区间开头v的唯一定义；2.以及活跃区间中v的引用。
因此需要重命名对定义和所有引用，具体的：遍历到定义时创建新变量，遇到引用，找到支配该处引用的定义并替换为相应创建的新变量，需利用此前求出的支配树。
alt text
alt text
由于mips里没有实现phi函数的指令，因此需要中间代码中的phi函数消除：

  1. 将phi替换为并行赋值指令,即生成一系列不在MIPS指令集中的pc指令，与phi不同的是，其插入的是前驱基本块的末尾，而mem2reg中phi指令插入的是后继基本块的开头，其实也就是因为在mips中，跳转后并不知道跳转前来自哪里
  2. 并行赋值指令串行化，也即替换为一系列move指令
并行赋值

若前驱基本块有多个后继，则所有后继中phi对应的pc指令都将插入前驱基本块末尾，但实际上只应该执行其中的一条，其他的pc指令不当被执行，执行可能将影响语义，因此提出关键边。
关键边：若控制流图中的边(u,v)，若u有多个后继，且v有多个前驱，则这边为关键边。
没有关键边的SSA称为边分割的SSA
对于多个后继的基本块，在其每条出边上新建一个基本块即可移除控制流图所有关键边。
alt text

串行化

称pc指令b<-a中，b为目标寄存器，a为源寄存器。
则可将所有涉及虚拟寄存器看作有向图节点，pc指令方向表示依赖方向，即b需要获得a的值，每次只能选目标寄存器b未被依赖的pc进行改写，否则将会因为改写b而导致别的pc指令的错乱。若依赖关系成环，则选环上一寄存器，将其复制为a‘来破环。
具体算法：
pc指令转化为move指令

实践

  1. 遇到了call指令没有正常维护使用链的情况，使用的指令需要都添加到usesList中；修正了求直接支配者的算法，应该是当前节点的所有支配者(不含自身)的支配者个数最多的节点，而不是最少。
  2. 修改了gep的翻译逻辑，由于alloca和store语句的消除，当函数参数作为偏移时，gep指令不能直接将偏移结果直接存在偏移参数对应的寄存器中，这将会覆盖相应寄存器的值，应该先存到结果寄存器中，最后再将结果寄存器与相应的地址相加得到最终结果，具体实现如下：
    1
    2
    3
    4
    5
    6
    7
    8
    Register offsetRegister = getValueRegisterOrK1(offset);
                    this.loadValueToRegister(offset, offsetRegister);
                    // 此时值已经存在了分配给偏移的寄存器中
                    // 此时进行移位操作
                    new MipsAlu(MipsAlu.ALUType.SLL, result,
                            offsetRegister, 2);
                    new MipsAlu(MipsAlu.ALUType.ADDU, result, addressRegister, result);

死代码删除

理论

在SSA分析基础上，删除非活跃的的指令，活跃指令包含：

  • 对涉及控制流或有副作用的指令，指令引用的变量是活跃的，如br、call、sw、ret等
  • 对为活跃变量定值的指令，指令引用的变量活跃
    以函数为单位变量所有指令，维护指令和变量的活跃标记，迭代更新活跃标记，对无用的，删除定义其的指令，修改时同时维护定义-使用链。

可以删除不可达的函数和基本块，前者通过调用关系从main出发遍历所有函数，后者从控制流图入口基本块出发遍历所有基本块，其实通过分析支配关系可知，入口基本块不支配不可达基本块，发生变化后可再次分析并删除不可达代码，如：常量折叠或常量传播后，若跳转跳转为常量，则可改为无条件跳转，改变控制流图中的点或边。

实践

  1. 去除一个基本块中跳转指令后的多余指令(这些指令都不会再被执行了)和函数中不能到达的基本块。
  2. 主要删除了没有被调用的函数、无法到达的基本块和不会被输入输出、产生副作用的函数调用、内存存储和跳转返回指令等调用的无用指令，同时还针对可以进行合并的基本块进行合并，删去连接两者的唯一的跳转指令。即如下所示的情况：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 判断当前基本块是否可以和其唯一前驱基本块进行合并
        public boolean canMergeBlock() {
            // 判断前驱基本块是否唯一
            if (this.preBlocks.size() == 1) {
                IrBasicBlock preBlock = this.preBlocks.get(0);
                // 判断前驱基本块是否只有唯一的后继基本块且为当前基本块
                return preBlock.postBlocks.size() == 1
                        && preBlock.postBlocks.get(0).equals(this);
            }
            return false;
        }

GVN & GCM

理论

局部值编号，通过哈希寻找基本块内等价指令，合并等价指令定义的变量。
具体的，处理一条指令d<-op(a1,a2,...)时:

  • 若指令计算结果为常数，则将d的所有引用都替换为这个常数，即常数折叠
  • 若指令结果与操作数ai相同，则同样全用ai替换
  • 若指令计算值与其他指令d'<-op(...)同，同理
    全局值编号与LVN类似，但不限于基本块内，而是寻找函数内等价指令。
    GVN可能导致定义在引用后，需全局代码移动来予以纠正。
    全局代码移动大致如下：
  • 计算支配关系并建立支配树
  • 基于循环分析求出各个基本块的循环深度
  • 求出每条指令能被调度的最早基本块
  • 求出每条指令能被调度的最晚基本块
  • 在最早和最晚确定的区间内选择合适的基本块
    选择依据是循环深度尽可能的浅，且尽可能靠前。

实践

此处进行了针对比较指令的常量折叠，因为运算指令在生成的时候已经进行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
IrValue valueL = usesList.get(0);
IrValue valueR = usesList.get(1);
if (valueL.isCon() && valueR.isCon()) {
    int numL = valueL.getConstInt();
    int numR = valueR.getConstInt();
    int result;
    if (type.equals(cmpType.EQ)) {
        result = (numL == numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.NE)) {
        result = (numL != numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SGE)) {
        result = (numL >= numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SGT)) {
        result = (numL > numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SLE)) {
        result = (numL <= numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SLT)) {
        result = (numL < numR) ? 1 : 0;
    }
    else {
        throw new RuntimeException("Illegal cmpType: " + type);
    }
    this.changeAllUsersToValue(new IrConstInt(new IrValueType(IrBaseType.INT1), result));
    // 折叠成功
    return true;
}
return false;

然后利用块内的GVN编号将针对alu、icmp、gep指令的公共子表达式进行了替换删除，具体做法就是为上述几种指令设计特有的GVN编号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// alu
// 按照字典序的方式组成string
        String nameL = usesList.get(0).getName();
        String nameR = usesList.get(1).getName();
        return (this.orderFree() && nameL.compareTo(nameR) >= 0) ?
                nameL + " " + instrType + " " + nameR :
                nameR + " " + instrType + " " + nameL;

// gep
        String addressName = getAddress().getName();
        String offsetName = getOffset().getName();
        return addressName + ":" + offsetName;

// icmp
// 按照从左至右排列的方式，可能没有覆盖全部类型，但是也能凑合用了
        String nameL = usesList.get(0).getName();
        String nameR = usesList.get(1).getName();
        return nameL + " " + instrType + " " + nameR;

然后遍历每个基本块，进行GVN编号与相应指令的哈希表维护，只使用当前基本块以及其支配者的特有的指令，若出现GVN编号重复则复用表中相同GVN编号该指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
boolean finished = true;
// 折叠潜在的常数比较指令
finished &= this.foldCompare(currentBlock);

// 当前基本块和其支配的基本块可以使用的新的公共子表达式，
// 由于对于其兄弟不一定可以使用，因此在遍历完所有子基本块后需要进行删除
HashSet<IrInstruction> usableBlocks = new HashSet<>();
finished &= this.removeSharedInstr(currentBlock, usableBlocks);
// 遍历其所直接支配的所有基本块
for (IrBasicBlock child : currentBlock.getChildren()) {
    finished &= this.visit(child);
}

// 你的兄弟享受不到你的红利嘞
for (IrInstruction instruction : usableBlocks) {
    gvnMap.remove(instruction.GVNValue());
}
return finished;

后端优化

对于alloca指令和gep指令翻译的优化

由于alloca指令的中间代码对应的值本质上就是存储空间的地址，同时该指令的使用不会跨越不同的函数栈，即在某一函数中定义的alloca不会在其他函数中再次被使用，则可以通过函数栈顶加上偏移的方式获得相应的alloca值。因此可以不用特意为其单开一块存储空间，而是直接考虑像记录该中间代码在栈中的位置一样，存储该指令值，只不过，对于其它指令来说获得在栈中位置后需要再从栈中取数，而对于alloca指令来说，其在栈中的偏移位置加上栈顶就是相应的值，不用多一次存取操作，可以减少对内存的操作。
同理，若gep的address是alloca，这里的alloca作用域一定限于当前的函数栈，且offset是constint，因此此时仍旧可以使用此前的只存储偏移的方式进行gep值的存储，减少对于内存的存取。
具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// alloca
 if (IOAdjuster.OPTIMIZE_BUTTON) {
            // 进行alloca指令的优化
            // 只存储相应的函数栈偏移不新开辟一个空间
            MipsManager.setValuesOffset(this, offset);
        }

// gep
if (offset instanceof IrConstInt irConstInt) {
                // 是常数的话，直接计算到相应的result寄存器中
                new MipsAlu(MipsAlu.ALUType.ADDIU, result, addressRegister,
                        irConstInt.getValue() << 2);
            }

// 同理存取时也不用直接从内存进行存取
// load
if (IOAdjuster.OPTIMIZE_BUTTON && address instanceof IrInstruction instruction
                && instruction.allocaOrConstGep()) {
            // 优化
            // 从栈中获取的偏移+上$sp就是实际地址
            new MipsLoadStore(MipsLoadStore.LoadStoreType.LW,
                    targetRegister, MipsManager.getValuesOffset(address),
                    Register.SP);
        }

// store
if (IOAdjuster.OPTIMIZE_BUTTON && address instanceof IrInstruction instruction &&
                instruction.allocaOrConstGep()) {
            // 优化
            new MipsLoadStore(MipsLoadStore.LoadStoreType.SW, tmpRegister,
                    MipsManager.getValuesOffset(address), Register.SP);
        }

乘除法优化

乘法优化

通过判断乘的常数是否为2的整数次幂，因此可以通过优化成<<与+的组合，例如：x*3 <=> x << 1 + x << 0,x*10 <=> x<<3 + x << 1,x*15 <=> x << 3 + x << 2 + x << 1 + x << 0。这样可以极大的简化运算。
同时对于两个操作数都是常数的情况，可以直接由编译器计算完成，直接得到相应的结果；对于其中一个操作数是常数的情况可以根据上述方式进行简化，其中可以特判1和-1的情况，前者保持非常数寄存器的值不变即可，而前者则用$0减去非常数寄存器值即可，对于0来说，相乘直接就是0了，因此需要特判上述三种常数。
对于两个都是非常数的情况只能相乘了。

除法优化

有定理如下：
$设m,d,l为非负整数，d != 0且2^{N+l} <= m * d <= 2^{N+l} + 2^l，则对于0<=n<2^N的整数n有n/d = (m * n) / 2^{N + l}$
大致思路是将除法转化为乘法指令和移位指令，如下:quotient = dividend / divisor = (dividend * multiplier) >> shift，即先乘一个较大的常数，然后用右移的方式得到最终的答案，因此核心在于如何得到multiplier，由于mips为32位的架构，因此需考虑溢出的问题，即mips中乘法运算会将结果保存在hi、lo中，当结果超过32位时，将出现高32位在hi寄存器中，低32位在lo中的情况。因此，尽量使得乘上multiplier后的数刚好在2^(N + l)和2^(N+l) + 2^l之间，其中N为32，这样乘完后取hi中的值，再将该值右移l位后的结果就是相应的整除结果。
其中，对于移位为0的情况，可以不用考虑，避免多余sra指令，例如： 

1
2
3
4
5
6
7
if (k == 1) {
                new MipsAlu(MipsAlu.ALUType.SRL, resultRegister, Register.K1, 32 - k);
            }
            else {
                new MipsAlu(MipsAlu.ALUType.SRA, resultRegister, Register.K1, k - 1);
                new MipsAlu(MipsAlu.ALUType.SRL, resultRegister, resultRegister, 32 - k);
            }

因此，可以依次枚举l，验证定理中的式子是否成立，进而得到一组合法的m、l，由于是向零取整的有符号除法，则计算m,l时N需要代入N-1=31，且d要取绝对值。
即由于$2^{N+l}/d<=m<=(2^{N+l} + 2^l)/d$，因此先令$l=log_2d$，这样可保证取值范围不为空，然后不断减小$l$，直到取值范围内只有一个整数，这样可以使$m$尽可能的小，且少数情况下可使$l=1$，在实现的时候可以使用一个子类来涵盖所有相关的信息。
当d>0时，可将n/d改写为：

  • $n, d=1$
  • $SRA(n+SRL(SRA(n, k-1), 32 - k), k), d = 2^k$
  • $SRA(MULSH(m,n), l-1) + SRL(n, 31), m < 2 ^{31}$
  • $SRA(n + MULSH(m-2^{32}, n), l - 1) + SRL(n,31)$, 其他情况
    SRA(x,n)为算数右移n位，SRL位逻辑右移n位。MULSH(x,y)为取x与y有符号乘后的高32位
    对于d<0的情况，求出|d|后对计算结果取反即可。

运算处的常量折叠

考虑了两个常数(包括IrConstInt和值为IrConstInt的Global)直接运算的情况，对加法考虑了+0的情况；对减法也考虑了-0和被0-的情况；对and考虑了x&0=0，x&(-1)=x，x&x=x的情况；对or考虑了x|0=x，x|(-1)=-1，x|x=x的情况；乘法只考虑了将乘以2的幂次的情况改为左移，看评测需求好像对于二进制只有两位1的转换为两个左移加法应该会优于单mul的效果，还考虑了乘0、乘1、乘-1的情况；对于除法，考虑了除1、除-1的情况，对于模，考虑了x%x=0，以及将x%d转化为x-x/N*N的情况。

线性寄存器分配

迫于时间原因，通过活跃变量分析实现了较为简单的线性寄存器池分配，也就是谁有空就用谁，将后续不再使用的寄存器释放，同时释放遍历的当前指令使用的中间代码为其在本基本块中最后一次使用，且其不在当前基本块的out集合中，也就是该基本块的后续支配基本块都不会再用到该中间代码，且其有寄存器分配在身，此时可以释放其所分配的寄存器。
具体实现如下：

1
2
3
4
5
6
7
if (this.valueRegisterMap.containsKey(useValue)
                            && lastUseMap.get(useValue).equals(instruction)
                            && !instruction.isInOutSet(useValue)) {
                        // 对该指令使用的该value后续不再参与分配
                        this.registerValueMap.remove(this.valueRegisterMap.get(useValue));
                        neverUseSet.add(useValue);
                    }

此外，尤其需要注意对于当前基本块与其兄弟基本块直接的寄存器分配情况，也就是注意需要缓存当前父节点使用的寄存器分配规则，你可以释放但是你的兄弟不一定可以。同时需要考虑其本身以及其所有子节点是否能够用到某个value，如果用不到则可释放，即考虑该中间代码是否在子节点的in集合中，有则说明后续还需要使用，否则则不用。
因此每次为一个基本块及其所有支配子基本块进行完寄存器分配都要进行寄存器分配关系的恢复，例如： 

1
2
3
4
// 释放所有子节点定义的value用到的寄存器
this.freeDefineRegisters(defineSet);
// 恢复所有子节点认为没有用的且不是子节点定义的value
this.recoverNeverUse(defineSet, neverUseAfterDefSet);

你应该注意到了，要想做的上面那些，对于in和out的求解至关重要，根据定义:in[B] = use[B] \cup (out[B] - def[B])；out[B] = \cup in[P] P为B的后继基本块，因此需要先求解def和use集合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for (IrFunction function : module.getFunctions()) {
        for (IrBasicBlock block : function.getBlocks()) {
            HashSet<IrValue> defSet = block.getDefSet();
            HashSet<IrValue> useSet = block.getUseSet();

            // 先考虑phi指令，这些指令应该是最早发生的以及使用的
            // 使用的是来自前驱节点的值，当前全算进use里
            for (IrInstruction instruction : block.getInstructions()) {
                if (instruction instanceof IrPhi phi ) {
                    for (IrValue value : phi.getUsesList()) {
                        if (value != null && value.isUseValue()) {
                            useSet.add(value);
                        }
                    }
                }
            }

            // 接着再分析其他指令
            for (IrInstruction instruction : block.getInstructions()) {
                // 对所有指令进行分析
                for (IrValue useValue : instruction.getUsesList()) {
                    if (!defSet.contains(useValue) && useValue != null
                            && useValue.isUseValue()) {
                        useSet.add(useValue);
                    }
                }
                // 分析instr本身是否为定义指令
                // 即先定义后使用
                if (!useSet.contains(instruction) || instruction.defValue()) {
                    defSet.add(instruction);
                }
            }
        }
    }

此后再进行in和out集合的求解，即可，注意根据定义是需要一直求到完全不发生变化为止：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
for (IrFunction function : module.getFunctions()) {
            ArrayList<IrBasicBlock> blocks = function.getBlocks();
            // 对每个函数内都进行活跃变量的分析，直到in、out集合不变为止
            boolean changed = true;
            while (changed) {
                changed = false;
                // 对所有基本块逆序遍历
                for (int i = blocks.size() - 1; i >= 0; i--) {
                    IrBasicBlock analysisBlock = blocks.get(i);
                    // out：考虑所有后继块的in
                    HashSet<IrValue> newOutSet = new HashSet<>();
                    for (IrBasicBlock postBlock : analysisBlock.getPostBlocks()) {
                        newOutSet.addAll(postBlock.getInSet());
                    }

                    // in:
                    HashSet<IrValue> newInSet = new HashSet<>(newOutSet);
                    newInSet.removeAll(analysisBlock.getDefSet());
                    newInSet.addAll(analysisBlock.getUseSet());

                    // 比较看是否有发生变化
                    HashSet<IrValue> oldOutSet = analysisBlock.getOutSet();
                    HashSet<IrValue> oldInSet = analysisBlock.getInSet();
                    if (!newOutSet.equals(oldOutSet)
                            || !newInSet.equals(oldInSet)) {
                        changed = true;
                        analysisBlock.setInSet(newInSet);
                        analysisBlock.setOutSet(newOutSet);
                    }

                }
            }
        }

特殊的，此处还需要注意不用为alloca和地址是alloca且偏移为常数的gep指令分配寄存器,因为在优化状态下，它们的值自然存在函数栈中，不需要参与到寄存器的分配中来。

窥孔优化

考虑了对于同一块地址进行连续的写入sw覆盖操作，只保留其中最近的一条：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
boolean finished = true;
        ArrayList<MipsComponent> text = module.getText();
        HashSet<MipsLoadStore> deleteSet = new HashSet<>();
        for (int i = 0; i < text.size(); i++) {
            if (i > 0) {
                // 考虑除了第一条指令外其前是否有连续写的情况发生
                MipsComponent nowInstr = text.get(i);
                if (nowInstr instanceof MipsLoadStore nowSW
                        && nowSW.isSW()) {
                    // 只有是sw指令才考虑连续写入的问题
                    MipsComponent preInstr = text.get(i - 1);
                    if (preInstr instanceof MipsLoadStore preSW
                            && preSW.isSW()) {
                        if (nowSW.getAddress().equals(preSW.getAddress())) {
                            // 前一个写入的地址与当前写入的地址一致，那么这两者取后者即可
                            finished = false;
                            deleteSet.add(preSW);
                        }
                    }
                }
            }
        }

        for (MipsLoadStore store : deleteSet) {
            // 删除所有连续写
            module.deleteTextValue(store);
        }
        return finished;

识别对同一地址的连续LW，只保留第一个LW，后续的LW转为MOVE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
boolean finished = true;
    // 识别对同一地址的连续LW，只保留第一个LW，
    // 后续的LW转为MOVE
    ArrayList<MipsComponent> text = module.getText();
    boolean flag = false;
    while (!flag) {
        flag = true;
        // 当无法再进行消除的时候退出
        ArrayList<MipsLoadStore> toMoveLWs = new ArrayList<>();
        Register originalRt = null;
        for (int i = 0; i < text.size(); i++) {
            MipsComponent component = text.get(i);
            if (component instanceof MipsLoadStore lw && lw.isLW()) {
                String address = lw.getAddress();
                for (int j = i + 1; j < text.size(); j++) {
                    if (text.get(j) instanceof MipsLoadStore postLw
                            && postLw.isLW() && postLw.getAddress().equals(address)) {
                        // 紧接着连续是对同一地址的数据加载，则可以寄存器复用
                        toMoveLWs.add(postLw);
                    }
                    else {
                        // 否则直接退出即可
                        break;
                    }
                }
                // 如果有连续的对同一地址的加载，那么lw就是始祖了
                if (!toMoveLWs.isEmpty()) {
                    // 有孩子孩孙
                    originalRt = lw.getRt();
                    // 直接退出进行替换
                    flag = false;
                    finished = false;
                    break;
                }
            }
        }
        if (originalRt != null) {
            // 存在始祖
            // 为孩子孩孙进行指令的替换，后续lw全换成move
            for (int i = 0; i < toMoveLWs.size(); i++) {
                MipsLoadStore lw = toMoveLWs.get(i);
                Register moveDst = lw.getRt();
                MipsMove newMove = new MipsMove(moveDst, originalRt, false);
                module.setTextValue(lw, newMove);
            }
        }
    }
    return finished;

利用zero替换掉被li用0赋值的寄存器，其中只能替换掉可以使用的寄存器，例如t0-t9、s0-s7、以及k0、k1、fp和gp(在我的设计中，这些都可以被使用()):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 由于将k0或者k1作为暂存
// 因此直到下一条对于k0或者k1的赋值
// 中间对于k0或者k1的引用都可以修改为zero
ArrayList<MipsComponent> text = module.getText();
boolean finished = false;
while (!finished) {
    finished = true;
    Iterator<MipsComponent> iterator = text.iterator();
    while (iterator.hasNext()) {
        // 考虑li指令，且只考虑li k0/k1/fp 0
        // 这三个临时寄存器
        MipsComponent component = iterator.next();
        if (component instanceof MipsLi li && li.canReplace()) {
            Register replacedRegister = li.getDst();
            // 删掉该li指令，直到下一条对该register进行赋值的指令之前
            // 中间所有对该寄存器的应用都可以用zero代替
            iterator.remove();
            while (iterator.hasNext()) {
                MipsComponent nextComponent = iterator.next();
                // 若发生改变则返回为true，则相应的还不能结束
                finished &= !nextComponent.setRegisterToZero(replacedRegister);
                if (nextComponent.valueToRegister(replacedRegister)) {
                    // 遇到对原寄存器赋值的指令，则设置完zero后直接退出
                    break;
                }
            }
        }
    }
}

基本块重排

若基本块B1后继仅有B2，也即B1无条件跳转到B2，那在汇编代码中直接将B1与B2相邻可节省B1的跳转，因此可以删除mips生成后多余的j跳转指令，例如对于j跳转的基本块就紧挨着j指令的情况：

ArrayList<MipsComponent> text = module.getText();
        int len = text.size();
        ArrayList<MipsJump> deleteArray = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            MipsComponent component = text.get(i);
            if (component instanceof MipsJump jump
                    && jump.getJumpType().equals(MipsJump.JumpType.J)) {
                // 只对j指令有效
                if (i < len - 1) {
                    MipsComponent nextComponent = text.get(i + 1);
                    if (nextComponent instanceof MipsLabel label) {
                        if (jump.getLabel().equals(label.getLabel())) {
                            // 添加删除j指令的下标
                            deleteArray.add(jump);
                        }
                    }
                }
            }
        }
        // 统一删除所有的多余j指令
        for (int i = 0; i < deleteArray.size(); i++) {
            module.deleteTextValue(deleteArray.get(i));
        }

重调添加if分支跳转基本块顺序，由于对于该分支的翻译是先
bne ... $zero true_block
再
j false_block
因此重调基本块顺序的时候先递归展开false_block，这样j false_block与false_block相连，又可以去掉一条j指令。
此外，还进行了去掉原先与跳转到end的j指令，直接将end安在jal main后执行即可: