Document Open Access Logo

LLVMTA: An LLVM-Based WCET Analysis Tool

Authors Sebastian Hahn , Michael Jacobs, Nils Hölscher , Kuan-Hsun Chen , Jian-Jia Chen , Jan Reineke

PDF
Thumbnail PDF

File

OASIcs.WCET.2022.2.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Sebastian Hahn
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Michael Jacobs
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Nils Hölscher
  • TU Dortmund University, Germany
Kuan-Hsun Chen
  • University of Twente, The Netherlands
Jian-Jia Chen
  • TU Dortmund University, Germany
Jan Reineke
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany

Funding

This work has been supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Transregional Collaborative Research Centre SFB/TR 14 (AVACS); by the Saarbrücken Graduate School of Computer Science, which received funding from the DFG as part of the Excellence Initiative of the German Federal and State Governments; and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 101020415).

Acknowledgements

We would like to thank all the students at Saarland University who contributed during the development of llvmta: in particular Claus Faymonville for his extensive contributions in a very early development stage, but also Tina Jung, Darshit Shah, and Tobias Stark.

Cite As Get BibTex

Sebastian Hahn, Michael Jacobs, Nils Hölscher, Kuan-Hsun Chen, Jian-Jia Chen, and Jan Reineke. LLVMTA: An LLVM-Based WCET Analysis Tool. In 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022). Open Access Series in Informatics (OASIcs), Volume 103, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/OASIcs.WCET.2022.2

Abstract

We present llvmta, an academic WCET analysis tool based on the LLVM compiler infrastructure. It aims to enable the evaluation of novel WCET analysis approaches in a state-of-the-art analysis framework without dealing with the complexity of modeling real-world hardware architectures. We discuss the main design decisions and interfaces that allow to implement new analysis approaches. Finally, we highlight various existing research projects whose evaluation has been enabled by llvmta.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software performance
  • Software and its engineering → Automated static analysis
  • Software and its engineering → Compilers
  • Computer systems organization → Real-time system architecture
