Example of Bound-T analysis for ADSP-21020

Introduction

This note shows how a small 'C' program for the APDSP-21020 is analysed by Bound-T and what the results are. Both execution time (WCET) analysis and stack-usage analysis are demonstrated.

The example is organized as follows:

The example program

The example program consists of a single 'C' file, example.c. The source code is displayed with line numbers for reference. When it can, Bound-T uses source-line numbers in its outputs to identify the relevant part of the program, for example a loop or a call. Here is a ZIP archive with all the files in case you prefer to browse them directly.

This program does nothing useful, but has been designed to illustrate several features and limitations of Bound-T with a compact example. For an overview of the example you can take an advance peek at the call graph, as drawn by Bound-T.

Some points to be noted in this example are:

Compiling and linking the example program

For this example, the program has been compiled and linked for the ADSP-21020 target processor, using the Analog Devices GCC-based compiler g21k. The executable file is included in the ZIP archive.

The executable file is named "prog" and is in COFF form. This is the main input to Bound-T.

Analysing the example with Bound-T

The operation and usage of Bound-T are explained in the User Guide, the Reference Manual, and the relevant Application Note documents. The following examples show some ways to use Bound-T/ARM7 to analyse this example program for its worst-case execution time and stack usage.

The only files from this folder that are actually needed for these example analyses are the ADSP-21020 executable "prog" and the assertion file "assertions.txt". In particular, the C source-code file is not necessary; Bound-T does not use the source-code files. The output from Bound-T includes references to source-code files and line-numbers, but these are all taken from the debugging information that the compiler generated and placed in the COFF file.

First experiment

As a first example we ask Bound-T to analyse the subprogram (C function) Count. The following command will do that:

boundt_sharc prog _Count

The components of this command are:

The result of this commmand is the following output. Line numbers are added here for reference.

1  Warning:prog:example.c:_Count:24-:Large literal 4294967294 = hex FFFFFFFE, used as signed = -2
2  Error:prog:example.c:_Count:23-27:Could not be fully bounded.
3  
4  
5  _Count
6     Loop unbounded at example.c:24-25, offset 00000005

Line 1 warns you that Bound-T has found, in the machine code for the Count function, a literal (immediate) operand with a large value, and that Bound-T assumes that this value should be interpreted as the two's complement negative number -2. A glance at the for-loop in the source code shows that this assumption is very probably correct.

Line 2 shows that Bound-T failed to find an upper bound on the execution time of Count. The rest of the output shows that the problem is the loop in Count, for which Bound-T did not find an iteration bound. This is understandable, because the loop depends on the parameter u, and the value of this parameter is not known when Count is analysed on its own, apart from its callers.

Full analysis fails

To analyse the top-level main subprogram in the example program, you can try the command

boundt_sharc prog _main

which asks Bound-T to analyse the main subprogram and all subprograms called from main. However, there are still some loops for which Bound-T cannot find iteration bounds, so the output of this command includes some warnings and error messages. Line numbers are added here for reference.

 1  Warning:prog:example.c:_Count:24-:Large literal 4294967294 = hex FFFFFFFE, used as signed = -2
 2  Loop_Bound:prog:example.c:_Solve:33-37:8
 3  Loop_Bound:prog:example.c:_main@11-=>_Foo@18-=>_Count:24-25:5
 4  Wcet_Call:prog:example.c:_main@11-=>_Foo@18-=>_Count:23-27:116
 5  Wcet_Call:prog:example.c:_main@11-=>_Foo:17-19:135
 6  Error:prog:example.c:_main:9-13:Could not be fully bounded.
 7  
 8  
 9  _main@12-=>_Solve@35-=>_Ones
10     Loop unbounded at example.c:45-49, offset 00000004
11  _main@12-=>_Solve@37-=>_Count
12     Loop unbounded at example.c:24-25, offset 00000005

The first Warning line (line 1) is the same as in the first example run, above.

The Loop_Bound lines (lines 2 and 3) report the iteration bounds that Bound-T determines for two loops. The first Loop_Bound line reports that the loop in the function Solve, at lines 33-37 in the source-code file "example.c", repeats at most 8 times. This loop bound is valid for all calls of Solve (it is context-independent).

The second Loop_Bound (line 3) is context-dependent, meaning that it is valid only for a particular call path. In this example, the second Loop_Bound line reports that the loop in the function Count, at lines 24-25 in "example.c", has an upper bound of 5 iterations when Count is called from the function Foo through the call at line 18 of "example.c", when Foo is called from the main function through the call at line 11. The line-number is given in the form "18-" because the compiler did not map the actual call instruction in Foo to line 18, but some instruction just before the call was mapped to line 18.

