close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

20141014 Stack, Prozeduraufruf - Informatik

EinbettenHerunterladen
Rechnerarchitekturen
und Betriebssysteme (CS201):
Memory Map, Stack,
Prozeduraufruf, Calling Convent.
14. Oktober 2014
Prof. Dr. Christian Tschudin
¨ Basel
Departement Mathematik und Informatik, Universitat
Wiederholung / Diskussion
¨
¨
1. Wie hangen
Wort- und Adressgrosse
zusammen? Bsp:
Ein x86-Prozessor hat 32-Bits Worte und 32-Bits-Adressen.
Der AVR-µPRozessor hat 8-Bits-Worte: wieviele Adress-Bits?
2. Warum gibt es beim AVR-Prozessor keinen Befehl
inc <memoryaddr>?
3. Was sind Adressierungsmodi einer CPU?
¨
4. In Assembler-Sprache konnen
Labels gesetzt werden: Zu
welchem Op-Code werden sie durch den Assembler ubersetzt?
¨
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 2/23
Uebersicht
• Restthemen fruherer
Slides:
¨
Stack-Maschine, Postfix-Code, Prozeduraufruf in Assembler
• Memory Map
• Stack
• Verwendung des Stacks fur
¨ Prozeduraufruf:
calling conventions
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 3/23
Speicheradressen des Datensegments (Memory Map)
0x0100 − 0x10ff
Stack
4096 Hauptspeicher−Zellen
(SRAM)
0x0060 − 0x00ff
160 "extended IO" Registers
0x0020 − 0x005f
64 "Input/Output" Register
32 "general purpose" Register
0x0000 − 0x001f
8−Bits
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 4/23
Stack-Maschinen
• Operationen meist nur im Register
wegen Geschwindigkeit (Speicherzugriff)
• Stack wird aber als Zwischenablage verwendet
• Beispiel: 3 * ( fct(4) + fct(5) ) sei zu berechnen
Umsetzung:
“push 3”
“call fct(4)” (Resultat auf dem Stack)
“call fct(5)” (Resultat auf dem Stack)
“pop r1 / pop r2 / add r1,r2 / pop r2 / mult r1,r2”
Heutige CPUs sind keine reinen Stackmaschinen, aber beinahe
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 5/23
Infix, Postfix und Prefix-Notation
Arithmetische Ausdrucke
in verschiedenen Darstellungen:
¨
• Normale (Infix-) Notation:
3 mult (4 plus 5)
• Postfix Notation:
3 4 5 plus mult
¨
– reine Stackmaschine: keine Register notig
– keine Klammern
– auch bekannt als RPN – “reverse polnish notation”
– Grundlage von PostScript, Forth
• Prefix Notation:
– z.B. in LISP, Tcl
c Christian Tschudin
(mult 3 (plus 4 5))
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 6/23
Exkurs: Postfix-Notation funktioniert auch fur
¨ Code
C: if ( test(a) ) { stmt1; } else { stmt2; }
Umsetzung in Postfixnotation (PostScript)
a
test
{ stmt1 }
{ stmt2 }
ifelse
%
%
%
%
%
%
push a
call: Funktion wird Resultat auf dem Stack lassen
dies setzt einen Codeblock auf den Stack
dies setzt einen Codeblock auf den Stack
erwartet 3 Argumente auf dem Stack, f¨
uhrt einen
der Codeblocks aus gem¨
ass 3. Wert auf Stack
¨
Vorteil: keine Labels notig
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 7/23
Postfix-Order abarbeiten (mit Register)
infix: a + b * c + (d * e + f) * g
postfix: a b c * + d e * f + g * +
Initialisiere Stack
DO Lese Postfix-Ausdruck Symbol f¨
ur Symbol
IF n¨
achstes Symbol ein Operand THEN push Operand
IF n¨
achstes Symbol ein Operator THEN
pop von zwei Operanden vom Stack (z.B. in Register)
wende Operator an
push des Resultats
FI
OD
Schlussresultat auf dem Stack
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 8/23
Postfix-Order erzeugen – Compiler-Arbeit
infix: a + b * c + (d * e + f) * g
postfix: a b c * + d e * f + g * +
Um Code fur
¨ eine Stack-Maschine zu
generieren:
+
• Syntaxbaum des vorliegenden
(Infix-) Ausdrucks erzeugen
*
+
*
a
b
• Baum “depth first” traversieren
(siehe Algo&Datenstrukturen)
+
*
c
d
c Christian Tschudin
e
f
g
• dabei Code fur
¨ den Operator
(eines Knotens) am Schluss
ausgeben.
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 9/23
Subroutinen
s1:
call s1
nop
ret
¨
Code an Adresse s1 soll mehrfach verwendet werden konnen.
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 10/23
(r)call und ret: Stack fur
nutzen
¨ Rucksprung-Adresse
¨
• call:
– legt das Wort “PC + 1” auf den Stack,
– SP (Stack-Ptr) wird um 2 verkleinert (post-decrement)
– setzt PC (Prog-Counter) auf die Adresse der Subroutine
• ret:
¨
– erhohe
SP um 2 (pre-increment)
– ersetzt PC mit Stackwort, auf den SP zeigt
•
rcall S1
...
S1:
... Code von S1 ...
ret
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 11/23
Prozedur-Aufruf – Beispiel mit max()
C: void max() { if (r1 > r2) r3 = r1; else r3 = r2; }
max:
L1:
L2:
main:
cp r2, r1
brge L1
mov r3, r1
rjmp L2
mov r3, r2
ret
...
; Prozedur max()
rcall max
; Prozeduraufruf
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 12/23
Prozedur-Aufruf – ohne Stackpointer!
Rucksprung-Adresse
muss nicht auf dem Stack abgelegt werden.
¨
• Statt rcall max (mit impliziter Benutzung des Stacks):
Rucksprungadresse
in Reg (oder Hauptspeicher) ablegen.
¨
• Beispiel mit Register Z (r30:r31)
max:
L2:
main:
next:
cp r2, r1
...
ijmp
; indirect Jump: benutzt Inhalt von Reg Z
ldi r30, LOW(next)
ldi r31, HIGH(next)
rjmp max
; statt rcall
...
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 13/23
Prozedur-Aufruf – ohne Stackpointer! (Forts)
• Problem: Nur 1 Register Z vorhanden:
– was, falls max() eine zweite Prozedur aufrufen muss?
• Fur
¨ jeden Aufruf (!) einen separaten Speicherplatz,
um Rucksprung
abzulegen
¨
¨
• Damit ist aber keine Rekursion moglich.
(→ fruhes
Fortran)
¨
¨
¨
• Man konnte
die separaten Speicherplatze
wie einen
Stapel verwalten
¨
(Rekursion auch ohne CPU-“Stackpointer” ist moglich)
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 14/23
Parameter-Uebergabe fur
¨ Prozeduren/Funktion
C: int max(int a, int b) { return a > b ? a : b }
• Aehnliche Diskussion wie bei Rucksprungadresse:
¨
Ein-/ausgehende Werte: Stapel, Register oder Hauptspeicher?
• Praxis:
a) einfache Param/Funktionswerte (z.B. int) via Register
b) Liste von Eingabeparameter auf dem Stack ubergeben
¨
• Beispiel:
ldi r24, 5
clr r25
rcall max
mov r18, r24
; Konvention: r24:r25 f¨
ur 16-Bit Resultate
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 15/23
Parameter-Uebergabe
Weitere Anforderungen
• Prozedur hat lokale Variablen
¨ gesichert werden
• Arbeitsregister mussen
temporar
¨
• “Calling Convention”:
¨
– wer ist fur
¨ die Register-Sicherung zustandig?
• “Stack Frame”: Speicherauslegeordnung einer Prozedur
– Rucksprungadresse
¨
– gesicherte Arbeitsregister
– lokale Variablen
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 16/23
Stack Frame (C-Stil)
Param N−1
...
Param 1
Rücksprungadresse
Framepointer
alter Framepointer
lokale Variablen
alte Reg−Werte
Stackpointer
c Christian Tschudin
Zwischenwerte
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
"callee frame" "caller frame"
Param N
• Stackpointer fur:
¨
– Zwischenwerte,
– Rucksprungadresse
¨
• Framepointer (FP)
• FP erlaubt Zugriff auf
– Parameter, sowie
– lokale Variablen
– mit (bekanntem)
– relativem Offset
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 17/23
Historische Bemerkung: Pascal vs C-Parameterubergabe
¨
• Pascal: PROCEDURE proc(a, b: INTEGER); ...
Aufruf: ... proc(3, 4);
• C: proc(int a, int b, ...); ...
Aufruf: ... proc(3, 4, 5, 6);
• Das heisst: C erlaubt variable Parameterzahl, siehe
printf(¨hello %s¨, ¨world¨);
Dies bedingt, dass C die Parameter in umgekehrter Reihenfolge
auf den Stack legt. Deshalb ist auch die Ausfuhrordnung
in C
¨
unbestimmt.
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 18/23
Funktionsaufruf und Parameter-Uebergabe
• Ablauf beim “Caller”:
– Arbeitsregister sichern
¨
– soviel Parameter wie moglich
in Register, sonst Stack
– Rucksprungadresse
sichern, Aufruf
¨
– Ergebniss aus dem r24:r25 Register lesen
• Ablauf beim “Callee”:
– Prolog: FP sicher, Param kopieren, neuer FP+SP, Reg sichern
– Code abarbeiten
– Resultat in richtige Register schieben
¨
– Epilog: Reg restaurieren, FP zurucksetzen,
Stack raumen
¨
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 19/23
Beispiel fur
¨ Framepointer-Verwendung
C: fct() { char a; ... }
• AVR-Konvention: Y-Register (r28:r29) als Frame Pointer
• AVR-Konvention: Framepointer zeigt auf unterste lokale Variable
push r29
push r29
in r28,__SP_L__
in r29,__SP_H__
sbiw r28, 1
...
; sichere alten Framepointer
;
;
;
;
low Byte des Stackpointers
high Byte
erniedrige SP-Wert um 1 (f¨
ur ’a’): FP-Wert!
Register-Param kopieren und SP neu setzen
• Bemerkung: SP wird durch eine IO-Operation gelesen, siehe IO
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 20/23
C-Compiler fur
¨ AVR-CPU
Crosscompiler
• Wird auf einem Host-Rechner ausgefuhrt
(z.B. Intel x86, Linux)
¨
• Erzeugt aber Code fur
¨ eine andere “Architektur”, wie AVR
gcc unterstutzt
¨ auch AVR:
– spezielle Version des Kompilers,
– muss speziell installiert werden (sudo apt-get install avr-gcc)
Aufruf (um Assembler-Code zu generieren, liegt in test.s vor):
/opt/cdk4avr/bin/avr-gcc -S test.c
c Christian Tschudin
Beispiel
CS201 – Rechnerarchitekturen und Betriebssysteme
main() { unsigned char a; a = 5; return 10 * a; }
main:
/* prologue: frame size=1 */
ldi r28,lo8(__stack - 1)
ldi r29,hi8(__stack - 1)
out __SP_H__,r29
out __SP_L__,r28
/* prologue end (size=4) */
ldi r24,lo8(5)
std Y+1,r24
ldd r24,Y+1
mov r18,r24
clr r19
mov r25,r19
mov r24,r18
; --> Forsetzung rechte Spalte
c Christian Tschudin
2013-10-14, 21/23
lsl r24
rol r25
lsl r24
rol r25
lsl r24
rol r25
add r24,r18
adc r25,r19
add r18,r24
adc r19,r25
mov r25,r19
mov r24,r18
/* epilogue: frame size=1 */
rjmp exit
/* epilogue end (size=1) */
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 22/23
Beispiel
main() { unsigned char a; a=5; return 10*a; }
(Forts.)
Der Compiler, das unbekannte Wesen . . .
Zuerst
% avr-gcc -S test.c
Dann
% avr-gcc -O9 -S test.c
ausfuhren
und jeweils test.s anschauen
¨
c Christian Tschudin
CS201 – Rechnerarchitekturen und Betriebssysteme
2013-10-14, 23/23
Document
Kategorie
Technik
Seitenansichten
5
Dateigröße
130 KB
Tags
1/--Seiten
melden