Search Results

Documents authored by Holsti, Niklas

Document
DOI: 10.4230/OASIcs.WCET.2015.85
Analysing Switch-Case Code with Abstract Execution

Authors: Niklas Holsti, Jan Gustafsson, Linus Källberg, and Björn Lisper

Published in: OASIcs, Volume 47, 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)

Abstract
Constructing the control-flow graph (CFG) of machine code is made difficult by dynamic transfers of control (DTC), where the address of the next instruction is computed at run-time. Switchcase statements make compilers generate a large variety of machine-code forms with DTC. Two analysis approaches are commonly used: pattern-matching methods identify predefined instruction patterns to extract the target addresses, while analytical methods try to compute the set of target addresses using a general value-analysis. We tested the abstract execution method of the SWEET tool as a value analysis for switch-case code. SWEET is here used as a plugin to the Bound-T tool: thus our work can also be seen as an experiment in modular tool design, where a general value-analysis tool is used to aid the CFG construction in a WCET analysis tool. We find that the abstract-execution analysis works at least as well as the switch-case analyses in Bound-T itself, which are mostly based on pattern-matching. However, there are still some weaknesses: the abstract domains available in SWEET are not well suited to representing sets of DTC target addresses, which are small but sparse and irregular. Also, in some cases the abstract-execution analysis fails because the used domain is not relational, that is, does not model arithmetic relationships between the values of different variables. Future work will be directed towards the design of abstract domains eliminating these weaknesses.
Cite as

