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

Holsti, Niklas

Analysing Switch-Case Tables by Partial Evaluation

pdf-format:
holsti.1195.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{holsti:OASIcs:2007:1195,
  author =	{Niklas Holsti},
  title =	{{Analysing Switch-Case Tables by Partial Evaluation}},
  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/1195},
  URN =		{urn:nbn:de:0030-drops-11954},
  doi =		{10.4230/OASIcs.WCET.2007.1195},
  annote =	{Keywords: WCET, switch-case, partial evaluation}
}

Keywords: WCET, switch-case, partial evaluation
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