Content

2 Computing a WCET

Although OTAWA is designed as a generic framework to develop static analyses for WCET computation, some facilities are provided to compute WCET using dedicated commands.

Although OTAWA does implement and implements several approaches to WCET computation, IPET (Implicit Path Enumeration Technique) is the more mature one. In addition, IPET seems to be the method that has been the most developed and that gave the most interesting and precise results.

In OTAWA, there are four ways to compute a WCET:

• oipet command provides minimal support for IPET computation and may be used for basic computations,

• owcet command allows to perform computation based on script adapted to specific architecture,

• the Eclispe plug-in gives access to architecture scripts in more friendly graphic way inside the Eclipse IDE,

• by writing your own program benefiting from the facilities of the framework (that is explored in the following sections).

2.1 oipet command

2.1.1 First Contact

oipet implements the IPET approach to compute WCETs. It may be simply called from a command line interface (shell) and only requires the path to the executable file to time.

  $ oipet executable_path
  WARNING: there is no data cache here !
  WCET [executable_path:main] = w

This command computes the WCET of the given executable file starting at the main function considering a scalar in-order pipelined processor with five stages without any cache (as stated by the warning sentence). You may experiment this command with the binary codes delivered with OTAWA (:resources:program_examples).

To load the binary code, the OTAWA framework first retrieves the kind of the executable file. If it is supported, the matching loader plugin processes the file. Currently, only PowerPC and ARM architectures are delivered by the core package but more are available on the OTAWA site (Sparc, TriCore, M68HCS12). Note that you may develop your own architecture plugin to be used in OTAWA (see the developer manual).

Then, the WCET is computed according to a sequence of analysis stages and the result is displayed (expressed in processor cycles). To get the accurate time t in seconds, consider the frequency f of the processor and the WCET w and perform the calculation below:

<m> t = w / f </m>

Usually, an embedded executable contains many different tasks to time that are called from an un-ended loop implemented in the main function. In OTAWA, we consider that tasks are identified by an entry function performing the task job. To apply oipet to a particular function, called task_entry, just append the function name to the command.

  $ oipet executable_path task_entry
  WCET [executable_path:task_entry] = w

As one may notice watching at the OTAWA samples, a single executable is not enough. First, the host architecture of the embedded program may be different from the default scalar non-pipelined processor. Second, some information cannot be automatically extracted from the program and must be provided by the developer. They are called flow facts and concerns mainly loop bounds.

2.1.2 Selecting the Hardware

Although the architecture family is provided in executable files, there are usually many different implementations of an ISA – Instruction Set Architecture. For example, many different OEM and chips support the ARM instruction set and their time behavior is quite different among the different implementations.

The hardware description is defined by several models:

• the processor model describes the pipeline,

• the cache model describes the cache,

• the address space describes how the memory is organized,

• the branch prediction model describes the branch predictor configuration.

Both models are expressed using XML files some of which are provided with OTAWA in the directory INSTALL_DIRECTORY/share/Otawa/.

You may freely examine these files to figure out the simple used encoding and possibly write your own hardware models. Take a look at the developer manual for more details on the format.

To configure the hardware model with oipet, you must use the following options:

• -p processor_path to select the processor model,

• -c cache_path to select the cache model.

Then, you may select policies that will perform more accurate computation of the WCET depending on the hardware configuration.

The -i option accepts an argument selecting how the instruction is analyzed:

• -i none: do not handle the instruction cache (default),

• -i ccg: use the Cache Conflict Graph approach of 1,

• -i cat: use an adaptation of the Category method of [Muller] to IPET.

Conversely, there are many ways to take into account the pipeline effects on the timing with option -t:

• -t trivial: use the simple scalar 5-stages pipeline (default),

• -t sim: use a simulator to compute time of instruction blocks,

• -t delta: improve the sim method with an inter-block computation from 2 (not safe with out-of-order processors),

• -t exegraph: use the ExeGraph approach of 3.

2.1.3 Specifying the Flow Facts

Currently, OTAWA has not the ability to derive automatically loop bounds from the executable. To compute a WCET, the user must provides them in a .ff flow fact file. This file path may be passed to oipet using option -f path or it is silently loaded by OTAWA deriving its name by appending .ff to the executable file path.

.ff has a simple text syntax where loops are identified by their header block. As in the sample below, a maximal count of iteration must be associated with the header block.

fibcall.c

int fib(int n) {
  int  i, Fnew, Fold, temp,ans;
  Fnew = 1;  Fold = 0;
  i = 2;
  while( i <= n ) {
    temp = Fnew;
    Fnew = Fnew + Fold;
    Fold = temp;
    i++;
  }
  ans = Fnew;
  return ans;
}
    
