D. Assembler, Compiler, Binder D.1.1 Einordnung und ...€¦ · Assembler: der Begriff wird oft unscharf verwendet, manchmal das Hilfsprogramm zur Assemblierung, manchmal die Assemblersprache

Elektronik: - Strom & Spannung, Transistoren, ICs

Architektur

Systemprogrammierung: - Betriebssystemkonzepte, E/A-Geräte, Treiber ...

„Höhere Informatik“: - Programmierung,, Datenbanken, Verteilte Systeme, Theorie ...

Digitaltechnik: - Rechnerarithmetik, Schaltwerke, Gatter, Logik ...

Rechnerarchitektur: - Bussysteme, Rechenwerke, Caches, Pipelining

Instruktionssatz: - Adressenbildung, Registersemantik, Assembler

Mikro-Architektur: - Instruktionszyklen, µ-Programme, RISC/CISC

B

E G

D

F

CH

D. Assembler, Compiler, Binder

D.1.1 Einordnung und ZielsetzungAssemblersprache als mnemonische Notation für Maschinenprogramme.Praktischer Gebrauch der Maschineninstruktionen.Vgl. mit höheren Programmiersprachen.Verbinden separat übersetzter Module.

D-1 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

D.1. Binäre Maschinenbefehle (Wiederholung)

Eine binäre Notation ist nicht mnemonisch & schlecht lesbar,manuelle Adressrechnungen und Anpassungen,unsystematische binäre Befehlscodierungen,manuelle Anpassung von Sprungdistanzen,kein Bezug auf externe Symbole.

Auch hexadezimale Notation ist ohne Kommentar äusserst unpraktisch:


0x00400000: 00 1F 08 20 # add $1, $0, $31 0x00400004: 03 E0 08 22 # sub $1, $31, $0 0x00400008 00 01 F8 2A # slt $31, $0, $1 0x0040000c: 20 07 AF FE # addi $7, $0, 0xaffe 0x00400010: AC 67 AF F0 # store $7, 0xaff0($3) 0x00400014: 08 10 00 00 # jump 0x400000

0x00400000: 00000000 00011111 00001000 00100000 0x00400004: 00000011 11100000 00001000 00100010 0x00400008: 00000000 00000001 11111000 00101010 0x0040000c: 00100000 00000111 10101111 11111110 0x00400010: 10101100 01100111 10101111 11110000 0x00400014: 00001000 00010000 00000000 00000000

D.2. Assemblierer, Binder, Lader

D.2.1 Programm-Herstellung (wiederholt)

Assemblierer = Programm zur maschinellen Übersetzung eines Quelltextes in Maschinencode etc.


Quellprogramm in Assemblersprache

Speicherabbild

Objektmodul

Assemblierer

Binder

Laden &Ausführen

Bibliotheken

Resultate

Binder verbindet den produzierten Maschinencode mit vorbereiteten Bibliotheken (falls erforderlich).Bibliotheken enthalten vorgefertigte & vorübersetzte Programmteile."Linkage"/Binde-Zeitpunkt:

statisch durch Binder, oder wenn das Program von Platte geladen wird, oder dynamisch im Laufe der Programmausführung,

Das gebundene Speicherabbild/Lademodul wird geladen und ausgeführt.


Programm in

Assembler-sprache

Assem-blierer

Objekt-Modulbzw.

Binde-Modul

BinderLade-Modul

bzw.Executable(auf Disk)

Lader

GeladenesProgramm (im RAM)Bibliotheken

D.2.2 Terminologie:Assemblersprache:

dient dem Niederschreiben von Assemblerroutinen/-programmen,erlaubt Maschinenbefehle in mnemonischer Form.

Assemblierer:Hilfsrogramm, welches aus einem Assemblerprogramm ein Bindemodul produziert,

Assembler:der Begriff wird oft unscharf verwendet,manchmal das Hilfsprogramm zur Assemblierung,manchmal die Assemblersprache.

Binder/Linker:Dient zum Zusammenfügen getrennt übersetzter Objektmodule (Bibliotheken), Querverweise müssen aufgelöst werden,keine Prüfung auf Typenkonsistenz.

Lader:Laden eines Programms an die gewünschte Stelle im Hauptspeicher, Relozierung bedeutet Programme zu verschieben und Referenzen anzupassen,Verwaltung und Berücksichtigung von Relokationsinformation.


D.2.3 Binder bzw. LinkerIn MARS ist nur die Direktive .globl und .extern verfügbar.Anweisungen zum Exportieren und Importieren von Labels/Symbolen:

Exportierte Labels können von anderen Assemblerteilen importiert werden,Assembler erzeugt Bindemodule und Relokationsinformation,Labels verweisen auf Sprungziele und „Entry-Points“,ESD-Symbole können auch auf Daten verweisen,Link- oder Relozierungsinfo ist im => ESD.

External Symbol-Table – ESD:wird vom "Assemblierer" erzeugt,Ist im Objektmodul mit enthalten,exportierte Symbole werden von anderen referenziert,importierte Symbole werden aus dem Code referenziert,Externe Symboltabelle dient als Hilfstabelle für den Binder,Binder erzeugt Lademodul aus separat übersetzten Modulen, der Lader lädt Modul an die zur Laufzeit gewünschte Adresse,der Lader passt zudem nötigenfalls die Referenzen an (Relozierung).

=> Binder als "Mehrfachreferenzstellenverknüpfer"D-6 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

Export

Import

Code

D.2.4 Teile eines Programm-ModulsProgram-Module enthalten nicht nur Instruktionen!Kopfsatz/Header:

Identifikator (Magic Number), Längenangaben, Datum ...

