Example of Bound-T analysis for Atmel AVR

Introduction

This note shows how a small 'C' program for the Atmel AVR 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. 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 Atmel AVR target processor, model AT90S8515, using the IAR C compiler. The executable file is named "prog.d90" and is in IAR's UBROF 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 the AVR version of Bound-T 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 AVR executable "prog.d90" and the assertion file "assert.txt". In particular, the C 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 UBROF 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_avr -at90s8515 prog.d90 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.d90:routines.c:Count25:18-20:13
2  Wcet:prog.d90:routines.c:Count25:14-22:285

Line 1 reports that Bound-T has determined that the loop in the Count25 routine, on lines 18-20 in the file "routines.c", repeats at most 13 times. To be precise, the "back edge" of the loop is executed at most 13 times. If you look at the machine code (using, for example, the Bound-T option -trace decode), you can see that this is a "top-test" loop, so the body of the loop is also executed 13 times, and the loop head, with the termination test, is executed 14 times.

Line 2 reports that Bound-T has determined an upper bound of 285 machine cycles on the worst-case execution time (WCET) of the function Count25. The line also shows that the function is located in the source-file "routines.c" on lines 14-22.

Full analysis fails

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

boundt_avr -at90s8515 prog.d90 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.d90:main.c:main:36-:Large combined 16-bit literal 65535 taken as signed = -1
 2  Warning:prog.d90:main.c:main:32-36:Eternal loop (no exit edges).
 3  Warning:prog.d90:routines.c:Foo:34-36:Large combined 16-bit literal 65533 taken as signed = -3
 4  Warning:prog.d90:routines.c:Foo7:43-:Large combined 16-bit literal 65526 taken as signed = -10
 5  Loop_Bound:prog.d90:routines.c:Count25:18-20:13
 6  Loop_Bound:prog.d90:routines.c:Foo7@45=>Count:27-29:4
 7  Loop_Bound:prog.d90:routines.c:Solve:57-69:8
 8  Loop_Bound:prog.d90:routines.c:main@28=>Foo@36=>Count:27-29:5
 9  Warning:prog.d90:main.c:main:17-36:Non-returning subprogram.
10  Wcet:prog.d90:routines.c:Count25:14-22:285
11  Wcet_Call:prog.d90:routines.c:Foo7@45=>Count:25-31:86
12  Wcet:prog.d90:routines.c:Foo7:41-49:155
13  Wcet_Call:prog.d90:routines.c:main@28=>Foo@36=>Count:25-31:105
14  Wcet_Call:prog.d90:routines.c:main@28=>Foo:34-38:116
15  Error:prog.d90:main.c:main:17-36:Could not be fully bounded.
16  
17  
18  main
19     Loop unbounded (eternal) at main.c:32-36, offset 00000026
20     main@32=>Solve@60=>Ones
21        Loop unbounded at routines.c:80-85, offset 00000010
22     main@32=>Solve@69=>Count
23        Loop unbounded at routines.c:27-29, offset 00000016

In the output quoted above, lines 1, 3, and 4 report on the interpretation of immediate operands and can be ignored.

Line 2 reports that Bound-T has found an eternal (non-terminating) loop in the main function at lines 32-36 in the file "main.c".

Lines 5 through 8 (the Loop_Bound lines) 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, line 6 reports that the loop in the function Count, at lines 27-29 in "routines.c", has an upper bound of 4 repetitions when Count is called from the function Foo7 through the call at line 45.

The fourth Loop_Bound line, line 8, shows that the same loop in Count has a different bound (5) when Count is called in a different context, from main via Foo.

After the Loop_Bound lines, the Warning line (line 9) reports that the main function never returns, which is understandable, because this function ends with an eternal loop. The main function is in the file "main.c", lines 17-36.

The Warning line is followed by some Wcet lines (lines 10 through 14) giving the WCET bounds computed for those subprograms that have no unbounded loops. The Wcet_Call lines show the WCET bounds for particular calls, when the loop-bounds depend on the call. For example, the first Wcet_Call line (line 11) reports that the function Count takes at most 86 machine cycles when it is called from Foo7 at line 45. In contrast, the second Wcet_Call line (line 13) reports that when Count is called from the function Foo it has the larger WCET bound of 105 cycles.

The Error line (line 15) reports that Bound-T could not find a WCET bound for the main function. The indented, hierarchical listing after the Error line shows that the problems are the eternal loop, a loop in the function Ones, which is called from the function 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 context (parameter values are different). In fact Solve does not give a static parameter value to the parameter of Count that controls the number of iterations of the loop.