Next, the two Wcet_Call lines (lines 4 and 5) show the computed execution-time bounds for those functions and contexts where Bound-T was able to compute a time bound. The Wcet_Call lines show context-dependent bounds, that is, bounds on particular calls of the functions. For example, the first Wcet_Call line reports that the Count function takes at most 116 machine cycles when it is called from Foo and the main function along the path identified in the corresponding Loop_Bound line (line 3). Context-independent execution-time bounds are reported in "Wcet" lines as shown below.

The Error line (line 6) reports that Bound-T could not find a WCET bound for the mai function (and perhaps for some lower-level functions). The indented, hierarchical listing after the Error line shows that the problems are a loop in the function Ones, which is called (at least) from the function Solve, and the loop in Count when Countis called from Solve. This is the same loop for which a Loop_Bound was found when Count was called from Foo, but that context-dependent bound does not apply when Count is called from another context (from Solve).

Bound-T cannot find bounds on these loops because they have no simple loop-counters (for exampe, the while-loop in Ones) or because Bound-T cannot find the initial value, final value, and step for the loop counter (for example, when Count is called from Solve). For such loops, the user must support Bound-T by stating assertions on the program's behaviour. We do that in the next section of this example.

Full analysis succeeds with assertions

To compute a WCET bound for the example program, we must help Bound-T find bounds on the loops reported in lines 9 through 12 above. This is done by writing an assertion file. This can be done in several ways, for example as in the following text (line numbers added for reference):

1  subprogram "_Ones"
2     loop repeats <= 32 times; end loop;
3  end "_Ones";
4
5  subprogram "_Solve"
6     variable "_Solve|_k" <= 32;
7  end "_Solve";

Line 1 above declares that the following lines, up to line 3, refer to the subprogram Ones. Line 2 specifies that the loop in Ones repeats at most 32 times in any call of Ones. This is because the uint variable x is 32 bits long and can be shifted right at most 32 times before it becomes zero. For the same reason, the value returned from Ones is always between 0 and 32.

Line 5 in the assertion file above declares that the following lines, up to line 7, refer to the subprogram Solve. Line 6 asserts that within this subprogram the variable k, which is local to Solve, has a value that is at most 32. This holds because k is assigned the return value from Ones, which is between 0 and 32 as explained above.

Assuming that the assertion file is named "assertions.txt", the following command invokes Bound-T as above to analyse the main function, but under these assertions:

boundt_sharc -assert assertions.txt prog _main

This time, the analysis succeeds without error messages. The output is the following, with line numbers added here for reference:

 1  Warning:prog:example.c:_Count:24-:Large literal 4294967294 = hex FFFFFFFE, used as signed = -2
 2  Loop_Bound:prog:example.c:_Solve:33-37:8
 3  Loop_Bound:prog:example.c:_Solve@37-=>_Count:24-25:16
 4  Loop_Bound:prog:example.c:_main@11-=>_Foo@18-=>_Count:24-25:5
 5  Wcet_Call:prog:example.c:_main@11-=>_Foo@18-=>_Count:23-27:116
 6  Wcet_Call:prog:example.c:_main@11-=>_Foo:17-19:135
 7  Wcet:prog:example.c:_Ones:43-51:723
 8  Wcet_Call:prog:example.c:_Solve@37-=>_Count:23-27:336
 9  Wcet:prog:example.c:_Solve:31-39:9517
10  Wcet:prog:example.c:_main:9-13:9680

The main result is the Wcet line for main (line 10) showing a WCET bound of 9680 cycles for main and all the functions it calls. There are also other new WCET results; for example, the last Wcet_Call line (line 8) shows that when Count is called from the Solve function it has a WCET bound of 336 cycles, larger than the bound of 116 cycles when Count is called from the function Foo.

Tabular output

If we add the command-line option "-table", Bound-T writes a tabular form of the analysis results as a number of output lines beginning with the keyword Time_Table:

Time_Table:prog:example.c:_main:9-13:9680:28:1:9680:9680:_main:example.c:9-13
Time_Table:prog:example.c:_main:9-13:135:19:1:135:135:_Foo:example.c:17-19
Time_Table:prog:example.c:_main:9-13:2804:2804:9:116:336:_Count:example.c:23-27
Time_Table:prog:example.c:_main:9-13:9517:322:1:9517:9517:_Solve:example.c:31-39
Time_Table:prog:example.c:_main:9-13:6507:6507:9:723:723:_Ones:example.c:43-51

