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.2010.77
URN: urn:nbn:de:0030-drops-28274
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2827/
Go to the corresponding OASIcs Volume Portal

Huber, Benedikt ; Puschner, Peter

A Code Policy Guaranteeing Fully Automated Path Analysis

pdf-format:
9.pdf (2 MB)

Abstract

Calculating the worst-case execution time (WCET) of real-time tasks is still a tedious job. Programmers are required to provide additional information on the program flow, analyzing subtle, context dependent loop bounds manually. In this paper, we propose to restrict written and generated code to the class of programs with input-data independent loop counters. The proposed policy builds on the ideas of single-path code, but only requires partial input-data independence. It is always possible to find precise loop bounds for these programs, using an efficient variant of abstract execution. The systematic construction of tasks following the policy is facilitated by embedding knowledge on input-data dependence in function interfaces and types. Several algorithms and benchmarks are analyzed to show that this restriction is indeed a good candidate for removing the need for manual annotations.

BibTeX - Entry

@InProceedings{huber_et_al:OASIcs:2010:2827,
  author =	{Benedikt Huber and Peter Puschner},
  title =	{{A Code Policy Guaranteeing Fully Automated Path Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{77--88},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Bj{\"o}rn Lisper},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2827},
  URN =		{urn:nbn:de:0030-drops-28274},
  doi =		{10.4230/OASIcs.WCET.2010.77},
  note =	{The printed version of the WCET'10 proceedings are published by OCG (www.ocg.at) - ISBN 978-3-85403-268-7},
  annote =	{Keywords: WCET analysis, path analysis, single-path code, SSA form}
}

Keywords: WCET analysis, path analysis, single-path code, SSA form
Collection: 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)
Issue Date: 2010
Date of publication: 26.11.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI