Scope-tree: a program representation for symbolic worst-case execution time analysis

Abstract

Most WCET analysis techniques only provide an upper bound on the worst case execution time as a constant value. However, it often appears that the execution time of a piece of code depends on the sizes or values of its input data or local parameters. The WCET of a function call may vary depending on the caller and parameters. We propose an approach to express the WCET of a program or sub-program as a symbolic expression. The obtained parametric WCET can then be later evaluated using the knowledge of input data and system configuration parameters. In this paper we present the concept of scope-tree as a generalisation of the traditional syntax tree representation of programs. In addition to their WCET, scopes are associated with an expression stating their maximum execution frequency and some variable declarations. These variables may be used for example to express data-dependent number of iterations or non-rectangular loops. We also present how the scope tree may be used to express inter-scope relations (e.g. mutually exclusive paths, loop down-sampling). Finally, this paper presents the use of scope-trees and scope-tree modifications on an example.