[컴퓨터시스템구조] 14. MIPS Sort

• C 코드 - swap

void swap(int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

• v : $a0
• k : $a1
• temp : $t0

 

• MIPS 코드

swap:
    sll $t1, $a1, 2                    # $t1 = k * 4
    add $t1, $a0, $t1              # $t1 = v + (k * 4) = &v[k]
    lw $t0, 0($t1)                    # temp = v[k]
    lw $t2, 4($t1)                    # $t2 = v[k+1]
    sw $t2, 0($t1)                   # v[k]= $t2
    sw $t0, 4($t1)                   # v[k+1] = temp
    jr $ra

 

---

 

• C 코드 - sort

void sort (int v[], int n) {
    int i, j;
    for (i = 0; i < n; i += 1) {
        for (j = i – 1; j >= 0 && v[j] > v[j + 1]; j -= 1) {
            swap(v, j);
        }
    }
}

• v : $a0
• n : $a1
• i : $s0
• j : $s1

 

• MIPS 코드

sort:
    addi $sp, $sp, -20
    sw $ra, 16($sp)
    sw $s3, 12($sp)
    sw $s2, 8($sp)
    sw $s1, 4($sp)
    sw $s0, 0($sp)
    move $s2, $a0                  # $s2=v
    move $s3, $a1                  # $s3=n
    move $s0, $zero               # i=0
L1:
    slt $t0, $s0, $s3                 # i<n이면 $t0=1
    beq $t0, $zero, Exit1         # i<n이 아니면 Exit1
    addi $s1, s0, -1                  # j=i-1
L2:
    slt $t0, $s1, $zero              # j<0이면 $t0=1
    bne $t0, $zero, Exit2         # j<0이면 L1
    sll $t1, $s1, 2                     # $t1=j*4
    add $t2, $s2, $t1                # $t2=&v[j]
    lw $t3, 0($t2)                      # $t3=v[j]
    lw $t4, 4($t2)                      # $t4=v[j+1]
    slt $t0, $t4, $t3                   # v[j+i]<v[j]이면 $t0=1
    beq $t0, $zero, Exit2          # v[j+i]<v[j]아니면 L1
    move $a0, $s2                   # swap의 v=v
    move $a1, $s1                   # swap의 k=j
    jal swap                              # swap 함수 호출
    addi $s1, $s1, -1                # j -= 1
    j L2                                     # L2로 이동
Exit2:
    addi $s0, $s0, 1                 # i += 1
    j L1                                     # L1으로 이동
Exit1:
    lw $s0, 0($sp)
    lw $s1, 4($sp)
    lw $s2, 8($sp)
    lw $s3, 12($sp)
    lw $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra

• callee : saved register
• caller : $ra 필수