Set of Software Quality Static Analyzers (SSQSA) is a set of software tools for static analysis that is incorporated in the framework developed to target the common aim - consistent software quality analysis. The main characteristic of all integrated tools is the independency of the input computer language. Language independency is achieved by enriched Concrete Syntax Tree (eCST) that is used as an intermediate representation of the source code. This characteristic gives the tools more generality comparing to the other similar static analyzers. The aim of this paper is to describe an early idea for introducing support for static timing analysis and Worst Case Execution Time (WCET) calculation at code level in SSQSA framework. Additional Key Words and Phrases: Worst case execution time, language independency The quality of each product, and therefore also the quality of the software product, can be described as the degree to which a given product meets the needs and requirements of users. Software quality model defined by standard ISO 9126-11 distinguishes six attributes of software quality: functionality, usability, reliability, efficiency, portability, and maintainability. The mentioned attributes of software quality can be monitored, evaluated, and controlled at early stages of software development by examining the source code and other static artefacts, or during the execution and testing process. Assessment of software quality attributes that is made on the source code or any of its internal representations without executing the program is called static analysis, while analysis of the program during execution time is called dynamic analysis. In the modern approach of software development, a great importance is given to monitoring and quality control in the early stages of development. Therefore static analysis becomes more important. One of the important quality attributes of real-time systems is the execution time. It is highly important for these systems to provide required services on time. One of the parameters to be measured in order to guarantee this attribute in real-time system quality monitoring is Worst Case Execution Time (WCET) [Wilhelm et al. 2008; Lokuciejewski and Marwedel 2009; Lokuciejewski and Marwedel 2011]. It is measured as a part of timing analysis and provides value of the longest execution time of a program that can ever occur. It can also be predicted as a part of static analysis as well as measured as a part of dynamic analysis. This paper provides early research toward support of static timing analysis and WCET calculation in SSQSA framework. In doing that, we shall take ALF as a domain specific language for WCET [Gustafsson et al. 2009] as our starting point and import the basic timing data into a SSQSA framework. The main difference between SQQSA set of static analyzers and ALF is in their level of abstraction: while ALF is intermediate language, enriched Concrete Syntax Tree - eCST (on which SSQSA framework is based) is a universal intermediate data structure. Furthermore, there are only several translators to ALF (C, C++,
Copyright © by the paper's authors. Copying permitted only for private and academic purposes.
In: Z. Budimac, T. Galinac Grbac (eds.): Proceedings of the 3rd Workshop on Software Quality, Analysis, Monitoring, Improvement, and Applications (SQAMIA), Lovran, Croatia, 19.-22.9.2014, published at http://ceur-ws.org. some assembler languages)2 [Gustafsson et al. 2009] while SSQSA supports many more high-level languages (Modula-2, Delphi, Java, C#,...). By including ALF into a SSQSA environment, we hope that we can introduce the WCET analysis to a much broader class of languages.
In the rest of the paper we describe the planned approach. Background for a described idea is provided in the subsequent section, while section number 3 illustrates the idea. Related work is provided by section number 4. Conclusion with plans for future work is given in the last section.
The basic idea for integrating static timing analysis into SSQSA framework is to introduce support for
domain specific languages
The main characteristic of SSQSA framework is its independency of the input computer language based on language independent tree representation of the source code - enriched Concrete Syntax Tree (eCST). Basic concept used here is to use universal nodes to enrich syntax tree so that they annotate semantics of the construct in its sub-tree. Universal nodes are constructed in three levels: - High-level eCST universal nodes mark entities declaration on the architectural level. Interfacelevel declarations of packages, classes, modules and methods, procedures, functions, etc. , as well as explicitly stated high-level relations between them (such as inheritance, instantiation, implementation, etc.). - Middle-level eCST universal nodes are those used at the level of entity definition. They appear in the body of the entities and mark individual statements, groups of statements or parts of statements with appropriate concept expressed by them (jump statement, loop statement, branch statement, condition, import statement, etc.). - Low-level eCST universal nodes are universal nodes that mark individual tokens with appropriate lexical category (keywords, separators, identifiers, etc.).
Based on the eCST representation of the source code we can (independently of an input language) generate other source code representations.
Generation of eCFG (enriched Control Flow Graph) is one of the first tasks to be completed toward the static timing analysis in the SSQSA framework. This is to be done based on a middle and low level universal nodes. Work on this task has been recently finished.
Furthermore, based on mainly high-level universal nodes we can generate different kind of software
networks completely independently of an input language [
Based on these program representations we can implement any of widely used approach to determine
upper bound of execution time (tree based, path based, implicit path enumeration, etc.) and suppo
ALF is an intermediate language used to represent input code written in language on high, middle, or low level. It can be also used to represent intermediate codes. Code represented by ALF language is adapted so that the WCET calculation is enabled. In other words, it contains all needed information.
Toward Language Independent Worst-Case Execution Time Calculation • 10:77
Currently, three translators exist: a translator from C/C++ to ALF, translator from proprietary IAR intermediate code to ALF, and translator from binary code to ALF.
By generating eCST for source code represented by ALF code we will be able to run WCET algorithms on it.
As described in [Kolek et al. 2013], we will need a grammar for ALF language in order to produce scanners and parsers to be used in eCSTGenerator. Furthermore, we have to determine which universal nodes are needed to implement algorithm. From this point of view the most important universal nodes already exist in the current catalogue. Furthermore it is possible that we will need to introduce a set of domain specific universal nodes.
Let us look at the input source code [Gustafsson et al. 2009]:
if (x > y) z = 42; This segment can be translated into the ALF code below: {switch {store {s_le 32 {load 32 {addr 32 {fref 32 x} {dec_unsigned 32 0}}}
{load 32 {addr 32 {fref 32 y} {dec_unsigned 32 0}}}} {target {dec_unsigned 1 1}
{label 32 {lref 32 exit} {dec_unsigned 32 0}}}} {addr 32 {fref 32 z} {dec_unsigned 32 0}} with {dec_signed 32 42}} {label 32 {lref 32 exit} {dec_unsigned 32 0}}
Generated segment of the ALF source code is much longer than the corresponding C code. Therefore corresponding eCST is also much larger. Figure 2 represents corresponding eCST for generated segment of ALF source code. Here we provide only the part of generated tree in order to demonstrate equivalency of trees for two languages.
In this section we will demonstrate idea for extracting XML timing information. For these purporses we will take basic example of branch statement. For all other needed information we can follow similar idea to export needed data.
Ba
<IfBlockK BTime=n WTime=n TotalTime=n … > <ThenBlockK Time=n … > … </ThenBlockK> <ElseBlock Time=n >
… </ElseBlockK> </IfBlockK> In eCST representation this would be encompassed by the unique BRANCH_STATEMENT node < BRANCH_STATEMENT" BTime=n WTime=n TotalTime=n> < BRANCH" Time=n>
… < BRANCH" Time=n>
…
Similarly we can extract all needed information from the source code to our XML representation (loops, conditions, etc.)
This XML representation will enable the flow of timing information between the tools, but also visualization of generated information, which means easier manipulation with timing facts.
Toward Language Independent Worst-Case Execution Time Calculation Timing analysis and WCET calculation is a very actual research topic and many tools are currently under development. Our attention is on tools calculating WCET on the level of a source code.
aiT3 [Lokuciejewski and Marwedel 2011] is a tool for static WCET analysis and is used to compute a safe upper bound of WCET. It accepts binary executable as its input, from which the control-flow graph is reconstructed. This graph is a code representation on which several static analyses are implemented to compute the execution time of each instruction. A global path analysis is used to compute overall WCET bound of tasks.
Bound-T4 is a WCET static analyzer with similar characteristics. It takes machine code as input and (based on control flow paths) generates WCET bounds and (optionally) stack-usage bounds.
FORTAS (the FORmal Timing Analysis Suite)5 combines execution time measurements with static program analysis techniques. It estimates WCET of software tasks running on embedded real-time systems based on a hybrid approach following the general principles of measurement-based timing analysis.
SWEET (Swedish WCET Analysis Tool)6 is a WCET analysis tool consisting of a flow analysis, a lowlevel analysis, and a WCET estimation. SWEET analyzes the intermediate format ALF [Gustafsson et al. 2009]. Given a code format, SWEET can perform a WCET analysis for it if there is a translator into ALF. Therefore, SWEET currently supports C/C++, IAR, and binaries, as previously mentioned.
By integration WCET static analyzer in SSQSA framework we can expect to cover wider specter of possible inputs which is the main goal of this research.
In this paper we propose a possible approach to enable support for WCET calculation into SSQSA framework. An idea based on introducing support for domain specific language is described in order to implement and test calculation algorithm. After this task is completed, exploration of the possibilities for extending the analysis to other supported languages is needed. The aim is to enable uniform application of the same algorithm implementation to all supported languages. This task should have two phases. First phase is to support language independent flow analysis. This will be the straightforward activity as generation of all language independent code representation is already enabled. Second phase is the platform dependent generation of WCET values. This task will require deeper research on extracting specific information to eCST. It may require introducing of the domain specific universal nodes. By these nodes we would annotate domain specific information in eCST. In validation stage, gained results are to be compared with results generated by existing language specific WCET calculation tools. First level validation will be by comparing gained results with the results generated by the SWEET tool.