main() {
  int a;
  a = 30;
  fib(a);
}

fibcall.ff

checksum "fibcall" 0x86c6f217;

// Function fib
loop 0x0005013c 29;

Building a flow fact file in OTAWA is currently a hard task: loop headers are identified by their address in the execution memory space. The easier way to build a .ff file is to use the mkff utility. Called on the executable, it generates a template .ff file where the loop counts are replaced by ? marks.

$ mkff executable > executable.ff

Template fibcall.ff

checksum "fibcall" 0x86c6f217;

// Function fib
loop 0x0005013c ?;

The user has to edit by hand with any text editor the generated file and to replace each ? mark by the program maximal loop count. The checksum must not be changed: it is used to check consistency of the flow fact file with the executable as header addresses may change when an executable is recompiled.

To help in the match of .ff loop and source loop, mkff comments the name of the function containing the loop and indents loops according to their nesting depth. If these indications are not enough, you may use dumpcfg utility to produce a representation of the CFG – Control Flow Graph – of the function.

$ dump -Did executable_path function_name > function_name.dot
$ dot -Tps function_name.dot > function_name.ps

This command produces a PostScript file that may be displayed with your preferred postscript viewer.

2.1.4 Details about the computation

To compute a WCET, oipet performs a lot of analyses on the program according to the selected options. To get the detail of the performed analyses, one may pass the -v option and get an ouput listing like below:

  $ oipet executable_path -v
  Starting CFGCollector (1.0.0)
  Ending CFGCollector
  Starting otawa::TrivialBBTime (1.0.0)
          process CFG main
                  process BB 0 (00000000)
  ...
  WCET [/home/casse/Benchs/snu-rt/fibcall/fibcall:main] = 960

When an analysis starts, a Starting line is displayed with the name and the version. Then an Ending is output when the analysis stops. The lines between start and stop output depends upon the performed analysis.

In the sample above, the TrivialBBTime analysis displays the processed function CFG and, inside them, the processed BB – Basic Blocks. If there is an error somewhere, it is easy to locate it on the processed program.

To have details about the performed analyses, please refer to the auto-documentation in INSTALL_PATH/share/Otawa/autodoc: each analysis matches a documented C++ class.

2.2 owcet command

oipet performs very basic WCET computations based on a bound set of analyzes. In addition, you have to provide description of the different architecture features that may be quite complex in some cases. In the opposite, owcet allows to use WCET computation scripts dedicated to a specific microprocessor model. These scripts comes with own set of hardware description files and possibly analyses supporing specific features of the microprocessor. Several microprocessor scripts are available on the OTAWA site, and may be freely downloaded and compiled.

2.2.1 Basics of owcet

The owcet is usually invoked with the following syntax from the command line shell:

$ owcet -s SCRIPT EXE_FILE [TASK_NAME]

Where SCRIPT is the name of the script. The scripts are installed in the directory otawa-config –scripts. The script files have .osx for extension and the SCRIPT may be either the script name without extension, or a file path designing a script file. To list the available scripts, you can use otawa-config:

$ otawa-config --list-scripts

The EXE_FILE is the ELF file containing the executable and TASK_NAME is an optional argument giving the name of the function representing the task. If TASK_NAME is omitted, the computation is performed for the main function. As for owcet, flow fact information (like loop bounds) may be required to achieve the computation. owcet supports the F4 flow fact format (as oipet) but also the FFX format (based on XML) providing much more expressivity for the flow facts. The FFX files may be edited by hand or generated by tools like oRange (described in the following section). Whatever the used format, the flow facts may be passed implicitely with a file named EXE_FILE.ff or EXE_FILE.ffx according to the used format, or by passing explicitely with the option -f or –flowfacts:

$ owcet -s SCRIPT EXE_FILE [TASK_NAME] -f PATH_TO_FLOWFACT_FILE

2.2.2 Tuning the computation

Usually, the delivered scripts provide several configuration items: either a script represents a family of microprocessors, or some properties on the environment of the microprocessor (that is the board it is mount on). To list the available parameters, one can type the following command:

$ owcet -s SCRIPT EXE_FILE --list

Either one can let undefined a parameter (using the default value), or you can pass it a parameter to the computation with option -p or –param passing as argument a string separated by an equal symbol =. On the left side, stands the parameter name and on the right side the parameter value:

$ owcet -s SCRIPT EXE_FILE -p PARAM1=VALUE1 -p PARAM2=VALUE2...

2.3 Producing the flowfacts