Suchen

C programmieren: Wie arbeitet ein C-Compiler?

Autor / Redakteur: Prof. Dr. Christian Siemers * / Sebastian Gerstl

Wie entsteht aus geschriebenem C-Code ein Programm, dass das Zielsystem auch versteht und Umsetzen kann? In diesem Beitrag sehen wir uns Aufbau und Arbeitsweise des C-Compilers genauer an.

Firmen zum Thema

Der C-Compiler verarbeitet den mit C programmierten Code und wandelt ihn in Maschinensprache um, die das Zielsystem auch versteht.
Der C-Compiler verarbeitet den mit C programmierten Code und wandelt ihn in Maschinensprache um, die das Zielsystem auch versteht.
(Bild: Clipdealer)

Unser vorheriger Grundlagenartikeln zum Programmiere mit C befasste sich speziell mit der Standardbibliothek und dem Präprozessor der Programmiersprache. Speziell letzterer ist eines der Elemente, mit dem geschriebener C-Code auch in eine Form umgewandelt wird, die der Rechner umsetzen kann, die sog. Maschinensprache. Dieser Vorgang nennt sich auch Compiling.

Die vier Compilerphasen beim Programmieren mit C

Die Übersetzung eines in C geschriebenen Programms erfolgt in insgesamt vier Phasen, von denen der Compiler an zweien unmittelbar beteiligt ist. Die vier Phasen sind:

Bildergalerie
Bildergalerie mit 12 Bildern
  • Präprozessorphase
  • Frontendphase des Compilers
  • Backendphase des Compilers
  • Linkerphase

Die Präprozessorphase wurde bereits erwähnt. Hierbei handelt es sich um eine Vorbereitung des zu übersetzenden Sourcecodes. Textmakros werden ersetzt, die so genannten include-Dateien eingesetzt, Kommentare gelöscht, die Zeilen immer durch ein Newline-Zeichen getrennt usw. Der Output dieser Phase ist ein reiner Sourcecode, der bislang noch keine Überprüfung oder Übersetzung erfahren hat.

Im Frontend des Compilers (siehe Bild 1) wird dieser Sourcecode eingelesen (Scanner) und überprüft (Parser). Ziel ist es dabei, die korrekte Syntax zu überprüfen, eine erste Syntaxumwandlung und erste Optimierungen durchzuführen. Das Ziel dieser Phase ist ein Zwischencode, der noch von dem Zielsystem (dem Mikroprozessor) unabhängig ist, aber dennoch die Umsetzung in Assembler- oder Maschinensprache vorbereitet. Der Output dieses Frontendteils wird im nächsten Abschnitt genauer betrachtet.

Im Backend des Compilers erfolgt das Einlesen des Zwischencodes (intermediate representation, IR), die Umsetzung in Assemblersprache einschließlich der maschinenspezifischen Optimierung und der Assemblerlauf. Ziel dieses Abschnitts ist der so genannte Objektcode, der neben dem Maschinencode – noch unvollständig – auch Informationen zu den Daten und Programmabschnitten mitführt.

Der Linker liest dann abschließend den Objektcode ein, dazu die angegebenen Standard- und spezifischen Bibliotheken, und fügt das zusammen. Nunmehr sind alle Adressen, auch die der aus der Bibliothek genutzten Funktionen (wie etwa printf) bekannt, und der Maschinencode kann mit allen Adressen vervollständigt werden. Output des Linkers ist ein ausführbarer Maschinencode (in einem File-format).

Die Erzeugung des Zwischencodes

Für den Zwischencode existiert kein genormtes Format, jeder Compiler nutzt dort seine hauseigene Syntax. Besonders interessant ist jedoch das Lance2-Compiler-System, das aus C ein low-level-C erzeugt und dieses als Zwischencode nutzt. Diese Untermenge von C, die dieses Compilersystem als Zwischencode (Intermediate Representation, IR) nutzt, ist natürlich beschränkt. Wesentliche Merkmale sind:

Anweisungen (Statements):

  • Zuweisungen (Assignments): a = b + c, y = function( a, b ), ...
  • Sprünge (Jumps): goto label_1; (diese Sprünge sind Compiler-berechnet und somit ”zugelassen“)
  • Bedingte Sprünge (Conditional Jumps): if( cond ) goto label_2;
  • Marken (Label): label_1:
  • Rücksprung ohne Rückgabewert (return void): return;
  • Rücksprung mit Rückgabewert (return value): return x;

Ausdrücke (Expressions):

  • Symbole: main, a, count …
  • Binäre Ausdrücke (binary expressions): a * b, x / y …
  • Unäre Ausdrücke (unary expressions): ~a, *p …
  • Type Casts: (int), (char)
  • Konstanten (in verschiedenen Formaten): -5, 3.141592653589

