1

My question is about procedures in MIPS and using arguments.

I'm trying to translate this small C Function to MIPS and I wasn't sure if I was in the right track. This is the C function:

0 int countNegatives(int table[] , int n) {
1    int count = 0;
2    int i;
3
4    for (i=0; i<n; i++) {
5      if (table[i] <0) {
6        count++;
7      }
8    }
9
10 return count;
11 }

And this what I have on MIPS

main:
    jal countNegatives

countNegatives:
    li $t0, 0  #count = 0
    li $t1, 0  #i = 0

loop:
    bge $t1, $a1, endloop
    sll $t2, $t1, 2  #$t2 = 4*i
    add $t2, $a0, $t2  #$t2 = &table[i]
    lw $t3, 0($t2)  #temp = table[i]
    bge $t3, $zero, endif
    addi $t0, $t0, 1  #counter++
endif:
    addi $t1, $t1, 1  #i++
endloop:
    jr $ra

My code doesn't really run on QTSpim, and so I'm also trying to know if I'm missing any MIPS convention, and if I'm using the arguments in the procedure in a correct manner.

Thanks in advance if anyone can check the code out and see if something is wrong.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847

2 Answers2

2

Except for some missing boilerplate, you were very close. Here's a version annotated with the bugs:

main:
# NOTE/BUG: a0/a1 are _not_ set up for the call
    jal     countNegatives

# NOTE/BUG: we just fall through into countNegatives again [which is bad]

countNegatives:
    li      $t0,0                   # count = 0
    li      $t1,0                   # i = 0

loop:
    bge     $t1,$a1,endloop
    sll     $t2,$t1,2               # $t2 = 4*i
    add     $t2,$a0,$t2             # $t2 = &table[i]
    lw      $t3,0($t2)              # temp = table[i]
    bge     $t3,$zero,endif
    addi    $t0,$t0,1               # counter++

endif:
    addi    $t1,$t1,1               # i++
# NOTE/BUG: we need to loop here

endloop:
    jr      $ra

Here's a working version [with the added boilerplate]:

    .data
arr:    .word   10 20 -5 7 -6 0 1 -1 37

    .text
    .globl  main
main:
    la      $a0,arr                 # point to array
    li      $a1,9                   # array count
    jal     countNegatives

    move    $a0,$v0
    li      $v0,1
    syscall

    li      $v0,10
    syscall

# countNegatives -- count number of negatives
#
# RETURNS:
#   v0 -- number of negative numbers found
#
# arguments:
#   a0 -- pointer to array
#   a1 -- array count
#
# temporaries:
#   t1 -- index variable "i"
#   t2 -- array offset / &table[i]
#   t3 -- temp (value of table[i])
countNegatives:
    li      $v0,0                   # count = 0
    li      $t1,0                   # i = 0

loop:
    bge     $t1,$a1,endloop         # i >= count? if yes, fly
    sll     $t2,$t1,2               # $t2 = 4*i
    addu    $t2,$a0,$t2             # $t2 = &table[i]
    lw      $t3,0($t2)              # temp = table[i]
    bge     $t3,$zero,endif
    addi    $v0,$v0,1               # counter++

endif:
    addi    $t1,$t1,1               # i++
    j       loop

endloop:
    jr      $ra

Here's a just for fun version that uses slt instead of a conditional branch [and eliminates an extra jump inside the loop]:

    .data
arr:    .word   10 20 -5 7 -6 0 1 -1 37

    .text
    .globl  main
main:
    la      $a0,arr                 # point to array
    li      $a1,9                   # array count
    jal     countNegatives

    move    $a0,$v0
    li      $v0,1
    syscall

    li      $v0,10
    syscall

# countNegatives -- count number of negatives
#
# RETURNS:
#   v0 -- number of negative numbers found
#
# arguments:
#   a0 -- pointer to array
#   a1 -- array count
#
# temporaries:
#   t1 -- index variable "i"
#   t2 -- array offset / &table[i]
#   t3 -- temp (value of table[i])
countNegatives:
    li      $v0,0                   # count = 0
    li      $t1,0                   # i = 0
    j       loop_start              # start the loop

loop:
    sll     $t2,$t1,2               # $t2 = 4*i
    addu    $t2,$a0,$t2             # $t2 = &table[i]
    lw      $t3,0($t2)              # temp = table[i]
    slt     $t3,$t3,$zero           # temp = (temp < 0)
    add     $v0,$v0,$t3             # counter += temp

    addi    $t1,$t1,1               # i++

loop_start:
    blt     $t1,$a1,loop            # i < count? if yes, fly

    jr      $ra

Here's another version that uses pointer arithmetic instead of index variables.

