Example of Bound-T/ARM7 analysis

Introduction

This note shows how a small 'C' program for the ARM7 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 two 'C' files, main.c and routines.c. There are also three header (.h) files and one ARM7 assembly-language file Startup.s (not shown). The source code is 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 ARM7 target processor, using the Keil/ARM RealView (armcc) compiler. A build script (build.bat) for this compilation and linking is included in the ZIP archive, as is the executable file. The target device is specifically the NXP LPC2138, running with the MAM enabled (MAM Mode 2) but set to use one-cycle flash access (MAMTIM = 1).

The executable file is named "prog" and is in ELF 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 ARM7 executable "prog" and the assertion file "assertions.txt". In particular, the C and assembler source-code files are 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 ELF file.

First experiment

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

boundt_arm7 -arm7 prog Count25

The components of this command are:

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

 1  Loop_Bound:prog:routines.c:Count25:9-11:12
 2  Wcet:prog:routines.c:Count25:7-13:145

Line 1 reports that Bound-T has determined that the loop in the Count25 subprogram, on lines 9-11 in the file "routines.c", repeats at most 12 times. (In fact the body of the loop -- the assignment to "*x" -- is executed 13 times because the compiler has generated code for a "bottom-test" loop. The Loop_Bound that Bound-T finds is only 12 because it shows the number of times the code jumps backwards to repeat the loop once more.)

Line 2 reports that the WCET bound for Count25 is 145 machine cycles. The line also shows that the subprogram is located in the source-file "routines.c" on lines 7-13. In case you wonder why these line numbers do not include the function declaration and parameter declarations, which occupy lines 5-6 in "routines.c", it is because Bound-T finds the line numbers from the debugging information and lines 5-6 do not lead to any executable ARM7 instructions that could be debugged.

Full analysis fails

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

boundt_arm7 -arm7 prog main

which asks Bound-T to analyse the "main" subprogram. However, there are 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:main.c:main:24:Eternal loop (no exit edges).
 2  Loop_Bound:prog:routines.c:Count25:9-11:12
 3  Loop_Bound:prog:routines.c:Foo7@36-=>Count:18-20:4
 4  Loop_Bound:prog:routines.c:Solve:48-60:7
 5  Loop_Bound:prog:routines.c:main@16-=>Foo@27=>Count:18-20:5
 6  Warning:prog:main.c:main:6-24:Non-returning subprogram.
 7  Wcet:prog:routines.c:Count25:7-13:145
 8  Wcet_Call:prog:routines.c:Foo7@36-=>Count:18-22:55
 9  Wcet:prog:routines.c:Foo7:33-40:80
10  Wcet_Call:prog:routines.c:main@16-=>Foo@27=>Count:18-22:67
11  Wcet_Call:prog:routines.c:main@16-=>Foo:27:71
12  Error:prog:main.c:main:6-24:Could not be fully bounded.
13
14
15  main
16     Loop unbounded (eternal) at main.c:24, offset 00000030
17     main@20=>Solve@51=>Ones
18        Loop unbounded at routines.c:71-76, offset 00000018
19     main@20=>Solve@60=>Count
20        Loop unbounded at routines.c:18-20, offset 00000000

In the output quoted above, line 1 reports that Bound-T has found an eternal (non-terminating) loop in the main subprogram on line 24 in the file "main.c".

The four Loop_Bound lines (lines 2-5) report the iteration bounds that Bound-T determines for four loops. Some of these bounds are context- dependent, meaning that they are valid only for a particular call path. For example, the second Loop_Bound line reports that the loop in the subprogram Count, at lines 18-20 in "routines.c", has an upper bound of 4 repetitions when Count is called from the subprogram Foo7 through the call at line 36. The line-number is given in the form "36-" because we are using the default option "-lines around" and the compiler did not map the actual call instruction to line 36, but some instruction just before the call was mapped to line 36.

The fourth Loop_Bound line (line 5) shows that the same loop in Count has a different bound when Count is called in a different context.

The Warning line (line 6) after the Loop_Bound lines says that the main subprogram never returns to its caller. This is of course due to the eternal loop at the end of the main subprogram.

The Error line (line 12) reports that Bound-T could not find a WCET bound for the main subprogram. The indented, hierarchical listing after the Error line shows that the problems are the eternal loop, a loop in the subprogram Ones, which is called from the subprogram Solve, and the loop in Count when Count is called from Solve. This is the same loop for which a Loop_Bound was found when Count was called from Foo7, but that bound does not apply when Count is called from Solve, because the former Loop_Bound depends on the parameter values in the call from Foo7.

The reasons why Bound-T cannot find bounds on these loops are explained in comments in the source-code file (routines.c). 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 16 through 20 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     loop that calls "Count"
 7        variable "Solve|k" <= 32;
 8     end loop;
 9  end "Solve";
10
11  subprogram "main"
12     loop repeats 1 time; end loop;
13  end "main";