Code- & Textsegmente:Maschinenbefehle, Konstanten, Strings, Sprungtabellen ...

Datensegment:initialisierte & nichtinitialisierte Variablen, Block Storage Segment ...

Symboltabelle (ESD):importierte & exportierte Variablen & Einsprungpunkte ...

Debugginginformation:Zeilenummern, Variablen, Datenstrukturen & Prozedurnamen

Relozierungsinformationen:Adressen, welche bei einer Verschiebung des Programmes angepasst werden müssen,bezogen auf das eigene Modul.


D.2.5 Typische Dateiformate für Programme*.c, *.s, *.asm, *.java:

Quellprogramme für Compiler oder Assemblierer.

*.exe, *.com, *.sys ...:Lademodul für Windows.

*.dllDynamic Link Library für Windows, evtl. Link at run-time.

*.out , *.oklassisches UNIX-Format,Details sind evtl. plattformabhängig

*.COFF (Common Object File Format) Idee des einheitlichen Formats über alle Plattformen Headervariable spezifiziert Prozessorplattform Variante PE-COFF (Portable Executable ...): Windows Welt

*.ELF (Executable and Linkable Format) einheitliches Format für UNIX-Systeme definiert auch Systemaufrufe und deren Semantik (System-API)


D.3. Assemblersprache

Programmiersprache für maschinennahe Programmierung:mnemonische Kürzel für die einzelnen Maschinenbefehle,symbolische Namen für Programm- und Datenadressen,Notation für die Adressierungsarten und Konstanten,normalerweise eine Zeile pro Maschinenbefehl,sog. Makros anstelle von Prozeduren.


0x00400000: 00000000 00011111 00001000 00100000 0x00400004: 00000011 11100000 00001000 00100010 0x00400008: 00000000 00000001 11111000 00101010 0x0040000c: 00100000 00000111 10101111 11111110 0x00400010: 10101100 01100111 10101111 11110000 0x00400014: 00001000 00010000 00000000 00000000

.text Main: add $1, $0, $31 # add register[0] and r[31] into r[1]

sub $1, $31, $0 # subtract r[0] from r[31] into r[1] slt $31, $0, $1 # set r[31] if r[0] < r[1] addi $7, $0, -20482 # add immediate+r[0] into r[7] sw $7, -20496($3) # store word from r[7] to Mem[$3+0xaff0] j Main # jump to instruction at Mem[Main]

Assemblierer

D.3.1 MARS – IDE IDE = Integrated Development Environment:

Texteditor, Assembler, Binder, Debugger ...

MARS = MIPS Assembler and Run-Time Simulator:http://www.cs.missouristate.edu/MARS/ Anzeige der Namen(Labels) für Sprungziele und Variablen,Anzeige der Instruktionen im Speicher,Anzeige der Prozessorregister,Anzeige des Datenspeichers,Text bedeutet hier Code.


D.3.2 Höhere Programmiersprachen im Vergleich:Wesentliche Erleichterung für Programmierarbeit:

Quelltext zum Beispiel in der Programmiersprache Java =>Typenkonzept für Zuweisungen & Prozeduraufrufe,mehr als ein Maschinenbefehl pro Statement,Compiler verwendet nicht alle Befehle,Geschwindigkeitsnachteil,Bessere Produktivität.

Entsprechendes Programm in Assemblersprache:auf die MIPS-CPU bezogene Instruktionskürzel,Gute Auslastung der vorhandenen Register,pro Zeile ein Maschinenbefehl,kein Typenkonzept.

Entsprechender Maschinencode:Daten & Code im Speicher festgelegt,Daten bei 0x10010000besondere Debugtechniken,keine Mnemonik.


... la $7,arr($0) addi $8,$7,40 addi $9,$0,'A'loop: sw $9,0($7) addi $7,$7,4 beq $7,$8,fin j loop ...

... max= 40; val= 'A'; do {

arr[inx++] = val; } while(inx < max); ...

0x400000: 0x3c0110010x400004: 0x342100000x400008: 0x000138200x40000c: 0x20e800280x400010: 0x200900410x400014: 0xace900000x400018: 0x20e700040x40001c: 0x10e800010x400020: 0x08100005

D.3.3 Vollständiges Assemblerprogramm

# s imp l e MIPS prog r amm to in i t i a l i z e an ar r a y# P. Schu l t h e s s , 9.5.2009 .da t a # va r i a b l e s @ 10010000ar r : .wo rd 0:10 # 10 e lemen t s (not 11) . t e x t # code s ta r t s here la $7, ar r ($0) # "Load add r" , s ta r t index add i $8,$7,40 # se t s top i n de x add i $9,$0,0x41 # 'A ' i n t o r[9]loop : sw $9,0($7) # s to r e to memory add i $7,$7,4 # inc r emen t index beq $7,$8, f i n # te rm i na t e ? j loop # repea t

f i n : add i $2,$0, 10 # reques t ex i tsysca l l # tha t i s a l l


D.4. Elemente der MIPS Assemblersprache

Quelltexte in Assemblersprache übersetzt der Assemblierer in Objektmodule:„Assembler“ bezeichnet oft die Sprache und oft das Übersetzerprogramm.

Zeilenorientierte Assemblerbefehle:Befehlszeilen werden in eine Maschineninstruktion übersetzt,Assemblerdirektiven bzw. Pseudobefehle steuern die Übersetzung.

Prinzipieller Aufbau einer Befehlszeile:[ Label ] Operationscode Operanden [ Kommentar ]

