License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1194/
Go to the corresponding OASIcs Volume Portal

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:
ermedahl.1194.pdf (0.2 MB)

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 =		{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
Collection: 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 | Privacy Published by LZI