CODEWITHSUNDEEP
cmipscompiler-optimization
Patrick Roberts
Patrick Roberts

Reputation: 51866

Compile C to MIPS Assembly in 7 instructions?

I just took a final exam and there was a question that seemed impossible given the restrictions. I'd be happy to be proven wrong but as far as I checked around, at least all my classmates agreed with my conclusion. Here's the question and the answer(s) I provided:

A C program snippet is provided as follows:

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

Write the equivalent in MIPS assembly using at most 7 instructions, using only the following instruction set:

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

a, b and c are accessible through the registers $t0, $t1 and $s0 respectively. You may use other registers as necessary but you may not assume any initial value.

Here's the answer I gave in as few lines as I could:

      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

I thought about it for a good 30 minutes during the 3 hour exam and I came up with two possibilities that the professor could have mistaken on the question. The more likely to me is that he was expecting us to program a do-while loop. The other less likely is that we were allowed to use beq in addition to the other instructions. Here are my answers for those:

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

I challenge anyone to find a shorter answer or to conclusively demonstrate that a shorter answer isn't possible, this has been bugging me a lot.

Update

I reviewed my final grade with my professor, and while he refused to provide an answer, he claimed that half the class got it correct. I found it unfair that my professor failed to provide proof of an existing answer while using that as the basis to deduct points from my exam, but there's not much I can do to argue my point, and would be unwise to pursue considering that with the curve for the low average on the final, I earned a 4.0 for the class.

I was still skeptical though, because I had found that he misgraded one of my Verilog code snippets that I had gotten full credit for after reviewing my final with him, so I found someone who got full credit for the MIPS assembly problem. He told me his strategy but couldn't remember his exact answer so I helped him recreate it, basing off of @Smac89's answer:

      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

So, this doesn't work either. The specific strategy he employed was that he had a guaranteed branch at the top of the loop and that he checked the condition at the bottom in two lines. However I can't think of a way to use slt or slti to create a valid flag to check with bne. It's possible that the professor may have misgraded whatever he attempted in 7 lines.

In conclusion, I still don't have an answer.

Upvotes: 3

Views: 640

Answers (2)

smac89
smac89

Reputation: 43088

What about this?

      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:

Upvotes: 3

xaxxon
xaxxon

Reputation: 19761

Building off Smac89's answer, this guarantees that C isn't 0 unless the loop is done, so the value of C can be used to branch on.

      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

Upvotes: 4

Related Questions