Label: Die Programmausführung beginnt beim obligatorischen Label „main“,Label dienen als Bezeichner und beginnen nicht mit einer Ziffer,symbolische Marke im Text, abgeschlossen durch ":",wird mit der aktuellen Speicheradresse verbunden,delegiert Adressrechnung an den Assemblierer.

Bedeutung der Operationscodes (siehe Referenztabelle):Befehle mit einem Inline-Operanden (load, store, add-immediate ...),Sprungbefehle (jump absolute, branch on equal ...),Registerbefehle (add, shift, set less than ...).


Operanden: Registernamen, Adressen, Werte, Konstanten, Zeichenketten, Angaben zur Adressierungsart,z.B.

add i $8, $0, 'A 'sw $8, cap i t a l A($0)

Kommentare:dienen der Erläuterung durch den menschlichen Leser,eingeleitet durch ein '#',bis Ende der Zeile.

Zahlendarstellung in Assemblersprache:Dezimalzahlen: wie gewohnt, z.B. 3455 Hexadezimalzahlen: beginnen mit 0x , z.B. 0xAffe4711 Oktalzahlen: beginnen mit einer Null, z.B. 0030701

In MARS nicht möglich:Konstante Berechnungen: z.B. range * elementSizeBerechnung des Wertes zur Übersetzungszeit.


D.4.1 AssemblerdirektivenAssemblerdirektiven steuern den Übersetzungsvorgang:

Vereinbarung von Konstanten & Variablen,Plazierung von Daten- und Codebereichen,Vereinbarung von Sprungzielen ...

Assemblierung von Daten- und Codesegmenten:.data zeigt auf die nächste freie Stelle im Datenbereich,.text zeigt auf die nächste freie Stelle im Codebereich,Symboltabelle mit lokalen & globalen Bezeichnern,Assembler kennt nur 2 Bereiche,evtl. mehrere Module binden.

Initialwerte:.data zeigt zu Beginn auf 0x10010000,.text zeigt zu Beginn auf 0x00400000.


Quellcode in Assemblersprache

Assemblierer/Übersetzer

.Dat

a

.Data

.Text

.Tex

t

Sym

bolta

belle D

ata

Segm

.Te

xt S

egm

.

D.4.2 Assembler-Direktiven für die Segmentierung:. t e x t [add res s ]

nachfolgende Assemblierung in das Textsegment (normalerweise Code), Von einer Modifikation des Codesegmentes wird abgeraten,Fakultative Adresse bezeichnet die neue Adresse.

.da t a [add res s ]nachfolgende Assemblierung in das Datensegment. Fakultativ Datenadresse neu setzen,Ausführung von Werten aus dem Datensegment als Instruktionen ist nicht empfohlen.

.ex t e r n symbS i zeDer nachfolgende Label hat die Grösse symbSize (fakultativ),er liegt nicht im eigenen Modul.

.g l o b l symb später geladene Module können sich an den Label als externe Referenz verbinden,damit können separat übersetzte Module untereinander kommunizieren,Ein Typenkonzept gibt es nicht.


D.4.3 Speicherreservierung und Variablendeklaration:.by t e by te 1 , b y t e2 , . . .

Bytes fortlaufend im Speicher ablegen.

.wo rd word1 ,wo r d2 , . . .32-Bit Wörter fortlaufend im Speicher ablegen.

. f l o a t g l z 1 , . . .Gleitkommazahlen assemblieren.

.doub l e number 1 , . . .Gleitkommazahlen doppelter Präzision assemblieren.

.asc i i "s t r i n g 1 " , " . . . "nachfolgende Zeichenketten fortlaufend im Speicher ablegen.

.asc i i z "s t r i n g 1 " , " . . . "nachfolgende Zeichenketten als Null-terminierte C-Strings im Speicher ablegen.

.a l i g n ndie nächste Adresse für den Assemblierer hat die untersten n Bits auf Null.

.space s i ze„size“ Bytes leeren Speicherplatz freilassen.


Hat die Zeile einen Label, so kann sie als Variable referenziert werden:

.data wordVar: .word 3536byteVar: .byte 0x35

.a l i gn 2char: .asc i i „z“

.text lw $9, wordVar($0) # Variab le nach Regis ter 9

Eine Alignierung auf 4 Bytes Grenzen ist für MIPS-Befehle erforderlich.Reservierung eines ganzen Speicherbereichs (nur DLX-Assemblierer):

z.B. mit:f ie ld : .space 100*4

es werden 100 aufeinander folgende Speicherwörter reserviert, d.h. die Assemblierung fährt fort an der Adresse field+400 .


D.5. Format der Basis-Instruktionen für MIPS

Alle Befehle 32 Bit breit. Nur drei verschiedene Formate.Referenzkarte für MIPS/SPIM Instruktionen (Basic & Pseudo):

http://refcards.com/docs/waetzigj/mips/mipsref.pdf

D.5.1 Sprungbefehle, J-Format:

Jump (j): j addressSprungziel maximal 228 (MIPS CPU skaliert die Sprungdistanz um Faktor 4).

Jump and L ink (ja l) : ja l addressdient dem Aufruf einer Subroutine und speichert die Rückkehradresse im Register 31,ansonsten wie Jump.


6 Bit Opcode 26 Bit Adresse

31 2526 0

D.5.2 Immediate-Befehle, I-Format:

Sto r e (sw, sh, sb): sw $1,adr($17)speichert 32-Bit Wörter, 16-Bit Wörter oder Bytes aus rs an die gegebene Adressse,Adressenbildung aus rt und immediate Operand mit Vorzeichenerweiterung,D.h. Indizierung mit rt (Indizierung optional).

