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

Sujets

• Informatik

Informations

• Publié par: friedrich-alexander-universitat_erlangen-nurnberg
• Publié le: 01 janvier 2004
• Nombre de lectures: 22
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

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 an