DROPS

Document

DOI: 10.4230/OASIcs.WCET.2006.667

Algorithms for Infeasible Path Calculation

Authors: Jan Gustaffson, Andreas Ermedahl, and Björn Lisper

Published in: OASIcs, Volume 4, 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) (2006)

Abstract

Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. One key component in static WCET analysis is to derive flow information, such as loop bounds and infeasible paths for the analysed program. Such flow information can be provided as either as annotations by the user, can be automatically calculated by a flow analysis, or by a combination of both. To make the analysis as simple, automatic and safe as possible, this flow information should be calculated automatically with no or very limited user interaction. In this paper we present three novel algorithms to calculate infeasible paths. The algorithms are all designed to be simple and efficient, both in terms of generated flow facts and in analysis running time. The algorithms have been implemented and tested for a set of WCET benchmarks programs.

Cite as

Jan Gustaffson, Andreas Ermedahl, and Björn Lisper. Algorithms for Infeasible Path Calculation. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gustaffson_et_al:OASIcs.WCET.2006.667,
  author =	{Gustaffson, Jan and Ermedahl, Andreas and Lisper, Bj\"{o}rn},
  title =	{{Algorithms for Infeasible Path Calculation}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Mueller, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2006.667},
  URN =		{urn:nbn:de:0030-drops-6677},
  doi =		{10.4230/OASIcs.WCET.2006.667},
  annote =	{Keywords: Worst case execution time, real-time, control flow analysis, abstract interpretation, infeasible paths}
}

Search Results

Documents authored by Gustaffson, Jan

Algorithms for Infeasible Path Calculation

Abstract

Cite as

Thanks for your feedback!

Could not send message