Note that under the mips ABI, only the s* regs must be preserved by callee, so a0 and a1 are used as temporaries.

Also note that when adding addresses/pointers, as good practice, we want to use the unsigned versions of the add instructions (i.e. addu and addiu) to prevent [the unlikely possibility of] an overflow exception.

    .data
arr:    .word   10 20 -5 7 -6 0 1 -1 37

    .text
    .globl  main
main:
    la      $a0,arr                 # point to array
    li      $a1,9                   # array count
    jal     countNegatives

    move    $a0,$v0
    li      $v0,1
    syscall

    li      $v0,10
    syscall

# countNegatives -- count number of negatives
#
# RETURNS:
#   v0 -- number of negative numbers found
#
# arguments:
#   a0 -- pointer to array (ptr)
#   a1 -- array count
#
# temporaries:
#   a1 -- array limit (endp)
#   t3 -- temp (value of table[i])
countNegatives:
    li      $v0,0                   # count = 0
    sll     $a1,$a1,2               # get byte offset
    addu    $a1,$a0,$a1             # endp = &arr[count]
    j       loop_start              # start the loop

loop:
    lw      $t3,0($a0)              # temp = *ptr
    slt     $t3,$t3,$zero           # temp = (temp < 0)
    add     $v0,$v0,$t3             # counter += temp

    addiu   $a0,$a0,4               # ptr += 4

loop_start:
    bne     $a0,$a1,loop            # ptr != endp? if yes, fly

    jr      $ra

So, the final asm version, translated back into C would look something like this:

int
countNegatives(int *table, int n)
{
    int *endp;
    int count = 0;

    endp = &table[n];

    for (;  table != endp;  ++table)
        count += (*table < 0);

    return count;
}
Craig Estey
  • 30,627
  • 4
  • 24
  • 48
  • If you're going to make a "cool guy" version, don't put a shift/add address calc inside the loop :P Just use `addiu $t2, $t2, 4` pointer increment, and use a `bne` against an end-pointer for the loop branch. This is what gcc does: https://godbolt.org/g/XmxVMu. Note that `bne` is not a pseudo-instruction, but `blt` with two registers is (it's a `slt` into a register and a `bne` against `$zero`). – Peter Cordes Mar 27 '18 at 17:27
  • Thanks a lot for the reply, didn't actually expect to get such a good answer tbh. – Nicolas Dahbar Mar 28 '18 at 16:56
0

It is not too difficult I think to see what decent compiler does:

https://godbolt.org/g/PiR8Ds

And you will have all the call conventions and another stuff toking by themselves.

 #include <stdio.h>

 int __attribute__((noinline)) countNegatives(int table[] , int n) {
    int count = 0;
    int i;

    for (i=0; i<n; i++) {
      if (table[i] <0) {
        count++;
      }
    }

return count;
 }

volatile int x[] = {454,-3,-5343,-3434,4534};

 int main(void)
 {
     printf("%d\n",countNegatives((int *)x, sizeof(x)/sizeof(x[0])));
 }


countNegatives:
  blez $5,$L6
  sll $5,$5,2

  addu $5,$4,$5
  move $2,$0
$L5:
  lw $3,0($4)
  addiu $4,$4,4
  slt $3,$3,0
  bne $4,$5,$L5
  addu $2,$2,$3

  j $31
  nop

$L6:
  j $31
  move $2,$0

$LC0:
  .ascii "%d\012\000"
main:
  lui $4,%hi(x)
  addiu $sp,$sp,-32
  li $5,5 # 0x5
  sw $31,28($sp)
  jal countNegatives
  addiu $4,$4,%lo(x)

  lui $4,%hi($LC0)
  move $5,$2
  jal printf
  addiu $4,$4,%lo($LC0)

  lw $31,28($sp)
  move $2,$0
  j $31
  addiu $sp,$sp,32

x:
  .word 454
  .word -3
  .word -5343
  .word -3434
  .word 4534
0___________
  • 60,014
  • 4
  • 34
  • 74
  • The OP is using SPIM, which doesn't have branch-delay slots. Also worth pointing out that gcc compiled it as `count += (table[i] < 0);` like you'd do by hand. (But interestingly, if you actually write it that way: https://godbolt.org/g/49sWEv gcc uses a shift by 31 to extract the high bit, instead of `slt` which more directly implements comparing into a register.) – Peter Cordes Mar 27 '18 at 17:22
  • gcc has a `-fno-delayed-branch` which fills branch-delay slots with NOP, making it easier to port to SPIM: https://godbolt.org/g/XmxVMu – Peter Cordes Mar 27 '18 at 17:29
  • It is quite logical. Just see the intermediate compiler outputs – 0___________ Mar 27 '18 at 17:40