Ein kurzer Blick in die obige Liste verrät, dass bei den Anweisungen Schleifen wie for, while und do .. while komplett fehlen. Diese Schleifen werden durch die aufgezählten Konstrukte abgebildet bzw. in diese übersetzt, und es gilt noch zu zeigen, wie dies erfolgt.

Der wichtigste Zusatz, das Zwischencodeformat betreffend, besteht noch in der Beschränkung der Ausdrücke und der Zuweisungen: Sie werden auf ein 3-Adressformat eingeschränkt, d.h., eine Wertzuweisung an ein links stehendes Symbol (a = ...) wird rechtsseitig durch einen unären oder einen binären Ausdruck bestimmt. Längere „Kettenrechnungen“ müssen dementsprechend in Teilrechnungen mit Einfügung temporärer Variablen geteilt werden, eine Aufgabe, die dem Compiler zufällt. Der Grund für diese Einschränkung ist sehr offen-sichtlich: Dem 3-Adressformat entsprechen häufig direkt Assemblerbefehle (etwa: ADD R3, R1, R2, was R3 = R1 + R2 bedeutet).

Bild 2 zeigt die Übersetzung einer if/else if/else-Verzweigung. Dabei wird deutlich, dass nur if-Konstrukte mit anschließendem Sprung (also zusammengefasst der ”bedingte Sprung“) genutzt werden. Die Bedingungen selbst müssen dabei invertiert ausgewertet werden, da ja die Liste der Anweisungen, die bei Erfüllung der ursprünglichen Bedingung auszuführen sind, nun übersprungen werden.

Dies mag etwas holprig wirken, denn bei Zulassung einer üblichen if-Verzweigung wäre dies wesentlich einfacher zu übersetzen. Diese Form der Übersetzung hat jedoch den entscheidenden Vorteil, dass nur bedingte Sprünge verwendet werden, und die lassen sich 1:1 in eine Sequenz von Assemblerbefehlen übersetzen, wie etwa:

cmp R1, R2; (Auswertung der Bedingung)
beq LABEL_IF_1;

Bild 3 zeigt die Übersetzung der while-Schleife, Bild 4 die der etwas komplexeren for-Schleife. In beiden Fällen werden bedingte und unbedingte Sprünge verwendet, um die Schleifenstruktur entsprechend abzubilden, wobei die Bedingung auch wieder invertiert verwendet werden müssen, um den Sprung aus der Schleife zu beschreiben. Entsprechend den hier gezeigten Codeabschnitten können nun auch die switch/case-Verzweigung (Bild 5) und die do..while-Schleife (Bild 6) übersetzt werden, wobei die Mehrfach-Fallunterscheidung (switch/case) etwas komplexer ist.

Laplace-Filter als Beispiel

Ein zweifellos sehr einfaches Filterprogramm zur Bildverarbeitung besteht in dem Laplace-Filter, das näherungsweise die zweite Ableitung eines zweidimensionalen Feldes bildet und dadurch die Kantendetektierung ermöglicht.

Der Algorithmus basiert darauf, dass für jeden neu zu berechnenden Punkt in einem Kantenbild der Wert aus dem ursprünglichen Bild für diesen Punkt genommen wird, mit dem Gewichtsfaktor 4 (im Fall eines 2-dimensionalen Filters) multipliziert wird, und von diesem Wert dann die unmittelbaren Nachbarn (keine Diagonalen) subtrahiert werden.

Bildergalerie
Bildergalerie mit 12 Bildern

Um die Darstellung des Übersetzungsvorgangs möglichst einfach zu halten, wird hier die eindimensionale Variante gewählt (Bild 7). Dieser Code wird nun entsprechend dem Lance2-Compilers in einen Zwischencode, wie zuvor beschrieben, übersetzt.

Konkret werden im Zwischencode nur wenige Operationen benötigt, so z.B.:

  • Wertzuweisungen an Variable, hierbei rechtsseitig einfache Rechnungen mit maximale zwei Operanden und einer Operation; dies wird auch für Adressrechnung bei indizierten Variablen benötigt.
  • Vergleiche mit Zuweisung des Booleschen Werts an eine Variable
  • if-Konstrukt mit einer Variablen, auf deren Wahrheitswert verglichen wird, mit anschließendem (Compiler-berechnetem) goto.

Generierung des Zwischencodes

