uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Analyzing execution-time of object-oriented programs using abstract interpretation
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2000 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

As a result of the industrial deployment of real-time systems, there is an increasing demandfor methods to perform safe and tight calculation of the worst case execution time (WCET) ofprograms. The WCET is a necessary prerequisite for guaranteeing correct timing behaviour ofreal-time systems. WCET calculation means to find the path, often among a huge number ofpaths, that takes the longest time to execute. The calculation is based on path information for theprogram, such as the maximum number of iterations in loops and identification of paths that arenever 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 manualannotation work.

The method, which is based on abstract interpretation, generates safe but not necessarily exactpath information. A trade-off between quality and calculation cost has to be made, since findingthe 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, toapproximate 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 makemanual annotation of the program all but trivial.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2000. , 248 p.
DoCS, ISSN 0283-0574 ; 115
National Category
Computer and Information Science
Research subject
Computer Systems
URN: urn:nbn:se:uu:diva-1174ISBN: 99-3237815-1OAI: oai:DiVA.org:uu-1174DiVA: diva2:160726
Public defence
2000-05-08, Room IX, University Building, Uppsala, Uppsala, 13:00
Available from: 2000-04-17 Created: 2000-04-17 Last updated: 2011-02-18Bibliographically approved

Open Access in DiVA

No full text

By organisation
Division of Computer SystemsComputer Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 537 hits
ReferencesLink to record
Permanent link

Direct link