Advanced compiling techniques to reduce RAM usage of static operating systems [Elektronische Ressource] / vorgelegt von Volker Barthelmann

Advanced Compiling Techniquesto reduce RAM Usageof Static Operating SystemsDer Technischen Fakult¨at derUniversit¨at Erlangen-Nurn¨ bergzur Erlangung des GradesDOKTOR-INGENIEURvorgelegt vonVolker BarthelmannErlangen – 20042Als Dissertation genehmigt vonder Technischen Fakult¨at derUniversit¨at Erlangen-Nurn¨ bergTag der Einreichung: 07.01.2004Tag der Promotion: 11.03.2004Dekan: Prof. Dr. Albrecht WinnackerBerichterstatter: Prof. Dr. Michael PhilippsenProf. Dr. Wolfgang Schr¨oder-PreikschatZusammenfassungIn den letzten Jahren wurde eine steigende Anzahl kleiner eingebetteter Systeme inhohen Stuc¨ kzahlen eingesetzt. Beispielsweise in der Automobilindustrie, wo ann¨ahernd100 elektronische Steuerger¨ate (ECUs) in einzelnen Oberklassefahrzeugen und bereitsmehrere DutzendinMittelklassefahrzeugenverbautwerden. Meistwerdenkleine“Sys-tem-on-Chip” Mikrocontroller mit statischen Betriebssystemen benutzt. Da das RAMaufdiesenChipssehrteueristundnurwenigeKBdavonaufsolchenSystemenverfu¨gbarsind, ist die Reduzierung des RAM-Verbrauchs ein wichtiger Punkt um Kosten zusenken — besonders bei der Produktion hoher Stu¨ckzahlen.DieseDissertationstellteinigeneueVerfahrenvor, umdenRAM-Verbrauchsolcher¨Systeme durch die Anwendung fortgeschrittener Ubersetzungs- und Optimierungstech-nikenzureduzieren. KlassischeOptimierungenwerdenhinsichtlichihrerAuswirkungenauf den RAM-Verbrauch untersucht.
Publié le : jeudi 1 janvier 2004
Lecture(s) : 22
Tags :
Source : D-NB.INFO/972029427/34
Nombre de pages : 145
Voir plus Voir moins