Load (lw, lu i , l hu , lbu . . .) : lw $1,adr($17)lädt 32-Bit Wörter, 16-Bit Wörter oder Bytes nach Register rt, Indizierung mit rs,load word signExtended, load upper-half of register, load halfword unsigned, load byte unsigned.

Immediate Arithmetik: addi $16,$17, iConstaddi – add immediateaddiu – add immediate unsignedandi – and immediate ...beq – branch on equal

bne – branch on not equallui – load upper immediateslti – set less than immediatesltiu – set less than imm. unsig.


6 Bit Opcode 16 Bit immediate Operand

31 2526 0

rs rt

20 15

D.5.3 Register-Befehle, R-Format:

Jeweils drei Operanden im R-Format:Zwei Input-Operanden, ein Resultat-Operand (Register r0 ist immer null),Verschiebungsdistanz für das Resultat (falls Shift-Befehl),Sekundärer Funktionscode.

Register-Operationen, z.B.: add $16,$17,$18add – addierenand – logisches Unddiv – Divisionjr – jump registerjalr – jump register and linkmult – Multiplikationnot – Negationor – inklusives Oder ...

seq – set if equalsgt – set if greaterslt – set less thansll – shift left logicalsrl – shift right logicalslrv – shift right logical varyingxor – exklusives Oder...u – für „unsigned“


6 Bit Opcode func

31 2526 0

rs rt

20 15

rd Shift amnt

510

D.5.4 Adressierungsmodi - nicht alle aus MIPSDirekte Adressierung (+index):

Wert direkt in Instruktion enthalten.

Registeradressierung:Werte liegen in CPU-Registern.

Basisbezogene Adressierung:Ein Register liefert eine Basisadresse,Dazu wird ein Adressoffset addiert,Werte im Hauptspeicher.

Relativ zum Programmzähler PZ:Daten und Code in der Nähe des PZ,Vereinfacht Relozierung von Code.

Absolute Adressierung (MIPS?):kein Basisregister, lange Adresse.

Indirekte Adressierung (nicht DLX/MIPS):Im Hauptspeicher wird eine Adresse gelesen,Über diese wird indirekt zugegriffen.


Haupt-speicher

CPU-Register

PZ

op rs rt

op rs rt

op rs rt

op rs

op rs

Value

func

Offset

Offset

Adresse

rd

op

Adresse

D.6. Kontrollkonstrukte von Hochsprachen

D.6.1 Umsetzung einer Pascal if-Anweisung in Assemblersprache

program IfStmt(out);(* Pascal if-Anweisung P. Sch., 20.10.07*)var low: string; hig: string; res: integer;begin low:='easy'; hig:='life'; if low < hig then res:=6 else res:=7end.

# If-Anweisung in Assemblersprache# 11.05.2009, P. Schulthess

.data low: .ascii "easy"hig: .ascii "life"res: .word 0 .textmain: lw $8,low # var. low => r8 lw $9,hig # var. high =>r9 sltu $10,$8,$9 # (low<high =>r10 beqz $10,else # branch if falsethen: addi $11,$0,0x6 # set to 6 j endif # skip else clauseelse: addi $11,$0,0x7 # set to 7endif:sw $11,res($0) # store result addi $2,$0,10 # request exit syscall # that is all


Die Zweige der If-Anweisung werden aneinandergefügt:„then“-Zweig darf nicht in den „else“-Zweig hineinlaufen,Einmal muss in jedem Fall gesprungen werden,Sprünge behindern die flüssige Bearbeitung.

Umdenken von der Speicher- in die Registerebene:In der Maschine werden die Variablen nach Möglichkeit in Registern gehalten,Die Register $t0 bis $t9 sind meist ungesicherte temporäre Register,Diese dürften durch eine aufgerufene Prozedur zerstört werden.

Übersetzung eines in höherer Programiersprache vorliegenden Quelltextes:Eventuell Übersetzung in Assemblersprache und anschliessend Asssmblierung,Abweichende Codeerzeugungmuster je nach gewählter Optimierungsstufe,Evtl. Aufruf einer Laufzeitbibliothek für den Stringvergleich,Ein suboptimaler Compiler würde zweimal speichern,Handhabung von Strings oft sehr umständlich,Evtl. Conditional Move erzeugen.

Conditional Move vermeidet Sprunganweisungen (nicht MIPS).


D.6.2 Übersetzung einer Case-Anweisung aus Pascal

Program cas(out); var arg, res: integer; begin arg:=3;

# Fallunterscheidung mit CASE bzw. SWITCH # 20.10.2007, P. Schulthess, einfaches Schema .text .globl main main: addi $8,$0,0x3 # get case argument slti $9,$8,0x0 # arg less than 0 ? bne $9,$0,else # argument is low slti $10,$8,0x4 # argument valid ? beq $10,$0,else # argument is high

Verzweigung über Sprungtabelle oder eine Folge von IF-Anweisungen.Abprüfen auf gültiges Argument in $8.Verzicht auf Tastatureingabe.Else-Fall auf nächster Seite.


case arg of

0: res:=0; 2: res:=2; 3: res:=3 else res:=-1 endend.

sll $11,$8,0x2 # 4 byte units lw $12,jtab($11) # index into table jr $12 # table stored targetcase0: addi $13,$0,0x0 j endcase2: addi $13,$0,0x2 j endcase3: addi $13,$0,0x3 j endelse: addi $13,$0, -1 j endend: addi $2,$0,10 syscall # Sprungtabelle, 4 Adressen-Einträge .data jtab: .word case0 .word else .word case2 .word case3


D.7. Sprachergänzungen

D.7.1 Pseudo-InstruktionenPseudoinstruktionen erscheinen gegenüber dem Programmierer wie reguläre:

