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 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:
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.
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.
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.
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.
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.
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.
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.
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.