Abstract Worst-case execution time (WCET) analysis is concerned with computing a precise-as-possible bound for the maximum time the execution of a program can take. This information is indispensable for developing safety-critical real-time systems, e. g., in the avionics and automotive fields. Starting with the initial works of Chen, Mok, Puschner, Shaw, and others in the mid and late 1980s, WCET analysis turned into a well-established and vibrant field of research and development in academia and industry. The increasing number and diversity of hardware and software platforms and the ongoing rapid technological advancement became drivers for the development of a wide array of distinct methods and tools for WCET analysis. The precision, generality, and efficiency of these methods and tools depend much on the expressiveness and usability of the annotation languages that are used to describe feasible and infeasible program paths. In this article we survey the annotation languages which we consider formative for the field. By investigating and comparing their individual strengths and limitations with respect to a set of pivotal criteria, we provide a coherent overview of the state of the art. Identifying open issues, we encourage further research. This way, our approach is orthogonal and complementary to a recent approach of Wilhelm et al. who provide a thorough survey of WCET analysis methods and tools that have been developed and used in academia and industry. Keywords Worst-case execution time (WCET) analysis · Annotation languages · Path-oriented, constraint-oriented, and hierarchy-oriented WCET annotation languages · WCET annotation language challenge Computing the time that the execution of a program can take in the worst case is challenging. It requires to cope with analysis problems that are computationally intractable or undecidable. Tools and methods for worst-case execution time analysis (WCET) thus usually content themselves to computing an upper bound of the actual WCET. The precision, generality, and efficiency of these tools and methods depend much on the accurate description and identification of feasible and infeasible program paths. A program path is feasible, 123 412 R. Kirner et al. if there is an actual program execution taking this path; it is infeasible otherwise. In practice, this information is computed by fully automatic program analyses, where possible; it is manually provided by application programmers otherwise. In both cases this requires a dedicated language in order to annotate this information and to pass it on to a subsequent WCET analysis. Such a language is commonly called an annotation language. Over the past two decades, an array of conceptually quite diverse annotation languages has been proposed to support the needs of different WCET analysis methods and tools. In this article, we present a systematic and comprehensive comparison of the various approaches for WCET annotation languages. This acts on our suggestion of the WCET annotation language challenge [32] complementing the WCET tool challenge [17, 22, 62] , and complements the recent survey of WCET analysis methods and tools by Wilhelm et al. [66]. Focusing on annotation languages for WCET analysis, we take a different angle, as Wilhelm et al. to add to characterize the state of the art in the field of WCET analysis. We believe that this provides a new stimulus for further research and development on WCET analysis methods and tools in general and annotation languages in particular. It is worth noting that there are also annotation languages for modeling real-time properties at system level like response time, throughput, or jitter. Examples of such system modeling languages are the modeling and analysis suite for real-time applications called MAST [23] and the UML Profile for Modeling and Analysis of Real-time and Embedded systems (UML-MARTE) [49] . Such real-time modeling languages at system level, however, are beyond the scope of languages considered in this article, though, for example, UML-MARTE could be extended by user-defined properties to host annotation concepts specifically for WCET analysis. The contribution of this article is thus twofold: first, to survey the annotation languages for WCET analysis which have been influential and formative for the field. Second, to identify open issues for further research which we consider essential for its further development and advancement. To this end we introduce a set of criteria that are pivotal for the suitability and usefulness of an annotation language. This leads us to a clustering of the various annotation languages and allows us to investigate and discuss their relative strengths and limitations. Based on these findings we suggest open issues for further research towards novel, easy to use, and expressive annotation languages, which we believe will support the further advancement of methods and tools for WCET analysis. In the long run, this can also be seen a step towards a universal WCET annotation language for a wide range of WCET analysis tools. This would especially enhance the interoperability of different supportive program analysis tools for WCET analysis for their mutual benefit. WCET annotation languages and WCET calculation methods are closely tied and cannot meaningfully be considered in complete isolation. We thus provide a brief summary of the fundamental WCET calculation methods and the fundamental kinds of flow information which are expressed by means of annotation languages in Sects. 2 and 3, respectively. This will set up the scene for our investigation and comparison of WCET annotation languages. Figure 1 summarizes the annotation languages we consider, grouped with respect to the WCET calculation method the WCET analysis tools using them are based on. This illustrates the close ties between WCET calculation methods and WCET annotation languages. WCET calculation: fundamental methods The WCET of a program can be calculated for the whole program at once. We call this global WCET calculation. Alternatively, the WCET can be calculated in a hierarchical bottom-up fashion. We call this scoped WCET calculation. Some of the WCET calculation techniques are inherently scoped methods, e. g., timing schema. But also WCET analysis performed intra-procedurally instead of inter-procedurally is a form of scoped WCET calculation. It is worth noting that scoped WCET calculation methods are only compatible with flow information that addresses properties within the same scope, i. e., with flow information that only addresses program parts within the same scope. The degree to which scoped WCET calculation is used by a concrete WCET analysis tool is thus formative for the WCET annotation language to be used with this tool. The timing schema approach is an efficient WCET calculation method that is also simple to implement [52, 54, 59] . Essentially, the timing schema consists of hierarchical WCET calculation rules for each node of the syntax tree representing elementary or composed statements. If T (A) denotes the local WCET bound of a node A, the local WCET of the sequential composition A; B of two nodes A and B is computed as T (A) + T (B). Analogously, the local WCET of a conditional statement if A then B else C fi; is computed as T (A)+max (T (B), T (C)) and the local WCET bound of a loop while A do B od; with at most LB iterations is computed as Fig. 1 Formative WCET annotation languages (note: the gray line indicates that the WCET calculation tool using TAL is hybrid, enjoying characteristics of hierarchy-oriented approaches as well as of unorthodox other ones). The various language aspects compared and discussed are listed systematically in Table 1 best-case execution time. Its computational complexity is linear with the program size. It thus scales well and can efficiently be applied to large programs. The efficiency of this approach comes at the price of lacking support for global flow information, i. e., flow information that describes relations across the boundaries on individual timing schema rules. This is because the timing schema approach represents a fine-grained scoped WCET calculation technique that uses the syntactical elements of control-flow constructs as scopes. For some programs, this can result in a much higher WCET overestimation compared with other WCET calculation techniques. Further, the timing schema approach does not provide an interface to model the complex execution states of modern processors that have features like pipelines and caches. This imposes an inherently high pessimism on the WCET bound for such processors. A refinement of the timing schema approach towards a more precise handling of nested loops has been presented by Colin and Puaut [10], cf. Sect. 6.6. As shown in Fig. 1 , all approaches that are based on a hierarchy-oriented annotation language use the timing schema for the WCET calculation. The explicit path-enumeration technique (EPET) searches the longest execution path by enumerating and comparing each program path. At a first glance, this seems a rather naive approach, and in fact, it does not scale (well) in the case of global WCET calculation. However, this approach has its merits when using scoped WCET calculation because the scoping allows to restrict the number of paths within each cluster such that their enumeration becomes feasible. For example, some path-oriented WCET calculation techniques use loop scopes as scopes for the analysis [18, 58] Static WCET calculation based on EPET is well suited to analyze the effects of pipelines. It allows to model the impact of the pipeline on an instruction sequence longer than just basic blocks, and thus increases the precision of the WCET bound. However, EPET itself is inappropriate to take rather global timing effects into account, like cache behavior. Thus, the cache analysis has to be done in a separate step prior to the EPET step. The separate analysis of cache and pipeline effects, however, can be unsound for processors showing timing anomalies [34, 44] . For measurement-based timing analysis using EPET a scoping is used to define the length of the paths for which the timing is obtained by execution-time measurements. Note that measurement-based timing analysis is a hybrid approach that uses execution time measurements as well as program analysis. The scoping used in measurement-based timing analysis can be of quite different granularity. For example, the pWCET tool of Bernat et al. [4] uses relatively fine-grained scoping, down to the basic-block level. In contrast, the philosophy of the MTime tool is to use a relatively coarse-grained scoping to reduce measurement error [67] . MTime is looking for a tradeoff between the maximum code length covered by sub-paths and the number of sub-paths to be measured. As shown in Fig. 1 , all approaches that are based on a path-oriented annotation language use EPET for the WCET calculation. The implicit path enumeration technique (IPET) has been pioneered by Li and Malik [42], as well as by Puschner and Schedl [55]. In contrast to path-based WCET calculation where paths are explicitly enumerated, IPET performs an implicit longest path search. The basic idea is to model the control flow of the program with constraints. To reduce the complexity, typically only linear constraints are used, i. e., the program is represented as an integer linear program (ILP). Subsequent to this basic modeling, supplemental flow information is often included smoothly in terms of additional constraints of the ILP problem. The finally formulated ILP problem is passed to an ILP solver that computes the desired WCET bound. Due to the broad availability of commercial and open-source ILP solvers, such ILP problems can be solved conveniently. As the IPET approach requires to solve a set of constraints describing the program behavior, it is per se a global WCET calculation method. It is also possible to use IPET as a scoped WCET calculation technique, as e. g. done by Ermedahl et al. [14] . The IPET-based WCET calculation is currently the most popular WCET calculation technique. It allows to directly use rather flexible flow information like linear flow constraints. Linear flow constraints are supported by so many annotation languages such that we describe them in more detail in Sect. 4. As shown in Fig. 1 , all approaches that are based on a constraint-oriented annotation language use IPET for the WCET calculation. Hierarchy, path, and constraint-oriented WCET calculation methods are currently most often used by WCET analysis tools. However, there are further approaches using different methods. For example, the WCET analysis method using the TAL annotation language uses the timing schema approach in combination with freely programmable algorithms. It is thus not a pure hierarchy-oriented approach, but a hybrid one. In Sect. 8 we consider methods falling in this group together with their annotation languages in more detail. We now continue with recalling the fundamental kinds of flow information. Flow information describes aspects of the dynamic program behavior that are relevant for WCET computation. It is expressed by means of WCET annotation languages. In the following we summarize the fundamental kinds of flow information, distinguishing static and dynamic information. The abstract syntax tree (AST) is a concise representation of a program which is stripped from information that is unnecessary for its compilation [2] . Primarily, the AST describes the syntactical structure of the program. Implicitly, it also describes its control flow. The control flow graph (CFG) is an explicit representation of a program's control flow [19] . Since branching constraints obeyed by actual program executions are not taken into account, it describes the static control flow. The nodes of the CFG represent the statements of the program, and the edges denote where execution might continue after executing a statement. Statements can be combined to basic blocks. A basic block is a sequence of maximum length of statements which can only be entered at the very first statement and left after the last one. A CFG can be assumed to have a unique start node representing the very first statement and an end node representing the last statement. The static control flow is then given by the set of paths leading from the start node to the end node. Programs with functions or procedures are represented by a flow graph system, where each Beyond loop bounds 415 function and procedure is represented by an ordinary CFG. An interprocedural control flow graph or super control flow graph represents the control flow by function calls and returns explicitly by splitting each call site into a new call and return node, and introducing a call and a return edge connecting the call node with the start node of the called procedure or function and its end node with the return node of the corresponding call site [47] . This way the CFGs of the flow graph system are merged to a single graph. The set of paths in the interprocedural control flow graph from the start node to the end node of the program that respect the call/return-behavior of procedure and function calls (also known as interprocedurally valid paths [60] ) denote the static control flow of a program with procedures and functions. Like for the AST, all branches are non-deterministically interpreted in a CFG and its interprocedural extensions in order to avoid undecidability issues. Hence, the static control flow of a program describes a superset of the program paths, for which there is an actual program execution, i. e., it describes a superset of the set of feasible program paths [5] . Another representation which is often used to describe the control flow induced by procedure and function calls is the call graph of a program [47] . A call graph contains a node for each procedure and function of a program. A directed edge leads from node m to node n in the call graph, if the procedure or function represented by m contains a call for the procedure or function represented by n. The call graph together with the flow graph system of a program can also be used to describe its static control flow. The dynamic control flow constrains the static control flow towards a more precise approximation of the set of feasible program paths. Typically, this is achieved by means of a control flow analysis, which conceptually can be thought of identifying a subset of the set of infeasible program paths. The precision of the approximation depends thus on the ability of the control flow analysis to identify infeasible program paths. To this end the control flow analysis can be guided by flow information to enhance its capabilities, where the flow information constrains and restricts the static control flow. This flow information is what is usually provided in terms of annotations of the program. Most important is here the provision of upper bounds for cycles in the static control flow representation of a program, which are due to loops and (mutually) recursive procedure and function calls. Generally, we distinguish the following kinds of dynamic control flow information: Loop bounds Loop bounds are the minimum information required by WCET analyzers to come up with a WCET bound for a program. For natural loops, i.e., loops with a distinct loop header dominating all nodes in the loop body and a back edge pointing to the loop header [2] , loop bounds specify the maximum iteration count of the loop body relative to the loop header. For non-natural loops, e. g., for irreducible loops, the specification of loop-bounds is less intuitive since there is no unique loop entry. Recursion bounds Recursion bounds are similar in flavor to loop bounds. They provide an upper bound for the number of times a recursive function or procedure calls itself upon each invocation. Specifying bounds for mutually recursive procedure calls is less obvious and not directly possible. Nested loops with non-rectangular iteration space If the range of an iteration variable (i, j, k, ...) of an inner loop depends on the current value of the iteration variable of an outer loop, the shape of the iteration space becomes non-rectangular [47] . Common examples are trapezoidal and triangular iteration spaces, the latter are also called triangle loops. Call contexts Call-contexts provide information about the context, in which a procedure is called at a particular call site, e. g., the values of procedure arguments and global variables. Call contexts allow to analyze a procedure call site specifically. In general, this allows more precise analysis results. For example, the computation of loop bounds that depend on the values of input parameters or global variables at a call site, will usually be more precise if the analysis can refer to call-context information at call sites [38] . Loop contexts Loop-contexts are similar to call contexts but focus on loops instead of call sites. Often, the first and subsequent loop iterations behave differently, e. g., because of cache effects. The precision of analyzing such loops can be improved when, e. g., an annotation language allows for annotating the first and subsequent iterations of a loop separately. Application contexts Application contexts provide information about the context an application is executed in, e. g., the possible states of the environment. An application context describes the environment of the program, while a call context describes the local context of a particular call site. Of course, a change in the application context can also cause a change of a particular call context. A program often behaves significantly different due to changes in the environment. The precision of analyses can thus be improved if annotation languages allow for the specification of specific application contexts. Execution order The WCET of a program can depend on the concrete order in which its statements are executed, e. g., because of effects of instruction pipelines, instruction/data caches, or processor parallelism. Most WCETcalculation methods do not take this into account and 123 416 R. Kirner et al. content themselves with estimates of the execution frequency of basic blocks. If, however, the method supports the modeling of a complex hardware architecture where the instruction timing depends on the execution history, the annotation language should support the specification of the execution order.
Additionally, state-of-the-art timing analyzers support powerful annotation languages to provide global path information REF (the impact on WCET optimization is evaluated in Section 7.3).
Beyond loop bounds: comparing annotation languages for worst-case execution time analysis
Software & Systems Modeling
Software & Systems Modeling
Computer Science