assemblymips

Usage of recursion with array in MIPS


.data
    A: .word 21 16 -12 25 -25 12 -32 -56 19 -11
.text
main:
    la $a0, A       #argument 1 : array address
    li $a1, 10      #argument 2 : number of elements in array   

    jal print

    li $v0, 10
    syscall

print:
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)


    blt $a0, $a1, print_recursive

    addi $sp, $sp, 12

    jr $ra

print_recursive:
    addi $a0, $a0, 1

    jal print

    lw $ra, 0($sp)
    lw $a0, 4($sp)
    lw $a1, 8($sp)

    lw $v0, 0($a0)

    li $v0, 1
    syscall

    addi $sp, $sp, 12

    addi $a0, $a0, 4

    jr $ra

Currently I'm learning MIPS in college and this is printing array's elements recursively. However, it makes error with "Can't expand stack segment by 8 bytes to 524288 bytes." I'm totally beginner of MIPS so I cannnot figure out what is the problem. Appreciate for advices.

printing array's elements


Solution

  • That error message indicates stack overflow, which is caused either by nonterminating recursion, or unbalanced stack handling.  Here primary issue is nonterminating recursion.

    Even if this code has a proper terminating condition it will never be reached, because the length value is not decremented.

    The stated terminating condition compares a pointer with a counter.  This is a type mismatch and would not be allowed in a higher level language like C.  What you want is to terminate the recursion when the counter is zero, as then there is nothing to print.

    Further, at one point this code is incrementing the pointer value by 1, which is a scaling error, since the pointer is a pointer to words.

    If you save $a0 and/or $a1 as they were needed after some function call, the proper approach to this is to reload them from their stack locations as needed — and they don't need to be reloaded into the same registers, when you just need their values.

    It would be non-standard and thus in some sense improper to restore $a0 and $a1 in function exit, as they are designated as call-clobbered registers, and such restore is a benefit to callers though callers should not expect call-clobbered registers to maintain their values across a function call.

    Restoring registers saved in prologue should only be done for $ra and $s registers.  (i.e. $a0 and $a1 are simply dropped.)

    So, the printing code after the jal can make use of the return value from function call (there is none in this case), any $s registers that have been properly set up before the call (also none here), and stack storage set up before the call.  What you want to print then should derive from the stack storage.

    In short you have this:

    void print_recursive ( int *ptr, int len ) {
       if ( ptr < len ) return; // type mismatch
       print_recursive ( (char*)ptr+1, len ); // incorrect scaling, missing decrement
       printf ( "%d\n", *ptr ); // never reached due to stack overflow
    }
    

    And you want this:

    void print_recursive ( int *ptr, int len ) {
       if ( len == 0 ) return; // proper termination condition
       print_recursive ( ptr+1, len-1 ); // +1 in C on word ptr means +4, decrement length
       printf ( "%d\n", *ptr ); // load saved ptr value from stack, then dereference
    }
    

    Let's observe that len is not used after the recursive function call, having already been checked for zero/non-zero, so doesn't need to be saved on the stack at all.  But ptr is used after a (recursive) function call, so ptr does need to be saved and restored for our own function's benefit, which is the *ptr usage, just before the actual printing of the integer.  $a0 and $a1 are call-clobbered registers, and should not be restored in function exit/epilog.


    Pointers are unsigned, and pointer arithmetic should be unsigned.  So, use addu and addiu instead of add and addi for pointer arithmetic.  Let's note that the stack pointer is a pointer, so stack allocations (e.g. addiu $sp, $sp, -4) should use the u forms.