Abstract
The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code.
In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level.
We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Abbreviations
- WCET:
-
Worst-case execution time
- BCET:
-
Best-case execution time
- IPET:
-
Implicit path enumeration technique
- LCFG:
-
Control-flow graph with loop-scope information
References
Allen R, Kennedy K (2002) Optimizing compilers for modern architectures. Morgan Kaufmann, San Mateo
Ball T, Larus JR (1996) Efficient path profiling. In: Proc IEEE international symposium on microarchitecture, pp 46–57
Cullmann C, Martin F (2007) Data-flow based detection of loop bounds. In: Proc 7th international workshop on worst-case execution time analysis, Pisa, Italy
Drewes F, Hoffmann B, Plump D (2002) Hierarchical graph transformation. J Comput Syst Sci 64:249–283. Short version in Proc FOSSACS 2000, LNCS, vol 1784
Engblom J (1997) Worst-case execution time analysis for optimized code. Master’s thesis, Uppsala University, Uppsala, Sweden
Engblom J, Ermedahl A, Altenbernd P (1998) Facilitating worst-case execution time analysis for optimized code. In: Proc 10th Euromicro real-time workshop, Berlin, Germany
Ferdinand C, Heckmann R, Langenbach M, Martin F, Schmidt M, Theiling H, Thesing S, Wilhelm R (2001) Reliable and precise WCET determination for a real-life processor. In: Proc of the 1st international workshop on embedded software (EMSOFT 2001), Tahoe City, CA, USA, pp 469–485
Gustafsson J, Ermedahl A (1998) Automatic derivation of path and loop annotations in object-oriented real-time programs. Parallel Distrib Comput Pract 1(2)
Gustafsson J, Ermedahl A, Sandberg C, Lisper B (2006) Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution. In: Proc 27th IEEE real-time systems symposium (RTSS 2006), Rio de Janeiro, Brazil
Healy CA, Arnold RD, Mueller F, Whalley D, Harmon MG (1999) Bounding pipeline and instruction cache performance. IEEE Trans Comput 48(1)
Healy CA, Sjödin M, Rustagi V, Whalley D, van Engelen R (2000) Supporting timing analysis by automatic bounding of loop iterations. Real-Time Syst 18:121–148
Healy CA, Whalley DB (2002) Automatic detection and exploitation of branch constraints for timing analysis. IEEE Trans Softw Eng 28:763–781
INFINEON (2000) C167CR derivatives. 16-bit single-chip microcontroller. User’s manual, Version 3.0. Infineon Technologies AG
Jaramillo CI, Gupta R, Soffa ML (1998) Capturing the effects of code improving transformations. In: Proc international conference on parallel architectures and compilation techniques (PACT’98), Paris, France, pp 118–123
Kirner R (2002) The programming language wcetC. Technical Report 02/2002, Technische Universität Wien, Institut für Technische Informatik, Treitlstr 1-3/182-1, 1040 Vienna, Austria
Kirner R (2003) Extending optimising compilation to support worst-case execution time analysis. PhD thesis, Technische Universität Wien, Vienna, Austria
Kirner R (2008) Compiler support for timing analysis of optimized code: precise timing analysis of machine code with convenient annotation of source code. VDM Verlag, Saarbrücken
Kirner R, Puschner P (2001) Transformation of path information for WCET analysis during compilation. In: Proc 13th IEEE Euromicro conference on real-time systems, Delft, The Netherlands, pp 29–36
Kirner R, Puschner P (2003) Timing analysis of optimised code. In: Proc 8th IEEE international workshop on object-oriented real-time dependable systems (WORDS 2003), Guadalajara, Mexico, pp 100–105
Kirner R, Knoop J, Prantl A, Schordan M, Wenzel I (2007) WCET analysis: the annotation language challenge. In: Proc 7th international workshop on worst-case execution time analysis, Pisa, Italy, pp 83–99
Kirner R, Kadlec A, Puschner P, Prantl A, Schordan M, Knoop J (2008) Towards a common WCET annotation language: essential ingredients. In: Proc 8th international workshop on worst-case execution time analysis, Prague, Czech Republic, pp 53–65
Li Y-TS, Malik S (1995) Performance analysis of embedded software using implicit path enumeration. In: Proc 32nd ACM/IEEE design automation conference, pp 456–461
Lim S-S, Bae YH, Jang GT, Rhee B-D, Min SL, Park CY, Shin H, Park K, Moon S-M, Kim C-S (1995) An accurate worst case timing analysis for RISC processors. Softw Eng 21(7):593–604
Lim S-S, Kim J, Min SL (1998) A worst case timing analysis technique for optimized programs. In: Proc 5th international conference on real-time computing systems and applications (RTCSA), Hiroshima, Japan, pp 151–157
Lokuciejewski P (2007) A WCET-aware compiler. Design, concepts and realization. VDM Verlag, Saarbrücken
Lokuciejewski P, Marwedel P (2009) Combining worst-case timing models, loop unrolling, and static loop analysis for WCET minimization. In: Proc 21st Euromicro conference on real-time systems, Dublin, Ireland
Lokuciejewski P, Falk H, Marwedel P, Theiling H (2008) WCET-driven, code-size critical procedure cloning. In: Proc 11th international workshop on software and compilers for embedded systems, Munich, Germany, pp 21–30
Lokuciejewski P, Cordes D, Falk H, Marwedel P (2009) A fast and precise static loop analysis based on abstract interpretation program slicing and polytope models. In: Proc international symposium on code generation and optimization, Seattle, USA
Marlowe TJ, Masticola SP (1992) Safe optimization for hard real-time programming. In: Proc 2nd international conference on systems integration (ICSI), pp 436–445
Mok AK, Amerasinghe P, Chen M, Tantisirivat K (1989) Evaluating tight execution time bounds of programs by annotations. In: Proc 6th IEEE workshop on real-time operating systems and software, Pittsburgh, PA, USA, pp 74–80
MRTC Benchmarks (2009) Mälardalen research and technology centre WCET benchmarks. Web page http://www.mrtc.mdh.se/projects/wcet/. Accessed online in January 2010
Muchnick SS (1997) Advanced compiler design & implementation. Morgan Kaufmann, San Mateo
Park CY (1993) Predicting program execution times by analyzing static and dynamic program paths. Real-Time Syst 5(1):31–62
Park CY, Shaw AC (1991) Experiments with a program timing tool based on a source-level timing schema. Computer 24(5):48–57
Pop S, Cohen A, Bastoul C, Girbal S, Silber GA, Vasilache N (2006) GRAPHITE: Loop optimizations based on the polyhedral model for GCC. In: Proc 4th GCC developer’s summit, pp 179–198
Prantl A (2007a) The CoSTA transformer: integrating optimizing compilation and WCET flow facts transformation. In: Proceedings 14 Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS’07)
Prantl A (2007b) Source-to-source transformations for WCET analysis: the CoSTA approach. In: Proc 24. Workshop der GI-Fachgruppe Programmiersprachen und Rechenkonzepte, Christian-Albrechts-Universität zu Kiel, Bad Honnef, Germany
Prantl A, Schordan M, Knoop J (2008) TuBound—a conceptually new tool for worst-case execution time analysis. In: Proc 8th international workshop on worst-case execution time analysis, Prague, Czech Republic
Puschner P, Schedl AV (1997) Computing maximum task execution times—a graph-based approach. Real-Time Syst 13:67–91
Quinlan DJ, Schordan M, Miller B, Kowarschik M (2004) Parallel object-oriented framework optimization. Concurr Comput Pract Exper 16(2–3):293–302
Ramalingam G (2002) On loops, dominators, and dominance frontiers. ACM Trans Program Lang Syst 24(5):455–490
Schulte D (2007) Flow Facts für WCET-optimierende Compiler: Modellierung und Transformation. VDM Verlag, Saarbrücken
Vrchoticky A (1994) Compilation support for fine-grained execution time analysis. In: Proc ACM SIGPLAN workshop on language, compiler and tool support for real-time systems, Orlando, FL
Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckman R, Mitra T, Mueller F, Puaut I, Puschner P, Staschulat J, Stenstrom P (2008) The worst-case execution time problem—overview of methods and survey of tools. ACM Trans Embed Comput Syst (TECS) 7(3)
Younis MF, Marlowe TJ, Tsai G, Stoyenko AD (1996) Toward compiler optimization of distributed real-time processes. In: Proc 2nd international conference on engineering of complex computer systems, pp 35–42
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Kirner, R., Puschner, P. & Prantl, A. Transforming flow information during code optimization for timing analysis. Real-Time Syst 45, 72–105 (2010). https://doi.org/10.1007/s11241-010-9091-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-010-9091-8