es gibt jedoch dafür keinen eigenen Operationscode,unter Umständen erzeugt der Assemblierer mehr als eine Instruktion daraus.

Pseudobefehle mit verbesserter Mnemonik:z.B. subi $8, $8, 4 => addi $8, $8, -4z.B. move $9, $8 => add $9, $8, $0

Pseudobefehle mit erweitertem I-Operanden:z.B. li $8,0xaffe0911($0) #load immediate eigentlich ist der I-Operand auf 16 Bit beschränkt.

Pseudobefehle zur Komplettierung des Repertoires:z.B. blt $8,$9,else #branch if less thandie MIPS hat nur einen simplen Komparator.

Vollständige Referenz im MARS-IDE:


0x3C01affe #lui $1,0xaffe0x34280911 #ori $8,$1,0x0911

0x0109082a #slt $1,$8,$90x14200002 #bne $1,$0,else

D.7.2 Pseudoinstruktionen zur AdressierungUnzulässiges(!) Beispielprogramm:

.data 0x1000 # this region not accepted in MARS !pattern: .word 0x00000001 # single-bit mask

.text 0x400000main: lw $16,pattern($0) # load pattern memory, 16-bit offset

addi $17,$zero,2 # variable for shiftingloop: sllv $16,$16,$17 # varying shift-amount in register

sw $16,pattern($0) # write back to main memoryj loop # jump back forever

Unbequeme Variablenadressierung in MARS:Der Mars-Simulator verbietet Datensegmente unterhalb 0x10000000,16-bit Offset in der lw-Instruktion kann nicht verwendet werden,Alle Variablen- oder Instruktions-Adressen sind 32-bit breit,Der Assemblierer verwendet Pseudo-Instruktionen,Eleganz der MIPS-Instruktionen geht verloren.

In MARS fehlt eine basisbezogene Adresserung, nicht jedoch in MIPS.


Leider verlangt MARS ein Datensegment über 0x10000000:lw, sw, la müssen damit zu Pseudo-Instruktionen werden:

.data 0x10010AFF # address will not fit into the 16 bit offsetpattern: .word 0x00000001 # single-bit mask

.text 0x400000main: lw $16,pattern # get bit pattern from main memory

addi $17,$zero,2 # variable for shiftingloop: sllv $16,$16,$17 # varying shift-amount in register 17

sw $16,pattern # write back to main memoryj loop # jump back forever

Als echte Instruktionsfolge ergibt sich:main: lui $1,0x1001 # load upper half of register 1

lw $16,$0x0aff,$1 # now 16-bit Offset is possibleaddi $17,$zero,2 # variable for shifting is 2

loop: sllv $16,$16,$17 # varying shift-amount in register 17lui $1,0x1001 # load uppe r ha l f o f reg i s t e r 1sw $16,$0x0aff,$1 # write back to main memoryj loop # jump back forever

Register 1 wird verbraucht und steht nicht mehr zur Verfügung!D-29 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

D.7.3 Funktionsbezogene RegisterbenennungNamenskonvention für kooperierende Module:

verbesserte Mnemonik, Darstellung im MARS Registerfenster,$zero enthält immer Null, kann geschrieben werden,$at für Assemblierer reserviert (Pseudoinstruktionen),$v0..$v1 Funktionsresultat und arithmetische Ausdrücke,$a0..$a3 Parameter für einen Funktionsaufruf,$t0..$t7 ungesicherte temporäre Register,$s0..$s7 gesicherte temporäre Register (auch nach Funkt.),$t8..$t9 ungesicherte temporäre Register,$k0..$k1 reserviert für den Betriebssystemkern (rt),$gp Global pointer - zeigt auf globale Variablen,$sp Stack pointer - zeigt auf „Top of Stack“,$fp Frame pointer – zeigt auf aktuellen Stackframe,$ra Return address – Rückkehradresse aus Funktion,$f0-$f31 Gleitkommaregister – hier nicht diskutiert.

Reservierte Register ( ) - bitte nicht anfassen!Gesicherte Register ( ):

bleiben erhalten; auch über den Funktionsaufruf hinweg,nötigenfalls durch die gerufene Funktion gesichert.

Ungesicherte Register ( ) könnten beim Funktionsaufruf zerstört werden.D-30 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

0$1

$4.. $7

$2 ..

$8 .. $15

$16 .. $23

$26 ..$28$29$30$31

$24 ..

0

$16 .. $23

$29$30$31

$1

$4.. $7

$2 ..

$8 .. $15

$26 ..$28

$24 ..

Funktions-aufruf

D.7.4 PrintSum – Ausgabe eines ResultatesEinschliesslich funktionsbezogene Registerbenennung.

# Summe der Elemente eines Vektors ausgeben# P. Schulthess, 1.5.2008 .Data vsize: .word 40vektor: .word 9,8,7,6,5,4,3,2,1,0 .Textmain: lw $t0,vsize($zero) # bytesize of vektorwhile: addi $t0,$t0,-4 # predecrement zlr in temp-0 lw $t1,vektor($t0) # load element from memory add $t2,$t2,$t1 # add element to $t2 (=sum) beqz $t0,fin # break if zlr is zero j while # iteratefin: addi $a0,$t2,0 # sum as parameter to print addi $v0,$zero,1 # integer-print syscall # OS/rt-service addi $v0,$zero,10 # terminate syscall # OS


D.7.5 Aufruf von OS-DienstenListe der OS-Dienst in der MARS Online-Hilfe.

Aufrufskonvention:Parameter in $a0 .. $a2,Funktionscode in $v0,

print, read, open, close, exit, midi, sleep, dialogs.


D.8. Stack / Stapelspeicher / Kellerspeicher

