Example of Bound-T analysis of an H8/300 program

Introduction

This note shows how a small 'C' program for the H8/300 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 two 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 H8/300 target processor, model H8/3292, using the GNU gcc compiler. The executable file is named "prog.coff" 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 the H8/300 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 H8/300 executable "prog.coff" and the assertion file "assertions.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 COFF 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_h8_300 -3292 prog.coff _Count25

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.coff:routines.c:_Count25:33:Immediate operand 254 taken as signed = -2
 2  Loop_Bound:prog.coff:routines.c:_Count25:33-35:12
 3  Wcet:prog.coff:routines.c:_Count25:30-37:234
 4  Also:prog.coff:main.c:_Count25:55:

Line 1 reports that Bound-T has encountered, in the H8/300 program, an instruction with an immediate (static constant) operand which has the value 254 (decimal) if interpreted as an unsigned number, but that Bound-T has preferred to interpret this operand as the negative number -2 (using two's complement). Such warnings can usually be ignored and you can suppress them with the command-line option -warn no_sign. The warning points to line 33 in the file routines.c; this line contains the C text

   for (; u > 0; u -= 2)

so it indeed seems that the interpretation -2 is correct.

The second output line (line 2) reports that Bound-T has determined that the loop in the Count25 routine, on lines 33-35 in the file "routines.c", iterates at most 12 times. To be precise, the "back edge" of the loop is executed at most 12 times. If you look at the machine code (using, for example, the Bound-T option -trace decode), you can see that this is a "bottom-test" loop, so the body of the loop is actually executed 13 times.

The third output line reports that Bound-T has determined an upper bound of 234 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 30-37. The last output line, starting with "Also", shows that the compiler has also connected line number 55 in the source-file "main.c" to the address of some instruction in the function Count25. This is probably an artifact of the program's source-code ending at this point.

Full analysis fails

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

boundt_h8_300 -3292 prog.coff _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.coff:main.c:_main:51:Eternal loop (no exit edges).
 2  Warning:prog.coff:routines.c:_Count25:33:Immediate operand 254 taken as signed = -2
 3  Warning:prog.coff:routines.c:_Foo7:63-:Immediate operand 65528 taken as signed = -8
 4  Warning:prog.coff:routines.c:_Count:42:Immediate operand 254 taken as signed = -2
 5  Loop_Bound:prog.coff:routines.c:_Count25:33-35:12
 6  Loop_Bound:prog.coff:routines.c:_Foo7@60-=>_Count:42-44:3
 7  Loop_Bound:prog.coff:routines.c:_Solve:72-84:7
 8  Loop_Bound:prog.coff:routines.c:_main@43-=>_Foo@51-=>_Count:42-44:4
 9  Warning:prog.coff:main.c:_main:33-51:Non-returning subprogram.
10  Wcet:prog.coff:routines.c:_Count25:30-37:234
11  Also:prog.coff:main.c:_Count25:55:
12  Wcet_Call:prog.coff:routines.c:_Foo7@60-=>_Count:41-46:94
13  Wcet:prog.coff:routines.c:_Foo7:57-64:168
14  Wcet_Call:prog.coff:routines.c:_main@43-=>_Foo@51-=>_Count:41-46:110
15  Wcet_Call:prog.coff:routines.c:_main@43-=>_Foo:50-53:128
16  Error:prog.coff:main.c:_main:33-51:Could not be fully bounded.
17  
18  
19  _main
20     Loop unbounded (eternal) at main.c:51, offset 0024
21     _main@47-=>_Solve@75-=>_Ones
22        Loop unbounded (exits at end only) at routines.c:99-100, offset 0006
23     _main@47-=>_Solve@84-=>_Count
24        Loop unbounded (exits at end only) at routines.c:42-44, offset 0006

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

The next three Warning lines (lines 2-4) report on the interpretation of immediate operands and can be ignored.

The next four output lines (Loop_Bound lines 5-8) 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 (link-name "_Count"), at lines 42-44 in "routines.c", has an upper bound of 3 iterations when Count is called from the function Foo7 through the call at line 60. The line-number is given with a trailing hyphen in the form "60-" because the compiler did not map the actual call instruction to line 60, but some instruction just before the call was mapped to line 60.

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

After the Loop_Bound lines, the Warning line (line 9) reports that the main function never returns (because it ends with an eternal loop). The main function is in the file "main.c", lines 33-51.

The following Wcet and Wcet_Call lines (lines 10-15) show WCET bounds that Bound-T has computed for those functions where it was able to bound the loops. Wcet_Call is like Wcet but shows a context-dependent WCET bound. For example, line 12 reports that the function Count takes at most 94 machine cycles when it is called from Foo7 at line 60. In contrast, the line 14 reports that when Count is called from the function Foo it has the larger WCET bound of 110 cycles. This difference comes from the different loop-bounds in the two contexts.

The Error line (line 16) 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 (in line 6) when Count was called from Foo7 and when Count was called from main via Foo (line 8), but those bounds do not apply when Count is called from Solve because the actual parameters are different, and in fact the call from Solve does give a static 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 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 20 through 24 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 "_Solve|_k" <= 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 (note that it must be identified by its link-name "_Ones"). Line 2 specifies that the loop in Onesrepeats 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 variable k, which is local to Solve, has a value that is at most 16. This holds because k is assigned the return value from Ones, which is between 0 and 16 as explained above.

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

boundt_h8_300 -3292 -assert assn.txt prog.coff _main

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

 1  Warning:prog.coff:main.c:_main:51:Eternal loop (no exit edges).
 2  Warning:prog.coff:routines.c:_Count25:33:Immediate operand 254 taken as signed = -2
 3  Warning:prog.coff:routines.c:_Foo7:63-:Immediate operand 65528 taken as signed = -8
 4  Warning:prog.coff:routines.c:_Count:42:Immediate operand 254 taken as signed = -2
 5  Loop_Bound:prog.coff:routines.c:_Count25:33-35:12
 6  Loop_Bound:prog.coff:routines.c:_Foo7@60-=>_Count:42-44:3
 7  Loop_Bound:prog.coff:routines.c:_Solve:72-84:7
 8  Loop_Bound:prog.coff:routines.c:_Solve@84-=>_Count:42-44:7
 9  Loop_Bound:prog.coff:routines.c:_main@43-=>_Foo@51-=>_Count:42-44:4
10  Warning:prog.coff:main.c:_main:33-51:Non-returning subprogram.
11  Wcet:prog.coff:routines.c:_Count25:30-37:234
12  Also:prog.coff:main.c:_Count25:55:
13  Wcet_Call:prog.coff:routines.c:_Foo7@60-=>_Count:41-46:94
14  Wcet:prog.coff:routines.c:_Foo7:57-64:168
15  Wcet_Call:prog.coff:routines.c:_main@43-=>_Foo@51-=>_Count:41-46:110
16  Wcet_Call:prog.coff:routines.c:_main@43-=>_Foo:50-53:128
17  Wcet:prog.coff:routines.c:_Ones:92-104:342
18  Wcet_Call:prog.coff:routines.c:_Solve@84-=>_Count:41-46:158
19  Wcet:prog.coff:routines.c:_Solve:68-88:4356
20  Wcet:prog.coff:main.c:_main:33-51:4950

Lines 1 through 4 and line 10 give the same Warnings as in the earlier analysis, without assertions. Lines 5 through 7 and 9 give the same Loop_Bounds as in the earlier analysis. Line 8 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 11 through 20 report WCET estimates (upper bounds) for various subprograms and calls. The last line (line 20) is the final result: the WCET of main is at most 4950 cycles. To find this value, Bound-T also computed WCET bounds for Count25 (234 cycles, line 11), Foo7 (168 cycles, line 14), Ones (342 cycles, line 17), and Solve (4356 cycles, line 19). 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 13, 15, 16, and 18.

You may wonder how Bound-T can compute a WCET bound of 4950 cycles for the main function although the function contains an eternal loop. The answer is the assertion (line 12 in the assertion file) 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.coff:main.c:_main:33-51:4950:64:1:4950:4950:_main:main.c:33-51
Time_Table:prog.coff:main.c:_main:33-51:234:234:1:234:234:_Count25:routines.c:30-37
Time_Table:prog.coff:main.c:_main:33-51:168:74:1:168:168:_Foo7:routines.c:57-64
Time_Table:prog.coff:main.c:_main:33-51:1468:1468:10:94:158:_Count:routines.c:41-46
Time_Table:prog.coff:main.c:_main:33-51:128:18:1:128:128:_Foo:routines.c:50-53
Time_Table:prog.coff:main.c:_main:33-51:4356:356:1:4356:4356:_Solve:routines.c:68-88
Time_Table:prog.coff:main.c:_main:33-51:2736:2736:8:342:342:_Ones:routines.c:92-104

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
-----     ----      -----     -------------       ----------
4950      64        1         4950      4950      _main
4356      356       1         4356      4356      _Solve
2736      2736      8         342       342       _Ones
1468      1468      10        94        158       _Count
234       234       1         234       234       _Count25
168       74        1         168       168       _Foo7
128       18        1         128       128       _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 H8/300 stack space used in the example program, starting from the main subprogram, give the command:

boundt_h8_300 -3292 -stack_path -no_time prog.coff _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.coff:main.c:_main:51:Eternal loop (no exit edges).
 2  Warning:prog.coff:routines.c:_Count25:33:Immediate operand 254 taken as signed = -2
 3  Warning:prog.coff:routines.c:_Foo7:63-:Immediate operand 65528 taken as signed = -8
 4  Warning:prog.coff:routines.c:_Count:42:Immediate operand 254 taken as signed = -2
 5  Stack:prog.coff:routines.c:_Count25:30-37:SP:0
 6  Also:prog.coff:main.c:_Count25:55:
 7  Stack:prog.coff:routines.c:_Count:41-46:SP:0
 8  Stack:prog.coff:routines.c:_Ones:92-104:SP:0
 9  Stack:prog.coff:routines.c:_Foo7:57-64:SP:4
10  Stack:prog.coff:routines.c:_Foo:50-53:SP:2
11  Stack:prog.coff:routines.c:_Solve:68-88:SP:6
12  Stack:prog.coff:main.c:_main:33-51:SP:10
13  Warning:prog.coff:main.c:_main:33-51:Non-returning subprogram.
14  Stack_Path:prog.coff:main.c:_main@47-=>_Solve:47-:SP:10:4:4:6
15  Stack_Leaf:prog.coff:routines.c:_Solve:68-88:SP: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. For example, the first such line (line 5) shows that the Count25 function uses no stack-space. Note that the stack-space used by the return address is charged to the caller, not to the callee.

The output lines starting with Stack_Path and Stack_Leaf show the call-path, starting from the main function, that uses the maximal amount of stack space. This is the path main => Solve. There can be other call-paths that use the same amount of stack space; Bound-T shows only one of these call-paths. 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-path has only one call and so there is only one Stack_Path line.

The four numbers at the end of the Stack_Path line show that the main function uses a total of 10 octets of stack space, of which 4 octets are used for its own purposes and 6 by its callees. The total and local usage (10 and 4 octets, respectively) include the return addresses that are pushed on the stack when the main function calls some other functions, such as Solve.

The Stack_Leaf line shows that the Solve function itself uses 6 octets of stack. The call-path ends here so this also an upper bound on the total stack usage of Solve and is not exceeded even when Solve calls other functions. Note that the return addresses for such calls from Solve are included in the stack usage of Solve (these 6 octets).

The total stack usage for the main function is simply the sum of the usages of main (4) and Solve (6), giving 10 octets, or 12 if we add the space for the return address of the main function. 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, because the startup functions may (and typically do) need some stack space.



Valid HTML 4.01 Transitional