我如何重新排列 MIPS 代码以减少所需的 NOP 数量？
How can I rearrange MIPS code to minimise the number of NOPs needed, by hand?
我遇到了以下 MIPS 代码，其中存在数据和负载使用风险。
0 addi $t0,$a0,4
1 addi $t1,$a1,4
2 sub $t2,$t0,$t1 #data hazard $t0, data hazard $t1
3 sll $t3,$a2,2
4 add $t4,$t0,$t3 #data hazard $t3
5 add $t5,$t1,$t3 #data hazard $t3
6 sw $t2,0($t4) #data hazard $t4
为了解决危险，我可以添加 5 NOPs（在第 1 行之后添加 2 个，在第 3 行之后添加 2 个，在第 5 行之后添加 1 个），或者我可以重写代码从而完全避免这些危险。重新排列代码，为了最小化 NOPs 的数量，我得到：
0 addi $t0,$a0,4
1 addi $t1,$a1,4
3 sll $t3,$a2,2
2 sub $t2,$t0,$t1 #data hazard $t1
4 add $t4,$t0,$t3
5 add $t5,$t1,$t3
6 sw $t2,0($t4) #data hazard $t4
然后通过在第 3 行后添加 1 NOP 和在第 5 行后添加 1 NOP 来解决这两个危险。但是，此代码相对简单且简短。如果我在考试中得到 20 行 MIPS 代码怎么办？是否有更快的方法或规则可以更轻松、更快速地（手动）重新排列代码？
对于指令调度算法，首先需要识别依赖链。 （与识别乱序执行的延迟关键路径时所做的相同。）
为有序机器安排指令：交错来自不同 dep 链的指令，从最长的一个开始。
当手动调整（或在优化编译器中）时，您甚至可以做一些事情，例如重新排列关联操作（例如 add）以创建不同的临时对象，从而创建更多的 ILP（指令级并行性）。例如将 a+b+c+d 变成 (a+b)+(c+d)。整数数学是关联的；浮点数学通常不是。
当然这只有在代码使用 addu / addiu 时才是安全的，而不是 MIPS 的 trap-on-signed-overflow add/addi。 C 编译器从不使用陷阱 add/sub，因此它们可以使用与 C 源代码不同的临时对象自由优化算术。你也应该这样做，除非你明确地想要一条可能陷入有符号溢出的指令。
显然经典的 MIPS 汇编程序可以为您重新安排代码以填充加载和分支延迟槽； this Silicon Graphics assembler manual from 1992 goes into some detail about aggressive instruction reordering by the assembler (unless you use .set noreorder and then branch-delay slots become visible.) The book See MIPS Run也可以提到这个。
据推测，SGI 汇编程序根据标签和分支指令检测基本块，并在单个块内进行指令调度。
当然好的高级语言的编译器也做指令调度。 （例如海湾合作委员会）。我认为 GNU 汇编程序没有优化的重新排序模式；它被设计为编译器的后端，可以自行安排指令。
与您在可以使用 add 结果之前具有多周期延迟的玩具示例不同，真正的经典 MIPS 是 classic 5-stage RISC 具有旁路转发和单周期 ALU延迟。 第一代没有互锁，因此有一个 1 个周期的加载延迟槽，分支延迟槽在架构上仍然可见。但是简单的 ALU 指令有 1 个周期的延迟。因此，真正的 MIPS 在调度指令时要避免的危险要少得多。但即便如此，后来的 MIPS 修订版删除了加载延迟槽以提高代码密度，因为当时相对原始的编译器找不到任何东西可以放在那里。 （停止而不是需要 NOP。）
具有这么多延迟槽（并且没有硬件互锁来停止）的真实机器对于代码密度/L1i 缓存占用空间来说是非常不切实际的，而且性能也很差。现实世界的商业设计绕过转发而不是停顿是有原因的。但是您的有效多周期延迟示例对于浮点来说是现实的。
（有趣的事实：MIPS 可以转发来自 的分支目标地址，总共只有 1 个分支延迟周期。
MIPS 一直坚持使用分支延迟槽，直到操作码的主要（且不向后兼容）重组引入无延迟槽分支（2014 年 MIPS32/64r6）。分支延迟槽中的指令无论是否采用分支都会执行，因此后来的 MIPS 硬件无法像加载延迟槽那样删除它。 RISC-V避免了这个错误。
我遇到了以下 MIPS 代码，其中存在数据和负载使用风险。
0 addi $t0,$a0,4
1 addi $t1,$a1,4
2 sub $t2,$t0,$t1 #data hazard $t0, data hazard $t1
3 sll $t3,$a2,2
4 add $t4,$t0,$t3 #data hazard $t3
5 add $t5,$t1,$t3 #data hazard $t3
6 sw $t2,0($t4) #data hazard $t4
为了解决危险，我可以添加 5 NOPs（在第 1 行之后添加 2 个，在第 3 行之后添加 2 个，在第 5 行之后添加 1 个），或者我可以重写代码从而完全避免这些危险。重新排列代码，为了最小化 NOPs 的数量，我得到：
0 addi $t0,$a0,4
1 addi $t1,$a1,4
3 sll $t3,$a2,2
2 sub $t2,$t0,$t1 #data hazard $t1
4 add $t4,$t0,$t3
5 add $t5,$t1,$t3
6 sw $t2,0($t4) #data hazard $t4
然后通过在第 3 行后添加 1 NOP 和在第 5 行后添加 1 NOP 来解决这两个危险。但是，此代码相对简单且简短。如果我在考试中得到 20 行 MIPS 代码怎么办？是否有更快的方法或规则可以更轻松、更快速地（手动）重新排列代码？
对于指令调度算法，首先需要识别依赖链。 （与识别乱序执行的延迟关键路径时所做的相同。）
为有序机器安排指令：交错来自不同 dep 链的指令，从最长的一个开始。
当手动调整（或在优化编译器中）时，您甚至可以做一些事情，例如重新排列关联操作（例如 add）以创建不同的临时对象，从而创建更多的 ILP（指令级并行性）。例如将 a+b+c+d 变成 (a+b)+(c+d)。整数数学是关联的；浮点数学通常不是。
当然这只有在代码使用 addu / addiu 时才是安全的，而不是 MIPS 的 trap-on-signed-overflow add/addi。 C 编译器从不使用陷阱 add/sub，因此它们可以使用与 C 源代码不同的临时对象自由优化算术。你也应该这样做，除非你明确地想要一条可能陷入有符号溢出的指令。
显然经典的 MIPS 汇编程序可以为您重新安排代码以填充加载和分支延迟槽； this Silicon Graphics assembler manual from 1992 goes into some detail about aggressive instruction reordering by the assembler (unless you use .set noreorder and then branch-delay slots become visible.) The book See MIPS Run也可以提到这个。
据推测，SGI 汇编程序根据标签和分支指令检测基本块，并在单个块内进行指令调度。
当然好的高级语言的编译器也做指令调度。 （例如海湾合作委员会）。我认为 GNU 汇编程序没有优化的重新排序模式；它被设计为编译器的后端，可以自行安排指令。
与您在可以使用 add 结果之前具有多周期延迟的玩具示例不同，真正的经典 MIPS 是 classic 5-stage RISC 具有旁路转发和单周期 ALU延迟。 第一代没有互锁，因此有一个 1 个周期的加载延迟槽，分支延迟槽在架构上仍然可见。但是简单的 ALU 指令有 1 个周期的延迟。因此，真正的 MIPS 在调度指令时要避免的危险要少得多。但即便如此，后来的 MIPS 修订版删除了加载延迟槽以提高代码密度，因为当时相对原始的编译器找不到任何东西可以放在那里。 （停止而不是需要 NOP。）
具有这么多延迟槽（并且没有硬件互锁来停止）的真实机器对于代码密度/L1i 缓存占用空间来说是非常不切实际的，而且性能也很差。现实世界的商业设计绕过转发而不是停顿是有原因的。但是您的有效多周期延迟示例对于浮点来说是现实的。
（有趣的事实：MIPS 可以转发来自
MIPS 一直坚持使用分支延迟槽，直到操作码的主要（且不向后兼容）重组引入无延迟槽分支（2014 年 MIPS32/64r6）。分支延迟槽中的指令无论是否采用分支都会执行，因此后来的 MIPS 硬件无法像加载延迟槽那样删除它。 RISC-V避免了这个错误。