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