Momenteel studeer ik voor mijn computerorganisatie halverwege en ik probeer de stapelaanwijzer en de stapel volledig te begrijpen. Ik ken de volgende feiten die het concept omringen:
- Het volgt het first in last out-principe
-
En het toevoegen van iets aan de stapel duurt twee stappen:
addi $sp, $sp, -4 sw $s0, 0($sp)
Wat ik denk dat me ervan weerhoudt om het volledig te begrijpen, is dat ik geen relevante, voor de hand liggende situatie kan bedenken waarin ik gegevens nodig zou hebben en/of zou willen bijhouden met een stapelaanwijzer.
Kan iemand het concept als geheel nader toelichten en me enkele bruikbare codevoorbeelden geven?
Antwoord 1, autoriteit 100%
Een belangrijk gebruik van stack is het nesten van subroutine-aanroepen.
Elke subroutine kan een set variabelen hebben die lokaal zijn voor die subroutine. Deze variabelen kunnen gemakkelijk worden opgeslagen op een stapel in een stapelframe. Sommige aanroepconventies geven ook argumenten door op de stapel.
Het gebruik van subroutines betekent ook dat je de beller moet volgen, dat is het retouradres.
Sommige architecturen hebben hiervoor een speciale stapel, terwijl andere impliciet de “normale” stapel gebruiken. MIPS gebruikt standaard alleen een register, maar in niet-bladfuncties (dwz functies die andere functies aanroepen) wordt dat retouradres overschreven. Daarom moet u de oorspronkelijke waarde opslaan, meestal op de stapel tussen uw lokale variabelen. De aanroepconventies kunnen ook verklaren dat sommige registerwaarden moeten worden bewaard in functieaanroepen, u kunt ze op dezelfde manier opslaan en herstellen met behulp van de stapel.
Stel dat je dit C-fragment hebt:
extern void foo();
extern int bar();
int baz()
{
int x = bar();
foo();
return x;
}
MIPS-montage kan dan eruit zien:
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
Antwoord 2, Autoriteit 22%
De MIPS-aanroepverdrag vereist eerst vier functieparameters in registers a0via a3en de rest, als er meer zijn, op de stapel. Wat meer is, het vereist ook de functie-beller om vier slots op de stapel voor de eerste vier parameters toe te wijzen, ondanks die in de registers worden gepasseerd.
Dus, als u toegang hebt tot parameter vijf (en verdere parameters), moet u spgebruiken. Als de functie op zijn beurt andere functies oproept en de parameters na de oproepen gebruikt, moet het a0via a3opslaan in die vier slots op de stapel om te voorkomen dat ze verloren zijn gegaan / overschreven. Nogmaals, u gebruikt spom deze registers naar de stapel te schrijven.
Als uw functie lokale variabelen heeft en niet alle in de registers (zoals wanneer het niet a0via a3kan houden wanneer deze andere functies noemt) , het zal de op stapelruimte voor die lokale variabelen moeten gebruiken, die opnieuw het gebruik van spvereisen.
Bijvoorbeeld, als u dit had:
int tst5(int x1, int x2, int x3, int x4, int x5)
{
return x1 + x2 + x3 + x4 + x5;
}
De demontage zou zoiets zijn als:
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
Zie, spwordt gebruikt om toegang te krijgen tot x5.
En als je dan zoiets als deze code hebt:
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)));
}
zo ziet het eruit bij demontage na compilatie:
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
Ik hoop dat ik de code heb geannoteerd zonder fouten te maken.
Houd er dus rekening mee dat de compiler ervoor kiest om r16en r17in de functie te gebruiken, maar ze op de stapel bewaart. Aangezien de functie een andere aanroept, moet deze ook zijn retouradres op de stapel behouden in plaats van het simpelweg in r31te bewaren.
PSOnthoud dat alle vertakkings-/spronginstructies op MIPS de onmiddellijk volgende instructie effectief uitvoeren voordat de besturing daadwerkelijk naar een nieuwe locatie wordt overgedragen. Dit kan verwarrend zijn.