0

I have the task of converting this code into assembly: 

int prodArray (int A[], int n) {
   if (!n)
        return 1;
   else if (n == 1)
        return A[0];
   int mid = n / 2;
   int left = prodArray(A, mid);
   int right = prodArray(A + mid, n - mid);
   return left * right;
}

Here is what I have so far, and note that loop, loop2, and loop3 are pretty much the same: 

main:
    add $t0, $0, $0         # Initialize t0
    add $t1, $0, $0         # Initialize t1
    addi $t4, $0, 1         # Make t2 equal to 1

# Main Loop
loop:
    beq $a1, $t2, exit      # If the second argument is 0 branch to exit
    beq $a1, $0, exit2      # If the second argument is 1 branch to exit2
    srl $t2, $a1, 1         # Divide n by 2
    sll $t3, $a1, 1         # Multiply n by 2
    add $a1, $t2, $0        # make n half
    b loop2                 # branch to loop

loop2:
    beq $a1, $t2, exit
    beq $a1, $0, exit2
    srl $t2, $a1, 1
    sll $t3, $a1, 1
    add $a0, $a0, $t2       # Make a0 point to A + mid
    b loop3

loop3:
    beq $a1, $t2, exit
    beq $a1, $0, exit2
    srl $t2, $a1, 1
    sll $t3, $a1, 1
    add $a1, $t2, $0
    b loop

# exit
exit:
    ja $ra, $t4

exit2:
    ja $ra, 0(a1)

I'm not very good at assembly and need any assistance I can get. Note that a0 is meant to be the first argument and a1 is meant to be the second argument.

Thanks for any guidance you're able to give!

Logan
  • 1,047
  • 10
  • 33
  • Am I reading it wrong, or could the original function be implemented as a simple linear loop? Wouldn't be true for floating-point, of course, but for ints the order should make no difference. – sh1 Feb 14 '16 at 07:46
  • It probably could be. I didn't make that function, one of my profs did. @sh1 – Logan Feb 14 '16 at 19:26
  • In those situations (moreso in job interviews, though) I wonder if they were testing you to see if you fixed the code before doing the work of converting it to assembly (which would be good industry practice, because you don't really want to optimise an algorithm _after_ you've hand-coded it in assembly), or if they just didn't think through their test case properly and would mark you down for changing the algorithm. – sh1 Feb 14 '16 at 19:33

2 Answers2

1

If you have the gcc compiler, use, the -S switch, for example: gcc -S helloworld.c . This will produce a .s file with the assembly code. This question has more info: How do you get assembler output from C/C++ source in gcc?

Community
  • 1
  • 1
JoelFan
  • 37,465
  • 35
  • 132
  • 205
  • Thanks for the tip! I used the gcc switch, but it seems to be using commands (such as: pushq, movq, cmpl, cltd) that I've never seen before and are not commands I've seen in class. But at least puts me on the right track. – Logan Feb 14 '16 at 05:17
  • @Anon That's generating x86 assembly, not MIPS assembly. –  Feb 14 '16 at 05:37
  • @Anon If you're using an x86 host then you need to find your MIPS cross-compiler version of gcc. It might be called `gcc-mips64-linux-gnuabi64` for example. You could also try `clang --target=mips` (or mips64 or something) if you have that handy and it's configured for MIPS. – sh1 Feb 14 '16 at 07:52
0

Here's a few pointers…

  1. There aren't any loops in the C code you're starting with, so there shouldn't be any loops in your assembly either. This function does call itself, but that should be implemented just like any other subroutine call (i.e, using jal), not by trying to inline the function into itself. (Indeed, you can't inline this subroutine without some rather major refactoring.)

    Remember to save any registers on the stack that you'll need to restore after the subroutine call, including the original arguments in $v0 and $v1, and the return address $ra.

  2. There is no ja instruction. The correct instruction to use at the end of a subroutine is jr $ra, and you need to put the return value in $v0 before executing that.

  3. Don't forget about branch delay slots! I see a number of places where an instruction may end up executing that you didn't want; you may want to just stick a nop after every conditional branch for now.