You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact webmaster@ide.mdh.se

Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation

Authors:


Publication Type:

Doctoral Thesis

Publisher:

Department of Computer Engineering, Mälardalen University, Box 883, S-721 23 Västerås, Sweden, and Department of Computer Systems, Information Technology, Uppsala University, Box 325, S-751 05 Uppsala, Sweden


Abstract

As a result of the industrial deployment of real-time systems, there is an increasing demand for methods to perform safe and tight calculation of the worst case execution time (WCET) of programs. The WCET is a necessary prerequisite for guaranteeing correct timing behaviour of real-time systems. WCET calculation means to find the path, often among a huge number of paths, that takes the longest time to execute. The calculation is based on path information for the program, such as the maximum number of iterations in loops and identification of paths that are never executed. In most existing WCET analysis methods, this information is given as manual annotations by the programmer.In this thesis we present a method which automatically calculates path information for object-oriented real-time programs by static analysis. Thus, the method can be used in automating the WCET analysis, thereby relieving the programmer from the tedious and error-prone manual annotation work.The method, which is based on abstract interpretation, generates safe but not necessarily exact path information. A trade-off between quality and calculation cost has to be made, since finding the exact information is a complex, often intractable problem for non-trivial programs.We show how the general abstract interpretation theory can be used, in a structured way, to approximate the semantics of an imperative or object-oriented programming language.We have chosen to analyze RealTimeTalk (RTT), an object-oriented language based on Smalltalk, and have developed a prototype tool which implements our analysis for a subset of the language. We show that the tool is capable of analyzing programs with a complexity which would make manual annotation of the program all but trivial.

Bibtex

@phdthesis{Gustafsson231,
author = {Jan Gustafsson},
title = {Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation},
number = {DoCS 00/11},
month = {May},
year = {2000},
school = {Department of Computer Engineering, M{\"a}lardalen University, Box 883, S-721 23 V{\"a}ster{\aa}s, Sweden, and Department of Computer Systems, Information Technology, Uppsala University, Box 325, S-751 05 Uppsala, Sweden },
url = {http://www.es.mdu.se/publications/231-}
}