Performance- und energieeziente Compilierung fu¨r digitale SIMD-Signalprozessoren mittels genetischer Algorithmen Dissertation zur Erlangung des Grades eines Doktors der Naturwissenschaften der Universita¨t Dortmund am Fachbereich Informatik von Markus Lorenz Dortmund 2003 Tag der mu¨ndlichen Pru¨fung: Dekan/Dekanin: Gutachter: Vorwort Diese Arbeit ist wa¨hrend meiner Zeit als wissenschaftlicher Mitarbeiter am Lehrstuhl Informatik XII der Universita¨t Dortmund unter der Betreuung von Prof. Dr. Peter Mar- wedel entstanden. Ich mo¨chte mich hiermit bei allen Personen bedanken, die direkt oder indirekt1 zu der Entstehung und Vollendung dieser Arbeit beigetragen haben. Ich danke Herrn Prof. Dr. Peter Marwedel fu¨r die Mo¨glichkeit zur Umsetzung dieser Arbeit und fu¨r seine Ratschla¨ge und Unterstu¨tzung, die er mir wa¨hrend der Entwicklung der Arbeit gegeben hat. Weiterhin mo¨chte ich Herrn Prof. Dr. Wolfgang Banzhaf fu¨r die Bereitschaft zur Erstellung des Zweitgutachtens danken. Ganz besonderer Dank gilt Steven Bashford, Heiko Falk, Birger Landwehr, Stefan Stein- ke und Lars Wehmeyer fu¨r deren vielfa¨ltige und groartige Unterstu¨tzung zur Erstellung dieser Arbeit. Neben den Kollegen am Lehrstuhl haben auch die Arbeiten der von mir betreuten Diplomanden David Kottmann, Martin Horst und Markus Fiesel einen groen Anteil an dieser Arbeit. Ebenso mo¨chte ich Thorsten Dra¨ger vom Lehrstuhl Mobile Nach- richtensysteme der TU Dresden fu¨r die hervorragende Zusammenarbeit danken. Vor allem mo¨chte ich meiner Frau dafu¨r danken, dass sie dieses Projekt unterstu¨tzt und mitermo¨glicht hat, obwohl die fu¨r die Forschung investierte Zeit ha¨u g u¨ber die geregelte Arbeitszeit weit hinausging. 1Die Arbeit ist von der Deutschen Forschungsgemeinschaft (DFG) gefo¨rdert worden. i Fu¨r meine Frau Sabine und fu¨r meine Kinder Maike und Robin. Inhaltsverzeichnis 1 Einleitung 1 1.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Phasen des Compilierungsprozesses . . . . . . . . . . . . . . . . . . 3 1.1.2 Digitale Signalverarbeitung . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Prozessoren der M3-Plattform . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 M3-DSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Energiekostenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Energieoptimierung durch Compiler . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Problemanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 Zielsetzungen und U¨berblick . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Compiler-Zwischendarstellungen 21 2.1 Grundlegende Begri e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Zwischendarstellungen existierender Compilersysteme . . . . . . . . . . . . 25 2.3 Low-Level Zwischendarstellung (GeLIR) . . . . . . . . . . . . . . . . . . . 29 2.3.1 Programmdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.2 Architekturdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3 Darstellung alternativer Maschinenprogramme . . . . . . . . . . . . 35 2.3.4 Constraintpropagierung . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.5 Analysen & Optimierungen . . . . . . . . . . . . . . . . . . . . . . 39 2.3.6 Graphische Visualisierung . . . . . . . . . . . . . . . . . . . . . . . 41 2.3.7 XeLIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.8 Simulationsumgebung . . . . . . . . . . . . . . . . . . . . . . . . . 43 iii 3 Codegenerierung fu¨r digitale Signalprozessoren 47 3.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.1 Baumbasierte vs. graphbasierte Codeselektion . . . . . . . . . . . . 48 3.1.2 Bedeutung phasengekoppelter Optimierungsverfahren . . . . . . . . 49 3.1.3 Bedeutung von Adressgenerierungseinheiten . . . . . . . . . . . . . 51 3.1.4 Kombination von Optimierungszielen . . . . . . . . . . . . . . . . . 52 3.2 Bestehende Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2.1 Codegenerierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2.2 Adresscode-Generierung . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.3 Energieoptimierungen . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 U¨bersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.5 Genetischer Codegenerator (GCG) . . . . . . . . . . . . . . . . . . . . . . 62 3.5.1 Optimierung auf Basis genetischer Algorithmen . . . . . . . . . . . 63 3.5.2 Mehrzieloptimierung mit genetischen Algorithmen . . . . . . . . . . 65 3.5.3 Chromosomale Darstellung . . . . . . . . . . . . . . . . . . . . . . . 67 3.5.4 Initialisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.5.5 Bewertung der Individuen . . . . . . . . . . . . . . . . . . . . . . . 74 3.5.6 Selektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.5.7 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.8 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.6 Adresscode-Generierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.6.1 Algorithmus zur Adresscode-Generierung . . . . . . . . . . . . . . . 80 3.6.2 Phasenkopplung mit Codegenerierung . . . . . . . . . . . . . . . . . 84 3.7 Adresscode-Kompaktierung . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.8 Bewertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.8.1 Einstellung der Parameter des genetischen Algorithmus . . . . . . . 86 3.8.2 Genetischer Codegenerator . . . . . . . . . . . . . . . . . . . . . . . 88 3.8.3 Adresscode-Generierung . . . . . . . . . . . . . . . . . . . . . . . . 92 3.8.4 Retargierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4 SIMD-Optimierungen 97 4.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.1.1 Allgemeine Problembereiche . . . . . . . . . . . . . . . . . . . . . . 99 4.1.2 M3-spezi sche Problembereiche . . . . . . . . . . . . . . . . . . . . 99 4.1.3 Auswirkungen auf den Codegenerator . . . . . . . . . . . . . . . . . 101 4.2 Bestehende Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.3 U¨bersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.4 Architekturdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.5 Programmdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.6 Vektorisierung von Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.6.1 Unterstu¨tzende Schleifentransformationen . . . . . . . . . . . . . . 114 4.6.2 U¨berpru¨fung auf Vektorisierbarkeit . . . . . . . . . . . . . . . . . . 117 4.6.3 Ausnutzung spezieller Datentransfers . . . . . . . . . . . . . . . . . 119 4.6.4 Optimierte Anordnung von Arrays . . . . . . . . . . . . . . . . . . 121 4.7 Optimierte Anordnung skalarer Variablen . . . . . . . . . . . . . . . . . . . 123 4.7.1 Problemde nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.7.2 Lo¨sungsansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 4.7.3 Integration in den Compilierungsprozess . . . . . . . . . . . . . . . 129 4.8 Bewertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.8.1 Vektorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.8.2 Anordnung skalarer Variablen . . . . . . . . . . . . . . . . . . . . . 135 5 Experimentelle Ergebnisse 139 5.1 Betrachtete Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.2 Bewertung der Compilertechniken . . . . . . . . . . . . . . . . . . . . . . . 141 5.3 Vergleich mit handgeneriertem Assemblercode . . . . . . . . . . . . . . . . 145 5.4 Systemvergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.5 HW/SW-Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6 Zusammenfassung 151 6.1 Compiler-Zwischendarstellung (GeLIR) . . . . . . . . . . . . . . . . . . . . 152 6.2 Zielarchitektur und Energiekostenmodell . . . . . . . . . . . . . . . . . . . 153 6.3 Genetischer Codegenerator (GCG) . . . . . . . . . . . . . . . . . . . . . . 154 6.4 SIMD-Optimierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.5 Konklusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 A Referenzcode 159 A.1 Testroutine complex multiply . . . . . . . . . . . . . . . . . . . . . . . . . 160 A.1.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 A.1.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 160 A.2 Testroutine complex update . . . . . . . . . . . . . . . . . . . . . . . . . . 161 A.2.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 A.2.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 161 A.3 Testroutine biquad one section . . . . . . . . . . . . . . . . . . . . . . . . . 162 A.3.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 A.3.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 162 A.4 Testroutine lattice2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 A.4.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 A.4.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 163 A.5 Testroutine dfg1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 A.5.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 A.5.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 164 A.6 Testroutine dfg2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 A.6.1 Quellprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 A.6.2 Handgeschriebener Pseudo-Assemblercode . . . . . . . . . . . . . . 165 Literaturverzeichnis 167 Indexverzeichnis 179 Kurz-Zusammenfassung In den letzten Jahren war ein sta¨ndig zunehmender Einsatz von eingebetteten Systemen in vielen Produkten unseres ta¨glichen Lebens zu verzeichnen. Ha¨u g sind an diese Sys- teme spezielle Anforderungen bezu¨glich einer Realzeitfa¨higkeit, einer geringen Gro¨e und auch zunehmend eines geringen Energiebedarfs gebunden. Um diesen Anforderungen zu genu¨gen und dennoch ein hohes Ma an Flexibilita¨t beim Systementwurf beizubehalten, werden anstelle von anwendungsspezi scher Hardware ha¨u g digitale Signalprozessoren (DSPs) zur Datenverarbeitung eingesetzt. Mit diesen wird auch bei Spezi kationsa¨nde- rungen in spa¨ten Entwicklungsphasen i.d.R. keine kosten- und zeitintensive Neuentwick- lung der verwendeten Hardware erforderlich. Leider stellt die manuelle U¨berfu¨hrung eines Anwendungsprogramms in Assemblercode des Zielprozessors eine a¨uerst zeitaufwa¨ndige und fehlertra¨chtige Aufgabe dar. Aus diesem Grund werden Compiler beno¨tigt, die in der Lage sind, eine gegebene Anwendung in ezienten Assemblercode zu u¨berfu¨hren. Im Vergleich zu General-Purpose Prozessoren (GPPs) weisen DSPs jedoch spezielle Architek- turmerkmale auf, die von herko¨mmlichen Compilertechniken nur unzureichend oder gar nicht ausgenutzt werden. Das Ziel dieser Arbeit besteht in der Entwicklung neuer Compilertechniken fu¨r DSPs, um die durch Compiler generierte Codequalita¨t insbesondere hinsichtlich der Ausfu¨hrungs- zeit und des Energiebedarfs zu verbessern. Um eine Wiederverwendung der entwickelten Techniken in anderen Compilern zu ermo¨glichen, setzen diese auf der ebenfalls in dieser Arbeit beschriebenen neuen Zwischendarstellung GeLIR (Generic Low-Level Intermediate Representation) auf. Als Schwerpunkt dieser Arbeit wird ein Codegenerator vorgestellt, der in der Lage ist, eine graphbasierte Codeselektion durchzufu¨hren und zusa¨tzlich die Phasen der Codeselektion, Instruktionsanordnung (einschlielich Kompaktierung) und Registerallokation im Sinne einer Phasenkopplung simultan lo¨st. Da dies die Lo¨sung eines NP-harten Optimierungs- problems darstellt, ist dem Codegenerator ein Optimierungsverfahren auf Basis eines ge- netischen Algorithmus zugrunde gelegt. Zusa¨tzlich werden bei der Durchfu¨hrung der Tei- laufgaben Codeselektion, Instruktionsauswahl und Registerallokation bereits Wechselwir- kungen mit der nachfolgend durchgefu¨hrten Adresscode-Generierung beru¨cksichtigt. Auf- grund der flexiblen Spezi kationsmo¨glichkeit von Kostenfunktionen in genetischen Opti- vii mierungsverfahren ist der Codegenerator unter Verwendung eines Energiekostenmodells in der Lage, eine energieeziente Auswahl und Anordnung von Instruktionen durchzufu¨hren. Als weiterer Schwerpunkt werden Optimierungsverfahren zur e ektiven Ausnutzung der parallelen Datenpfade und von SIMD-Speicherzugri en vorgestellt. Mit der Integration des Energiekostenmodells in den Codegenerator und den Simulator wird dabei mit dieser Arbeit erstmalig das Potential von SIMD-Operationen hinsichtlich der energieezienten Ausfu¨hrung von DSP-Programmen compilerunterstu¨tzt untersucht. Durch die beispiel- hafte Implementierung der Techniken fu¨r eine DSP-Architektur und die Retargierung des genetischen Codegenerators auf einen weiteren DSP wird die Anwendbarkeit fu¨r reale Prozessoren gezeigt. Kapitel 1 Einleitung Durch die zunehmende Miniaturisierung elektronischer Schaltungen in den letzten Jahr- zehnten wurden den Anwendern stetig steigende Rechenleistungen bei immer geringer werdender Chipfla¨che zur Verfu¨gung gestellt. 1965 sagte Gordon Moore in dem spa¨ter nach ihm benannten Moore’schen Gesetz voraus, dass sich in den darauf folgenden zehn Jahren bis 1975 die Anzahl der auf einem integrierten Schaltkreis vorhandenen Transis- toren alle 18 Monate verdoppelt [Moo65]. Wie in Abb. 1.1 zu erkennen ist, hat dieses Gesetz bis heute noch anna¨hernd bestand. Intels Paolo Gorgini ist sogar der Meinung, dass dieses Gesetz fu¨r weitere 15 Jahre zutri t. So soll es im Jahre 2014 Chips mit 64 Milliarden Transistoren und 3,6 GHz Taktfrequenz geben [Sti99]. 1.000 10.000 100.000 1.000.000 10.000.000 100.000.000 Jahr # T r a n s i s t o r e n 4004 8008 8080 286 386 486 Pentium Pentium II Pentium III Pentium 4 8086 1 9 7 1 1 9 7 2 1 9 7 4 1 9 7 8 1 9 8 2 1 9 8 5 1 9 8 9 1 9 9 3 1 9 9 7 1 9 9 9 2 0 0 0 Vorhersage Abb. 1.1: Moore’sches Gesetz am Beispiel der Entwicklung der Intel-Prozessoren (ent- nommen aus [Int]) 1 2 KAPITEL 1. EINLEITUNG Durch die Miniaturisierung besteht die Mo¨glichkeit immer gro¨ere, leistungsfa¨higere Sys- teme bestehend aus optimierter Hardware und darauf lau a¨higer Software auf einem Chip (SoC = Systems-on-Chip) zu integrieren. Hierdurch ko¨nnen eingebettete Systeme den sta¨ndig durch neue Anwendungen gestiegenen Anforderungen bezu¨glich Ausfu¨hrungszeit, Chipgro¨e und in zunehmendem Mae auch geringem Stromverbrauch gerecht werden. Eingebettete Systeme sind in der Regel Bestandteil eines komplexeren Systems und zeich- nen sich im Wesentlichen dadurch aus, dass sie physikalische Informationen u¨ber Sensoren aufnehmen, verarbeiten und bestimmte Steuerungs- und Regelungsaufgaben durchfu¨hren. Typische Einsatzgebiete stellen Anwendungen in Handys (z.B. SMS, WAP), in Automo- bilen (z.B. Fensterheber, Airbags) und in Flugzeugen (z.B. Kollisionswarngera¨te) dar. Insbesondere bei mobilen Gera¨ten, wie Handys, stellt neben einer Echtzeitverarbeitung, einer geringen Gro¨e und einem geringen Gewicht, der Energieverbrauch ein wichtiges Verkaufsargument dar. Wa¨hrend fru¨her diese Aufgaben aufgrund der bestehenden Anfor- derungen noch von speziell an die Anwendung angepassten ASICs (Application Speci c Integrated Circuits) durchgefu¨hrt werden mussten, wurde in zunehmendem Mae eine Softwarelo¨sung durch den Einsatz von eingebetteten Prozessoren mo¨glich. Dies ist a¨uerst erstrebenswert, da diese programmierbar sind und somit bei Spezi kationsa¨nderungen in spa¨ten Designzyklen oder bei Updates/Upgrades, eine kosten- und zeitintensive Neuent- wicklung vermeiden (Time-to-Market). Um den genannten Anforderungen gerecht zu werden, werden ha¨u g digitale Signalpro- zessoren (DSPs) eingesetzt, deren Befehlssa¨tze im Vergleich zu General-Purpose Prozes- soren (GPPs) eine wesentlich e ektivere Umsetzung von rechenintensiven Anwendungen erlauben. Leider werden aufgrund der unzureichenden Codequalita¨t der von Compilern generierten Programme, Assemblerprogramme (oder zumindest Teile davon) i.d.R. immer noch per Hand erzeugt. Dies ist jedoch ein sehr zeitaufwa¨ndiger Vorgang, der eine hohe Fehleranfa¨lligkeit und eine geringe Portabilita¨t zur Folge hat. Aus diesem Grund besteht ein sehr groer Bedarf an optimierenden Compilern, die an die Architektur angepasst und damit in der Lage sind, die speziellen Architektureigenschaften von DSPs e ektiv auszunutzen [MG95]. Nach einer Einfu¨hrung in die Problematik im na¨chsten Abschnitt werden kurz die Pro- zessoren der M3-Plattform, die in dieser Arbeit als Zielarchitektur dienen, vorgestellt. In Abschnitt 1.3 werden dann Mo¨glichkeiten zur Reduzierung des Energieverbrauchs durch Compiler vorgestellt. Nach einer allgemeinen Problemanalyse bestehender DSP-Compiler wird abschlieend auf die Zielsetzungen dieser Arbeit eingegangen. 1.1. EINFU¨HRUNG 3 1.1 Einfu¨hrung In diesem Abschnitt wird ein U¨berblick u¨ber die zugrunde liegende Problematik der Code- generierung gegeben, indem zuna¨chst der grundsa¨tzliche Aufbau von Compilern beschrie- ben wird. Danach werden anhand der Aufgaben der digitalen Signalverarbeitung allge- meine Anforderungen an die Prozessoren, hier im speziellen digitale Signalprozessoren, abgeleitet. 1.1.1 Phasen des Compilierungsprozesses Die Aufgabe eines Compilers besteht in der Transformation eines gegebenen Quellpro- gramms in die Sprache des Zielprozessors, unter Wahrung der semantischen Korrektheit und gegebenenfalls Einhaltung weiterer Randbedingungen. Da es sich hierbei um eine sehr komplexe Aufgabe handelt, wird der Compilierungsprozess in mehrere Phasen un- terteilt. In Abb. 1.2 sind dies die Teilbereiche Front-End, Middle-End und Back-End, die sich wiederum in mehrere Teilphasen unterteilen. IR to LIR C to IR IR LIR to Asm ASM C-Src LIR prozessorunabhängig prozessorabhängig Standardoptimierungen - Constant-Folding - Copy-Propagation - Dead-Code-Elimination - ... ! ! ! Standardoptimierungen Codegenerierung Peephole-Optimierungen - Codeselektion (CS) - Instruktionsanordnung (IA) - Registerallokation (RA) - Adresscode-Generierung (ACG) Front-End Middle-End Back-End Abb. 1.2: Compilierungsphasen Das Front-End liest zuna¨chst ein gegebenes Hochsprachenprogramm (hier gegeben in der Programmiersprache C) ein und transformiert dieses nach Durchfu¨hrung einer le- xikalischen, syntaktischen und semantischen Analyse in eine prozessorunabha¨ngige Zwi- schendarstellung IR (Intermediate Representation). Danach ko¨nnen auf dieser Darstellung im Middle-End prozessorunabha¨ngige Standardoptimierungen wie z.B. Constant-Folding, Copy-Propagation oder Dead-Code-Elimination durchgefu¨hrt werden, die jeweils eine gege- bene IR einlesen und modi ziert zuru¨ckschreiben (s. [ASU86, Muc97] fu¨r einen U¨berblick). Diese Optimierungen ko¨nnen fu¨r jede betrachtete Zielarchitektur wieder verwendet wer- den, da bislang keinerlei prozessorspezi sche Eigenschaften beru¨cksichtigt worden sind. 4 KAPITEL 1. EINLEITUNG Im Back-End gilt es nun, das durch die IR gegebene Programm in ein a¨quivalentes Pro- gramm zu u¨berfu¨hren, das auf der zugrunde gelegten Zielarchitektur ausgefu¨hrt werden kann. Da dies eine sehr komplexe Aufgabe darstellt, wird dieser Vorgang in eine Reihe von Teilaufgaben unterteilt, die sinnvollerweise wiederum auf einer einheitlichen Zwischendar- stellung LIR (Low-Level IR) arbeiten sollten. Mit der Durchfu¨hrung der Codegenerierung werden nun schrittweise architekturspezi sche Informationen der LIR hinzugefu¨gt. Dabei werden im Allgemeinen die folgenden Teilaufgaben unterschieden:  Mit der Durchfu¨hrung der Codeselektion (CS) gilt es, die vorhandenen Operationen der LIR mit elementaren Anweisungen der Zielmaschine (Maschinenoperationen) zu u¨berdecken. Beispiele fu¨r Maschinenoperationen (MOs) sind Anweisungen zur Durchfu¨hrung eines Datentransfers oder einer arithmetischen Operation. Wenn eine geringe Ausfu¨hrungszeit das Optimierungsziel darstellt, kann z.B. eine Minimierung der Anzahl der erforderlichen MOs als Optimierungskriterium dienen. Zur Minimie- rung des Energieverbrauchs bietet es sich stattdessen an, solche MOs auszuwa¨hlen, die den geringsten Energieverbrauch aufweisen. Da in diesem Schritt jedoch kei- ne Entscheidungen hinsichtlich der parallelen Ausfu¨hrung getro en werden, kann dies nur einen ungefa¨hren Anhaltspunkt u¨ber die letztendlich resultierende Anzahl erforderlicher Prozessorzyklen geben.  Die Aufgabe der Instruktionsanordnung (IA) besteht in der Zuordnung von MOs zu ausfu¨hrbaren Befehlen der Zielmaschine (Maschineninstruktionen) unter Einhaltung der gegebenen Randbedingungen, wie z.B. Datenabha¨ngigkeiten. Im einfachsten Fall entha¨lt dabei jede Maschineninstruktion (MI) genau eine Maschinenoperation. Fu¨r Prozessoren mit parallelen Ausfu¨hrungsmo¨glichkeiten, wie es bei DSPs u¨blicherweise gegeben ist, umfasst diese Phase zusa¨tzlich noch die Aufgabe der Kompaktierung, bei der die gegebenen MOs zu MIs zusammengefasst werden. Die Ausfu¨hrungszeit kann reduziert werden, indem die Gesamtzahl der resultierenden MIs minimiert wird. Allerdings ergeben sich auch hier Wechselwirkungen zu den anderen Teilphasen, wie z.B. der Registerallokation.  Die Registerallokation (RA) hat die Aufgabe, alle in einem Programm verwende- ten und durch Modi kationen (Transformationen und Optimierungen) hinzugefu¨gte tempora¨re Variablen (virtuelle Register) auf reale Register der Zielmaschine abzubil- den. Dabei muss entschieden werden, welche Variablen in Registern gehalten werden (Registervergabe) und welche Register konkret verwendet werden sollen (Registerbin- dung). U¨bersteigt die Anzahl der gleichzeitig lebendigen Variablen1 die Anzahl der verwendbaren Register, so mu¨ssen Variablen in den Speicher ausgelagert (gespillt) 1Dies sind Variablen, die zu einem spa¨teren Zeitpunkt der Programmausfu¨hrung noch verwendet werden, ohne dass sie zuvor mit einem neuen Wert u¨berschrieben werden. 1.1. EINFU¨HRUNG 5 und ein entsprechender Spillcode eingefu¨gt werden. Da dies zusa¨tzlicher Taktzyklen und energieintensiver Speicherzugri e bedarf, besteht das Ziel dieser Phase in der Minimierung des Spillcodes.  Sind, wie bei DSPs u¨blich, spezielle Adressgenerierungseinheiten (AGUs) vorhan- den, fu¨hren Codegeneratoren fu¨r DSPs zusa¨tzlich noch eine Adresscode-Generierung (ACG) durch. Diese hat die Aufgabe, zuna¨chst allen relevanten Variablen konkrete Speicheradressen zuzuweisen und danach alle fu¨r die Speicherzugri e erforderlichen Adressen mit geringst mo¨glichem Overhead zu berechnen. Da sich die zuvor beschriebenen Teilphasen insbesondere bei Architekturen mit irregula¨ren Befehlssa¨tzen gegenseitig beeinflussen (Phasenkopplungsproblem), mu¨ssen diese zur Erzie- lung von optimalen Lo¨sungen simultan gelo¨st werden. Allerdings stellt bereits die optimale Lo¨sung jeder einzelnen Phase fu¨r den allgemeinen Fall die Lo¨sung eines NP-harten Op- timierungsproblems dar, so dass aufgrund der erforderlichen Phasenkopplung die Suche nach optimalen oder nahezu optimalen Lo¨sungen erheblich erschwert wird. Nach der Durchfu¨hrung von Optimierungen im Back-End ko¨nnen wiederholt Standard- optimierungen, wie z.B. Dead-Code-Elimination ausgefu¨hrt werden, diesmal jedoch un- ter Beru¨cksichtigung architekturspezi scher Merkmale. Abschlieend werden i.d.R. auf dem generierten Maschinencode lokale Optimierungen (Peephole-Optimierungen) durch- gefu¨hrt. 1.1.2 Digitale Signalverarbeitung Aufgrund des zunehmenden Bedarfs an schneller und fehlerfreier Datenverarbeitung wer- den in immer sta¨rkerem Mae digitale anstelle analoger Signale verarbeitet. Ein wichtiger Grund ist dabei die Mo¨glichkeit der Durchfu¨hrung von Spezi kationsa¨nderungen in Soft- ware. Des Weiteren besteht ha¨u g z.B. auch die Mo¨glichkeit der Rekonstruktion eines durch Rauschen verfa¨lschten Ursprungssignals beim Empfa¨nger und das Anlegen von Ko- pien ohne Qualita¨tsverlust. Der FIR-Filter (FIR = Finite Impulse Response) stellt einen ha¨u g umgesetzten Algo- rithmus in der digitalen Signalverarbeitung dar [EB98]. Das Verhalten eines FIR-Filters N -ter Ordnung, mit dem Eingangswert x[n−i] und dem Filterkoezienten b[i] kann durch die Gleichung y[n] = N−1 ∑ i=0 b[i]  x[n − i] beschrieben werden. Der Ausgangswert y[n] zum Zeitpunkt n stellt dann die gewichtete Summe der letzten N Eingangswerte dar. In Abb. 1.3 ist der dazugeho¨rige Signalflussgraph dieses FIR-Filters dargestellt. 6 KAPITEL 1. EINLEITUNG + * Z -1 * * * + + Z -1 Z -1 ... ... x[n] b[0] b[1] b[N-2] b[N-1] x[n-1] x[n-(N-2)] x[n-(N-1)] y[n] Abb. 1.3: Signalflussgraph eines FIR-Filters N-ter Ordnung Die mit Z−1 benannten Elemente stellen Verzo¨gerungselemente (z.B. Register oder Spei- cher) dar, die eine Kopie ihres Eingangswertes mit Verzo¨gerung an ihren Ausgang wei- terleiten. Im Falle des dargestellten FIR-Filters sind N − 1 solcher Verzo¨gerungselemente erforderlich, die auch als Delay-Line bezeichnet werden. Zu jedem Zeitpunkt entha¨lt die Delay-Line die letzten N − 1 in das System eingegangenen Signale, die einschlielich des aktuellen Eingabewertes x[n] zur Berechnung des neuen Ausgabesignals y[n] beno¨tigt wer- den. Fu¨r die Berechnung des nachfolgenden Ausgabesignals werden die Werte innerhalb der Delay-Line um jeweils eine Position nach rechts geschoben. Danach kann ein neuer Ausgabewert berechnet werden, indem das aktuelle Eingangssignal und die in der Delay- Line enthaltenen Signale mit den Filter-Koezienten b[0] bis b[N − 1] multipliziert und aufsummiert werden. Durch die Wahl der La¨nge der Delay-Line und der Koezienten wird das Verhalten eines solchen FIR-Filters bestimmt. Erfolgt die Umsetzung mittels eines DSPs, ko¨nnen ohne aufwa¨ndige A¨nderungen der Hardware unterschiedliche Filter durch Umprogrammieren des DSPs realisiert werden. Um z.B. die Implementierung des FIR-Filters so ezient wie mo¨glich zu gestalten, stellen DSPs Befehle zur Verfu¨gung, die speziell an derartige Aufgaben angepasst sind [Mar97, EB98]. Dies sind z.B.:  Bilden der Summe von Multiplikationen mit Hilfe von MAC-Operationen (MAC = Multiply-Accumulate).  Erho¨hung der Speicherbandbreite z.B. durch Aufteilung des Speichers in zwei oder mehrere getrennte Datenspeicher, auf die gleichzeitig zugegri en werden kann. Dies ermo¨glicht z.B. in der FIR-Routine das parallele Laden des zu verarbeitenden Ein- gangssignals und eines Filter-Koezienten.  Unterstu¨tzung einer (ha¨u g eingeschra¨nkten) parallelen Ausfu¨hrung von Datenma- nipulationen, Datentransfers und/oder Speicherzugri en. Dazu werden u.a. spezielle Adressgenerierungseinheiten eingesetzt, die aufgrund vorhandener Spezialbefehle ei- ne e ektive Adressberechnung parallel zu anderen Funktionseinheiten erlauben. 1.2. PROZESSOREN DER M3-PLATTFORM 7  Verringerung des Schleifen-Overheads durch die Ausfu¨hrung einer begrenzten An- zahl von Instruktionen in Zero-Overhead Hardware-Loops (ZOL). Diese erlauben nach der Initialisierung eines speziellen Hardwareregisters mit der Anzahl aus- zufu¨hrender Schleifeniterationen die Ausfu¨hrung der eingebetteten Instruktionen ohne den sonst u¨blichen Schleifen-Overhead. 1.2 Prozessoren der M3-Plattform Aufgrund der unterschiedlichen Anwendungsbereiche und den damit verbundenen an- wendungsspezi schen Anforderungen, fu¨r die DSPs eingesetzt werden sollen, werden von DSP-Herstellern zunehmend Plattformlo¨sungen angestrebt. Dadurch soll die Entwicklung von speziellen ASICs mit den damit verbundenen Nachteilen vermieden werden. So kann mit Hilfe einer DSP-Plattform schnell und kostengu¨nstig ein speziell an die Anwendung angepasster DSP entwickelt werden. Bei steigenden Anforderungen an den DSP kann dadurch eine aufwa¨ndige Neuentwicklung oder sogar der Einsatz von ASICs vermieden werden, da die bestehende DSP-Architektur einfach erweiterbar ist [WFL+99]. Beispiele fu¨r solche Plattformlo¨sungen stellen der StarCore von Motorola [Sta], der TigerShark von Analog Devices [Tig] und die M3-Plattform von der TU Dresden [FWD+98, WFL+99] dar. Da der Speicher in den Prozessoren ha¨u g einen Engpass darstellt, wird in vie- len Prozessoren der Speicher in mehrere Speicherba¨nke aufgeteilt. So sind z.B. beim DSP56000 [Mot86], der ADSP-210x-Familie [Dev91] und dem Gepard [GFO97] zwei Speicherba¨nke vorhanden, auf die gleichzeitig zugegri en werden kann. Im Unterschied dazu verwendet der Media-Prozessor von MicroUnity einen breiten Standardspeicher, der in Gruppen unterteilt ist [Han96]. Mehrere Daten werden dabei zu einer Gruppe zusam- mengefasst und u¨ber eine gemeinsame Adresse angesprochen. Auf diese Weise geladene Daten ko¨nnen dann nach dem SIMD-Prinzip (SIMD = Single Instruction Multiple Data) verarbeitet werden. Allerdings ist bei einer Erweiterung dieser Architektur ein Neuentwurf der Kommunikationseinheit erforderlich. Die M3-Plattform basiert, wie der Media-Prozessor von MicroUnity, ebenfalls auf dem Gruppenprinzip, ermo¨glicht jedoch durch die Aufteilung in modulare Einheiten eine ein- fache Anpassung an applikationsspezi sche Spezi kationsa¨nderungen. Eine Anpassung an eine gro¨ere Rechenleistung kann z.B. durch eine Erho¨hung der Anzahl paralleler Daten- pfade erreicht werden, auf denen eine Abarbeitung nach dem SIMD-Prinzip vorgesehen ist. Da i.d.R. nicht zu jedem Zeitpunkt alle Datenpfade beno¨tigt werden, besteht neben der Ausfu¨hrung von SIMD-Operationen ebenfalls die Mo¨glichkeit der Abarbeitung in einem speziellen Einstreifen-Modus. Hierbei erfolgt die Verarbeitung nach dem SISD-Prinzip (SISD = Single Instruction Single Data) lediglich auf einem Streifen (Slice), indem die 8 KAPITEL 1. EINLEITUNG restlichen Datenpfade abgeschaltet werden. Ein Slice besteht dabei aus einem Datenpfad inklusive dazugeho¨riger Eingangsregister (s. auch Abb. 1.4). Das Befehlswort ist als VLIW (Very Long Instruction Word) organisiert und erlaubt z.B. eine unabha¨ngige Kontrolle zur Datenmanipulation, fu¨r Datentransfers, zur Programm- steuerung und Adressgenerierung. Die Prozessoren dieser skalierbaren Plattform dienen als Zielarchitektur dieser Arbeit, wobei der im folgenden Abschnitt na¨her beschriebene M3-DSP eine konkrete Instanz darstellt. 1.2.1 M3-DSP Der M3-DSP stellt eine Instanz mit 16 Slices der skalierbaren M3-Plattform fu¨r Anwen- dungen aus dem Bereich der mobilen Telekommunikation dar (s. Abb. 1.4). Gruppenspeicher für Daten (16 x 16) bit Verbindungsnetzwerk Zwischenregisterfile M A 0 L o k a l e K o m m u n i k a t i o n MAC ALU Slice 0 AGU B 0 C 0 D 0 ACCU 0 A 1 L o k a l e K o m m u n i k a t i o n MAC ALU 1 B 1 C 1 D 1 ACCU 1 A 15 MAC ALU 15 B 15 C 15 D 15 ACCU L o k a l e K o m m u n i k a t i o n ... 15 Abb. 1.4: Basisarchitektur des M3-DSPs Um eine e ektive parallele Verwendung aller Datenpfade zu erlauben, ist der auf dem Chip vorhandene Speicher als Gruppenspeicher organisiert. Dies bedeutet, dass mit jedem Speicherzugri auf jeweils eine Gruppe von 16 Datenworten lesend/schreibend zugegrif- fen wird. Bei einem Ladezugri wird die adressierte Gruppe in das Zwischenregister le M geladen, von dem aus die geladenen Daten u¨ber ein anwendungsspezi sches Verbindungs- netzwerk in die Gruppenregister les der Datenpfade transportiert werden ko¨nnen. Mit " Gruppenregister le\ wird die Menge der Register aller Slices mit demselben Label (z.B. A oder B in Abb. 1.4) bezeichnet. Neben dem Transfer einzelner Daten u¨ber das Verbin- dungsnetzwerk sind vor allem auch komplexe SIMD-Datentransfers mo¨glich. So besteht z.B. mit dem Vektordatentransfer die Mo¨glichkeit, alle Daten vom Zwischenregister le M in eines der Gruppenregister les A, B, C oder D zu transportieren, wobei jedes Datum 1.2. PROZESSOREN DER M3-PLATTFORM 9 innerhalb desselben Slices verbleibt. Dies bedeutet, dass bei einem Vektordatentransfer vom Zwischenregister le M in das Gruppenregister le A die Datentransfers A[0] = M[0], A[1] = M[1], ... , A[15] = M[15] innerhalb eines Taktzyklus ausgefu¨hrt werden. SIMD- Datentransfers wie Zurich-Zip ermo¨glichen dahingegen einen Transfer u¨ber Slice-Grenzen hinaus, indem alle Werte um eine bestimmte Anzahl Slices nach rechts oder links verscho- ben werden ko¨nnen und unterstu¨tzen damit beispielsweise eine eziente Implementierung des FIR-Filters [LBSL97, DF02]. Um das gesamte Verbindungsnetzwerk klein zu halten, ist keine vollsta¨ndige Vernetzung umgesetzt, wie dies z.B. mit einem Kreuzschienenver- teiler (Crossbar-Netz) mo¨glich gewesen wa¨re. Eine solche Realisierung wu¨rde die erfor- derliche Chipgro¨e und dadurch auch den Energieverbrauch erheblich erho¨hen. Ebenfalls dadurch begru¨ndet, ist eine Verwendung der Eingangsregister der Funktionseinheiten in den einzelnen Datenpfaden nur in eingeschra¨nkter Art und Weise mo¨glich. Des Weiteren ko¨nnen zur Verringerung des Schleifen-Overheads bis zu 256 Prozessorinstruktionen in einer Hardwareschleife ausgefu¨hrt werden, wobei die Anzahl der Iterationen mit 215 − 1 Iterationen nach oben begrenzt ist. Da der M3-DSP alle DSP-typischen Charakteristika aufweist und zusa¨tzlich noch eine SIMD-Ausfu¨hrung von Operationen unterstu¨tzt, stellt dieser Prozessor zur Demonstration der zu entwickelnden Compilertechniken eine geeignete Beispielarchitektur dar. 1.2.2 Energiekostenmodell Um die Codequalita¨t eines Maschinenprogramms hinsichtlich eines bestimmten Krite- riums beurteilen und optimieren zu ko¨nnen, bedarf es eines geeigneten Kostenmodells, mit dem hinreichend genaue Bewertungen durchgefu¨hrt werden ko¨nnen. Zur Bewertung mehrerer unterschiedlicher Codesequenzen wa¨hrend der Compilierung muss das Kosten- modell insbesondere auch eine schnelle Bewertung ermo¨glichen. Dies ist (in Abwesenheit von hardwaregesteuerten Caches) bezogen auf die Ausfu¨hrungsgeschwindigkeit und die Codegro¨e relativ einfach anhand des Instruktionssatzes mo¨glich. So werden in diesen Fa¨llen meist die Anzahl der beno¨tigten Prozessorzyklen oder der erforderliche Programm- speicherplatz aller Instruktionen aufaddiert. Soll jedoch als Optimierungskriterium ein geringer Energieverbrauch dienen, so werden Energieverbrauchswerte einzelner Prozes- sorinstruktionen oder Teilsequenzen beno¨tigt, die i.d.R. nicht vorhanden bzw. zuga¨nglich sind. Diese Werte mu¨ssen dann ermittelt und in einer Form zur Verfu¨gung gestellt werden, die es dem Compiler erlaubt, eine ausreichend genaue Di erenzierung von Codesequen- zen durchzufu¨hren. Die Ermittlung des Energieverbrauchs einer gegebenen Codesequenz kann grundsa¨tzlich mittels Simulation einer gegebenen Hardwarebeschreibung oder Mes- sung am realen Chip erfolgen, ermo¨glicht jedoch keine Bewertung von Codesequenzen im Compiler. Aus diesem Grund wird ein geeignetes Kostenmodell beno¨tigt, das einmal auf- gestellt, zur Ermittlung des Energiebedarfs beliebiger Instruktionssequenzen im Compiler 10 KAPITEL 1. EINLEITUNG dienen kann. Dazu wurde in [TMW94b, LTMF95] ein Energiekostenmodell auf Instruktionsebene vor- gestellt, bei dem der Gesamtenergieverbrauch aus dem Energieverbrauch einer einzel- nen Instruktion (Basis-Energiekosten) und dem (aufgrund von Zustandsa¨nderungen des Schaltkreises) zusa¨tzlich erforderlichen Energieverbrauch jeweils zweier aufeinander fol- gender Instruktionen (Overhead-Energiekosten) berechnet werden kann. Die relevanten Werte wurden dabei durch Messungen am realen Chip ermittelt. Weitere Energiekosten- modelle auf dieser Basis sind z.B. in [SS99, SBT00, SKWM01] beschrieben. Mit Hilfe von Strom-Messungen am Siliziumchip des M3-DSPs wurde (in Zusammenar- beit mit der TU Dresden) ebenfalls ein solches Kostenmodell gewonnen [DF02]. Um die Anzahl der durchzufu¨hrenden Energiemessungen zu minimieren, wurden in Analogie zu [TMW94b] alle Befehle, die a¨hnliche Energiekosten verursachen, zu Energiegruppen zu- sammengefasst und anschlieend hinsichtlich ihres Energieverbrauches gleich behandelt. In Tabelle 1.1 sind dies z.B. die Energiegruppen NOP, AGU 1, AGU 2, ... , LMI 1. Eine grobe Unterteilung des Befehlssatzes wurde anhand der Funktionseinheiten des VLIW-basierten Instruktionswortes vorgenommen. Dabei handelt es sich bei AGU (Address Generation Unit), DMU (Data Manipulation Unit), DTU (Data Transfer Unit), DAU (Data Alignment Unit) und PCU (Program Control Unit) um reale Funktionseinheiten des Prozessors, die unabha¨ngig voneinander angesteuert werden ko¨nnen. Die Energiegruppen LMI 1 (LMI = Load Move Instruction) und NOP (No Operation) stellen Sonderfa¨lle dar. Bei der Entwicklung des Kostenmodells stellte sich heraus, dass im Falle des M3-DSPs eine Aufteilung der Energiekosten in Basis- und Overheadkosten, wie es in [TMW94b] vorgeschlagen wird, zu groen Abweichungen im Vergleich zu Messungen wa¨hrend der Ausfu¨hrung auf dem M3-DSP fu¨hrt. Es hat sich gezeigt, dass eine solche Unterteilung (fu¨r den M3-DSP) auch nicht erforderlich ist, weil letztendlich nur der Gesamtenergieverbrauch jeweils zweier aufeinander folgender Maschineninstruktionen beno¨tigt wird. So ergeben sich fu¨r den M3-DSP durch eine Zusammenfassung der beiden Einzelkosten zu einem Wert wesentlich genauere Ergebnisse. Des Weiteren sind gegenu¨ber dem in [TMW94b] vorgestellten Modell aufgrund des VLIW-basierten Instruktionswortes Erweiterungen hin- sichtlich der Bewertung von parallelen Ausfu¨hrungsmo¨glichkeiten erforderlich. Leider gibt es aufgrund der hohen Parallelita¨t trotz der Einteilung in Energiegruppen immer noch eine Vielzahl von Kombinationsmo¨glichkeiten aufeinander folgender Maschineninstruktionen. Glu¨cklicherweise hat sich herausgestellt, dass der Energieverbrauch komplexerer (paralle- ler) Befehle mit Hilfe relativ weniger Messungen berechnet werden kann. Bevor im Folgenden das Energiekostenmodell fu¨r den M3-DSP angegeben wird, werden zuvor noch einige zum Versta¨ndnis erforderliche Notationen eingefu¨hrt:  Eine Sequenz von Maschineninstruktionen mii wird mit MIs bezeichnet. Es gilt: MIs = (mi 1 , mi 2 , . . . , mii, . . . , mi jMIsj), mit jMIsj  1 1.2. PROZESSOREN DER M3-PLATTFORM 11 Funktions- Energie- einheiten gruppen Maschinenoperationen NOP NOP NOP AGU 1 Store AGU AGU 2 Load AGU 3 Adressregister-Modi kation DMU 1 SISD MAC (Addition), SISD ADD, SISD MUL DMU 2 SISD MAC (Subtraktion), SISD SUB DMU DMU 3 SIMD MAC (Addition), SIMD ADD, SIMD MUL ... ... DTU 1 ElementDT, ImmediateDT DTU DTU 2 VectorDT ... ... DAU 1 Pack DAU DAU 2 ShiftLeft, ShiftRight PCU PCU 1 Goto, Push, Pop LMI LMI 1 Move, LoadImmediate Tabelle 1.1: Einteilung des Befehlssatzes in Energiegruppen  Der Energieverbrauch zweier aufeinander folgend ausgefu¨hrter Maschineninstruk- tionen mii und mij wird mit Emi i ,mi j bezeichnet, wobei i, j 2 f1, . . . , jMIsjg und j = i + 1 gilt.  Jede Maschineninstruktion mi entha¨lt mindestens eine Maschinenoperation mo. Es gilt: moj 2 mi, mit j 2 f1, . . . , jmijg  Die einer Maschinenoperation mo zugeordnete Energiegruppe wird mit EGrmo be- zeichnet. Es gilt: EGrmo 2 fNOP,AGU 1, . . . ,LMI 1g  Die Menge aller Energiegruppen der in einer Maschineninstruktion mi enthaltenen Maschinenoperationen wird mit EGrmi bezeichnet. Es gilt: EGrmi = fEGrmo 1 , . . . ,EGrmo |mi| g  Die Menge der im Energiekostenmodell betrachteten Funktionseinheiten wird mit EnFU bezeichnet. Es gilt: EnFU = fAGU,DMU,DTU,DAU,PCU,LMIg.  Eine Maschinenoperation mo, die auf der Funktionseinheit fu 2 EnFU ausgefu¨hrt wird, wird mit mofu bezeichnet. 12 KAPITEL 1. EINLEITUNG Der Energieverbrauch EMIs einer Sequenz MIs von Maschineninstruktionen kann wie folgt, durch Aufsummieren der Energiewerte zweier aufeinander folgender Maschinenin- struktionen ermittelt werden: EMIs = jMIsj−1 ∑ i=1 Emi i ,mi i+1 Wenn EMess einen gemessenen Wert und EComp einen Wert darstellt, der auf der Basis von gemessenen Werten berechnet wird, dann kann der Energieverbrauch von zwei aufein- ander folgend ausgefu¨hrten Maschineninstruktionen mii und mij durch folgende Formel bestimmt werden. Emi i ,mi j = { EMessEGr mi i ,EGr mi j , falls Messwert vorhanden ECompmi i ,mi j , sonst Soll also der Energieverbrauch zweier Maschineninstruktionen mi 1 und mi 2 bestimmt wer- den, mit EGrmi 1 = fAGU 1,DAU 1g und EGrmi 2 = fAGU 2g, dann wird zuna¨chst u¨ber- pru¨ft, ob fu¨r diese Kombination von Energiegruppen der Wert EMess fAGU 1kDAU 1g,fAGU 2g vorliegt. In diesem Fall wu¨rde das dem Eintrag 3,05 in der Zeile AGU 1 k DAU 1 und der Spalte AGU 2 von Tabelle 1.2 entsprechen. Die Eintra¨ge in dieser Tabelle stellen auf die Ausfu¨hrung eines NOPs genormte Energie- werte fu¨r unterschiedliche Kombinationen von Maschineninstruktionen dar. Bei Bedarf besteht jederzeit die Mo¨glichkeit, weitere Messungen durchzufu¨hren und der Energieda- tenbasis hinzuzufu¨gen. Ist fu¨r eine bestimmte Kombination kein entsprechender Eintrag vorhanden, wird der Energiebedarf zweier aufeinander folgender Maschineninstruktionen mii und mij, mit momi i 2 mii und momi j 2 mij, folgendermaen berechnet: ECompmi i ,mi j = ∑ 8fu2FU E mo fu mi i ,mo fu mi j − (jEnFUj − 1)  EMessNOP,NOP Durch Subtraktion des (jEnFUj − 1)-fachen Energieverbrauchs eines NOPs wird beru¨ck- sichtigt, dass bei allen gemessenen Werten nicht nur der Energieverbrauch einer einzelnen Funktionseinheit gemessen wurde, sondern ebenfalls der Energieverbrauch der restlichen Funktionsheiten, auf denen NOPs ausgefu¨hrt werden. Der Energieverbrauch, der auf einer einzelnen Funktionseinheit anfa¨llt, la¨sst sich mit Hilfe der folgenden Formel berechnen: E mo fu i ,mo fu j = { EMess mo fu i ,mo fu j , falls Messwert vorhanden EMess mo fu i ,NOP + EMess mo fu j ,NOP , sonst Eine Validierung des Energiekostenmodells erfolgte durch einen Vergleich des auf Basis des Energiekostenmodells vorhergesagten Energieverbrauchs, mit dem durch Messung am realen Chip ermittelten. Hierbei ergab sich lediglich eine Abweichung von weniger als 2% im Vergleich zur Ausfu¨hrung auf dem M3-DSP [DF02]. 1.3. ENERGIEOPTIMIERUNG DURCH COMPILER 13 E-Gruppe NOP AGU 1 AGU 2 AGU 3 DMU 1 DMU 2 DMU 3 DTU 1 DTU 2 NOP 1,00 1,57 1,30 1,04 1,31 1,35 5,60 1,22 1,19 AGU 1 1,57 2,14∗ 1,87∗ 1,61∗ 1,88∗ 1,92∗ 6,17∗ 1,79∗ 1,76∗ AGU 2 1,30 1,87∗ 1,60∗ 1,29 1,61∗ 1,65∗ 5,90∗ 1,52∗ 1,49∗ AGU 3 1,04 1,61∗ 1,29 1,07∗ 1,35∗ 1,39∗ 5,63∗ 1,25∗ 1,23∗ DMU 1 1,31 1,88∗ 1,61∗ 1,35∗ 1,03 5,32 5,34 1,53∗ 1,50∗ DMU 2 1,35 1,92∗ 1,65∗ 1,39∗ 5,32 1,03 6,09 1,57∗ 1,55∗ DMU 3 5,60 6,17∗ 5,90∗ 5,63∗ 5,34 6,09 1,24 5,81∗ 5,79∗ DTU 1 1,22 1,79∗ 1,52∗ 1,25∗ 1,53∗ 1,57∗ 5,81∗ 1,09 1,29 DTU 2 1,19 1,76∗ 1,49∗ 1,23∗ 1,50∗ 1,55∗ 5,79∗ 1,29 1,11 DAU 1 2,40 2,97∗ 2,70∗ 2,44∗ 2,71∗ 2,76∗ 7,00∗ 2,62∗ 2,59∗ DAU 2 2,60 3,17∗ 2,90∗ 2,64∗ 2,91∗ 2,95∗ 7,20∗ 2,82∗ 2,79∗ PCU 1 1,05 1,62∗ 1,35∗ 1,08∗ 1,36∗ 1,40∗ 5,65∗ 1,26∗ 1,24∗ LMI 1 1,06 1,63∗ 1,36∗ 1,10∗ 1,37∗ 1,42∗ 5,66∗ 1,28∗ 1,26∗ AGU 1 k DAU 1 2,86 3,54 ∗ 3,05 2,86 3,28∗ 3,33∗ 7,57∗ 3,19∗ 3,16∗ AGU 1 k DAU 2 3,00 3,74 ∗ 3,47∗ 3,21∗ 3,48∗ 3,52∗ 7,77∗ 3,39∗ 3,36∗ AGU 2 k DTU 1 1,51 ∗ 2,09∗ 1,82∗ 1,55∗ 1,83∗ 1,87∗ 6,11∗ 1,39∗ 1,71∗ Tabelle 1.2: Teil der Datenbasis des Energiekostenmodells. Alle mit einem * markierten Werte stellen auf der Basis von real durchgefu¨hrten Messungen berechnete Werte dar. 1.3 Energieoptimierung durch Compiler In diesem Abschnitt wird erla¨utert, inwiefern ein Energiekostenmodell in einem Compiler zur Energieoptimierung eingesetzt werden kann. Bei genauerer Betrachtung der einzel- nen Energiedaten fu¨r den M3-DSP wird ersichtlich, dass Load- und Store-Operationen (s. Eintra¨ge der Energiegruppen AGU 1 und AGU 2 in Tabelle 1.2) im Vergleich zu SISD- Prozessorinstruktionen des Datenpfades (s. z.B. Eintra¨ge der Energiegruppen DTU 1 und DMU 1) einen erho¨hten Energiebedarf aufweisen. Insbesondere bei Stores ist dies ersichtlich, da diese jeweils in Verbindung mit einer DAU-Operation durchgefu¨hrt werden (s. z.B. Ein- trag AGU 1 || DAU 1). Den ho¨chsten Energiebedarf weisen jedoch die SIMD-Operationen (s. z.B. Energiegruppe DMU 3) auf, deren Energieverbrauch um den Faktor vier bis fu¨nf ho¨her ist, als der einer SISD-Operation. Da allerdings im Optimalfall 16 " sinnvolle\ Da- tenberechnungen parallel durchgefu¨hrt werden ko¨nnen, kann damit der Energie-Overhead gegenu¨ber einer SISD-Ausfu¨hrung wieder mehr als ausgeglichen werden. Des Weiteren ist zu erwarten, dass zusa¨tzlich wesentlich weniger Datentransferbefehle erforderlich sind. Neben der Entwicklung von Optimierungen zur Verringerung der Ausfu¨hrungszeit, lohnt sich zwecks Reduzierung des Energieverbrauchs damit auch die Entwicklung von Techni- ken, die 14 KAPITEL 1. EINLEITUNG  zu einer Reduzierung von Speicherzugri en fu¨hren und  die vorhandenen Datenpfade sinnvoll ausnutzen. Wie wir anhand von Beispielen im Folgenden sehen werden, kann der Energieverbrauch zusa¨tzlich durch eine geschickte Auswahl und Anordnung von Maschinenoperationen zu Maschineninstruktionen reduziert werden. In Abb. 1.5 sind zuna¨chst zwei unterschiedliche Schedules a) und b) mit jeweils vier Ma- schineninstruktionen, repra¨sentiert durch ihre entsprechende Energiegruppe (z.B. AGU 2, DMU 1) angegeben. // // // // MI 1 MI 2 MI 3 MI 4 AGU 2 DMU 1 DTU 1 DMU 1 _ _ _ _ } 1,61 Schedule a) 4,67 Summe ==== } 1,53 } 1,53 // // // // MI 1 MI 2 MI 3 MI 4 AGU 2 DTU 1 DMU 1 DMU 1 _ _ _ _ } 1,52 Schedule b) 4,08 Summe ==== } 1,53 } 1,03 Energieverbrauch normiert auf NOPs Energieverbrauch normiert auf NOPs Abb. 1.5: Beispiel zur Energiereduzierung durch Instruktionsanordnung Als einziger Unterschied zwischen diesen beiden Schedules ist zu erkennen, dass die Ma- schineninstruktionen MI 2 und MI 3 vertauscht sind. Dadurch begru¨ndet ergeben sich fu¨r die aufeinander folgenden Befehle unterschiedliche (auf die Ausfu¨hrung eines NOPs genormte) Energiekosten in Ho¨he von 4,67 NOPs fu¨r Schedule a) und von 4,08 NOPs fu¨r Schedule b), was einer Reduzierung von 12,6 % entspricht. Allerdings besteht nicht nur die Mo¨glichkeit einer Energiereduzierung durch eine Neuan- ordnung der Instruktionen. Wie in Abb. 1.6 anhand zweier unterschiedlicher Maschinen- programme fu¨r den Ausdruck c = (2  a) + b + (2  a); verdeutlicht, kann ebenfalls durch eine geschickte Instruktionsauswahl der Energiever- brauch bei gleicher Ausfu¨hrungszeit erheblich reduziert werden2. 2In diesem Beispiel wird davon ausgegangen, dass die Variablen a, b und c globale Variablen darstellen und von daher aus dem Speicher geladen und wieder zuru¨ckgeschrieben werden mu¨ssen. 1.3. ENERGIEOPTIMIERUNG DURCH COMPILER 15 PP = 0; M = MEM[PP&0] || A[0] = 2; M = MEM[PP&1] || C[0] = M[0]; B[0] = M[0]; Accu[0] = B[0]+A[0]*C[0]; Accu[0] = Accu[0]+A[0]*C[0]; MEM[PP&2] = Accu; LMI 1 AGU 2 || DTU 1 AGU 2 || DTU 1 AGU 1 || DAU 1 _ _ _ _ _ _ _ _ _ _ // // // MI 1: MI 2: MI 3: MI 6: MI 7: // // // // MI 4: MI 5: DTU 1 DMU 1 DMU 1 // // // // // // // MI 1: MI 2: MI 3: MI 4: MI 5: MI 6: MI 7: LMI 1 AGU 2 || DTU 1 AGU 2 || DTU 3 DMU 1 || DTU 3 DTU 1 || DMU 1 DMU 1 AGU 1 || DAU 1 _ _ _ _ _ _ _ _ _ _ PP = 0; M = Mem[PP & 0] || C[0] = 2; M = Mem[PP & 1] || B[0] = M[0]; Accu[0] = B[0]*C[0] || B[0] = M[0]; A[0] = Accu[0] || Accu[0] = B[0]+Accu[0]; Accu[0] = A[0]+Accu[0]; Mem[PP&2] = Accu; _ _ } } } } } } 1,58 1,98 1,77 1,41 1,24 3,28 } } } } } } 1,58 1,69 1,39 1,53 1,03 3,28 Maschinenprogramm a) Maschinenprogramm b) Energieverbrauch normiert auf NOPs Energieverbrauch normiert auf NOPs 11,26 10,50 Gesamtenergieverbrauch normiert auf NOPs Gesamtenergieverbrauch normiert auf NOPs ===== ===== Abb. 1.6: Vergleich des Energieverbrauchs unterschiedlicher Maschinenprogramme Fu¨r jede Maschineninstruktion sind jeweils die Energiegruppen der verwendeten Maschi- nenoperationen mit angegeben. Z.B. wird in Maschinenprogramm a) in MI 2 eine Ma- schinenoperation aus Energiegruppe AGU 2 parallel zu einer aus DTU 1 ausgefu¨hrt. Es ist zu erkennen, dass beide Maschinenprogramme mit sieben Maschineninstruktionen diesen Ausdruck umsetzen, wobei jedoch der Energieverbrauch von Maschinenprogramm b) um 6,7 % geringer ist als der von Maschinenprogramm a). Dies la¨sst sich in diesem Beispiel anhand der Tatsache begru¨nden, dass in Maschinenprogramm b) die Umsetzung mit Hilfe von zwei MAC-Operationen erfolgt (MI 5 und MI 6), wa¨hrend bei Maschinenprogramm a) stattdessen eine Multiplikation (MI 4) und zwei Additionen (MI 5 und MI 6) Verwendung nden. Dadurch ist auch ein zusa¨tzlicher Datentransfer in MI 5 erforderlich. Des Weiteren wird in MI 3 von Maschinenprogramm b) ein weniger energieintensiver Datentransferbe- fehl aus der Energiegruppe DTU 1 statt aus der Energiegruppe DTU 3 verwendet. 16 KAPITEL 1. EINLEITUNG 1.4 Problemanalyse Aufgrund mangelnder Techniken zur Handhabung irregula¨rer Prozessorarchitekturen wei- sen DSP-Compiler oft eine unzureichende Codequalita¨t in Hinblick auf Realzeitfa¨higkeit, Codegro¨e und damit auch Energieverbrauch auf [ZVSM94]. Die verfu¨gbaren Compi- ler fu¨hren i.d.R. eine baumbasierte Codeselektion durch, bei der ein gegebener Daten- flussgraph (DFG) an gemeinsamen Teilausdru¨cken (CSEs = Common Subexpressions) in Ba¨ume zerlegt und fu¨r jeden der resultierenden Ba¨ume eine separate Codeselektion durch- gefu¨hrt wird [ASU86, WM95]. Die Durchfu¨hrung einer baumbasierten Codeselektion fu¨r einen Baum mit n Knoten ist zwar sehr laufzeitezient in O(n) mo¨glich, weist allerdings insbesondere fu¨r irregula¨re Architekturen einige Nachteile auf [Bas95]:  Wa¨hrend in GPPs mit groen Register les CSEs normalerweise in Registern gehal- ten werden, ist dies bei irregula¨ren Architekturen mit Spezialregistern i.d.R. nicht der Fall. Stattdessen legen herko¨mmliche Compiler CSEs im Speicher ab und laden diese bei jeder Verwendung neu [AML96, LDKT95], was zu potentiell vermeidbaren Speicherzugri en und Instruktionen fu¨hrt.  Die Phase der Codeselektion wird nur lokal fu¨r Ba¨ume durchgefu¨hrt. Da- durch ko¨nnen potentielle U¨berdeckungsmo¨glichkeiten von Knoten unterschiedlicher Ba¨ume (mit Maschinenoperationen) nicht beru¨cksichtigt werden. Ein solches Ver- fahren wa¨re also nicht in der Lage, das energieezientere Maschinenprogramm b) in Abb. 1.6 zu generieren. Stattdessen mu¨ssten die in MI 5 und MI 6 vorhandenen MAC-Operationen in Einzeloperationen aufgeteilt werden, weil die Multiplikation und die beiden Additionen jeweils unterschiedlichen Ba¨umen angho¨ren wu¨rden.  Die bei irregula¨ren Architekturen so wichtige Phasenkopplung wird nur einge- schra¨nkt durchgefu¨hrt. Mit diesen Verfahren kann die Phase der Codeselektion fu¨r Ba¨ume zwar optimal durchgefu¨hrt werden, allerdings bezieht sich der Begri der Optimalita¨t lediglich auf sequentiellen Code. Da im resultierenden Code noch kein (durch Registerallokation erforderlicher) Spillcode enthalten ist, mu¨ssen die Pha- sen der Registerallokation und Codekompaktierung zusa¨tzlich in nachgeschalteten Phasen durchgefu¨hrt werden.  Energiekostenmodelle lassen sich zwar in die einzelnen Codegenerierungs-Phasen integrieren, ko¨nnen allerdings nur sehr ungenaue Abscha¨tzungen u¨ber den letztend- lichen Energieverbrauch liefern. So ko¨nnen sich energiebewusste Entscheidungen in fru¨hen Phasen spa¨ter durchaus als ungu¨nstig erweisen, da z.B. das nachtra¨gliche Einfu¨gen von Spillcode die vorhandenen Codesequenzen (und damit auch die Swit- chingaktivita¨ten aufeinander folgender Instruktionen) stark beeinflusst. 1.4. PROBLEMANALYSE 17 Um den bei DSPs ha¨u g gegebenen Echtzeitanforderungen gerecht werden zu ko¨nnen, mu¨ssen Compiler in der Lage sein, die speziellen Architekturmerkmale zu beru¨cksichtigen. Im einzelnen betri t dies eine e ektive Ausnutzung ... ... von komplexen Operationen wie der MAC-Instruktion, mit der eine Multiplikation gefolgt von einer Addition in einem Taktzyklus ausgefu¨hrt werden kann. ... der parallelen Ausfu¨hrungsmo¨glichkeiten auf Instruktionsebene (ILP = Instruction Level Parallelism). Im Falle der Prozessoren der M3-Plattform umfasst dies zusa¨tz- lich die Ausnutzung von SIMD-Operationen in Verbindung mit einer e ektiven Nut- zung der komplexen Datentransfer-Modi des Verbindungsnetzwerkes. ... gegebener Speicherressourcen, wie z.B. von Speicherba¨nken oder des On-Chip- Gruppenspeichers der M3-Prozessoren. ... von speziellen Adressgenerierungsbefehlen zur e ektiven Ausnutzung der AGU, um den vorhandenen Adressierungs-Overhead so gering wie mo¨glich zu halten. ... vorhandener Spezialbefehle zur Reduzierung des Schleifen-Overheads. Um die Korrektheit des generierten Codes zu gewa¨hrleisten, mu¨ssen bei der Compilierung eine Reihe von Randbedingungen in der Verwendung von Registern, Datentransfers und der Parallelisierung beru¨cksichtigt werden. Im Falle der Compilierung fu¨r Prozessoren der M3-Plattform umfasst dies jedoch eine Reihe weiterer Randbedingungen, die vor allem durch den Gruppenspeicher und die Sonderfunktionalita¨t des Datenpfades 0 (Einstreifen- Modus) verursacht werden:  Handhabung irregula¨rer Datentransfer-Modi. Um z.B. auch bei einer Abarbeitung im SISD-Modus eine e ektive Bereitstellung von Daten zu gewa¨hrleisten, sind speziell abgestimmte Datentransferbefehle zu und von Registern des Datenpfades 0 vorhanden.  Beibehaltung der Datenkonsistenz des Gruppenspeichers. Im Gegensatz zu u¨blicherweise verwendeten Techniken muss ein Codegenerator fu¨r die M3-Prozessoren in der Lage sein, anstelle einzelner Daten, Gruppen von Daten zu laden, zu speichern und zu spillen.  Einhaltung weiterer Randbedingungen, die sich aufgrund von verwendeten Datentransferbefehlen fu¨r die Adresscode- Generierung ergeben. Da architekturspezi sche Optimierungen ha¨u g fest in den entsprechenden Compiler in- tegriert sind, ko¨nnen diese Optimierungen nicht in anderen Compilern genutzt werden. 18 KAPITEL 1. EINLEITUNG Dies fu¨hrt dazu, dass bestimmte Optimierungen fu¨r andere Architekturen immer wie- der neu implementiert werden. Aus diesem Grund ist ein allgemeines Austauschformat (in Form einer LIR) zwischen den einzelnen Optimierungsphasen a¨uerst wu¨nschenswert, bei dem prozessorspezi sche Architekturmerkmale abgelegt und von den zu entwickeln- den Optimierungen abgefragt werden ko¨nnen. Neben der Wiederverwendbarkeit einzelner Optimierungen oder bestimmter Teile, wird durch ein solches allgemeines Austauschfor- mat eine modulare und generische Entwicklung von performance- und energieezienten Optimierungstechniken mo¨glich. 1.5 Zielsetzungen und U¨berblick Der Schwerpunkt dieser Arbeit besteht in der Entwicklung von neuen Compilertechniken fu¨r DSPs, mit dem Ziel, den vorhandenen Overhead herko¨mmlicher Compilertechniken vor allem in Bezug auf die Ausfu¨hrungszeit und den Energieverbrauch zu reduzieren. Dabei gilt es alle entwickelten Techniken in einem einheitlichen Back-End (Codegenerator) zu integrieren. Als Zielarchitekturen dienen die parallelen Prozessoren der M3-Plattform, von denen im speziellen der M3-DSP betrachtet wird. Um eine modulare und generische Implementierung der entwickelten Compilertechni- ken zu ermo¨glichen und des Weiteren die Erweiterbarkeit um weitere Optimierungen zu gewa¨hrleisten, setzen alle in dieser Arbeit beschriebenen Techniken auf der in Kapitel 2 eingefu¨hrten Zwischendarstellung GeLIR (Generic Low-Level Intermediate Representati- on) auf. Durch die Verwendung von GeLIR als einheitlichem Austauschformat ko¨nnen alle implementierten Techniken auf einfache Art und Weise auch fu¨r andere Zielarchitekturen adaptiert werden. Als Schwerpunkt dieser Arbeit wird in Kapitel 3 ein Codegenerator vorgestellt, der in der Lage ist, eine graphbasierte Codeselektion durchzufu¨hren und zusa¨tzlich die Phasen der Codeselektion, Instruktionsanordnung (einschlielichKompaktierung) und Registeralloka- tion im Sinne einer Phasenkopplung simultan lo¨st. Da dies die Lo¨sung eines NP-harten Op- timierungsproblems darstellt, ist dem Codegenerator ein Optimierungsverfahren auf Basis eines genetischen Algorithmus zugrunde gelegt. Zusa¨tzlich werden bei der Durchfu¨hrung der Teilaufgaben Codeselektion, Instruktionsauswahl und Registerallokation bereits Wech- selwirkungen mit der nachfolgend durchgefu¨hrten Adresscode-Generierung beru¨cksichtigt. Als weitere wichtige Eigenschaft des genetischen Optimierungsverfahrens wird eine einfa- che Beru¨cksichtigung unterschiedlicher Kostenfunktionen besprochen, die u.a. eine Opti- mierung hinsichtlich der Ausfu¨hrungszeit, des Energieverbrauchs und deren Kombination ermo¨glicht. Als weiterer Schwerpunkt dieser Arbeit werden in Kapitel 4 Verfahren vorgestellt, die eine Ausnutzung von SIMD-Befehlen fu¨r die Prozessoren der M3-Plattform ermo¨glichen, bzw. 1.5. ZIELSETZUNGEN UND U¨BERBLICK 19 zu einer e ektiveren Ausnutzung fu¨hren. Dies betri t insbesondere die Vektorisierung von Schleifen. Es wird sich zeigen, dass ha¨u g erst durch eine optimierte Anordnung der Arrays im On-Chip-Gruppenspeicher und durch eine Anwendung von Schleifentransformationen eine Schleife vektorisiert werden kann. Zur Reduzierung des vorhandenen Overheads bei der Handhabung des Gruppenspeichers im SISD-Modus wird in diesem Kapitel des Weite- ren ein Verfahren zur Anordnung von skalaren Variablen zu Gruppen vorgestellt, mit dem vor allem die Anzahl der mittels SIMD-Anweisungen durchzufu¨hrenden Speicherzugri e gegenu¨ber einer einfachen Anordnung drastisch verringert werden kann. Als Kern dieses Verfahrens wird ein genetisches Partitionierungsverfahren verwendet, das auch allgemein zur Lo¨sung von Partitionierungsproblemen verwendet werden kann. Bevor in Kapitel 6 eine Zusammenfassung dieser Arbeit gegeben wird, werden fu¨r die vorgestellten Techniken in Kapitel 5 experimentelle Ergebnisse fu¨r eine Reihe von realen DSP-Routinen und einer MP3-Anwendung pra¨sentiert. Dies schliet ebenfalls eine am Beispiel des M3-DSPs durchgefu¨hrte HW/SW-Exploration ein, bei der die Auswirkungen von Hardware-A¨nderungen auf die resultierende Codequalita¨t untersucht werden. 20 KAPITEL 1. EINLEITUNG Kapitel 2 Compiler-Zwischendarstellungen Bei der Entwicklung von Compilern spielen Zwischendarstellungen eine zentrale Rolle, da diese allgemein als Austauschformat fu¨r die Compilertechniken dienen. So erlauben Zwi- schendarstellungen aufgrund genormter Schnittstellen u.a. die Wiederverwendung bereits implementierter Techniken in unterschiedlichen Compilern und die simultane Entwick- lung von Compilertechniken, wodurch in erheblichem Mae Kosten und Zeit eingespart werden ko¨nnen. Um die Entwicklung neuer Compilertechniken zu vereinfachen, werden im Allgemeinen Informationen zur Verfu¨gung gestellt, die Aussagen u¨ber die Anwend- barkeit bzw. semantische Korrektheit bestimmter Modi kationen (Transformationen und Optimierungen) erlauben. Insbesondere wenn sehr umfangreiche und komplexe Modi kationen vorgenommen wer- den, sollte eine Validierung so einfach wie mo¨glich umsetzbar sein. Dazu ist eine Simulation und graphische Visualisierung beliebiger Zwischenresultate sehr wu¨nschenswert. Mit Hil- fe einer Simulation wird nicht nur die Mo¨glichkeit zu einer automatisierten Validierung gescha en, sondern auch ermo¨glicht, durchgefu¨hrte Optimierungen auf ihre E ektivita¨t hin zu u¨berpru¨fen. Dabei sollten zur Bewertung zumindest Daten u¨ber die Anzahl der ausgefu¨hrten Zyklen bereitgestellt werden. Da in dieser Arbeit ein Schwerpunkt auf der Entwicklung von energieezienten Optimierungen liegt, sind zusa¨tzlich Angaben u¨ber den Energieverbrauch erforderlich, die allerdings von herko¨mmlichen Simulatoren nicht zur Verfu¨gung gestellt werden. Im Vergleich zu einer rein maschinenunabha¨ngigen (High-Level) Darstellung stellt die Umsetzung dieser Anforderungen auf der maschinenabha¨ngigen (Low-Level) Ebene ein wesentlich gro¨eres Problem dar. So mu¨ssen zuna¨chst die erforderlichen architekturspezi - schen Merkmale fu¨r eine mo¨glichst breite Klasse von Architekturen geeignet zur Verfu¨gung gestellt werden. Im nachfolgenden Abschnitt werden zuna¨chst einige zum Versta¨ndnis des Aufbaus von Compiler-Zwischendarstellungen erforderliche Begri e und Grundlagen dargelegt. Auf- grund der engen Verwandtschaft von der in dieser Arbeit verwendeten und weiterent- 21 22 KAPITEL 2. COMPILER-ZWISCHENDARSTELLUNGEN wickelten Zwischendarstellung GeLIR (Generic Low-Level IR) und der von Bashford ent- wickelten CoLIR (Constraint based Low-Level IR), wurden einige der nachfolgend ein- gefu¨hrten Begri e und De nitionen aus [Bas01] u¨bernommen. 2.1 Grundlegende Begri e Die Programmdarstellung in Compiler-Zwischendarstellungen orientiert sich ha¨u g an der allgemeinen Struktur von Programmen imperativer Programmiersprachen, bei der ein Programm aus einer Menge von Funktionen besteht. Diese ergeben sich direkt aus den im Quellprogramm verwendeten Funktionen. Eine Darstellung der dort enthaltenen Kontrollstrukturen (wie z.B. Verzweigungen), erfolgt ha¨u g mittels Kontrollflussgraphen. De nition 2.1 (Kontrollflussgraph) Ein Kontrollflussgraph (CFG) ist ein gerichteter Graph G = (V, E), dessen Knoten v 2 V entsprechend des potentiell mo¨glichen Kontroll- flusses u¨ber Kanten ei,j = (vi, vj) 2 E  V  V miteinander verbunden werden. Die Knoten selbst enthalten sequentiell auszufu¨hrende Anweisungen und ko¨nnen aufgrund von Verzweigungen des Kontrollflusses mehrere Nachfolger haben. Die Knoten eines Kontrollflussgraphen ko¨nnen z.B. Basisblo¨cke (s. De nition weiter un- ten) sein, deren enthaltene Anweisungen auf unterschiedliche Arten dargestellt werden ko¨nnen. Dies kann wiederum mittels eines Kontrollflussgraphen geschehen, bei dem ent- sprechend der Ausfu¨hrungsreihenfolge zweier Anweisungen Kanten eingefu¨gt werden. De nition 2.2 (Basisblock) Ein Basisblock (BB) stellt eine maximale Sequenz von An- weisungen dar, bei der sich der Kontrollfluss nur nach der letzten Anweisung der Sequenz aufteilen und nur bei der ersten Anweisung der Sequenz wieder zusammenflieen kann. In Abb. 2.1 wird dies anhand der Aufteilung einer Funktion entsprechend ihres Kon- trollflusses in Basisblo¨cke verdeutlicht. Wie zu erkennen ist, erfolgt eine Unterteilung der Funktion main in vier u¨ber Kontrollflusskanten verbundene Basisblo¨cke BB 1 bis BB 4. Wa¨hrend aufgrund der Kontrollflussverzweigung nach der Beendigung von BB 1 keine allgemeine Aussage daru¨ber gemacht werden kann, ob die in BB 2 oder BB 3 enthalte- nen Anweisungen ausgefu¨hrt werden, steht die Ausfu¨hrungsreihenfolge der Anweisungen (AMOs = abstrakte Maschinenoperationen) innerhalb der einzelnen Basisblo¨cke fest. De nition 2.3 (Abstrakte Maschinenoperation) Eine abstrakte Maschinenoperati- on (AMO) stellt eine maschinenunabha¨ngige, elementare Anweisung der Zwischendarstel- lung dar. 2.1. GRUNDLEGENDE BEGRIFFE 23 int x, y; int main() { int ret; if(x