The reasons why Bound-T cannot find bounds on these loops are explained in comments in the source-code files. 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 19 through 23 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 16 times; end loop;
 3  end "Ones";
 4
 5  subprogram "Solve"
 6     loop that calls "Count"
 7        variable address "p16" <= 16;
 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 Ones repeats at most 16 times in any call of Ones. This is because the uint variable x is 16 bits long and can be shifted right at most 16 times before it becomes zero. For the same reason, the value returned from Ones is always between 0 and 16.

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 value at address "p16" has a value that is at most 16. The address "p16" refers to the AVR register pair R17:R16. The compiler has allocated this register pair for the C variable k. The assertion holds because k is assigned the return value from Ones, which is between 0 and 16 as explained above. It would of course be nicer to write this assertion using the C-level variable name, as

variable "k" <= 16;

but unfortunately, in this example and at this point in the code, the structure of the variable-to-register mapping in the UBROF debugging information is such that Bound-T does not know that k is held in register pair R17:R16. However, in general assertions on variable values can often use the source-level variable names.

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

boundt_avr -at90s8515 -assert assert.txt prog.d90 main

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

 1  Warning:prog.d90:main.c:main:36-:Large combined 16-bit literal 65535 taken as signed = -1
 2  Warning:prog.d90:main.c:main:32-36:Eternal loop (no exit edges).
 3  Warning:prog.d90:routines.c:Foo:34-36:Large combined 16-bit literal 65533 taken as signed = -3
 4  Warning:prog.d90:routines.c:Foo7:43-:Large combined 16-bit literal 65526 taken as signed = -10
 5  Loop_Bound:prog.d90:routines.c:Count25:18-20:13
 6  Loop_Bound:prog.d90:routines.c:Foo7@45=>Count:27-29:4
 7  Loop_Bound:prog.d90:routines.c:Solve:57-69:8
 8  Loop_Bound:prog.d90:routines.c:Solve@69=>Count:27-29:8
 9  Loop_Bound:prog.d90:routines.c:main@28=>Foo@36=>Count:27-29:5
10  Warning:prog.d90:main.c:main:17-36:Non-returning subprogram.
11  Wcet:prog.d90:routines.c:Count25:14-22:285
12  Wcet_Call:prog.d90:routines.c:Foo7@45=>Count:25-31:86
13  Wcet:prog.d90:routines.c:Foo7:41-49:155
14  Wcet_Call:prog.d90:routines.c:main@28=>Foo@36=>Count:25-31:105
15  Wcet_Call:prog.d90:routines.c:main@28=>Foo:34-38:116
16  Wcet:prog.d90:routines.c:Ones:76-88:173
17  Wcet_Call:prog.d90:routines.c:Solve@69=>Count:25-31:162
18  Wcet:prog.d90:routines.c:Solve:52-73:3238
19  Wcet:prog.d90:main.c:main:17-36:3844

There are now more Loop_Bound lines and more Wcet and Wcet_Call lines, as expected.

You may wonder how Bound-T can compute a WCET bound of 3844 cycles for the main function although the function contains an eternal loop. The answer is that "assert.txt" contains an assertion (line 12 in the assertion display above) that makes Bound-T include only one iteration of the eternal loop in the WCET.

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.d90:main.c:main:17-36:3844:50:1:3844:3844:main:main.c:17-36
Time_Table:prog.d90:main.c:main:17-36:285:285:1:285:285:Count25:routines.c:14-22
Time_Table:prog.d90:main.c:main:17-36:155:69:1:155:155:Foo7:routines.c:41-49
Time_Table:prog.d90:main.c:main:17-36:1487:1487:10:86:162:Count:routines.c:25-31
Time_Table:prog.d90:main.c:main:17-36:116:11:1:116:116:Foo:routines.c:34-38
Time_Table:prog.d90:main.c:main:17-36:3238:385:1:3238:3238:Solve:routines.c:52-73
Time_Table:prog.d90:main.c:main:17-36:1557:1557:9:173:173:Ones:routines.c:76-88

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
-----     ----      -----     -------------       ----------
3844      50        1         3844      3844      main
3238      385       1         3238      3238      Solve
1557      1557      9         173       173       Ones
1487      1487      10        86        162       Count
285       285       1         285       285       Count25
155       69        1         155       155       Foo7
116       11        1         116       116       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

The IAR compiler for the AVR uses the AVR's hardware stack (the SP stack) only for return addresses. The compiler defines its own stack for stack-allocated parameters and local variables, with the Y register as the stack pointer. Thus, an IAR-compiled AVR program uses two stacks and generally uses different amounts of space on each stack.