D.8.1 AllgemeinHauptspeicherbereich, dessen eines Ende dynamisch wächst bzw. schrumpft.Verwendung des Kellers für:

Übergabe von Parametern an Unterprogramme,Rücksprungadressen bei Unterprogrammaufrufen,Zurückschneiden des Kellers nach Prozeduraufrufen,Sicherung von Registerinhalten bei Unterbrechungen,lokale Variablen in Unterprogrammen,temporäre Werte in Berechnungen !!

Registerkonvention für MIPS/DLX:Register 29 dient als Stapelzeiger/Stackpointer,Register 30 zeigt auf die lokalen Variablen,Register 31 enthält Rückkehradresse ...

Wachstumsrichtung des Kellers: Stack wächst Richtung der niedrigeren Adressen („von oben nach unten“),Stackpointer zeigt auf zuletzt eingefügtes Byte bzw. Wort,d.h. niedrigste gültige Adresse im Stack,d.h. "oberstes" Stackbyte.


Stack

S / TOS

minS

Hauptspeicher

maxS

0

maxMem

D.8.2 Push-Operation Daten zum Stack hinzufügen:

der Keller wächst - meist zu niedrigeren Adressen hin,Indizierte Adressierung (MIPS ohne Autodekrement),Dekrementieren des Stackzeigers,"Oben" auf den Keller,Kellerüberlauf ?

Push-Operation:Stackzeiger $29 um 4 dekrementieren,1 Wort auf dem Stack einkellern,d.h. addi $sp,$sp , - 4und sw $t0 ,0($29)

Pop-Operation:Ein Wort vom Keller holen,Stackzeiger $29 um 4 inkrementieren, d.h. lw $t 1 ,0($sp) und add i $sp,$sp , +4


$29Altes $29

Wort

$29Altes $29

$9

$8

D.9. Unterprogrammtechnik

D.9.1 „Welcome“-Programm in JavaSoll dreimal eine parametrisierte Nachricht anzeigen.Etwas wortreiche Java-Syntax für diesen Zweck.

public class Welcome { public static void main(String[] args) {wSub(2008);wSub(2009);wSub(2010);

} static void wSub(int year){ System.out.print(year); System.out.println(" Welcome to Java"); System.out.println(); } }


D.9.2 "Welcome"-Programm in MIPS Assemblersprache

# Subroutinenaufruf für 3-maliges Welcome # Peter Schulthess, 1.5.2008 .textmain: addi $a0,$0,2008 # parameter in $4 jal wSub # invoke once addi $a0,$0,2009 # parameter jal wSub # invoke twice

addi $a0,$0,2010 # parameter jal wSub # invoke thrice addi $v0,$zero,10 # request exit syscall # invoke OSwSub: # encapsulates 2 system calls addi $v0,$zero,1 # print integer syscall # OS - printInt la $a0,msg($zero) # address of msg addi $v0,$zero,4 # print msg-string syscall # OS - printString jr $31 # subroutine return, target in $31 .data msg: .asciiz " Welcome to MARS\n\n" # includes 2 newline chars


Ablauf:Hauptprogramm ruft dreimal die Prozedur "wSub" (Codeersparnis),"wSub" ruft die Laufzeitumgebung (Dateisystem) über Syscall,Run-time Support besorgt die Formatierung und die Ausgabe,Die Rückkehradresse wird in Register 31 ($ra) gespeichert,Parameter in Register 4 bzw. $a0 übergeben.

N.B. Stack wird erst bei verschachtelten Aufrufen benötigt ...D-37 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

Programmodul "Welcome"

main

wSub

MIPS Betriebssystem

Datei-system

Bild-schirm-treiber

D.9.1 Vorteile der Unterprogrammtechnik:Codeökonomie:

Häufig benutzte Programmteile werden einmal geschrieben und mehrfach verwendet,Fremde Unterprogramme/Bibliotheken können vom Binder hinzugebunden werden, Unverzichtbare Abstraktionswirkung für höhere Programmiersprachen,Bequeme Speichervergabe und Speicherrückgabe.

Parameter und Ergebnisse: Übergabe wahlweise in Registern oder auf dem Stack möglich,Vorgegebene Parameterreihenfolge auf dem Stack,Registerkonvention bestimmt das Resultatregister,Leider oft divergierende Aufrufskonventionen.

Weitere Elemente auf dem Keller (optional):Dynamische & statische Prozedur-Verkettung,Klassendeskriptor & Objektreferenz,Rücksprungadresse der Prozedurlokale & temporäre Variablen,RegistersicherungFunktionswert ...

Beim Anfordern von OS-Funktionen evtl. im OS den Stack umschalten.D-38 Technische Informatik 1, Sommersemester 2009, ©P. Schulthess, VS Informatik, Ulm

D.10. Rekursiver Subroutinen-Aufruf

Java Programm als Modell für die Formulierung in Assemblersprache:. . .recur ( 7, 0xaffe ) ;. . . void recur ( int depth, int mark){ i f ( depth==0) return; else recur (depth- 1, mark); }. . .

Mehrere verschachtelte Stackframes werden aufgebaut:der Stackframe der aktuellen Prozedur wird über den Framepointer ($fp) gefunden,Framepointer=Basepointer (EBP für 32 Bit Intelx86 CPUs),Rückkehradresse zum Aufrufer einkellern aus $31/$ra,Referenz auf vorhergehenden Stackframe aus $fp,zu sichernde Register,lokale Variablen.

„mark“ dient der Wiedererkennung im Speicherabbild (in MARS).Abbruchbedingung nicht vergessen.