Diese Form des Zwischencodes bedeutet aber auch, dass voraussichtlich eine Vielzahl von temporären Variablen benötigt wird, da viele Zwischenrechnungen zu machen sind. Im Zwischencode – hier werden die Zeilen ab 101 durchnummeriert – in Listing in Bild 8 fällt sofort die Vielzahl der Variablen auf, die hier zusätzlich zum Originalcode deklariert werden. Die Zeilen 101-102 entsprechen der Deklaration der Arrays in C, sie werden die Größe 100 haben. Die in der Funktion laplace_filter_1d (Bild 7) deklarierte Variable taucht in Zeile 105 wieder auf, sie werden lediglich zusätzlich mit einem ’_’ versehen und durchnummeriert, ansonsten entspricht diese Deklaration der von C.

Die nun folgenden Variablen sind alles vom Compiler erzeugte temporäre Variablen. Man erkennt sie gut an dem fehlenden Unterstrich im Namen. Diese Variablen werden für Berechnungen gebraucht, die im C-Code noch ohne Zwischenschritte auskamen, und sind eine Folge der Übersetzung in der 3-Adresscode. Da der Compiler temporäre Variabelen nicht wieder verwendet, legt er erst einmal für jede dieser Berechnungen eine neue temporäre Variable an. Etwaige Optimierungen sind Aufgabe des nachfolgenden Codegenerators.

Bild 9 zeigt den entstehenden Zwischencode bei den gegebenen Voraussetzung. Die einzelnen Berechnungen erscheinen recht komplex, etwa für den Zugriff auf bild[x+1] (Zeile 150-155), sie sind aber notwendig, und in jeder Zeile wird das 3-Adressformat eingehalten. Der Zugriff auf bild[x+1] bedeutet nicht anderes, als dass die Adresse &bild[0] + (x+1)*sizeof(bild[0]) gebildet und dann auf den Inhalt lesend oder schreibend zugegriffen wird. Diese Berechnung der Zugriffsadresse ist in den Zeilen 150 (Basisadresse als char *) sowie 151-154 (Index- und Adressberechnung) codiert und steht dann in der Variablen t22 zur Verfügung. Die Operation sizeof(bild[0]) liefert dabei den 2 für short.

Das Setzen der Basisadresse &bild[0] findet offenbar mehrfach in den Zeilen 137, 143 und 150 statt. Dies kann eventuell optimiert werden, wobei der Compiler exakt prüfen muss, ob nicht durch externe Programmteile – eine Interrupt Service Routine etwa – die Adresse verändert werden könnte, da bild[] global definiert wurde. In diesem Fall kann aber die Adresse selbst nicht verändert werden – sie ist konstant, nur die Inhalte sind variabel – so dass die Zeilen 143 und 150 entfallen können ( nächsten Abschnitt).

Die Zeilen 134 bis 136 stellen die Auswertung der Schleifenendebedingung dar. Zunächst wird der aktuelle Wert von x_3 mit 99 (X_DIM-1) verglichen, und das Vergleichsergebnis wird der Compiler-generierten Variablen t1 zugewiesen. Diese Variable fungiert als Boole’sche Variable, d.h., sie soll nur Werte für true und false speichern. Die Zuweisung des negierten Wahrheitswerts an t24 in Zeile 135 und die Auswertung durch einen bedingten Sprung (Zeile 136) komplettieren diesen Abschnitt.

Vom Zwischencode zum Assemblercode

Die Übersetzung des Zwischencodes in einen Assemblercode soll anhand einer Modell-CPU erfolgen. Diese wird als MPM3, Mikroprozessormodell #3, bezeich-net und stellt einen RISC-Prozessor mit einer intrinsischen Verarbeitungsbreite von 16 bit dar. Dieses Modell wurde gewählt, weil die typischen Vorgänge daran sehr gut gezeigt werden können, ohne auf die Spezialitäten einer marktgängigen Architektur eingehen zu müssen.

Die spontane Übersetzung des Zwischencodes wird durch einen weiteren Vorgang, die Abbildung der Variablen auf Register oder Speicher betreffend, gebremst. Die Abbildung auf den Maschinencode ist tatsächlich nicht besonders schwierig, hingegen sind die Anforderungen an die Daten schon schwieriger erfüllbar. Bei diesem Vorgang müssen insbesondere Randbedingungen wie Laufzeitminimierung erfüllt werden.

Die Übersetzung des ersten Teils des Zwischencodes (siehe Bild 8) fällt überraschend klein aus. Die gesamte Abbildung der doch eher großen Menge an Variablen erfolgt so, dass lediglich die Variablen bild[] und kanten[] im Speicher angelegt und mit Werten initialisiert wird. Die Initialisierung erfolgt dem Datentyp short gemäß mit 16 bit (DW, define word). Die übrigen Variablen werden auf 7 der vorhandenen 8 Datenregister R0 bis R7 abgebildet (siehe Tabelle 1).

Bild 11 zeigt die Übersetzung des Zwischencodes in den Assemblercode und hierbei auch einige Optimierungsmöglichkeiten (die keineswegs immer im Backendgenerator vorhanden sein werden). Wie bereits dargestellt können die Zeilen 143 und 150 durch Optimierung entfallen (im Übrigen bereits im Zwischencode).

