MIPS: odpowiednie zastosowanie dla wskaźnika stosu ($ sp) i stosu

Question

Obecnie studiuję na temat śródokresu organizacji komputerowych i staram się w pełni zrozumieć wskaźnik stosu i stos. Znam tych następujące fakty, które otaczają koncepcję:

• Wynika pierwszy w ostatniej zasady zewnątrz

• i dodając coś do stosu trwa proces dwuetapowy:

  addi $sp, $sp, -4 
  sw $s0, 0($sp) 
  

To, co myślę, powstrzymuje mnie przed pełnym zrozumieniem, to to, że nie mogę wymyślić istotnej, samoświadomej sytuacji, w której potrzebowałbym i/lub chciałbym śledzić dane za pomocą wskaźnika stosu.

Czy ktoś mógłby rozwinąć koncepcję jako całość i podać kilka przydatnych przykładów kodu?

Answer 1

Ważnym zastosowaniem stosu jest zagnieżdżanie wywołań podprogramów.

Każda podprocedura może mieć zestaw zmiennych lokalnych dla tego podprogramu. Te zmienne można wygodnie przechowywać na stosie w ramce stosu . Niektóre konwencje wywoływania przekazują również argumenty na stosie.

Korzystanie z podprogramów oznacza także, że należy śledzić dzwoniącego, czyli adres zwrotny. Niektóre architektury mają dedykowany stos do tego celu, podczas gdy inne domyślnie używają "normalnego" stosu. MIPS domyślnie używa tylko rejestru, ale w funkcjach innych niż liść (tj. Funkcje, które wywołują inne funkcje), zwracany adres jest nadpisywany. Dlatego musisz zapisać oryginalną wartość, zwykle na stosie wśród zmiennych lokalnych. Konwencje wywoływania mogą również zadeklarować, że niektóre wartości rejestrów muszą być zachowane przez wywołania funkcji, podobnie można je zapisać i przywrócić za pomocą stosu.

Załóżmy, że ten fragment w C:

extern void foo(); 
extern int bar(); 
int baz() 
{ 
    int x = bar(); 
    foo(); 
    return x; 
} 

zespół MIPS może wówczas postać:

addiu $sp, $sp, -8 # allocate 2 words on the stack 
sw $ra, 4($sp)  # save $ra in the upper one 
jal bar    # this overwrites $ra 
sw $v0, ($sp)  # save returned value (x) 
jal foo    # this overwrites $ra and possibly $v0 
lw $v0, ($sp)  # reload x so we can return it 
lw $ra, 4($sp)  # reload $ra so we can return to caller 
addiu $sp, $sp, 8 # restore $sp, freeing the allocated space 
jr $ra    # return 

Answer 2

MIPS konwencji wywoływania wymaga pierwsze cztery parametry funkcyjne, które należy w rejestrach a0 przez a3 a odpocznij, jeśli jest ich więcej, na stosie. Co więcej, wymaga również, aby funkcja wywołująca funkcję przydzieliła cztery gniazda na stosie dla pierwszych czterech parametrów, mimo że są one przekazywane w rejestrach.

Tak więc, jeśli chcesz uzyskać dostęp do parametru piątego (i dalszych parametrów), musisz użyć sp. Jeśli funkcja z kolei wywołuje inne funkcje i używa jej parametrów po wywołaniu, będzie musiała przechowywać a0 do a3 w tych czterech gniazdach na stosie, aby uniknąć ich zgubienia/nadpisania. Ponownie użyj sp, aby zapisać te rejestry na stosie.

Jeśli funkcja ma zmienne lokalne i nie może utrzymać je wszystkie w rejestrach (jak wtedy, gdy nie można zachować a0 przez a3 gdy wywołuje inne funkcje), będzie musiał wykorzystać przestrzeń na stosu dla tych, zmienne lokalne, które ponownie wymagają użycia sp.

Na przykład, jeśli miał to:

int tst5(int x1, int x2, int x3, int x4, int x5) 
{ 
    return x1 + x2 + x3 + x4 + x5; 
} 

jego demontaż byłoby coś takiego:

tst5: 
     lw  $2,16($sp) # r2 = x5; 4 slots are skipped 
     addu $4,$4,$5 # x1 += x2 
     addu $4,$4,$6 # x1 += x3 
     addu $4,$4,$7 # x1 += x4 
     j  $31  # return 
     addu $2,$4,$2 # r2 += x1 

Apostolskiej sp jest używany do dostępu x5.

A jeśli masz kod coś takiego:

int binary(int a, int b) 
{ 
    return a + b; 
} 

void stk(void) 
{ 
    binary(binary(binary(1, 2), binary(3, 4)), binary(binary(5, 6), binary(7, 8))); 
} 

to właśnie wygląda w demontażu po kompilacji:

binary: 
     j  $31      # return 
     addu $2,$4,$5    # r2 = a + b 

stk: 
     subu $sp,$sp,32    # allocate space for local vars & 4 slots 
     li  $4,0x00000001   # 1 
     li  $5,0x00000002   # 2 
     sw  $31,24($sp)    # store return address on stack 
     sw  $17,20($sp)    # preserve r17 on stack 
     jal  binary     # call binary(1,2) 
     sw  $16,16($sp)    # preserve r16 on stack 

     li  $4,0x00000003   # 3 
     li  $5,0x00000004   # 4 
     jal  binary     # call binary(3,4) 
     move $16,$2     # r16 = binary(1,2) 

     move $4,$16     # r4 = binary(1,2) 
     jal  binary     # call binary(binary(1,2), binary(3,4)) 
     move $5,$2     # r5 = binary(3,4) 

     li  $4,0x00000005   # 5 
     li  $5,0x00000006   # 6 
     jal  binary     # call binary(5,6) 
     move $17,$2     # r17 = binary(binary(1,2), binary(3,4)) 

     li  $4,0x00000007   # 7 
     li  $5,0x00000008   # 8 
     jal  binary     # call binary(7,8) 
     move $16,$2     # r16 = binary(5,6) 

     move $4,$16     # r4 = binary(5,6) 
     jal  binary     # call binary(binary(5,6), binary(7,8)) 
     move $5,$2     # r5 = binary(7,8) 

     move $4,$17     # r4 = binary(binary(1,2), binary(3,4)) 
     jal  binary     # call binary(binary(binary(1,2), binary(3,4)), binary(binary(5,6), binary(7,8))) 
     move $5,$2     # r5 = binary(binary(5,6), binary(7,8)) 

     lw  $31,24($sp)    # restore return address from stack 
     lw  $17,20($sp)    # restore r17 from stack 
     lw  $16,16($sp)    # restore r16 from stack 
     addu $sp,$sp,32    # remove local vars and 4 slots 
     j  $31      # return 
     nop 

Mam nadzieję, że odnotowany kodu bez popełniania błędów.

Należy zauważyć, że kompilator używa funkcji r16 i r17 w funkcji, ale zachowuje je na stosie. Ponieważ funkcja wywołuje inną, musi również zachować swój adres powrotu na stosie, zamiast po prostu zachować go w r31.

PS Pamiętaj, że wszystkie instrukcje oddział/skok na MIPS skutecznie wykonać natychmiast następującą instrukcję zanim faktycznie przeniesienie kontroli do nowej lokalizacji. To może być mylące.