research-article

Combined WCET analysis of bitcode and machine code using control-flow relation graphs

Authors:

Benedikt Huber,

Daniel Prokesch,

Peter PuschnerAuthors Info & Claims

LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Pages 163 - 172

https://doi.org/10.1145/2491899.2465567

Published: 20 June 2013 Publication History

Abstract

Static program analyses like stack usage analysis and worst-case execution time (WCET) analysis depend on the actual machine code generated by the compiler for the target system. As the analysis of binary code is costly, hard to diagnose and platform dependent, it is preferable to carry out parts of these analyses on a higher-level program representation. To this end, the higher-level code and the machine code need to be related, a difficult task due to the complexity of modern optimizing compilers.

In this article, we present a novel representation called control-flow relation graphs, which provide an accurate model of the control-flow relation between machine code and the compiler's intermediate representation. In order to facilitate the integration of our approach in existing compiler frameworks, we develop a construction algorithm that builds the control-flow relation graph from partial mappings provided by the compiler. The WCET calculation method for control-flow relation graphs processes flow information from both the intermediate representation and machine code. Furthermore, we demonstrate the transformation of flow information from the IR to the machine code level, in order to use existing industrial-strength WCET analysis tools operating on machine code. We implemented the construction algorithm within the LLVM compiler framework, along with an implementation of the combined WCET calculation method.

The evaluation demonstrates that the approach is able to relate bitcode (LLVM's intermediate representation) and machine code in a precise way, with a WCET increase of at most 2% when using flow facts on the bitcode level, compared to equivalent ones on the machine-code level. As the methods presented in this article provide a cost-effective way to reuse platform independent flow information, they have the potential to simplify WCET analysis, and popularize its use in the development process of real-time systems.

References

[1]

R. L. Bernstein. Producing good code for the case statement. Software: Practice and Experience, 15 (10): 1021--1024, 1985.

Digital Library

[2]

J. Berstel. Transductions and context-free languages, volume 4. Teubner Stuttgart, 1979.

[3]

A. Bouchhima, P. Gerin, and F. Petrot. Automatic instrumentation of embedded software for high level hardware/software co-simulation. In Design Automation Conference, 2009. ASP-DAC 2009. Asia and South Pacific, pages 546--551, Jan. 2009.

Digital Library

[4]

A. R. Bradley and Z. Manna. The Calculus of Computation: Decision Procedures with Applications to Verification. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007.

Digital Library

[5]

J. Engblom, A. Ermedahl, and P. Altenbernd. Facilitating worst-case execution times analysis for optimized code. In Proceedings of the 10th Euromicro Workshop on Real-Time Systems, pages 146--153, June 1998.

[6]

H. Falk and P. Lokuciejewski. A compiler framework for the reduction of worst-case execution times. Real-Time Systems, pages 1--50, 2010.

Digital Library

[7]

J. Gustafsson, A. Ermedahl, C. Sandberg, and B. Lisper. Automatic derivation of loop bounds and infeasible paths for wcet analysis using abstract execution. In Proceedings of the 27th IEEE International Real-Time Systems Symposium, RTSS, pages 57--66, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[8]

J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper. The Mälardalen WCET benchmarks -- past, present and future. pages 137--147, Brussels, Belgium, July 2010. OCG.

[9]

R. Kirner, P. Puschner, and A. Prantl. Transforming flow information during code optimization for timing analysis. Real-Time Systems, 45: 72--105, 2010. ISSN 0922--6443. 10.1007/s11241-010--9091--8.

Digital Library

[10]

C. Lattner and V. Adve. LLVM: a compilation framework for lifelong program analysis transformation. In Code Generation and Optimization, 2004. CGO 2004. International Symposium on, pages 75--86, march 2004.

Digital Library

[11]

A. Mok, P. Amerasinghe, M. Chen, and K. Tantisirivat. Evaluating tight execution time bounds of programs by annotations. IEEE Real-Time Syst. Newsl., 5 (2--3): 81--86, May 1989.

Digital Library

[12]

G. C. Necula. Translation validation for an optimizing compiler. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI '00, pages 83--94, New York, NY, USA, 2000. ACM.

Digital Library

[13]

P. P. Puschner and A. V. Schedl. Computing maximum task execution times - a graph-based approach. Real-Time Systems, 13 (1): 67--91, 1997.

Digital Library

[14]

J. Schnerr, O. Bringmann, A. Viehl, and W. Rosenstiel. High-performance timing simulation of embedded software. In Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE, pages 290 --295, june 2008.

Digital Library

[15]

M. Schoeberl, T. B. Preußer, and S. Uhrig. The embedded Java benchmark suite JemBench. In phProceedings of the 8th International Workshop on Java Technologies for Real-Time and Embedded Systems, JTRES'10, pages 120--127, New York, NY, USA, 2010. ACM.

Digital Library

[16]

M. Schoeberl, P. Schleuniger, W. Puffitsch, F. Brandner, C. W. Probst, S. Karlsson, and T. Thorn. Towards a time-predictable dual-issue microprocessor: The Patmos approach. In phFirst Workshop on Bringing Theory to Practice: Predictability and Performance in Embedded Systems (PPES 2011), pages 11--20, March 2011.

[17]

C. Sinz, F. Merz, and S. Falke. LLBMC: A bounded model checker for LLVM's intermediate representation (competition contribution). In C. Flanagan and B. König, editors, phProceedings of the 18th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'12), pages 542--544. Springer-Verlag, 2012.