Die Optimierung kann sogar noch weitergehen: Das Programm läuft ein Weile in der Schleife von LL1 (Zeile 133) bis goto LL1 (Zeile 164), und in der gesamten Schleife werden der Wert für short *bild (in R1) und short *kanten (ebenfalls in R1) drei- bzw. einmal im Register geschrieben und dann lesend benutzt. Wenn man also den Wert für short *kanten in einem anderen Register speichern kann (z.B. in R7), dann könnten die Zeilen 310/311 und 326/327 im Assemblercode nach oben, also zwischen Zeile 307 und 308 geschoben werden. Dieses Verfahren, Instruction Scheduling genannt, bewirkt in diesem Fall, dass die Zeilen nur einmal für alle Schleifen durchlaufen werden und spart somit Rechenzeit.

Noch kurz ein Wort zu den vielleicht ungewöhnlich ausschauenden Zeilen 310/311 bzw. 326/327. In diesen Assemblercodezeilen wird ein Register mit einer 16-bit-Konstanten geladen. Die zugrunde liegende Architektur ist (angenommen) eben-falls mit 16-bit-Datenstrukturen (Register, ALU) und 16-bit Adressen versehen, und hierbei kommt es zum Problem. Bei RISC-Prozessoren ist es sozusagen Pflicht, dass ein Befehl in einem Takt bearbeitet wird, und wenn nun ein Befehl eine Breite von 16 bit im Speicher hat, dann passen keine Konstanten mit 16 bit Breite dort hinein (weil ja die Operation auch noch beschrieben werden muss).

Die Lösung besteht in dem Befehlspaar MOV/MOVH (Move und Move High Byte). Der erste Teil kopiert den Operanden – der untere Teil der Adresse für bild bzw. kanten – in die entsprechenden Bits des Registers, meist mit Belegung auch der oberen Bits (auf 0 oder mit Vorzeichenerweiterung), und MOVH kopiert dann den Operanden, dem oberen Teil der Adresse entsprechend, in die oberen Bits des Registers.

Letztes Augenmerk soll noch auf die Übersetzung der bedingten Sprünge gelegt werden (Zeile 134-136). Der Zwischencode bestand hier aus drei Anweisungen: die Bedingung wird auf ihren Wahrheitswert berechnet, der Wert wird invertiert, und unter Auswertung dieses entstehenden booleschen Wertes wird dann gesprun-gen (oder nicht). Im Assemblercode treten hiervon nur noch zwei Anweisungen auf: Die Auswertung der Bedingung wird auf das Setzen von Flags abgebildet (Zeile 309), und diese Flags werden – mit logischer Invertierung, denn BGE bedeutet branch if greater or equal, was die umgekehrte Bedingung zu kleiner (less than) ist – dann in Zeile 310 ausgewertet.

C-Compiler: Optimierungsmöglichkeiten

Im vorangegangenen Beispiel wurden die Zeilen 143 und 150 wegoptimiert, weil es sich offensichtlich immer um die gleiche Zuweisung handelt. Im Allgemeinen gilt, dass derartige Optimierung der mehrfachen Wertzuweisung durchgeführt werden können, wenn sichergestellt ist, dass Wertänderungen – auch durch externe Routinen wie ISR – ausgeschlossen sind.

Diese Optimierung, die bereits im Zwischencode erfolgen kann, ist immer dann möglich, wenn die entsprechende Variable lokal angelegt ist oder bei globaler Speicherklasse konstant ist.

Im Fall der Beispiels des eindimensionalen Laplace-Filters (Bild 7) galt die zweite Voraussetzung, da die Adresse des Arrays bild[], also &(bild[0]), konstant angelegt wird.

Mit diesem Beispiel wollen wir die Grundlagen zur C-Programmierung vorerst abschließen. Damit sich keine Fehler beim Coden einschleichen empfiehlt es sich allerdings, einige Leitlinien zu beachten. In einem Abschließenden Artikel zum Programmieren mit C wollen daher – beispielhaft – auf Codierungsregeln (Coding Rules) eingehen, die gerade für Softwareentwicklung in sicherheitskritischen Bereichen gelten und anerkannt sind.

Dieser Beitrag findet sich im Handbuch „Embedded Systems Engineering“ im Kapitel "Einführung in die Sprache C". Das Handbuch ist auch als kostenlose PDF-Version in voller Länge auf ELEKTRONIKPRAXIS.de verfügbar.

* Prof. Dr. Christian Siemers lehrt an der Technische Universität Clausthal und arbeitet dort am Institut für Elektrische Informationstechnik (IEI).

(ID:45439187)