Bound-T calls these two stacks the "SP" stack and the "-Y" stack, where the "-" sign indicates that the compiler-defined stack grows downwards (to smaller memory addresses). When Bound-T analyses the stack usage of an IAR-compiled AVR program it does a separate analysis for each stack and produces separate results for each stack.

To compute an upper bound on the amount of stack space used in the example program, starting from the main subprogram, give the command:

boundt_avr -at90s8515 -stack_path -no_time prog.d90 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.d90:main.c:main:36-:Large combined 16-bit literal 65535 taken as signed = -1
 2  Warning:prog.d90:main.c:main:32-36:Eternal loop (no exit edges).
 3  Warning:prog.d90:routines.c:Foo:34-36:Large combined 16-bit literal 65533 taken as signed = -3
 4  Warning:prog.d90:routines.c:Foo7:43-:Large combined 16-bit literal 65526 taken as signed = -10
 5  Stack:prog.d90:routines.c:Count25:14-22:SP:2
 6  Stack:prog.d90:routines.c:Count25:14-22:-Y:2
 7  Stack:prog.d90:routines.c:Count:25-31:SP:0
 8  Stack:prog.d90:routines.c:Count:25-31:-Y:0
 9  Stack:prog.d90:routines.c:Ones:76-88:SP:0
10  Stack:prog.d90:routines.c:Ones:76-88:-Y:0
11  Stack:prog.d90:routines.c:Foo7:41-49:SP:2
12  Stack:prog.d90:routines.c:Foo7:41-49:-Y:4
13  Stack:prog.d90:routines.c:Foo:34-38:SP:2
14  Stack:prog.d90:routines.c:Foo:34-38:-Y:0
15  Stack:prog.d90:routines.c:Solve:52-73:SP:2
16  Stack:prog.d90:routines.c:Solve:52-73:-Y:6
17  Stack:prog.d90:main.c:main:17-36:SP:4
18  Stack:prog.d90:main.c:main:17-36:-Y:8
19  Warning:prog.d90:main.c:main:17-36:Non-returning subprogram.
20  Stack_Path:prog.d90:main.c:main@21=>Count25:21:SP:4:2:2:2
21  Stack_Leaf:prog.d90:routines.c:Count25:14-22:SP:2:2::
22  Stack_Path:prog.d90:main.c:main@32=>Solve:32:-Y:8:2:2:6
23  Stack_Leaf:prog.d90:routines.c:Solve:52-73:-Y:6:6::

The Warning lines repeat the warnings about the immediate operands and the eternal loop, already discussed above. These have no effect on the stack analysis.

The output lines starting with "Stack" show the total stack utilization in each function. Since there are two stacks, the output lines come in pairs, one giving the result for the "SP" stack and the other for the "-Y" stack. For example, the first such pair (lines 5 and 6) shows that the Count25 function uses 2 octets of "SP" space and also two octets of "-Y" space. The "SP" space does not include the stack space used by the return address of Count25; the return-address space is charged to the stack usage of the caller, not to the callee.

You may wonder why Count25 needs two octets of "SP" space although the SP stack is used only for return addresses and the call graph does not show any calls from Count25 to other subprograms. In fact Count25 does call another routine, as shown by the "rcall" instruction in the first basic block in the flow-graph of Count25, but the called routine is an IAR library routine that Bound-T recognises as a "prologue" routine that must be analysed as an integral part of Count25 and not handled as an independent subprogram. Thus this routine does not appear as a separate box in the call-graph.

The final Stack line-pair (lines 17 and 18) shows that the main subprogram, together with its callees, uses a total of 4 octets of "SP" space and 8 octets of "-Y" space.

The output lines starting with Stack_Path and Stack_Leaf show the call-paths, starting from the main function, that use the maximal amount of stack space.

There can be other call-paths that use the same amount of stack space; Bound-T shows only one of these call-paths for each stack. Stack_Path lines are used for the higher levels of the path, and a Stack_Leaf line for the lowest (deepest) level, which ends the call-path. In this example the call-paths have only one call and so there is only one Stack_Path line per stack.

The subprogram named in a Stack_Leaf line is not necessarily a "leaf" subprogram (one that calls no other subprograms). A Stack_Leaf subprogram may call other subprograms but these calls do not increase the overall stack usage.

Note that a given C compiler and run-time library may or may not use a return address for the main function. Note also that the total stack usage from boot (reset) of the processor may be larger than Bound-T shows for the main subprogram, because the startup functions may (and typically do) need some stack space.



Valid HTML 4.01 Transitional