Loading
 |
Subrutiner |
På föreläsningen måndagen 7/11 fortsatte vi med MIPS-assembler. Nytt för dagen var subrutiner och stacken. Avslutningsvis pratade vi om hur det går till när en eller flera källkodsfiler sätts samman till ett körbart program.
Vissa av exempelprogram studerades med hjälp av MIPS-simulatorn SPIM. Genom att koppla en videoprojektor till min laptop kunde sedan de närvarande följa simuleringen.
Emellanåt kommenterade och ritade jag på svarta tavlan. Dessa kommentarer och figurer finns tyvär inte med i dessa anteckningar.
~ Karl
En subrutin, även kallad procedur eller funktion, är en del av ett datorprogram som återanvänds på många olika ställen och därför har skiljts ut från resten av programmet (huvudprogrammet). Som sådan är den en uppfinning av 1950-talet.
Ett första litet exempel på en subrutin ser vi nedan.
.data
NL: .asciiz "\n"
.text
.globl main
main:
# Prepare subroutine call
add $a0, $zero, 10
jal add_four
move $a0, $v0 # integer to print
li $v0, 1 # system call code for print_int
syscall
done: jr $ra
#-----------------------------------------------------------------------------
# PROCEDURE: add_four
#
# DESCRIPTION: This is just a small example subroutine that adds the
# number 4 to given input number.
#
# INPUT: $a0 - a number
#
# OUTPUT: $v0 - the input number + 4
#-----------------------------------------------------------------------------
add_four:
addi $v0, $zero, 0 # $v0 = sum = 0
addi $v0, $a0, 4
jr $ra # return to caller
Vid etiketten add_four startar en subrutin. I den inledande kommentaren anges att indata skall ges i register $a0 och att utdata ges i register $v0. Vi ser även att subrutien är mycket enkel, allt den gör är att addera fyra till det tal som ges som indata.
Kör programmet i spim eller xspim.
Men! Något verkar ha gått brutalt fel. programmet skriver ut 1411111111111111111111...1111 (talet 14 följt av en mkt lång radda ettor).
För att ta reda på vad som gått fell kan vi steppa programmet i xspim.
Notera speciellt vad som händer när instruktionen jal add_four utförs, programpekaren $pc ändras till att peka på etiketten add_four och registret $ra ändras till att innehålla återhopps-adressen, dvs adressen till raden direkt efter jal add_four.
När subrutinen är klar och det är dags att hoppa tillbaka funkar det fint med jr $ra och vi är tillbaka i main och resultatet 14 skrivs ut.
Sedan är det dags att avsluta programmet med jr $ra och vad händer nu? Jo - programmet hoppar mycket riktigt till den adress som finns lagrad i $ra och det är raden diret efter jal add_four. Notera att $v0 nu innehåller talet 1 vilket gör att $a0 sätts till ett vilket gör talet ett skrivs ut med hjälp av syscall. Sedan försöker vi med jr $ra igen och vi hamnar i en oändlig loop...
Problemet med subroutines_crazy.s var att både main och add_four behöver använda samma register ($ra) för att hoppa tillbaka till respektive anropare. Vi skall nu se hur vi kan använda minnet på ett fiffigt sätt (stack) för att lösa detta
I MIPS-assembler kan dessa operation skrivas:
# Pusha innehållet i $s0 på stacken:
addi $sp, $sp, -4 # Flytta ner stack-pekaren
# (stacken växer neråt).
sw $s0, 0($sp) # Skriv in värdet på stack-toppen
# Poppa tillbaka innehållet i $s0 från stacken:
lw $s0, 0($sp) # Läs värdet på stack-toppen
addi $sp, $sp, 4 # Flytta upp stack-pekaren
Genom att main pushar värdet av $ra på stacken innan anrop till add_four kan vi återställa $ra genom att poppa stacken i slutet av main.
.data
NL: .asciiz "\n"
.text
.globl main
main:
addi $sp, $sp, -4 # push return address (save)
sw $ra, 0($sp)
# Prepare subroutine call
add $a0, $zero, 10
jal add_four
move $a0, $v0 # integer to print
li $v0, 1 # system call code for print_int
syscall
lw $ra, 0($sp) # pop return address (restore)
addi $sp, $sp, 4
done: jr $ra
#-----------------------------------------------------------------------------
# PROCEDURE: add_four
#
# DESCRIPTION: This is just a small example subroutine that adds 4 to the input.
#
# INPUT: $a0 - a number
#
# OUTPUT: $v0 - the input number + 4
#-----------------------------------------------------------------------------
add_four:
addi $v0, $zero, 0 # $v0 = sum = 0
addi $v0, $a0, 4
jr $ra # return to caller
Leaf-procedure: En subrutin som i sin tur inte anropar andra subrutiner (eller sig själv).
I exemplet ovan är add_four ett exempel på en leaf-procedure. Eftersom main anropar subrutinen add_four är main inte någon leaf-procedure.
I fallet med leaf-procedure behöver vi inte spara undan $ra på stacken.
Konvention: överenskommelse, en godtycklig men hävdvunnen eller allmänt erkänd ordning eller praxis som följs då inget särskilt talar där emot.
Vid anrop till subrutiner sparas returadressen i det speciella registret $ra. I bland är det praktiskt att låta en subrutin anropa andra subrutiner och då måste returvärdet i $ra sparas undan innan nästa subrutinanrop. Ett bra ställa att spara undan detta värde är stacken. Ett specialfall av detta är när en subrutin anropar sig själv, sk rekursion.
Exempel: om vi vill beräkna 5! så vet vi att detta betyder 5! = 1*2*3*4*5 = 120. I pseudokod kan vi definiera definiera en funktion som beräknar n! enligt:
fakultet(n) {
if (n==0)
return 1;
else
return n*fakultet(n-1);
}
.data
NL: .asciiz "\n"
.text
.globl main
main:
addi $sp, $sp, -4 # push return address on stack
sw $ra, 0($sp)
# Prepare subroutine call
addi $a0, $zero, 5
jal fact
move $a0, $v0 # integer to print
li $v0, 1 # system call code for print_int
syscall
lw $ra, 0($sp) # pop return address
addi $sp, $sp, 4
done: jr $ra
#-----------------------------------------------------------------------------
# DESCRIPTION: Rekursiv fakulets beräkning.
#
# fact(n) = 1 if n == 0
# = n*fact(n-1) otherwise
#
# $s0 - används för att spara undan n i varje rekursivt steg.
#
# INPUT: $a0 - a number n
#
# OUTPUT: $v0 - n!
#-----------------------------------------------------------------------------
fact:
addi $sp, $sp, -4 # pusha returadressen
sw $ra, 0($sp)
beqz $a0, basfall # n == 0?
# Rekursivt steg:
# Vill "komma ihåg" värdet av n
# över det rekursiva anropet.
addi $sp, $sp, -4 # pusha $s0
sw $s0, 0($sp)
# Nu kan vi använda s0.
move $s0, $a0 # spara n i $s0
addi $a0, $a0, -1 # n-1
jal fact # rekursivt anrop ==> $v0 = fact(n)
# s0 innehåller n även efter det rekursiva anropet.
mul $v0, $s0, $v0 # fact(n) = n*fact(n-1)
# Nu finns värdet av fact(n) i $v0
# Återställ $s0
lw $s0, 0($sp) # poppa $s0
addi $sp, $sp, 4
# Vi är redo att retunera
j return
basfall:
addi $v0, $zero, 1
return:
lw $ra, 0($sp) # popa returadressen
addi $sp, $sp, 4
jr $ra # Hoppa tillbaka till anroparen
Hittils har vi endast tittat på heltal lagrade som ord om fyra bytes i taget. Nu har det blivit dags att titta närmare på andra typer av data som lagras byte för byte.
Med hjälp av ASCII-kodning ges varje tecken en kod (ett tal), till exempel har tecknet 'a' ASCII-kod 0x41, dvs ett tal om en byte.
.data
NL: .asciiz "\n"
str: .asciiz "Hello world!"
.text
.globl main
main: addi $s0, $zero, 0
la $t0, str # pointer to current byte in string
while: lb $t1, 0($t0) # get the current byte
li $v0, 1
add $a0, $zero, $t1 # print the ASCII-value
syscall
beq $t1, $zero, done # Look for Nul-termination (ASCII 0)
li $v0, 4 # print new-line
la $a0, NL
syscall
addi $t0, $t0, 1 # Address to next byte
j while
done: jr $ra
.data
NL: .asciiz "\n"
mon: .asciiz "Monday"
tue: .asciiz "Tuesday"
wed: .asciiz "Wednesday"
thu: .asciiz "Thursday"
fri: .asciiz "Friday"
sat: .asciiz "Saturday"
sun: .asciiz "Sunday"
week: .word mon, tue, wed, thu, fri, sat, sun
.text
.globl main
main:
# 1a elementet (dag-0) finns på week + 0
# 2a elementet (dag-1) finns på week + 4
# osv
# 7e elementet (dag-6) finns på week + 24
add $t0, $zero, $zero # index till dag-0
addi $t1, $zero, 24 # index till dag-6
# loopa genom hela veckan (dag-0 till dag-6)
loop: bgt $t0, $t1, done
lw $a0, week($t0) # address till dag-sträng
li $v0, 4 # system call code for print_str
syscall
# ny rad
li $v0, 4 # system call for print_str
la $a0, NL # address of string to print
syscall
addi $t0, $t0, 4 # nästa dag
j loop
done:
jr $ra
Assembler: (eller assembelspråk) är ett enklare sätt att skriva maskinkod genom att ge instruktionerna korta memokoder (mnemonics). Assembler skiljer sig beroende på vilken CPU man skriver den för.
Assemblerkoden "översätts" sedan till maskinkod genom en assemblerare/assemblator. Det finns även disassemblerare som översätter färdig maskinkod till assemblerkod, med mer eller mindre lyckat resultat.
Object file: Assemblatorn översätter en källfil (assembler) till maskinkod. Utöver maskinkod innehåller objektfilen även information som gör det möjligt att bygga ett körbart program utifån flera objektfiler.
Program library: En färdig sammling subrutiner (och data) som är tänkt att användas av flera olika program.
I en käll-fil (module) är det vanligt att det finns referenser till subrutiner och data som definierats i andra moduler eller bibliotek.
Notera assembler-direktivet .globl
För att andra moduler skall kunna använda sig av etiketter i en modul måste dessa deklareras som globala, tex .globl main
Inbyggda system (tex bromssystemet på en bil)
Merparten av koden är skiven i något (eller några) högnivåspråk. Tidskritiska delar skrivs i assembler
Program profiling: För att ta reda på vilka delar av ett program som behöver optimeras analyseras programmet med hjälp av en så kallad profilerare.
Assemblatonr översätter en assembler-fil till binär-fil (instruktioner och data).
För att vi tillsammans skall kunna göra kursen bättre är det viktigt att ni kommer med synpunkter. Självklart går det bra att framföra åsikter muntligt eller via e-post. Vill man vara anonym går det bra att använda formuläret nedan.