Advanced Compiling Techniques
to reduce RAM Usage
of Static Operating Systems
Der Technischen Fakult¨at der
Universit¨at Erlangen-Nurn¨ berg
zur Erlangung des Grades
DOKTOR-INGENIEUR
vorgelegt von
Volker Barthelmann
Erlangen – 20042
Als Dissertation genehmigt von
der Technischen Fakult¨at der
Universit¨at Erlangen-Nurn¨ berg
Tag der Einreichung: 07.01.2004
Tag der Promotion: 11.03.2004
Dekan: Prof. Dr. Albrecht Winnacker
Berichterstatter: Prof. Dr. Michael Philippsen
Prof. Dr. Wolfgang Schr¨oder-PreikschatZusammenfassung
In den letzten Jahren wurde eine steigende Anzahl kleiner eingebetteter Systeme in
hohen Stuc¨ kzahlen eingesetzt. Beispielsweise in der Automobilindustrie, wo ann¨ahernd
100 elektronische Steuerger¨ate (ECUs) in einzelnen Oberklassefahrzeugen und bereits
mehrere DutzendinMittelklassefahrzeugenverbautwerden. Meistwerdenkleine“Sys-
tem-on-Chip” Mikrocontroller mit statischen Betriebssystemen benutzt. Da das RAM
aufdiesenChipssehrteueristundnurwenigeKBdavonaufsolchenSystemenverfu¨gbar
sind, ist die Reduzierung des RAM-Verbrauchs ein wichtiger Punkt um Kosten zu
senken — besonders bei der Produktion hoher Stu¨ckzahlen.
DieseDissertationstellteinigeneueVerfahrenvor, umdenRAM-Verbrauchsolcher
¨Systeme durch die Anwendung fortgeschrittener Ubersetzungs- und Optimierungstech-
nikenzureduzieren. KlassischeOptimierungenwerdenhinsichtlichihrerAuswirkungen
auf den RAM-Verbrauch untersucht. Durch geschickte Auswahl von Optimierungsal-
gorithmen kann der RAM-Verbrauch in einer Testreihe um fast 20% gesenkt werden.
¨Obergrenzenfu¨rStackgroße¨ nderTasksderAnwendungwerdenvomUbersetzerstatisch
berechnet. Durch modulub¨ ergreifende Analyse auf Hochsprachenebene werden hier
guteErgebnisseerreicht,dieimVergleichmiteinemkommerziellverfu¨gbarenWerkzeug
Vorteile in der Handhabbarkeit und Zuverlas¨ sigkeit zeigen. Als wichtigster Punkt wer-
dendieRegisters¨atze,diedasBetriebssystemsichernmuss,wenneinTaskunterbrochen
wird, optimiert,indemvermiedenwird,Registerunn¨otigzuspeichern. Registervergabe
ub¨ er Taskgrenzen hinweg reduziert den Speicherbedarf fur¨ diese Registers¨atze weiter.
¨DieneuenAlgorithmenwurdenineinenUbersetzereingebautundeinekommerzielle
OSEK Implementierung wurde modifiziert, um die neuen Optimierungen zu nutzen.
Tests auf echter Hardware, sowie Vergleiche mit kommerziellen Programmen zeigen
nichtnur, dassdasSystemfunktioniertundsowohlBenutzbarkeitalsauchWartbarkeit
verbessert, sondern auch, dass eine signifikante Reduzierung des RAM-Verbrauchs und
der damit verbundenen Kosten m¨oglich ist. In einer Reihe von Benchmarks wird der
RAM-Verbrauch i.d.R. um 30%–60% gesenkt.
34Abstract
Inrecentyears,arapidlygrowingnumberofsmallembeddedsystemshavebeenusedin
veryhighvolumes. Oneexampleistheautomotiveindustry, wherethenumberofElec-
tronic Control Units (ECU) in a single car is approaching 100 for high end automobiles
and several dozens are used in mid-range cars. Small system-on-chip microcontrollers
are often used with static operating systems. As on-chip RAM is rather expensive and
only few KBs of RAM are available on such devices, reducing the RAM usage is an
important objective in order to save costs — especially in high-volume production.
This thesis presents several new approaches to reduce the RAM usage of such sys-
tems by applying advanced compilation and optimization techniques. Common opti-
mizations are examined regarding their impact on RAM usage. By selecting classical
optimization algorithms regarding their impact on RAM usage, the RAM required for
a series of test cases is reduced by almost 20%. Upper bounds for stack sizes of ap-
plication tasks will be statically calculated using high-level analysis available in the
compiler. Comparisons with a commercial tool working on machine-code-level show
clear advantages regarding maintainability as well as reliability. Most important, the
register sets stored by the operating system when a task is preempted are optimized
by abstaining from saving unnecessary registers. Inter-task register-allocation further
reduces the RAM required to save those task contexts.
The new algorithms have been added to a production quality compiler and a full
commercial OSEK implementation was modified to make use of the new optimizations.
Testsonrealhardwareaswellascomparisonswithcommercialtoolsnotonlyshowthat
the system works and improves usability and maintainability, but also that significant
reductions of RAM requirements, and therefore cost savings, are possible. In a series
of benchmarks, RAM usage is reduced on average by 30%–60%.
56Contents
1 Introduction 13
1.1 Static Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Compilers for Embedded Systems . . . . . . . . . . . . . . . . . . . . . . 16
1.3 RAM Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Contributions and Organization of this Thesis . . . . . . . . . . . . . . . 17
2 Target/Environment 19
2.1 OSEK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Portability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.3 OSEK Implementation Language . . . . . . . . . . . . . . . . . . 20
2.1.4 Task Management . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.5 OSEK Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.6 OSEK Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.7 Interrupt Service Routines . . . . . . . . . . . . . . . . . . . . . . 24
2.1.8 Properties of Application Code . . . . . . . . . . . . . . . . . . . 24
2.2 Examples of relevant Microcontrollers . . . . . . . . . . . . . . . . . . . 25
2.2.1 68HC12/HCS12 . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 C16X/ST10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.3 MPC5XX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 The vbcc Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 Support for Embedded Systems . . . . . . . . . . . . . . . . . . . 30
2.3.3 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.4 Cross-Module Analysis . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Common Optimizations 35
3.1 Why Optimizing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.1 Disadvantages of Optimizing Compilers . . . . . . . . . . . . . . 36
3.1.2 Advantages of Optimizing Compilers . . . . . . . . . . . . . . . . 37
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Discussion of selected Optimizations . . . . . . . . . . . . . . . . . . . . 39
3.3.1 Flow Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.2 Dead Assignment Elimination . . . . . . . . . . . . . . . . . . . . 40
3.3.3 Constant Propagation . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.4 Common Subexpression Elimination . . . . . . . . . . . . . . . . 42
3.3.5 Copy Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.6 Loop-Invariant Code Motion . . . . . . . . . . . . . . . . . . . . 46
3.3.7 Strength-Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.8 Loop Unrolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
78 CONTENTS
3.3.9 Function Inlining . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.10 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.11 Instruction Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.12 Alias Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.13 Inter-Procedural Data-Flow Analysis . . . . . . . . . . . . . . . . 59
3.3.14 Cross-Module Optimizations . . . . . . . . . . . . . . . . . . . . 61
3.4 Combination of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4 Stack Analysis 67
4.1 Existing practice and Related Work . . . . . . . . . . . . . . . . . . . . 68
4.1.1 Guessing and Testing . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.2 High-Water Marks . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1.3 Manual Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.4 Traditional Compilers . . . . . . . . . . . . . . . . . . . . . . . . 72
4.1.5 Post Link-Time Analyzers . . . . . . . . . . . . . . . . . . . . . . 73
4.1.6 Further Related Work . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.7 Example: AbsInt StackAnalyzer . . . . . . . . . . . . . . . . . . 78
4.2 High-Level Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2.3 Results and Comparison . . . . . . . . . . . . . . . . . . . . . . . 92
5 Context Optimization 111
5.1 Task Contexts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2 Current Practice and Related Work . . . . . . . . . . . . . . . . . . . . 112
5.3 Context Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.3.2 Bounding Task-Contexts . . . . . . . . . . . . . . . . . . . . . . . 115
5.3.3 Inter-Task Register-Allocation . . . . . . . . . . . . . . . . . . . 116
5.4 Requirements on Compilers . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.5 Experimental Implementation and Results . . . . . . . . . . . . . . . . . 118
6 Real OSEK Implementation 121
6.1 ProOSEK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.1 Adaption of ProOSEK to vbcc . . . . . . . . . . . . . . . . . . . 122
6.2.2 Stack Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.3 Task Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2.4 Calculation of Task Contexts . . . . . . . . . . . . . . . . . . . . 123
6.2.5 Inter-Task Register-Allocation . . . . . . . . . . . . . . . . . . . 127
6.2.6 Generation of Stacks . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2.7 Context-Switch Code . . . . . . . . . . . . . . . . . . . . . . . . 128
6.2.8 System Calls and System Stack . . . . . . . . . . . . . . . . . . . 129
6.2.9 Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.3 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.3.1 Task Constellations . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.3.2 LED Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.3.3 Interior Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7 Conclusion and Future Work 133List of Figures
1.1 Die Overlay showing ROM and RAM sizes. . . . . . . . . . . . . . . . . 14
1.2 Architecture of a Static Operating System . . . . . . . . . . . . . . . . . 15
1.3 New Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1 OIL Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 OSEK OS Task-State Transitions . . . . . . . . . . . . . . . . . . . . . . 22
2.3 OSEK OS preemptive Scheduling . . . . . . . . . . . . . . . . . . . . . . 22
2.4 OSEK OS non-preemptive Scheduling . . . . . . . . . . . . . . . . . . . 23
2.5 OSEK Interrupt Handling . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 HC12 Register Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7 C16X/ST10 Register Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 PowerPC Register Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1 StackAnalyzer ControlCenter . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Stacyzer Entry Point Selection Window . . . . . . . . . . . . . . . 80
4.3 Full Graph View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Zoom into Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.5 StackAnalyzer computes wrong stack . . . . . . . . . . . . . . . . . . . . 100
4.6 t8.c interpretation by StackAnalyzer . . . . . . . . . . . . . . . . . . . . 103
4.7 Faked Switch Statement on C16X . . . . . . . . . . . . . . . . . . . . . . 105
4.8 Faked Switch Statement on PowerPC. . . . . . . . . . . . . . . . . . . . 107
5.1 Interference Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.1 ProOSEK Configurator . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
910 LIST OF FIGURES

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.