Converting a C program into MIPS assembly language program

Question

I am trying to convert a C program into a MIPS assembly program. The following is my C code for the program: (Note: Bulbs[number] is an array initialized to all zero values for a "number" entered by the user)

for(int i = 1; i <= number; i++) 
            for(int j = 1; j <= number; j++) 
                if(j % i == 0) 
                    Bulbs[j-1] = (Bulbs[j-1] + 1) % 2;

What I have so far is as follows:

li $t0, 0                   #$t0 is set to 0 to be used as index for for loop1
li $t1, 0                  #$t1 is set to 0 to be used as index for for loop2

li $s2, 4                  #integer 4 is stored in s2
mult $s3, $s2              #input number($s3) is multiplied by 4
mflo $s4                   #result of multiplication is stored in $s4

loop1:
bgt $t0, $s4, end_loop1      #if t$0 > $s4(input number*4), exit loop1, 
                           #performing multiplication by 4 since word occupies 4 bytes
addi $t3, $t3, 1                #t3 is initialized to serve as "i" from for loop1
loop2: 
    bgt $t1, $s4, end_loop2 #if $t1 > (input number*4), exit loop2
    addi $t4, $t4, 1            #t4 is initialized to serve as "j" from for loop2
    div $t4, $t3
    mfhi $t5                #$t4 % $t3 is stored in $t5
    bne $t5, $zero, if_end  #checking for if condition

    if_end:
    addi $t1, $t1, 4        #increment $t1 by 4 to move to next array element
    j loop2                 #jump back to top of loop2

end_loop2:
addi $t0, $t0, 4            #increment $t0 by 4 
j loop1                     #jump back to the top of loop1

end_loop1:

I think my for-loop implementation works and I have the if conditional accurately set-up (correct me if I am wrong), but I do not know how I can implement the 'Bulbs[j-1] = (Bulbs[j-1] + 1) % 2;' line after my if conditional. I am new to MIPS and would appreciate any help or feedback!

"Converting" C code into assembly code, isn't that the work for a *compiler*? ;) — Some programmer dude, Sep 30 '17 at 10:46
This converter is called "the compiler" and it is much much better than 99.99% human converters - here is your code; https://godbolt.org/g/CPZtob — 0___________, Sep 30 '17 at 10:48
Hey @PeterJ_01, a lot of this does make sense. But what do lines like $LFB24 = . and $LBB5 = . represent? — Abhishek Rauniyar, Sep 30 '17 at 11:26
No, ability to hand-compile simple functions can be important. — Malcolm McLean, Sep 30 '17 at 11:57

K4rolis · Accepted Answer · 2017-09-30T15:01:16.740

0

I'm assuming that you have Bulbs defined as an array somewhere. Then

Bulbs[j-1] = (Bulbs[j-1] + 1) % 2;

should be translated to something like:

la   $t7, Bulbs    # Move base pointer of bulbs to $t7
add  $t7, $t7, $t1 # $t7 = &Bulbs[j]
lw   $t6, -4($t7)  # $t6 = Bulbs[j - 1]
addi $t6, $t6, 1   # $t6 = Bulbs[j - 1] + 1
andi $t6, $t6, 1   # $t6 = (Bulbs[j - 1] + 1) % 2
sw   $t6, -4($t7)  # Bulbs[j - 1] = $t6

This is based on this information. I haven't done MIPS assembly before, but it's RISC, so how hard can it be? :)

By the way, there appears to be a bug in your assembly translation. In C version, your j starts at 1, whereas in the assembly version it seems to start at 0 (the $t1 array index just gets initialised to 0 on the second line and does not get modified until after the loop body). The fix is simple - initialise it to 4 instead of 0.

edited Sep 30 '17 at 15:01

answered Sep 30 '17 at 11:45

K4rolis

124
4

2

Are you kidding? `rem` hardware division for a constant divisor of 2? (https://stackoverflow.com/questions/40354978/why-is-this-c-code-faster-than-my-hand-written-assembly-for-testing-the-collat/40355466#40355466). Or is that a pseudo-instruction that the assembler will turn into an `AND`? We know `Bulbs[j-i]` is non-negative. – Peter Cordes Sep 30 '17 at 14:35
@PeterCordes good comment - it was a tiny bit rushed response. Haven't written enough assembler to quickly optimise (x % 2) as (x & 0x1), but it is quite obvious, let me update my answer. But in the end the difference _should_ be a single instruction when compared to `rem` anyway (div + a move in contrast to a single and), not that terrible. – K4rolis Sep 30 '17 at 14:57
2

Not all instructions run at the same speed. On modern x86, `div` is about 30 times higher latency than `and` (1 cycle). If anything, it's probably worse on MIPS, since high-performance hardware dividers are expensive (in silicon die area). See the answer I linked for more about division being slow, and how you have to know what you're doing to make better code than a compiler. (But if you do, you often can.) – Peter Cordes Sep 30 '17 at 15:04
1

Hint, `(x + 1) & 1` is add without carry. That's the same operation as `xor`, so you could `xori $t6, $t6, 1`. gcc misses that optimization, even if you give it a `bool` array. Clang (for x86) spots it, though, and compiles that C statement to a single instruction: `xor byte ptr [rdi + rcx - 1], 1` (With a read-modify-write memory destination). Anyway, gcc5.4 for MIPS does of course hoist the `la` out of the loop and increments a pointer. https://godbolt.org/g/J6Ms3j – Peter Cordes Sep 30 '17 at 15:15

Converting a C program into MIPS assembly language program

1 Answers1