3 Stackframes auf dem Stack/Keller:Parameter hier in den Registern übergeben, nicht auf dem Keller,Return Address zeigt in den Codebereich,Frame Pointer zeigt in den Keller,„mal höher mal niedriger“.


RücksprungFramezeiger

RegistersicherungLokale Variablen






RegistersicherungLokale Variablen $sp

$fp



$fp



$fp

Code

Rekursives Programm in Assemblersprache:# Rekursiver Subroutinen-Aufruf, P. Schulthess, 2.5.2008 .textmain: addi $a0,$0,7 # depth=7 lui $a1,0xaffe # marker value, upper half of word jal recur # invoke recur(7 deep) addi $v0,$0,10 # end of program syscallrecur: sw $ra,0($sp) # save return address ($31) sw $fp,-4($sp) # save frame/base pointer sw $a0,-8($sp) # keep parameter locally sw $a1,-12($sp) # debug mark add $fp,$0,$sp # new frame on stack addi $sp,$sp,-16 # 16 bytes pushed beq $a0,$0,ret # end of recursion addi $a0,$a0,-1 # decrement, parameter jal recur # invoke next levelret: addi $sp,$sp,16 # must pop 16 bytes lw $ra,0($sp) # restore return address lw $fp,-4($sp) # restore frameptr jr $ra # exit from recur


Prozeduraufruf:Parameter in Register $a0.. legen,Prozedur-Aufruf mit Jump-And-Link Instruktion (j a l ). Die Instruktion legt die Rückkehradresse in das Register $31/$ra ab.

Prozedur-Prolog:Rückkehradresse auf dem Keller sichern (falls rekursive Situation),falls nötig alten Framepointer ($fp) auf dem Keller sichern (Dynamic Link),Register sichern, welche voraussichtlich durch unsere Prozedur zerstört werden,Stackzeiger in Register $29/$sp dekrementieren (Stack wächst hier nach unten).

Prozedur-Epilog:Stackzeiger inkrementieren, Stack schrumpft, Speicher wird freigegeben,Zerstörte Arbeitsregister wiederherstellen (entfällt hier),alten Frame/Base Pointer wiederherstellen ($30),Rückkehradresse in Register-31 bereitlegen,Rücksprung (j r – jump to register).

Konvention zur Registersicherung:Die aufgerufene Subroutine sichert die Register $16 bis $23 falls diese verändert werden,Zurückgegebener Funktionswert in Register $2 und $3 - $v0..$v1,Aktuelle Parameter in $4 bis $7 - $a0..$a3


D.10.1 Iterative Berechnung von Fibonacci-Zahlen/* Fibonacci Zahlen */...int tmp;int fibAlt=0; int fibNeu=1; int zlr=2;int max=7;while(true){ tmp = fibAlt;

fibAlt = fibNeu;fibNeu = fibNeu+tmp;if(max == zlr)break;zlr++;

}...

# Fibonacci Zahlen iterativ berechnen .textmain: # $t0 is fibAlt addi $t1, $0, 1 # init fibNeu addi $t2, $0, 2 # init zlr=2 addi $t3, $0, 7 # init max=7while: add $t4,$0,$t0 # save fibAlt add $t0,$0,$t1 # set fibAlt add $t1,$t1,$t4 # compute fibNeu beq $t2,$t3,fin # equal? $t1,$t2 addi $t2,$t2,0x1 # zlr++ j while # iteratefin: addi $v0,$0,10 # terminate syscall


Übersichtlicher für den Programmierer, aber weniger schnell ist die rekursive Variante:

stat i c int rF i bo( int N){ i f (N<3) return 1;

return rF i bo(N-1) + rF i b o(N-2);}

Allgemeine Bemerkungen:Die Rekursion auf dem Keller wird in der MIPS-Architektur leider etwas umständlich,MIPS als Beispiel für einen Rechner mit einfachen Befehlen & vielen Registern,Mikrocontroller haben im Gegensatz dazu nur wenige Register,aber viele Adressierungsmodi & spezielle Stackinstruktionen,Damit wird die µC-Programmierung „trickreicher“,Die Konzepte auf Assemblerebene sind ähnlich.

Unser aktuelles Ziel ist es, die didaktische Lücke zwischen Hardware und Programmiersprache zu schließen, und nicht die Programmierung von Mikrocontroller-Systemen zu vermitteln.


D.10.2 Rekursive Berechnung von Fibonacci-ZahlenRekursive Definition:

für alle n > 2: fibo(n) = fibo(n – 1) + fibo(n – 2);für n in {1,2}: fibo = 1;

Umsetzung in rekursive Unterprogrammaufrufe: Rekursionstiefe nur durch verfügbare Stackgröße beschränkt,Verkettungen & Rückkehradressen auf den Stack legen,Wiederverwendete Register im Keller sichern,Ergebnisrückgabe in einem Register,Parameterübergabe in Registern.

Maschinen mit wenig Registern (Intel x86, M6809 ...):Bei jedem Aufruf wird ein neuer, vollständiger Stackframe angelegt,Parameter werden typischerweise auf dem Keller übergeben,Operanden und Zwischenresultate meist auf dem Keller,Oft besondere Stack-Instruktionen (push-All ..).

Maschinen mit vielen Registern, z.B. DLX & MIPS:Die Berechnung erfolgt primär in den Registern,Nur bei Bedarf werden Register eingekellert.


D.10.3 Rekursives Fibonacci-Programm in Java

publ ic clas s Fibonacc i {

publ ic stat i c void main(St r ing [ ] args ) {System.out.pr in t ln (F ibo (1 ) ) ;System.out.pr in t ln (F ibo (2 ) ) ;System.out.pr in t ln (F ibo (5 ) ) ;System.out.pr in t ln (F ibo (6 ) ) ;

}stat i c int Fibo( int N) {

i f (N<3) return 1;return Fibo(N- 1)+Fibo(N- 2);

}}