Digital Library

[18]

S. Stattelmann, O. Bringmann, and W. Rosenstiel. Dominator homomorphism based code matching for source-level simulation of embedded software. In Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, CODES+ISSS '11, pages 305?--314, New York, NY, USA, 2011. ACM.

Digital Library

[19]

S. Stattelmann, G. Gebhard, C. Cullmann, O. Bringmann, and W. Rosenstiel. Hybrid source-level simulation of data caches using abstract cache models. In Design, Automation Test in Europe Conference Exhibition (DATE), 2012, pages 376--381, Mar. 2012.

Digital Library

[20]

R. E. Tarjan. A unified approach to path problems. J. ACM, 28 (3): 577--593, July 1981.

Digital Library

[21]

H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET prediction by separate cache and path analyses. Real-Time Systems, 18 (2/3), 2000.

Digital Library

[22]

Z. Wang and J. Henkel. Accurate source-level simulation of embedded software with respect to compiler optimizations. In Design, Automation Test in Europe Conference Exhibition (DATE), 2012, pages 382 --387, Mar. 2012.

Digital Library

[23]

F. Zuleger, S. Gulwani, M. Sinn, and H. Veith. Bound analysis of imperative programs with the size-change abstraction. In E. Yahav, editor, phStatic Analysis, volume 6887 of Lecture Notes in Computer Science, pages 280--297. Springer Berlin / Heidelberg, 2011.

Digital Library

Cited By

Wägemann P(2022)Static Worst-Case Analyses and Their Validation Techniques for Safety-Critical SystemsErnst Denert Award for Software Engineering 202010.1007/978-3-030-83128-8_11(227-247)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-83128-8_11
Schuster SWagemann PUlbrich PSchroder-Preikschat W(2019)Proving Real-Time Capability of Generic Operating Systems by System-Aware Timing Analysis2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00034(318-330)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00034
Wagemann PDistler TEichler CSchroder-Preikschat W(2017)Benchmark Generation for Timing Analysis2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2017.6(319-330)Online publication date: Apr-2017
https://doi.org/10.1109/RTAS.2017.6
Show More Cited By

Index Terms

Combined WCET analysis of bitcode and machine code using control-flow relation graphs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Combined WCET analysis of bitcode and machine code using control-flow relation graphs
LCTES '13