Line 1 above declares that the following lines, up to line 3, refer to the subprogram Ones. Line 2 specifies that the loop in Onesrepeats 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 9, refer to the subprogram Solve. Line 6 declares that the following lines, up to line 8, refer in particular to that loop within Solve that contains a call to Count. Line 7 asserts that within this loop 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_arm7 -arm7 -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:main.c:main:24:Eternal loop (no exit edges).
 2  Loop_Bound:prog:routines.c:Count25:9-11:12
 3  Loop_Bound:prog:routines.c:Foo7@36-=>Count:18-20:4
 4  Loop_Bound:prog:routines.c:Solve:48-60:7
 5  Loop_Bound:prog:routines.c:Solve@60=>Count:18-20:16
 6  Loop_Bound:prog:routines.c:main@16-=>Foo@27=>Count:18-20:5
 7  Warning:prog:main.c:main:6-24:Non-returning subprogram.
 8  Wcet:prog:routines.c:Count25:7-13:145
 9  Wcet_Call:prog:routines.c:Foo7@36-=>Count:18-22:55
10  Wcet:prog:routines.c:Foo7:33-40:80
11  Wcet_Call:prog:routines.c:main@16-=>Foo@27=>Count:18-22:67
12  Wcet_Call:prog:routines.c:main@16-=>Foo:27:71
13  Wcet:prog:routines.c:Ones:69-80:298
14  Wcet_Call:prog:routines.c:Solve@60=>Count:18-22:199
15  Wcet:prog:routines.c:Solve:44-64:4121
16  Wcet:prog:main.c:main:6-24:4449

Lines 1 through 4 and line 6 give the same Warning and the same Loop_Bounds as in the earlier analysis, without assertions. Line 5 gives a new Loop_Bound, for Count when called from Solve; this Loop_Bound is deduced from the assertion on the value of k in Solve. No Loop_Bound line appears for the loops in Ones and main, because these loops were directly bounded by assertions.

Lines 8 through 16 report WCET estimates (upper bounds) for various subprograms and calls. The last line (line 16) is the final result: the WCET of main is at most 4449 cycles. To find this value, Bound-T also computed WCET bounds for Count25 (145 cycles, line 8), Foo7 (80 cycles, line 10), Ones (298 cycles, line 13), and Solve (4121 cycles, line 15). These WCET values apply to any call of these subprograms. For the subprograms Count and Foo, Bound-T had to consider the context of the call, and found WCET bounds for four different calls as shown by the lines 9, 11, 12, and 14.

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:main.c:main:6-24:4449:32:1:4449:4449:main:main.c:6-24
Time_Table:prog:main.c:main:6-24:145:145:1:145:145:Count25:routines.c:7-13
Time_Table:prog:main.c:main:6-24:80:25:1:80:80:Foo7:routines.c:33-40
Time_Table:prog:main.c:main:6-24:1714:1714:10:55:199:Count:routines.c:18-22
Time_Table:prog:main.c:main:6-24:71:4:1:71:71:Foo:routines.c:27
Time_Table:prog:main.c:main:6-24:4121:145:1:4121:4121:Solve:routines.c:44-64
Time_Table:prog:main.c:main:6-24:2384:2384:8:298:298:Ones:routines.c:69-80

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
-----     ----      -----     -------------       ----------
4449      32        1         4449      4449      main
4121      145       1         4121      4121      Solve
2384      2384      8         298       298       Ones
1714      1714      10        55        199       Count
145       145       1         145       145       Count25
80        25        1         80        80        Foo7
71        4         1         71        71        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.

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 ARM7 stack space used in the example program, starting from the main subprogram, give the command:

boundt_arm7 -arm7 -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:main.c:main:24:Eternal loop (no exit edges).
 2  Stack:prog:routines.c:Count25:7-13:SP:0
 3  Stack:prog:routines.c:Count:18-22:SP:0
 4  Stack:prog:routines.c:Ones:69-80:SP:0
 5  Stack:prog:routines.c:Foo7:33-40:SP:4
 6  Stack:prog:routines.c:Foo:27:SP:0
 7  Stack:prog:routines.c:Solve:44-64:SP:8
 8  Stack:prog:main.c:main:6-24:SP:16
 9  Warning:prog:main.c:main:6-24:Non-returning subprogram.
10  Stack_Path:prog:main.c:main@20=>Solve:20:SP:16:8:8:8
11  Stack_Leaf:prog:routines.c:Solve:44-64:SP:8:8::

The two Warnings in lines 1 and 9 are about the eternal loop in main and the fact that the main subprogram never returns. This has no effect on the stack analysis.

The final Stack line (line 8) shows that the total stack utilization of the main subprogram, including all the subprograms that main calls, is 16 stack locations (16 octets). The earlier Stack lines (lines 2-7) show the stack utilization in lower-level subprograms, many of which need no stack space at all (the final number is zero). The Solve subprogram needs 8 octets and Foo7 needs 4 octets.

The Stack_Path and Stack_Leaf lines (lines 10 and 11) show the call-path, starting from main, that represents the maximum stack usage. This is simply the call from main to Solve; the deeper calls from Solve to Ones and to Count are not listed because they need no additional stack space.

The first and only Stack_Path line shows that the main subprogram requires 16 octets in all, composed of 8 octets for its own use, representing the local variables in main and space for parameters for callees, and 8 octets for the stack usage in callees (here only the Solve subprogram).

The Stack_Leaf line (line 11) shows that the last subprogram on the worst-case call path, Solve, needs 8 stack octets for itself and that deeper calls are not shown because they are not relevant to the stack usage.

The total usage in main, 16 octets, is simply the sum 8 (main) + 8 (Solve). Note that there can be other call-paths that have the same stack usage; Bound-T shows just one of these maximal paths. Note also that the total stack usage from boot (reset) of the processor may be larger, because the startup functions may (and typically do) need some stack space.



Valid HTML 4.01 Transitional