Die Formulierung in Java spiegelt direkt die Definition der Fibonacci-Reihe.Weniger übersichtlich ist hingegen die Formulierung in Assemblersprache.


D.10.4 Rekursive Fibonacci-Berechnung in AssemblerspracheEin Beispiel für Stackrekursion in Assemblersprache:

Etwas umständliche Abbruchbedingung,Framepointer kann hier entfallen.

Visualisierung im MARS IDE:$gp wird missbraucht, um den Stack im Datenfenster anzuzeigen,Stackframe wird auf 16 Bytes aufgefüllt zur besseren Visualisierung,Stackposition für $ra-Sicherung wird gelöscht, um die Visualisierung zu verbessern.

# rekursive Fibonacci Berechnung, P.S., 9.5.09main: addi $gp,$sp, -412 # trick data display

addi $t1,$0,1 # oneaddi $t2,$0,2 # twoaddi $a0,$0,24 # parameter is 24jal fibo # invokeadd $a0,$v0,$0 # result into $a0addi $v0,$0,1 # printInt syscall # I/O

addi $v0,$0,10 # terminate syscall # OS


fibo: sw $ra, 0($sp) # save return address sw $s0,-4($sp) # save $s0 sw $s1,-8($sp) # save $s1 addi $sp,$sp,-16 # stack adjust, pad 4

add $s0,$a0,$0 # a0 unsaved, s0 as N addi $v0,$0,1 # default result is 1 beq $a0,$t1,ret # end if N=1 beq $a0,$t2,ret # end if N=2 addi $a0,$s0,-1 # parameter n-1 jal fibo # fibo(n-1) add $s1,$v0,$0 # result to $s1 addi $a0,$s0,-2 # parameter n-2 jal fibo # fibo(n-2) add $v0,$v0,$s1 # ...+...ret: addi $sp,$sp,16 # stack adjust up lw $s1,-8($sp) # restore $s1 lw $s0,-4($sp) # restore $s0 lw $ra, 0($sp) # restore $ra sw $0, 0($sp) # visualize stack jr $ra # return, result in v0


Prolog

Body

Epilog

D.10.5 BildschirmauszugBreak am tiefsten Rekursionspunkt.Stack bei 0x7ffff000.


D.11. Bibliotheksmodule als separate Dateien

Vorerst 3 Speichersegmente:Textsegment, Datensegment, Extern-Segment (0x400000, 0x10010000, 0x10000000).

Direktive .globl :macht ein Label des aktuellen Moduls (Quell-Datei) für andere Module sichtbar,gilt für Variablennamen oder für Sprungadressen im Programmtext,Allozierung entweder im Daten- oder im Textsegment.

Direktive .extern :Alloziert einen Speicherbereich im externen Speichersegment ( typisch ab 0x10000000 ),Speicherbereich ist nicht typisiert, sondern nur mit Längenangabe versehen,macht den zugeordneten Label global sichtbar,nur nützlich für Variablenamen.

Programmfragment: .extern mnExt,4 # allocated in external segment, public .data .globl mnVar # allocated in data segment, public

mnVar: .word 0x00affe00 # global var as parameter for extInc


D.11.1 Beispiel zum Einbinden einer BibliothekOptional alle asm-Dateien aus einen Verzeichnis assemblieren lassen:

Menu: => Settings => assemble all files …


.extern xxVar,4 # allocated in external segment, public .extern mnExt,4 # allocated in external segment, public .data .globl mnVar # allocated in data segment, public

MnVar: .word 0x00affe00 # global var as parameter for extIncxxVar: .word 0x00affe04 # allocated in data segment, private

.textmain: jal extInc # invoke extInc as a subroutine

addi $2,$0,10 # parm for exit-syscall Syscall # exit

.extern bibEx,8 # allocated in external segment, public .extern xxVar,4 # declared but invisible, unused .data

xxVar: .word 0x00affe08 # private to bib-module, unused .text .globl extInc # our code but public

ExtInc: lw $t0,mnVar # load as global variable addi $v0,$t0,1 # increment the value (as result) sw $v0,mnVar # store the value back jr $ra # return from subroutine

BibDemoBib.asm

BibDemoMain.asm

D.12. Fazit

Höhere Sprachen:abstrahieren von der Maschinenarchitektur (Register, Opcodes ...), erlauben eine Konzentrierung auf den Algorithmus,oft suboptimale Codeerzeugung.

Assemblersprache:verbesserte Mnemonik gegenüber binärer Programmierung (Label, Formate),die volle Rechenleistung und alle CPU-Resourcen können genutzt werden,viele Details der Registernutzung und bei Aufrufen sind zu beachten,Wechselwirkung zwischen Architektur & Programm wird sichtbar,Konventionen zum Binden und zum Systemaufruf beachten.

Pseudo-Instruktionen und Makros:Spracherweiterung für den Assemblerprogrammierer,erlauben eine gewisse Konfigurierbarkeit des Programmes,können unwichtige Details aus dem Haupttext wegdefinieren.

MIPS Architektur:Interrupts & Gleitkomma-Verarbeitung haben wir hier weggelassen,einfacher Instruktionssatz mit vielen Registern,effiziente Implementierung möglich.


Documents

D. Assembler, Compiler, Binder D.1.1 Einordnung und ...€¦ · Assembler: der Begriff wird oft unscharf verwendet, manchmal das Hilfsprogramm zur Assemblierung, manchmal die Assemblersprache