The table is best viewed by passing the output through a script that formats the table for easy reading, with this result:

Total     Self      Num       Time Per Call
Time      Time      Calls     Min       Max       Subprogram
-----     ----      -----     -------------       ----------
9680      28        1         9680      9680      _main
9517      322       1         9517      9517      _Solve
6507      6507      9         723       723       _Ones
2804      2804      9         116       336       _Count
135       19        1         135       135       _Foo

As you can see, the table shows at a glance which subprograms are used in the worst-case scenario, how many times each subprogram is called, how much time is spent in the subprogram including its callees, and how much of this time is spent in other subprogram itself, excluding callees.

You may wonder why the the table above gives 9 executions of the function Ones, although an inspection of the example program shows that it is really executed only 8 times from the loop in Solve. The reason is that the particular form of looping code chosen by the compiler for this loop conspires with the break statement in the loop to make it appear that the call to Ones in the loop might execute 9 times, as far as the analysis in Bound-T can tell. This approximation can be corrected by another assertion (saying that the call from Solve to Ones is executed at most 8 times) but Tidorum also plans to improve the loop analysis to avoid problems of this kind.

Call graph and control-flow graphs

If we add the command-line options "-dot graphs.dot" and "-draw total", Bound-T draws the call-graph of main and the control-flow graphs of each analysed subprogram. The graphs are written to the file named in the -dot option (here graphs.dot) in a textual notation called the DOT form (from Drawer Of Trees). The program dot, from the Bell Labs GraphViz package, converts the graphs to other forms such as Postscript. The images that you can open from the links below have been converted to the PNG (Portable Network Graphics) form.

The control-flow graphs can be labeled with various kinds of information. For example, the option "-draw decode" will show the disassembled instructions in each graph node; this option was used to generate the graphs presented above. The "-draw" options are explained in the Bound-T Reference Manual.

Stack analysis

To compute an upper bound on the amount of CCP (C Calling Protocol) stack space used in the example program, starting from the main subprogram, give the command:

boundt_sharc -stack_path -no_time prog _main

The option "-no_time" disables WCET analysis so that we need no assertion file (in this example, but assertions may be required for stack-usage analysis of some programs). This gives the following output (line numbers are added here for reference):

1  Warning:prog:example.c:_Count:24-:Large literal 4294967294 = hex FFFFFFFE, used as signed = -2
2  Stack:prog:example.c:_Count:23-27:CCP:5
3  Stack:prog:example.c:_Ones:43-51:CCP:4
4  Stack:prog:example.c:_Foo:17-19:CCP:9
5  Stack:prog:example.c:_Solve:31-39:CCP:10
6  Stack:prog:example.c:_main:9-13:CCP:13
7  Stack_Path:prog:example.c:_main@12-=>_Solve:12-:CCP:13:3:3:10
8  Stack_Path:prog:example.c:_Solve@37-=>_Count:37-:CCP:10:5:5:5
9  Stack_Leaf:prog:example.c:_Count:23-27:CCP:5:5::

The output starts with the familiar Warning line.

The following lines that start with the word Stack show how much CCP stack each function uses, which is the last number on the line. This includes the stack-space used in calls to other functions. For example, the first Stack line shows that the function Count uses 5 stack locations (5 words of 32 bits), including the space used by any functions that Count calls.

The last Stack line (line 6) shows that the main function needs a total of 13 words of stack space. This includes the stack space used by all functions that main calls and the return address for main as well as the saved frame pointer for the function that calls main, assuming that main is called with the normal C Calling Protocol.

Note that the "stack" we are talking about here is the software stack, in main memory, defined by the C Calling Protocol (CCP). It is not the SHARC hardware stack of PC values. (Bound-T/SHARC does not yet analyse the usage of the PC stack, but could easily be extended to do so.)

The lines that start with the words Stack_Path and the final line that starts with Stack_Leaf show which sequence of calls, starting in main, leads to the highest stack usage of 13 words. The four numbers at the end of these lines show, respectively:

Thus, the first Stack_Path line shows that the main function requires stack space as follows:

The other Stack_Path lines show the rest of the call-path from main that requires the largest amount of stack space, which is the path main => Solve => Count. The last line is marked Stack_Leaf to show that the call-path ends here.

There may be other call-paths that have the same total stack usage. Bound-T shows only one of the paths that has this maximal usage.

Note that the total stack usage from boot (reset) of the processor may be larger than computed for main, because the startup functions may (and typically do) need some stack space, before the main function is entered.



Valid HTML 4.01 Transitional