Niklas Holsti, Jan Gustafsson, Linus Källberg, and Björn Lisper. Analysing Switch-Case Code with Abstract Execution. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 85-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{holsti_et_al:OASIcs.WCET.2015.85,
  author =	{Holsti, Niklas and Gustafsson, Jan and K\"{a}llberg, Linus and Lisper, Bj\"{o}rn},
  title =	{{Analysing Switch-Case Code with Abstract Execution}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{85--94},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.85},
  URN =		{urn:nbn:de:0030-drops-52598},
  doi =		{10.4230/OASIcs.WCET.2015.85},
  annote =	{Keywords: ynamic control flow, indexed branch, machine-code analysis, WCET analysis}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.WCET.2009
OASIcs, Volume 10, WCET'09, Complete Volume

Authors: Niklas Holsti

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
OASIcs, Volume 10, WCET'09, Complete Volume
Cite as

9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{holsti:OASIcs.WCET.2009,
  title =	{{OASIcs, Volume 10, WCET'09, Complete Volume}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009},
  URN =		{urn:nbn:de:0030-drops-35729},
  doi =		{10.4230/OASIcs.WCET.2009},
  annote =	{Keywords: Performance of Systems, Software/Program Verification}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2009.2295
WCET 2009 -- Preface to 9th International Workshop on Worst-Case Execution Time Analysis

Authors: Niklas Holsti

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
On June 30, 2009, thirty-five people from nine countries and three continents met in Trinity College, Dublin, to hold the 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09, http://www.artist-embedded.org/artist/WCET-2009.html). The workshop was organised as a satellite event of the 21st Euromicro Conference on Real-Time Systems (ECRTS'09, http://ecrts09.dsg.cs.tcd.ie). The final proceedings here presented contain the workshop papers as updated in response to the discussion at the workshop, the abstract of the invited talk by prof. Petru Eles, and a summary of the panel discussion that concluded the workshop. The slide presentations can be retrieved from the workshop web-site referenced above.
Cite as

9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. i-iv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{holsti:OASIcs.WCET.2009.2295,
  author =	{Holsti, Niklas},
  title =	{{WCET 2009 -- Preface to 9th International Workshop on Worst-Case Execution Time Analysis}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{i--iv},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2295},
  URN =		{urn:nbn:de:0030-drops-22958},
  doi =		{10.4230/OASIcs.WCET.2009.2295},
  annote =	{Keywords: Worst-case execution time, WCET analysis, real-time systems, scheduling}
}
Document
DOI: 10.4230/OASIcs.WCET.2009.2278
Teaching WCET Analysis in Academia and Industry: A Panel Discussion

Authors: Niklas Holsti, Guillem Bernat, Christian Ferdinand, Peter Puschner, and Reinhard Wilhelm

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
The last item on the programme of the WCET'09 workshop was a panel discussion on "Teaching WCET analysis in academia and industry". The panelists presented three position statements to initiate a general discussion of the subject. This summary contains the panelists' position statements and notes of the panel discussion.
Cite as

Niklas Holsti, Guillem Bernat, Christian Ferdinand, Peter Puschner, and Reinhard Wilhelm. Teaching WCET Analysis in Academia and Industry: A Panel Discussion. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{holsti_et_al:OASIcs.WCET.2009.2278,
  author =	{Holsti, Niklas and Bernat, Guillem and Ferdinand, Christian and Puschner, Peter and Wilhelm, Reinhard},
  title =	{{Teaching WCET Analysis in Academia and Industry: A Panel Discussion}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2278},
  URN =		{urn:nbn:de:0030-drops-22780},
  doi =		{10.4230/OASIcs.WCET.2009.2278},
  annote =	{Keywords: WCET analysis, teaching, courses}
}
Document
DOI: 10.4230/OASIcs.WCET.2008.1663
WCET 2008 -- Report from the Tool Challenge 2008 -- 8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis

Authors: Niklas Holsti, Jan Gustafsson, Guillem Bernat, Clément Ballabriga, Armelle Bonenfant, Roman Bourgade, Hugues Cassé, Daniel Cordes, Albrecht Kadlec, Raimund Kirner, Jens Knoop, Paul Lokuciejewski, Nicholas Merriam, Marianne de Michiel, Adrian Prantl, Bernhard Rieder, Christine Rochange, Pascal Sainrat, and Markus Schordan

Published in: OASIcs, Volume 8, 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08) (2008)

Abstract
Following the successful WCET Tool Challenge in 2006, the second event in this series was organized in 2008, again with support from the ARTIST2 Network of Excellence. The WCET Tool Challenge 2008 (WCC'08) provides benchmark programs and poses a number of "analysis problems" about the dynamic, run-time properties of these programs. The participants are challenged to solve these problems with their program analysis tools. Two kinds of problems are defined: WCET problems, which ask for bounds on the execution time of chosen parts (subprograms) of the benchmarks, under given constraints on input data; and flow-analysis problems, which ask for bounds on the number of times certain parts of the benchmark can be executed, again under some constraints. We describe the organization of WCC'08, the benchmark programs, the participating tools, and the general results, successes, and failures. Most participants found WCC'08 to be a useful test of their tools. Unlike the 2006 Challenge, the WCC'08 participants include several tools for the same target (ARM7, LPC2138), and tools that combine measurements and static analysis, as well as pure static-analysis tools.
Cite as

Niklas Holsti, Jan Gustafsson, Guillem Bernat, Clément Ballabriga, Armelle Bonenfant, Roman Bourgade, Hugues Cassé, Daniel Cordes, Albrecht Kadlec, Raimund Kirner, Jens Knoop, Paul Lokuciejewski, Nicholas Merriam, Marianne de Michiel, Adrian Prantl, Bernhard Rieder, Christine Rochange, Pascal Sainrat, and Markus Schordan. WCET 2008 -- Report from the Tool Challenge 2008 -- 8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis. In 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08). Open Access Series in Informatics (OASIcs), Volume 8, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{holsti_et_al:OASIcs.WCET.2008.1663,
  author =	{Holsti, Niklas and Gustafsson, Jan and Bernat, Guillem and Ballabriga, Cl\'{e}ment and Bonenfant, Armelle and Bourgade, Roman and Cass\'{e}, Hugues and Cordes, Daniel and Kadlec, Albrecht and Kirner, Raimund and Knoop, Jens and Lokuciejewski, Paul and Merriam, Nicholas and de Michiel, Marianne and Prantl, Adrian and Rieder, Bernhard and Rochange, Christine and Sainrat, Pascal and Schordan, Markus},
  title =	{{WCET 2008 -- Report from the Tool Challenge 2008 -- 8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  pages =	{1--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Kirner, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2008.1663},
  URN =		{urn:nbn:de:0030-drops-16637},
  doi =		{10.4230/OASIcs.WCET.2008.1663},
  annote =	{Keywords: WCET analysis, benchmark}
}
Document
DOI: 10.4230/OASIcs.WCET.2008.1660
Computing time as a program variable: a way around infeasible paths

Authors: Niklas Holsti

Published in: OASIcs, Volume 8, 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08) (2008)

Abstract
Conditional branches connect the values of program variables with the execution paths and thus with the execution times, including the worst-case execution time (WCET). Flow analysis aims to discover this connection and represent it as loop bounds and other path constraints. Usually, a specific analysis of the dependencies between branch conditions and assign­ments to variables creates some representation of the feasible paths, for example as IPET execution-count constraints, from which a WCET bound is calculated. This paper explores another approach that uses a more direct connection between variable values and execution time. The execution time is modeled as a program variable. An analysis of the dependencies between variables, including the execution-time variable, gives a WCET bound that excludes many infeasible paths. Examples show that the approach often works, in principle. It remains to be seen if it is scalable to real programs.
Cite as

Niklas Holsti. Computing time as a program variable: a way around infeasible paths. In 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08). Open Access Series in Informatics (OASIcs), Volume 8, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{holsti:OASIcs.WCET.2008.1660,
  author =	{Holsti, Niklas},
  title =	{{Computing time as a program variable: a way around infeasible paths}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Kirner, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2008.1660},
  URN =		{urn:nbn:de:0030-drops-16608},
  doi =		{10.4230/OASIcs.WCET.2008.1660},
  annote =	{Keywords: WCET, flow analysis, infeasible paths, dependency analysis}
}
Document
DOI: 10.4230/OASIcs.WCET.2007.1195
Analysing Switch-Case Tables by Partial Evaluation

Authors: Niklas Holsti

Published in: OASIcs, Volume 6, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07) (2007)

Abstract
Tracing the flow of control in code generated from switch-case statements is difficult for static program analysis tools when the code contains jumps to dynamically computed target addresses. Analytical methods such as abstract interpretation using integer intervals can work for some forms of switchcase code, for example a jump via a table of addresses indexed 1 .. n, but fail when the target compiler encodes the switch-case structure in a ROM table with a complex format and uses a library routine to interpret the table at runtime. This paper shows how to extract the flow of control from such switch-case tables by partial evaluation of the table-interpreting routine. The resulting control-flow graph allows accurate analysis of the execution time and the logical conditions for reaching each case in the switch-case statement. The method is implemented in Tidorum's Bound-T tool for worstcase executiontime analysis. The implementation builds on some basic BoundT features for modeling program states in the flowgraph and propagating constant values through the graph.
Cite as

Niklas Holsti. Analysing Switch-Case Tables by Partial Evaluation. In 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07). Open Access Series in Informatics (OASIcs), Volume 6, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{holsti:OASIcs.WCET.2007.1195,
  author =	{Holsti, Niklas},
  title =	{{Analysing Switch-Case Tables by Partial Evaluation}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  pages =	{1--8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Rochange, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2007.1195},
  URN =		{urn:nbn:de:0030-drops-11954},
  doi =		{10.4230/OASIcs.WCET.2007.1195},
  annote =	{Keywords: WCET, switch-case, partial evaluation}
}
Document
DOI: 10.4230/OASIcs.WCET.2005.812
Using a WCET Analysis Tool in Real-Time Systems Education

Authors: Samuel Petersson, Andreas Ermedahl, Anders Pettersson, Daniel Sundmark, and Niklas Holsti

Published in: OASIcs, Volume 1, 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05) (2007)

Abstract
To reach a more widespread use, WCET analysis tools need to be a standard part in the education of embedded systems developers. Many real-time courses in academia use Lego Mindstorms, an off-the-shelf kit of Lego bricks for building and controlling small prototype robots. We describe work on porting the Bound-T WCET analysis tool to the Lego Mindstorms microprocessor; the Renesas H8/3292. We believe that this work will make students, and indirectly the industry of tomorrow, aware of the benefits of WCET analysis tools. We also present the real-time laboratory framework in which this WCET analysis tool will be used. The framework has been developed with schedulability and timing predictability in mind, and is already used in a number of real-time courses given at M¨alardalen University in Sweden. The developed WCET tool and the real-time laboratory framework will be freely available for academic use.
Cite as

Samuel Petersson, Andreas Ermedahl, Anders Pettersson, Daniel Sundmark, and Niklas Holsti. Using a WCET Analysis Tool in Real-Time Systems Education. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 29-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{petersson_et_al:OASIcs.WCET.2005.812,
  author =	{Petersson, Samuel and Ermedahl, Andreas and Pettersson, Anders and Sundmark, Daniel and Holsti, Niklas},
  title =	{{Using a WCET Analysis Tool in Real-Time Systems Education}},
  booktitle =	{5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
  pages =	{29--32},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-24-8},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{1},
  editor =	{Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.812},
  URN =		{urn:nbn:de:0030-drops-8126},
  doi =		{10.4230/OASIcs.WCET.2005.812},
  annote =	{Keywords: }
}
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 Imprint Privacy Contact