用 7 条指令将 C 语言编译成 MIPS 汇编语言？

Question

我刚刚参加了期末考试，有一道题似乎在限制条件下不可能完成。我很高兴被证明是错误的，但据我检查，至少我所有的 class 伙伴都同意我的结论。这是我提供的问题和答案：

提供一个C程序片段如下：

c = a + b + 6;
while (c > 5) {
  c = c - a;
  b = b + 1;
}

使用最多 7 条指令编写 MIPS 汇编中的等价物，仅使用以下指令集：

add, addi, sub, subi, slt, slti, bne

a、b、c分别可以通过寄存器$t0、$t1、$s0访问。您可以根据需要使用其他寄存器，但您不能假定任何初始值。

以下是我用尽可能少的几行给出的答案：

      add $s0, $t0, $t1
      addi $s0, $s0, 6
loop: slti $t2, $s0, 6
      bne $t2, [=12=], skip
      sub $s0, $s0, $t0
      addi $t1, $t1, 1
skip: subi $t2, $t2, 1
      bne $t2, [=12=], loop

我在 3 小时的考试中思考了整整 30 分钟，我想出了两种可能是教授在这道题上弄错了。对我来说更有可能的是他希望我们编写一个 do-while 循环。另一个不太可能的是我们被允许在其他指令之外使用 beq 。以下是我对这些问题的回答：

同时进行：

      add $s0, $t0, $t1
      addi $s0, $s0, 6
loop: sub $s0, $s0, $t0
      addi $t1, $t1, 1
      slti $t2, $s0, 6
      subi $t2, $t2, 1
      bne $t2, [=13=], loop

beq 允许：

      add $s0, $t0, $t1
      addi $s0, $s0, 6
loop: slti $t2, $s0, 6
      bne $t2, [=14=], skip
      sub $s0, $s0, $t0
      addi $t1, $t1, 1
skip: beq $t2, [=14=], loop

我挑战任何人找到更短的答案或最终证明更短的答案是不可能的，这一直困扰着我。

更新

我和我的教授一起复习了我的期末成绩，虽然他拒绝提供答案，但他声称 class 一半的人都答对了。我发现我的教授未能提供现有答案的证据，同时以此作为从我的考试中扣分的基础，这是不公平的，但我无能为力证明我的观点，并且考虑到这一点是不明智的对于决赛的低平均曲线，我在 class.

中获得了 4.0

虽然我仍然持怀疑态度，因为我发现他对我的一个 Verilog 代码片段进行了错误的评分，在与他一起复习我的期末考试后我获得了满分，所以我找到了一个在 MIPS 程序集上获得满分的人问题。他告诉我他的策略，但不记得他的确切答案，所以我根据@Smac89 的回答帮他重新创建了它：

      addi $t2, $t0, 6   # d = a + 6
      add $s0, $t2, $t1  # c = d + b
      bne $t2, $t0, comp # (d != a) ? comp
loop: sub $s0, $s0, $t0  # c = c - a;
      addi $t1, $t1, 1   # b = b + 1;
comp: slti $t2, $s0, 6   # d = (c < 6)
      subi $t2, $t2, 1   # invert the flag
      bne $t2, [=15=], loop  # !(c < 6) ? loop

所以，这也行不通。他采用的具体策略是，他在循环的顶部有一个有保证的分支，他分两行检查底部的条件。但是我想不出一种方法来使用 slt 或 slti 创建一个有效的标志来检查 bne。教授在 7 行中尝试的任何内容都可能打错了分数。

总之，我还是没有答案。

Answer 1

这个呢？

      addi $s1, $t0, 6     # d = a + 6
      add $s0, $s1, $t1    # c = d + b
loop: slti $t2, $s0, 6     # while (is c less than 6? i.e. c is not greater than 5) 
      bne $t2, $zero, exit # (c <= 5)? exit
      sub $s0, $s0, $t0    # c = c - a;
      addi $t1, $t1, 1     # b = b + 1;
      bne $s1, $t0, loop   # (True condition to loop: d != a)
exit:

Answer 2

基于 Smac89 的答案，这保证 C 不为 0，除非循环完成，因此 C 的值可用于分支。

      add  $s0, $t0, $t1    # c = a + b
loop: slti $t2, $s0, 0      # while (is c less than 0? 
      bne  $t2, $zero, exit # (c > 5)
      sub  $s0, $s0, $t0    # c = c - a;
      addi $t1, $t1, 1      # b = b + 1;
      bne  $t2, $s0, loop   # Loop again unless s0 is 0 -- then we're done
exit: addi $s0, $s0, 6      # add the missing 6

用 7 条指令将 C 语言编译成 MIPS 汇编语言？

Compile C to MIPS Assembly in 7 instructions?

c

mips

compiler-optimization

更新