Keywords
  • WCET analysis
  • low-level analysis
  • LLVM

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Martin Alt, Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. Cache behavior prediction by abstract interpretation. In Proceedings of the Third International Static Analysis Symposium, SAS 1996, Aachen, Germany, pages 52-66, 1996. URL: https://doi.org/10.1007/3-540-61739-6_33.
  2. Anil Altinay, Joseph Nash, Taddeus Kroes, Prabhu Rajasekaran, Dixin Zhou, Adrian Dabrowski, David Gens, Yeoul Na, Stijn Volckaert, Cristiano Giuffrida, Herbert Bos, and Michael Franz. BinRec: dynamic binary lifting and recompilation. In Angelos Bilas, Kostas Magoutis, Evangelos P. Markatos, Dejan Kostic, and Margo I. Seltzer, editors, EuroSys '20: Fifteenth EuroSys Conference 2020, Heraklion, Greece, April 27-30, 2020, pages 36:1-36:16. ACM, 2020. URL: https://doi.org/10.1145/3342195.3387550.
  3. Sebastian Altmeyer. Analysis of preemptively scheduled hard real-time systems. PhD thesis, Saarland University, 2013. URL: http://scidok.sulb.uni-saarland.de/volltexte/2013/5279/.
  4. Kapil Anand, Matthew Smithson, Khaled Elwazeer, Aparna Kotha, Jim Gruen, Nathan Giles, and Rajeev Barua. A compiler-level intermediate representation based binary analysis and rewriting system. In Zdenek Hanzálek, Hermann Härtig, Miguel Castro, and M. Frans Kaashoek, editors, Eighth Eurosys Conference 2013, EuroSys '13, Prague, Czech Republic, April 14-17, 2013, pages 295-308. ACM, 2013. URL: https://doi.org/10.1145/2465351.2465380.
  5. Mihail Asavoae, Claire Maiza, and Pascal Raymond. Program semantics in model-based WCET analysis: A state of the art perspective. In Claire Maiza, editor, 13th International Workshop on Worst-Case Execution Time Analysis, WCET 2013, July 9, 2013, Paris, France, volume 30 of OASIcs, pages 32-41. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: https://doi.org/10.4230/OASIcs.WCET.2013.32.
  6. Olaf Bachmann, Paul S. Wang, and Eugene V. Zima. Chains of recurrences - a method to expedite the evaluation of closed-form functions. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994, Oxford, UK, pages 242-249, 1994. URL: https://doi.org/10.1145/190347.190423.
  7. Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. OTAWA: an open toolbox for adaptive WCET analysis. In Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner, and Theo Ungerer, editors, Software Technologies for Embedded and Ubiquitous Systems - 8th IFIP WG 10.2 International Workshop, SEUS 2010, Waidhofen/Ybbs, Austria, October 13-15, 2010. Proceedings, volume 6399 of Lecture Notes in Computer Science, pages 35-46. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16256-5_6.
  8. Sébastien Bardin, Philippe Herrmann, and Franck Védrine. Refinement-based CFG reconstruction from unstructured programs. In Ranjit Jhala and David A. Schmidt, editors, Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Austin, TX, USA, January 23-25, 2011. Proceedings, volume 6538 of Lecture Notes in Computer Science, pages 54-69. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-18275-4_6.
  9. Tobias Blaß, Sebastian Hahn, and Jan Reineke. Write-back caches in WCET analysis. In Proceedings of the 29th Euromicro Conference on Real-Time Systems, ECRTS 2017, June 2017. Google Scholar
  10. Silvian Calman and Jianwen Zhu. Interprocedural induction variable analysis based on interprocedural SSA form IR. In Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE 2010, Toronto, Ontario, Canada, pages 37-44, 2010. URL: https://doi.org/10.1145/1806672.1806680.
  11. Sudipta Chattopadhyay and Abhik Roychoudhury. Scalable and precise refinement of cache timing analysis via path-sensitive verification. Real Time Syst., 49(4):517-562, 2013. URL: https://doi.org/10.1007/s11241-013-9178-0.
  12. Antoine Colin and Isabelle Puaut. A modular & retargetable framework for tree-based WCET analysis. In 13th Euromicro Conference on Real-Time Systems (ECRTS 2001), 13-15 June 2001, Delft, The Netherlands, Proceedings, pages 37-44. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/EMRTS.2001.933995.
  13. Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, pages 238-252, 1977. URL: https://doi.org/10.1145/512950.512973.
  14. Christoph Cullmann. Cache persistence analysis: Theory and practice. ACM Transactions on Embedded Computing Systems, 12(1s):40:1-40:25, 2013. URL: https://doi.org/10.1145/2435227.2435236.
  15. Christoph Cullmann and Florian Martin. Data-flow based detection of loop bounds. In Proceedings of the 7th International Workshop on Worst-Case Execution Time Analysis, WCET 2007, Pisa, Italy, 2007. URL: https://doi.org/10.4230/OASIcs.WCET.2007.1193.
  16. Sun Ding, Hee Beng Kuan Tan, and Kaiping Liu. A survey of infeasible path detection. In Joaquim Filipe and Leszek A. Maciaszek, editors, ENASE 2012 - Proceedings of the 7th International Conference on Evaluation of Novel Approaches to Software Engineering, Wroclaw, Poland, 29-30 June, 2012, pages 43-52. SciTePress, 2012. Google Scholar
  17. Jakob Engblom. Processor Pipelines and Static Worst-Case Execution Time Analysis. PhD thesis, Uppsala University, Sweden, 2002. URL: http://nbn-resolving.de/urn:nbn:se:uu:diva-1832.
  18. Alexis Engelke, Dominik Okwieka, and Martin Schulz. Efficient LLVM-based dynamic binary translation. In Ben L. Titzer, Harry Xu, and Irene Zhang, editors, VEE '21: 17th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, Virtual USA, April 16, 2021, pages 165-171. ACM, 2021. URL: https://doi.org/10.1145/3453933.3454022.
  19. Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Björn Lisper. Loop bound analysis based on a combination of program slicing, abstract interpretation, and invariant analysis. In Proceedings of the 7th International Workshop on Worst-Case Execution Time Analysis, WCET 2007, Pisa, Italy, 2007. URL: https://doi.org/10.4230/OASIcs.WCET.2007.1194.
  20. Heiko Falk and Paul Lokuciejewski. A compiler framework for the reduction of worst-case execution times. Real Time Syst., 46(2):251-300, 2010. URL: https://doi.org/10.1007/s11241-010-9101-x.
  21. Claus Faymonville. Evaluating compositional timing analyses. Master’s thesis, Saarland University, 2015. Google Scholar
  22. Christian Ferdinand, Reinhold Heckmann, Marc Langenbach, Florian Martin, Michael Schmidt, Henrik Theiling, Stephan Thesing, and Reinhard Wilhelm. Reliable and precise WCET determination for a real-life processor. In Thomas A. Henzinger and Christoph M. Kirsch, editors, Embedded Software, First International Workshop, EMSOFT 2001, Tahoe City, CA, USA, October, 8-10, 2001, Proceedings, volume 2211 of Lecture Notes in Computer Science, pages 469-485. Springer, 2001. URL: https://doi.org/10.1007/3-540-45449-7_32.
  23. Andrea Flexeder, Bogdan Mihaila, Michael Petter, and Helmut Seidl. Interprocedural control flow reconstruction. In Proceedings of the 8th Asian Symposium on Programming Languages and Systems, APLAS 2010, Shanghai, China, pages 188-203, 2010. URL: https://doi.org/10.1007/978-3-642-17164-2_14.
  24. David Griffin, Benjamin Lesage, Alan Burns, and Robert I. Davis. Lossy compression for worst-case execution time analysis of PLRU caches. In Mathieu Jan, Belgacem Ben Hedia, Joël Goossens, and Claire Maiza, editors, 22nd International Conference on Real-Time Networks and Systems, RTNS '14, Versailles, France, October 8-10, 2014, page 203. ACM, 2014. URL: https://doi.org/10.1145/2659787.2659807.
  25. Daniel Grund and Jan Reineke. Abstract interpretation of FIFO replacement. In Jens Palsberg and Zhendong Su, editors, Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings, volume 5673, pages 120-136. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03237-0_10.
  26. Daniel Grund and Jan Reineke. Precise and efficient FIFO-replacement analysis based on static phase detection. In 22nd Euromicro Conference on Real-Time Systems, ECRTS 2010, Brussels, Belgium, July 6-9, 2010, pages 155-164. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/ECRTS.2010.8.
  27. Daniel Grund and Jan Reineke. Toward precise PLRU cache analysis. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OASICS, pages 23-35. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010. URL: https://doi.org/10.4230/OASIcs.WCET.2010.23.
  28. Nan Guan, Mingsong Lv, Wang Yi, and Ge Yu. WCET analysis with MRU cache: Challenging lru for predictability. ACM Trans. Embed. Comput. Syst., 13(4s):123:1-123:26, April 2014. URL: https://doi.org/10.1145/2584655.
  29. Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi. FIFO cache analysis for WCET estimation: a quantitative approach. In Enrico Macii, editor, Design, Automation and Test in Europe, DATE 13, Grenoble, France, March 18-22, 2013, pages 296-301. EDA Consortium San Jose, CA, USA / ACM DL, 2013. URL: https://doi.org/10.7873/DATE.2013.073.
  30. Jan Gustafsson, Andreas Ermedahl, Christer Sandberg, and Björn Lisper. Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution. In Proceedings of the 27th IEEE Real-Time Systems Symposium, RTSS 2006, Rio de Janeiro, Brazil, pages 57-66, 2006. URL: https://doi.org/10.1109/RTSS.2006.12.
  31. Jan Gustafsson, Björn Lisper, Christer Sandberg, and Nerina Bermudo. A tool for automatic flow analysis of C-programs for WCET calculation. In Proceedings of the 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, WORDS 2003, Guadalajara, Mexico, pages 106-112, 2003. URL: https://doi.org/10.1109/WORDS.2003.1218072.
  32. Sebastian Hahn. On static execution-time analysis. PhD thesis, Saarland University, Saarbrücken, Germany, 2019. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/27440.
  33. Sebastian Hahn and Daniel Grund. Relational cache analysis for static timing analysis. In Proceedings of the 24th Euromicro Conference on Real-Time Systems, ECRTS 2012, Pisa, Italy, pages 102-111, 2012. URL: https://doi.org/10.1109/ECRTS.2012.14.
  34. Sebastian Hahn, Michael Jacobs, and Jan Reineke. Enabling compositionality for multicore timing analysis. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, pages 299-308, 2016. URL: https://doi.org/10.1145/2997465.2997471.
  35. Sebastian Hahn and Jan Reineke. Design and analysis of SIC: A provably timing-predictable pipelined processor core. In 2018 IEEE Real-Time Systems Symposium, RTSS 2018, Nashville, TN, USA, December 11-14, 2018, pages 469-481. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/RTSS.2018.00060.
  36. Sebastian Hahn and Jan Reineke. Design and analysis of SIC: a provably timing-predictable pipelined processor core. Real Time Syst., 56(2):207-245, 2020. URL: https://doi.org/10.1007/s11241-019-09341-z.
  37. Sebastian Hahn, Jan Reineke, and Reinhard Wilhelm. Towards compositionality in execution time analysis: definition and challenges. SIGBED Review, 12(1):28-36, 2015. URL: https://doi.org/10.1145/2752801.2752805.
  38. Damien Hardy, Benjamin Rouxel, and Isabelle Puaut. The Heptane static worst-case execution time estimation tool. In Jan Reineke, editor, 17th International Workshop on Worst-Case Execution Time Analysis, WCET 2017, June 27, 2017, Dubrovnik, Croatia, volume 57 of OASIcs, pages 8:1-8:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/OASIcs.WCET.2017.8.
  39. Christopher A. Healy, Robert D. Arnold, Frank Mueller, David B. Whalley, and Marion G. Harmon. Bounding pipeline and instruction cache performance. IEEE Trans. Computers, 48(1):53-70, 1999. URL: https://doi.org/10.1109/12.743411.
  40. Reinhold Heckmann, Marc Langenbach, Stephan Thesing, and Reinhard Wilhelm. The influence of processor architecture on the design and the results of WCET tools. Proceedings of the IEEE, 91(7):1038-1054, 2003. URL: https://doi.org/10.1109/JPROC.2003.814618.
  41. John L. Hennessy and David A. Patterson. Computer Architecture - A Quantitative Approach (5. ed.). Morgan Kaufmann, 2012. Google Scholar
  42. Julien Henry, Mihail Asavoae, David Monniaux, and Claire Maiza. How to compute worst-case execution time by optimization modulo theory and a clever encoding of program semantics. In Youtao Zhang and Prasad Kulkarni, editors, SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2014, LCTES '14, Edinburgh, United Kingdom - June 12 - 13, 2014, pages 43-52. ACM, 2014. URL: https://doi.org/10.1145/2597809.2597817.
  43. Michael Jacobs. Design and Implementation of WCET Analyses: Including a Case Study on Multi-Core Processors with Shared Buses. PhD thesis, Saarland University, 2021. URL: https://doi.org/10.22028/D291-34893.
  44. Michael Jacobs, Sebastian Hahn, and Sebastian Hack. WCET analysis for multi-core processors with shared buses and event-driven bus arbitration. In Proceedings of the 23nd International Conference on Real-Time Networks and Systems, RTNS 2015, Lille, France, 2015. Google Scholar
  45. Johannes Kinder, Florian Zuleger, and Helmut Veith. An abstract interpretation-based framework for control flow reconstruction from binaries. In Proceedings of the 10th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2009, Savannah, GA, USA, pages 214-228, 2009. URL: https://doi.org/10.1007/978-3-540-93900-9_19.
  46. Jens Knoop, Laura Kovács, and Jakob Zwirchmayr. Symbolic loop bound computation for WCET analysis. In Edmund M. Clarke, Irina B. Virbitskaite, and Andrei Voronkov, editors, Perspectives of Systems Informatics - 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers, volume 7162 of Lecture Notes in Computer Science, pages 227-242. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-29709-0_20.
  47. Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the Second IEEE / ACM International Symposium on Code Generation and Optimization, CGO 2004, San Jose, CA, USA, pages 75-88, 2004. URL: https://doi.org/10.1109/CGO.2004.1281665.
  48. Xianfeng Li, Abhik Roychoudhury, and Tulika Mitra. Modeling out-of-order processors for WCET analysis. Real-Time Systems, 34(3):195-227, 2006. URL: https://doi.org/10.1007/s11241-006-9205-5.
  49. Xianfeng Li, Liang Yun, Tulika Mitra, and Abhik Roychoudhury. Chronos: A timing analyzer for embedded software. Sci. Comput. Program., 69(1-3):56-67, 2007. URL: https://doi.org/10.1016/j.scico.2007.01.014.
  50. Yau-Tsun Steven Li and Sharad Malik. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, & Tools for Real-Time Systems, LCT-RTS 1995, La Jolla, California, pages 88-98, 1995. URL: https://doi.org/10.1145/216636.216666.
  51. Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-Mook Moon, and Chong-Sang Kim. An accurate worst case timing analysis for RISC processors. IEEE Trans. Software Eng., 21(7):593-604, 1995. URL: https://doi.org/10.1109/32.392980.
  52. Björn Lisper. SWEET - A tool for WCET flow analysis (extended abstract). In Tiziana Margaria and Bernhard Steffen, editors, Leveraging Applications of Formal Methods, Verification and Validation. Specialized Techniques and Applications - 6th International Symposium, ISoLA 2014, Imperial, Corfu, Greece, October 8-11, 2014, Proceedings, Part II, volume 8803 of Lecture Notes in Computer Science, pages 482-485. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45231-8_38.
  53. Thomas Lundqvist and Per Stenström. Timing anomalies in dynamically scheduled microprocessors. In Proceedings of the 20th IEEE Real-Time Systems Symposium, RTSS 1999, Phoenix, AZ, USA, pages 12-21, 1999. URL: https://doi.org/10.1109/REAL.1999.818824.
  54. Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. A survey on static cache analysis for real-time systems. Leibniz Transactions on Embedded Systems LITES, 3(1):05:1-05:48, 2016. URL: https://doi.org/10.4230/LITES-v003-i001-a005.
  55. Florian Martin, Martin Helmut Alt, Reinhard Wilhelm, and Christian Ferdinand. Analysis of loops. In Kai Koskimies, editor, Compiler Construction, 7th International Conference, CC'98, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'98, Lisbon, Portugal, March 28 - April 4, 1998, Proceedings, volume 1383 of Lecture Notes in Computer Science, pages 80-94. Springer, 1998. URL: https://doi.org/10.1007/BFb0026424.
  56. Laurent Mauborgne and Xavier Rival. Trace partitioning in abstract interpretation based static analyzers. In Proceedings of the 14th European Symposium on Programming, ESOP 2005, Edinburgh, UK, pages 5-20, 2005. URL: https://doi.org/10.1007/978-3-540-31987-0_2.
  57. Bernhard Meindl and Matthias Templ. Analysis of commercial and free and open source solvers for linear optimization problems. Technical report, Institut für Statistik und Wahrscheinlichkeitstheorie, Vienna University of Technology, 2012. Google Scholar
  58. Marianne De Michiel, Armelle Bonenfant, Hugues Cassé, and Pascal Sainrat. Static loop bound analysis of C programs based on flow analysis and abstract interpretation. In The Fourteenth IEEE Internationl Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008, Kaohisung, Taiwan, 25-27 August 2008, Proceedings, pages 161-166. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/RTCSA.2008.53.
  59. Vincent Mussot, Jordy Ruiz, Pascal Sotin, Marianne De Michiel, and Hugues Cassé. Expressing and exploiting conflicts over paths in WCET analysis. In Martin Schoeberl, editor, 16th International Workshop on Worst-Case Execution Time Analysis, WCET 2016, July 5, 2016, Toulouse, France, volume 55 of OASIcs, pages 3:1-3:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/OASIcs.WCET.2016.3.
  60. Peter P. Puschner, Daniel Prokesch, Benedikt Huber, Jens Knoop, Stefan Hepp, and Gernot Gebhard. The T-CREST approach of compiler and WCET-analysis integration. In 16th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, ISORC 2013, Paderborn, Germany, June 19-21, 2013, pages 1-8. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/ISORC.2013.6913220.
  61. Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Erwan Jahier, Nicolas Halbwachs, Fabienne Carrier, Mihail Asavoae, and Rémy Boutonnet. Improving WCET evaluation using linear relation analysis. Leibniz Trans. Embed. Syst., 6(1):02:1-02:28, 2019. URL: https://doi.org/10.4230/LITES-v006-i001-a002.
  62. Jan Reineke. The semantic foundations and a landscape of cache-persistence analyses. Leibniz Trans. Embed. Syst., 5(1):03:1-03:52, 2018. URL: https://doi.org/10.4230/LITES-v005-i001-a003.
  63. Jan Reineke, Daniel Grund, Christoph Berg, and Reinhard Wilhelm. Timing predictability of cache replacement policies. Real-Time Systems, 37(2):99-122, November 2007. URL: https://doi.org/10.1007/s11241-007-9032-3.
  64. Jan Reineke, Björn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anomalies. In Proceedings of the 6th International Workshop on Worst-Case Execution Time Analysis, WCET 2006, Dresden, Germany, 2006. URL: https://doi.org/10.4230/OASIcs.WCET.2006.671.
  65. Christine Rochange and Pascal Sainrat. A context-parameterized model for static analysis of execution times. Trans. High Perform. Embed. Archit. Compil., 2:222-241, 2009. URL: https://doi.org/10.1007/978-3-642-00904-4_12.
  66. Georg Sander. Graph layout through the VCG tool. In Roberto Tamassia and Ioannis G. Tollis, editors, Graph Drawing, pages 194-205, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg. Google Scholar
  67. Alexander Sepp, Bogdan Mihaila, and Axel Simon. Precise static analysis of binaries by extracting relational information. In Martin Pinzger, Denys Poshyvanyk, and Jim Buckley, editors, 18th Working Conference on Reverse Engineering, WCRE 2011, Limerick, Ireland, pages 357-366. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/WCRE.2011.50.
  68. Thomas Sewell, Felix Kam, and Gernot Heiser. Complete, high-assurance determination of loop bounds and infeasible paths for WCET analysis. In 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), Vienna, Austria, April 11-14, 2016, pages 185-195. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/RTAS.2016.7461326.
  69. Darshit Shah, Sebastian Hahn, and Jan Reineke. Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis. In Florian Brandner, editor, 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018), volume 63 of OpenAccess Series in Informatics (OASIcs), pages 7:1-7:11, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.WCET.2018.7.
  70. Micha Sharir and Amir Pnueli. Two approaches of interprocedural data flow analysis. In Steven S. Muchnick and Neil D. Jones, editors, Program flow analysis: theory and applications, chapter 7, pages 189-233. Prentice Hall, Englewood Cliffs, New Jersey, 1981. Google Scholar
  71. Tyler Sondag and Hridesh Rajan. A more precise abstract domain for multi-level caches for tighter WCET analysis. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, pages 395-404, 2010. URL: https://doi.org/10.1109/RTSS.2010.8.
  72. Ingmar Jendrik Stein. ILP-based Path Analysis on Abstract Pipeline State Graphs. PhD thesis, Saarland University, 2010. Google Scholar
  73. Gregory Stock, Sebastian Hahn, and Jan Reineke. Cache persistence analysis: Finally exact. In IEEE Real-Time Systems Symposium, RTSS 2019, Hong Kong, SAR, China, December 3-6, 2019, pages 481-494. IEEE, 2019. URL: https://doi.org/10.1109/RTSS46320.2019.00049.
  74. Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, and Ting Chen. Efficient detection and exploitation of infeasible paths for software timing analysis. In Ellen Sentovich, editor, Proceedings of the 43rd Design Automation Conference, DAC 2006, San Francisco, CA, USA, July 24-28, 2006, pages 358-363. ACM, 2006. URL: https://doi.org/10.1145/1146909.1147002.
  75. Henrik Theiling. Extracting safe and precise control flow from binaries. In 7th International Workshop on Real-Time Computing and Applications Symposium (RTCSA 2000), 12-14 December 2000, Cheju Island, South Korea, pages 23-30. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/RTCSA.2000.896367.
  76. Henrik Theiling. Control Flow Graphs for Real-Time System Analysis - Reconstruction from Binary Executables and Usage in ILP-based Path Analysis. PhD thesis, Saarland University, 2002. Google Scholar
  77. Henrik Theiling and Christian Ferdinand. Combining abstract interpretation and ILP for microarchitecture modelling and program path analysis. In Proceedings of the 19th IEEE Real-Time Systems Symposium, Madrid, Spain, December 2-4, 1998, pages 144-153. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/REAL.1998.739739.
  78. Stephan Thesing. Safe and Precise WCET Determination by Abstract Interpretation of Pipeline Models. PhD thesis, Saarland University, 2004. Google Scholar
  79. Valentin Touzeau, Claire Maïza, David Monniaux, and Jan Reineke. Ascertaining uncertainty for efficient exact cache analysis. In Rupak Majumdar and Viktor Kuncak, editors, Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part II, volume 10427 of Lecture Notes in Computer Science, pages 22-40. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63390-9_2.
  80. Valentin Touzeau, Claire Maïza, David Monniaux, and Jan Reineke. Fast and exact analysis for LRU caches. Proc. ACM Program. Lang., 3(POPL):54:1-54:29, January 2019. URL: https://doi.org/10.1145/3290367.
  81. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 7(3):36:1-36:53, 2008. URL: https://doi.org/10.1145/1347375.1347389.
  82. Stephan Wilhelm. Symbolic representations in WCET analysis. PhD thesis, Saarland University, 2012. URL: http://scidok.sulb.uni-saarland.de/volltexte/2012/4914/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact