MIPS——递归调用

Posted on | In | |
Words count in article: 1.1k | Reading time ≈ 6

嵌套过程

不调用其他过程的过程称为叶过程(leaf procedure)。如果所有过程都是叶过程，那么情况就很简单。但是某个过程可以调用其他过程，甚至调用的是自身的“克隆”。在调用非叶过程时使用寄存器需要十分小心。

例如，假设主程序将参数3存入寄存器a0,然后使用jal A调用过程A。再假设过程A通过jal B调用过程B，参数为7，同样存入a0。由于A尚未结束任务，所以在寄存器a0的使用上存在冲突。同样，在寄存器ra保存的返回地址也存在冲突，因为它现在保存着B的返回值。

我们必须采取措施阻止这类问题发生：

一个解决方法是将其他所有必须保存的寄存器压栈，就像将保存寄存器压栈一样。调用者将所有调用后还需的参数寄存器（a1~a3）或临时寄存器（t0~t9）压栈。被调用者将返回地址寄存器(ra)和被调用者使用的保存寄存器（a0~a7）都压栈。栈指针 sp 随这栈中的寄存器个数调整。到返回时，寄存器会从存储器中恢复，栈指针也会随着重新调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>

int factorial(int n);

int main()
{
    int n;
    scanf("%d", &n);
    int res = factorial(n);
    printf("%d\n",res);
    return 0;
}

int factorial(int n)
{
    if (n < 1)  return 1;
    else  return n * factorial(n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
.data
    prompt1: .asciiz "Enter the number\n"
    prompt2: .asciiz "The factorial of n is:\n"

.text
main:
    # Print prompt1
    li $v0, 4
    la $a0, prompt1
    syscall

    # Read integer
    li $v0, 5
    syscall

    # Call factorial
    move $a0, $v0
    jal factorial
    move $a1, $v0 # save return value to a1

    # Print prompt2
    li $v0, 4
    la $a0, prompt2
    syscall

    # Print result
    li $v0, 1
    move $a0, $a1
    syscall

    # Exit
    li $v0, 10
    syscall

    ## Function int factorial(int n)
    factorial:
        ## YOUR CODE HERE
        addi $sp,$sp,-8            #adjust stack for 2 items
        sw   $ra,4($sp)            #save return address
        sw   $a0,0($sp)            #save the argument n
    
        slti $t0,$a0,1             #if n < 1,then set $t0 as 1
        beq  $t0,$zero,L1          #if equal,then jump L1
                                   #above all,if n >= 1,then jump L1
        #if(n < 1)
        addi $v0,$zero,1            #return 1
        addi $sp,$sp,8              #pop 2 items off stack
        jr   $ra                    #return to caller
        #else
        L1:
            add $a0,$a0,-1          #argument :n - 1
            jal factorial           #call factorial with (n-1)
        
           lw   $a0,0($sp)          #restore argument n
           lw   $ra,4($sp)          #restore address
           addi $sp,$sp,8           #adjust stack pionter
           mul  $v0,$a0,$v0         #return n * factorial(n-1)
           jr   $ra                 #return to caller
    ## END OF YOUR CODE
  #jr $ra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
###########################################################################
#
#    #include<iostream>
#    using namespace std;
#    int sum(int n) {
#        if (n == 1) {
#            return 1;
#        }
#        return n+sum(n-1);
#    }
#
#    int main() {
#      int n = 10;
#      int result = sum(n);
#      cout << result << endl;
#      return 0;
#    }
#
###########################################################################
.text
.globl main
main:
  # Argument for termination condition is saved in $s1, it is 1.
  addi $s1,$0,1
  # Calculate the sum from 1 to 10, n = 10, it is saved in $a1.
  addi $a1,$0,10

  addi $v0,$0,0

  # jump to funcion int sum(int n)
  jal sum
  # print result
  j result

# function
sum:
  # push
  # adjust stack for 2 items (2 * 4 = 8)
  addi $sp,$sp,-8
  #save return address
  sw $ra,4($sp)
  #save argument
  sw $a1,0($sp)

  # n == 1, calculate sum
  beq $a1,$s1,calculate

  # n ！= 1
  # n = n - 1
  addi $a1,$a1,-1
  # push
  jal sum
  # continue to pop

  # branch
  calculate:
    # load argument
    lw $a1,0($sp)
    # load return address
    lw $ra,4($sp)
    # adjust stack for 2 items (2 * 4 = 8)
    addi $sp,$sp, 8
    # n+sum(n-1)
    add $v0,$a1,$v0

    # continue to pop until return main
    jr $ra


result:
  move $a0,$v0
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall

  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  li $v0, 10                                       # exit
  syscall

.data                                              # statement of data
  change:                                          # name of string
       .asciiz "\n"                                # definition of string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
###########################################################################
#
#    #include<iostream>
#    using namespace std;
#    int sum(int n) {
#        if (n != 1) {
#            return n+sum(n-1);
#        }
#        return 1;
#    }
#
#    int main() {
#      int n = 10;
#      int result = sum(n);
#      cout << result << endl;
#      return 0;
#    }
#
###########################################################################
.text
.globl main
main:
  # Argument for termination condition is saved in $s1, it is 1.
  addi $s1,$0,1
  # Calculate the sum from 1 to 10, n = 10, it is saved in $a1.
  addi $a1,$0,10

  # jump to funcion int sum(int n)
  jal sum
  # print result
  j result

# function
sum:
  # push
  # adjust stack for 2 items (2 * 4 = 8)
  addi $sp,$sp,-8
  #save return address
  sw $ra,4($sp)
  #save argument
  sw $a1,0($sp)

  # n ！= 1, continue to push
  bne $a1,$s1,push_number_and_calculate

  # n == 1, return 1 (pop)
  addi $v0,$0,1
  addi $sp,$sp,8
  # continue to pop
  jr $ra

  # branch
  push_number_and_calculate:
    # n = n - 1
    addi $a1,$a1,-1
    # push
    jal sum

    # pop 2,3,4,...,10, and calculate n+sum(n-1)
    # load argument
    lw $a1,0($sp)
    # load return address
    lw $ra,4($sp)
    # adjust stack for 2 items (2 * 4 = 8)
    addi $sp,$sp, 8
    # n+sum(n-1)
    add $v0,$a1,$v0

    # continue to pop until return main
    jr $ra


result:
  move $a0,$v0
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall

  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  li $v0, 10                                       # exit
  syscall

.data                                              # statement of data
  change:                                          # name of string
       .asciiz "\n"                                # definition of string
Donate? comment?