License
when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2007.1194
URN: urn:nbn:de:0030-drops-11946
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1194/

Ermedahl, Andreas ; Sandberg, Christer ; Gustafsson, Jan ; Bygde, Stefan ; Lisper, Björn

Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

pdf-format:
Dokument 1.pdf (166 KB)


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. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea is to bound the number of different states in the loop which can influence the exit conditions. Given that the loop terminates, this number provides an upper loop bound. An algorithm based on the approach has been implemented in our WCET analysis tool SWEET. We evaluate the algorithm on a number of standard WCET benchmarks, giving evidence that it is capable to derive valid bounds for many types of loops.

BibTeX - Entry

@InProceedings{ermedahl_et_al:OASIcs:2007:1194,
  author =	{Andreas Ermedahl and Christer Sandberg and Jan Gustafsson and Stefan Bygde and Bj{\"o}rn Lisper},
  title =	{{Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Christine Rochange},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1194},
  URN =		{urn:nbn:de:0030-drops-11946},
  doi =		{http://dx.doi.org/10.4230/OASIcs.WCET.2007.1194},
  annote =	{Keywords: WCET analysis, loop-bound analysis, program slicing, abstract interpretation, invariant analysis}
}

Keywords: WCET analysis, loop-bound analysis, program slicing, abstract interpretation, invariant analysis
Seminar: 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)
Issue date: 2007
Date of publication: 13.11.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI