如何用7个步骤将C语言编译成MIPS汇编?

3

我刚刚参加了一场期末考试,其中有一道问题在限制条件下似乎是不可能的。如果能证明我错了我会很高兴,但据我所知,至少我的同学都同意我的结论。以下是题目和我提供的答案:

给出如下C程序片段:

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

使用最多7条指令,只使用以下指令集,在MIPS汇编中写出等效代码:
add, addi, sub, subi, slt, slti, bne
$t0、$t1和$s0分别通过寄存器访问。如有必要,您可以使用其他寄存器,但不能假定任何初始值。
以下是我尽可能简洁的回答:
      add $s0, $t0, $t1
      addi $s0, $s0, 6
loop: slti $t2, $s0, 6
      bne $t2, $0, skip
      sub $s0, $s0, $t0
      addi $t1, $t1, 1
skip: subi $t2, $t2, 1
      bne $t2, $0, loop

我在3小时的考试中思考了30分钟,想出了两种教授可能会误解问题的可能性。在我看来,更有可能的是他希望我们编写一个do-while循环。另一种可能性较小,即我们可以使用beq指令以及其他指令。以下是我的答案: do-while:
      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, $0, loop

beq allowed:

      add $s0, $t0, $t1
      addi $s0, $s0, 6
loop: slti $t2, $s0, 6
      bne $t2, $0, skip
      sub $s0, $s0, $t0
      addi $t1, $t1, 1
skip: beq $t2, $0, loop

我挑战任何人找到更短的答案或者能够确凿地证明没有更短的答案,这一直困扰着我。

更新

我和我的教授回顾了我的最终成绩,虽然他拒绝提供答案,但他声称班上有一半的学生回答正确。我认为我的教授在扣分时没有提供现有答案的证据是不公平的,但我无法争辩我的观点,而且考虑到期末低平均分的曲线,我获得了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, $0, loop  # !(c < 6) ? loop

所以,这个方法也不起作用。他采取的具体策略是,在循环顶部有一个保证分支,并在两行中在底部检查条件。然而,我无法想到一种使用sltslti创建有效标志以与bne检查的方法。可能教授可能对他在7行中尝试的任何内容进行了错误评分。
总之,我仍然没有答案。

@xaxxon请详细说明一下,我不确定我理解你的意思。 - Patrick Roberts
X * a < b + 1 -- 你的意思是什么? - Patrick Roberts
@xaxxon 当你不被允许使用乘法或除法指令时,这个问题就没有意义了。 - Patrick Roberts
@JeffMercado 我同意你对这个问题的评估,这也是我一开始感到沮丧的原因之一。为了保护我的教授隐私,我不打算透露这门课的名称。 - Patrick Roberts
去问另一位教授... - xaxxon
显示剩余8条评论
2个回答

4
在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 

我正在尝试考虑可能会使其无效的边缘情况,但据我所知它似乎能够正常工作。 - Patrick Roberts
我猜第6行甚至不需要 t2.. 直接使用 $0 就可以了。 - xaxxon
只有两个小修正,你需要将第7行的add改为addi,因为它需要一个立即数。如果你愿意,你也可以将slti改为slt并使用$0,但这只是个人口味问题。我会在明天早上想一想,如果我仍然喜欢它,我会接受的。这里有一个赞。 - Patrick Roberts
谢谢。是的,正如你所指出的,我不懂mips汇编 - 我只是试图理解概念而不是语法 :) 重新阅读文档,现在我明白了。修复了add / addi。 - xaxxon
哦,我刚意识到,第6行的“bne”是不正确的。常见的边缘情况:当c恰好为0时,您会将其增加回6,这比5大,在这种情况下,它应该再次循环。尝试得不错。 - Patrick Roberts
很有趣...如果允许大于号,我会有一些有趣的解决方案。这些数字感觉非常仔细地挑选出来的。当你得到结果后,请务必发布答案。 - xaxxon

3

这个怎么样?

      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:

你知道t2的值,对吧?为什么不在最后一行使用它呢? - xaxxon
删除第二行。旧的第三行现在与0进行比较,而不是6。旧的第七行现在在t2和s0上执行BNE操作(如果s0为0,则无论如何我们都完成了)。新的最后一行将6添加到c中。 - xaxxon
@PatrickRoberts,你是对的。那个寄存器只会被jal指令更新,它基本上是将pc值复制到$ra中。我已经使用其他东西作为循环。 - smac89
我以为我已经解决了它,但是当我在脑海中思考时,我忘记了需要反转标志... - Patrick Roberts
@PatrickRoberts 还在不断攻克这个问题吗?我很欣赏你的韧性 :) - smac89
显示剩余12条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接