Static program analyses like stack usage analysis and worst-case execution time (WCET) analysis depend on the actual machine code generated by the compiler for the target system. As the analysis of binary code is costly, hard to diagnose and platform ...
Combined WCET analysis of bitcode and machine code using control-flow relation graphs
LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Static program analyses like stack usage analysis and worst-case execution time (WCET) analysis depend on the actual machine code generated by the compiler for the target system. As the analysis of binary code is costly, hard to diagnose and platform ...
Points-to analysis with efficient strong updates
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

This paper explores a sweet spot between flow-insensitive and flow-sensitive subset-based points-to analysis. Flow-insensitive analysis is efficient: it has been applied to million-line programs and even its worst-case requirements are quadratic space ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

June 2013

184 pages

ISBN:9781450320856

DOI:10.1145/2491899

General Chair:
Björn Franke
University of Edinburgh, UK
,
Program Chair:
Jingling Xue
University of New South Wales, Australia

ACM SIGPLAN Notices Volume 48, Issue 5
LCTES '13
May 2013
165 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499369
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '13

Sponsor:

LCTES '13: SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2013

June 20 - 21, 2013

Washington, Seattle, USA

Acceptance Rates

LCTES '13 Paper Acceptance Rate 16 of 60 submissions, 27%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wägemann P(2022)Static Worst-Case Analyses and Their Validation Techniques for Safety-Critical SystemsErnst Denert Award for Software Engineering 202010.1007/978-3-030-83128-8_11(227-247)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-83128-8_11
Schuster SWagemann PUlbrich PSchroder-Preikschat W(2019)Proving Real-Time Capability of Generic Operating Systems by System-Aware Timing Analysis2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00034(318-330)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00034
Wagemann PDistler TEichler CSchroder-Preikschat W(2017)Benchmark Generation for Timing Analysis2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2017.6(319-330)Online publication date: Apr-2017
https://doi.org/10.1109/RTAS.2017.6
Dietrich CWagemann PUlbrich PLohmann D(2017)SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems (Outstanding Paper)2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2017.37(37-48)Online publication date: Apr-2017
https://doi.org/10.1109/RTAS.2017.37
Sieh VBurlacu RHonig TJanker HRaffeck PWagemann PSchroder-Preikschat W(2017)An End-to-End Toolchain: From Automated Cost Modeling to Static WCET and WCEC Analysis2017 IEEE 20th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC.2017.10(158-167)Online publication date: May-2017
https://doi.org/10.1109/ISORC.2017.10
Korsholm SSchoeberl MPuffitsch WZiarek L(2015)Safety-Critical Java on a Time-Predictable ProcessorProceedings of the 13th International Workshop on Java Technologies for Real-time and Embedded Systems10.1145/2822304.2822309(1-9)Online publication date: 7-Oct-2015
https://dl.acm.org/doi/10.1145/2822304.2822309
Li HPuaut IRohou E(2015)Tracing Flow Information for Tighter WCET EstimationProceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2015.18(217-226)Online publication date: 19-Aug-2015
https://dl.acm.org/doi/10.1109/RTCSA.2015.18
Wägemann PDistler THönig TJanker HKapitza RSchröder-Preikschat W(2015)Worst-Case Energy Consumption Analysis for Energy-Constrained Embedded SystemsProceedings of the 2015 27th Euromicro Conference on Real-Time Systems10.1109/ECRTS.2015.17(105-114)Online publication date: 8-Jul-2015
https://dl.acm.org/doi/10.1109/ECRTS.2015.17
Schoeberl MAbbaspour SAkesson BAudsley NCapasso RGarside JGoossens KGoossens SHansen SHeckmann RHepp SHuber BJordan AKasapaki EKnoop JLi YProkesch DPuffitsch WPuschner PRocha ASilva CSparsø JTocchi A(2015)T-CRESTJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2015.04.00261:9(449-471)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.sysarc.2015.04.002
Li HPuaut IRohou EJan MBen Hedia BGoossens JMaiza C(2014)Traceability of Flow InformationProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659805(97-106)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659805
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten