Worst-case execution time aware compilation techniques for real-time systems

✍ Scribed by Lokuciejewski, Paul;Marwedel, Peter

• Publisher: Springer
• Year: 2010;2011
• Tongue: English
• Leaves: 268
• Series: Embedded systems
• Edition: 1st ed
• Category: Library

✦ Synopsis

This book presents the first comprehensive approach integrating WCET considerations into the code generation process. Based on the proposed reconciliation between a compiler and a timing analyzer, a wide range of novel optimization techniques is provided.

✦ Table of Contents

Abstract Domain......Page 4
Acknowledgements......Page 5
Label Determination......Page 11
Evolutionary Multi-objective Optimization Algorithms......Page 14
Cover......Page 1
Abstract Semantics......Page 3
Appendix B Transformation of Conditions......Page 7
Internal Structure of WCC's Optimizer......Page 8
References......Page 9
WCET-Aware Source Code Level Optimizations......Page 2
Contents......Page 6
Encoding of Optimization Sequences......Page 10
List of Figures......Page 12
List of Tables......Page 15
Introduction......Page 16
Related Work......Page 17
Design of Embedded Real-Time Systems......Page 18
Statistical Hypothesis Testing......Page 19
Industrial Practice for Meeting Timing Constraints......Page 20
Motivating Example......Page 21
WCET-Aware Compilation......Page 22
Contribution of This Work......Page 24
Outline......Page 26
Static Approach......Page 28
Hybrid Approach......Page 29
Control Flow......Page 30
Processor Behavioral Analysis......Page 31
Context-Dependent Timing Analysis......Page 32
Flow Facts......Page 33
Static WCET Analyzer aiT......Page 35
Pareto Front Approximation......Page 13
Challenges for WCET Minimization......Page 23
Learning Algorithms......Page 25
WCET......Page 34
Summary......Page 36
Introduction......Page 37
Related Work......Page 38
Related Work......Page 39
Compiler Frontend ICD-C IR......Page 40
Worst-Case Loop Iteration Counts......Page 42
Standard Source Code Level Optimizations......Page 43
Compiler Backend LLIR......Page 44
Standard Assembly Level Optimizations......Page 45
Conversion from LLIR to CRL2......Page 47
Operation Identification......Page 48
WCET......Page 49
Loop Transformation......Page 51
Invocation of aiT......Page 52
Import of Worst-Case Execution Data......Page 53
Specification of Flow Facts......Page 54
Translation and Transformation of Flow Facts......Page 55
Related Work......Page 56
Abstract Interpretation......Page 57
Modified Abstract Interpretation......Page 58
Construction of the Invariant Path......Page 59
Interprocedural Program Slicing......Page 60
Case Study: WCET-Aware Loop Unswitching......Page 61
Ehrhart Polynomial Evaluation......Page 65
Static Statement Evaluation......Page 66
Analysis Time......Page 67
Back-Annotation......Page 68
Introduction......Page 27
Code Generator......Page 46
Exploitation of Memory Hierarchy Specification......Page 50
Polyhedral Condition Evaluation......Page 62
Preconditions for Loop Evaluation......Page 64
Mapping of Low-Level to High-Level Components......Page 69
Back-Annotated Data......Page 71
WCET-Aware Source Code Level Optimizations......Page 74
Introduction......Page 75
Existing Code Optimization Techniques......Page 76
Procedure Cloning......Page 77
Motivating Example......Page 78
Related Work......Page 81
Standard Procedure Cloning......Page 82
Selection of Functions to Be Cloned......Page 83
Impact of Standard Cloning on WCET......Page 84
Experimental Results for Standard Procedure Cloning......Page 85
WCET......Page 86
Code Size......Page 87
WCET-Aware Procedure Cloning......Page 88
WCET......Page 90
Code Size......Page 91
Optimization Run Time......Page 92
Motivating Example......Page 93
Superblock-Based ACET Minimization......Page 94
WCET Minimization......Page 95
Trace Selection......Page 96
Longest Path Approach......Page 97
Concepts of Superblocks......Page 98
Assembly Superblocks......Page 99
Preprocessing......Page 101
IPET-Based WCEP Update......Page 103
Alias Analysis......Page 104
Livetime Analysis......Page 105
WCET-SB Dead Code Elimination......Page 106
WCET......Page 107
ACET......Page 109
Optimization Run Time......Page 110
Motivating Example......Page 111
Related Work......Page 112
Standard Loop Unrolling......Page 113
Worst-Case Loop Iteration Counts......Page 115
I-Cache and Memory Constraints......Page 116
Exploiting Back-Annotation......Page 117
Prediction of Unrolling Effects......Page 118
Determination of Final Unrolling Factor......Page 120
WCET-Aware Unrolling Heuristics......Page 121
WCET......Page 122
ACET......Page 124
Code Size......Page 125
Optimization Run Time......Page 126
Motivating Example......Page 127
Related Work......Page 128
Invariant Path Paradigm......Page 129
IF-THEN Structure......Page 130
IF-THEN-ELSE Structure with Statically Evaluable Condition......Page 131
IF-THEN-ELSE Structure with Statically Non-evaluable Condition......Page 132
Invariant Path Ratio......Page 133
Case Study: WCET-Aware Loop Unswitching......Page 134
Optimization Run Time......Page 138
WCET......Page 139
Code Size......Page 140
Summary......Page 141
Introduction......Page 143
Existing Code Optimization Techniques......Page 144
Procedure Positioning......Page 145
Motivating Example......Page 146
Related Work......Page 148
Standard Procedure Positioning......Page 149
WCET-Centric Call Graph-Based Positioning......Page 150
Greedy WCET-Aware Positioning Approach......Page 151
Heuristic WCET-Aware Positioning Approach......Page 154
Optimization Run Time......Page 156
Motivating Example......Page 157
Related Work......Page 159
Local Instruction Scheduling......Page 160
List Scheduling......Page 161
WCET-Aware Trace Scheduling......Page 163
WCET......Page 166
ACET......Page 167
Optimization Run Time......Page 168
Introduction......Page 170
MLB Heuristic Generation for ACET Reduction......Page 172
Supervised Learning......Page 173
Integration and Use of MLB Heuristics in Compilers......Page 174
Motivating Example......Page 176
Standard Function Inlining......Page 177
Related Work......Page 178
Register Pressure Analyzer......Page 179
Label Determination......Page 180
Model Induction......Page 181
Random Forests......Page 182
Accuracy of Classification......Page 183
Variable Importance Measure......Page 184
WCET......Page 185
Code Size......Page 188
Compilation Run Time......Page 189
Motivating Example......Page 190
Standard Loop-Invariant Code Motion......Page 191
MLB Heuristic Generation at Assembly Level......Page 193
Learning Algorithms......Page 194
Performance Evaluation......Page 195
Parameter Optimization......Page 197
Label Determination......Page 198
Application of WCET-Aware LICM......Page 199
WCET......Page 200
Compilation run time......Page 204
Summary......Page 205
Introduction......Page 207
Motivation......Page 209
Related Work......Page 211
Compiler Optimization Sequence Exploration......Page 212
Adaptive Compilers......Page 213
Internal Structure of WCC's Optimizer......Page 214
Available Compiler Optimizations......Page 215
Encoding of Optimization Sequences......Page 216
Objective Functions......Page 218
Pareto Front Approximation......Page 219
Evolutionary Multi-objective Optimization Algorithms......Page 220
Statistical Performance Assessment......Page 221
Hypervolume Indicators......Page 224
Statistical Hypothesis Testing......Page 225
Experimental Results for Optimization Exploration......Page 226
Statistical Performance Assessment......Page 228
Analysis of Pareto Front Approximations......Page 230
Analysis of the Optimization Sequences......Page 232
Cross Validation......Page 233
Optimization Run Time......Page 235
Research Contributions......Page 238
Extensions to WCC Framework......Page 239
WCET-Aware Assembly Level Optimizations......Page 240
Extensions to WCC Compiler Framework......Page 242
Multi-objective Optimizations......Page 243
Concrete Semantics......Page 244
Abstract Semantics......Page 246
Abstract Domain......Page 247
Calculation of Abstract Semantics......Page 248
Appendix B Transformation of Conditions......Page 250
References......Page 252
Index......Page 265