Flow-graphs from Bound-T analysis of AVR example

Flow graph of main

Bound-T can draw control-flow graphs (or flow graphs, for short) of the analysed subprograms. The image on the right shows the simple flow graph of the main subprogram. It begins with the subprogram name at the top and an arrow from the name, to the box that represents the entry point of the subprogram.

Most boxes in a flow-graph diagram represents basic blocks of code. A basic block is a sequence of instructions that is entered only at the first instruction and left only at the last instruction. Depending on command-line options Bound-T can label (fill in) the box with various data about the basic block. In this example we have used the option "-draw decode" to include the disassembled instructions and their addresses, and the option "-draw no_line" to omit the name of the source-code file and the numbers of the source lines that give rise to these instructions. The last two text lines in each box show the number of times this basic block is executed in the worst-case scenario ("count") and the WCET bound ("time").

The other boxes in a flow-graph diagram represent the execution of other sub­programs due to calls from the present subprogram. These boxes are labelled with "call <callee name>" followed by the execution "count" and the execution "time" bound. The last line in the box for a callee shows the part of the time that is spent in the callee (which currently is all of the "time" for this box; in a future version of Bound-T there will be an option to compress the flow-graphs by combining these call boxes with the basic-block box that contains the call instruction, and then this "callees" label will be significant).

The arrows show the flow of control between the basic blocks and callees. The labels on the arrows show the logical condition of taking this arrow and how many times the arrow is executed in the worst-case scenario. Since the main subprogram has no conditional branches all the conditions are "true", and all arrows in its flow graph are executed once, until we come to the loop at the end. The loop-head box is is labeled with "loop #1" where "1" is the number of of the loop (within this subprogram). In fact, thanks to the "repeats 1 time" assertion on this loop, its looping arrow is also executed once (that is to say, Bound-T includes only one execution of this eternal loop in the WCET bound).

A box that has no arrows leaving it represents a basic block that ends by returning from the subprogram. In this flow-graph no block is a return block, because main ends with the eternal loop and never returns to its caller.

One context, or summary total of all contexts

A flow-graph drawing can represent one execution context of the subprogram, or the total of all execution contexts of this subprogram. To be precise, in the first case the flow graph shows the sub­program's execution bounds for one context, while in the second case it shows the sum total of all calls to this subprogram, in all contexts, that are included in the worst-case scenario. The flow graph of main shows one execution context of main (and this is the only execution context since main is the root subprogram of this example analysis).

A "total" flow-graph drawing differs from a one-context drawing only when the subprogram has context-specific execution bounds in the analysis. In this example program this happens only for the subprogram Count, which has different execution bounds when it is called from subprogram Foo7 (when Count takes at most 86 cycles), when it is called from subprogram Foo (when Count takes at most 105 cycles) and when it is called from subprogram Solve (when Count takes at most 162 cycles). This is illustrated in the context-specific form of the call-graph drawing.

Flow-graph of main

Flow graph of Count

The flow graph drawing on the right shows a summary of the ten calls of the Count subprogram including all three execution contexts.

This subprogram is more complex than the main subprogram. This subprogram contains conditional branches that form a loop, and as you can see the box at the head of the loop is labeled with "loop #1" where "1" is the number of of the loop (within this subprogram). The loop contains one other block, the block starting at address 0000B4 hex.

In a summary flow-graph drawing, the execution-count and execution-time labels in boxes and arrows show first the value (or value range) for one call of the subprogram, and then after a semicolon comes the total (summary) value for all calls of the subprogram. For example, the loop-head block is executed between 5 and 9 times in each of the ten calls to Count, giving a total of 83 executions when the ten calls are summed. Each execution of this block takes 4 cycles, which totals to 332 cycles for the 83 executions of this block in the ten calls of Count.

Note that Bound-T has not actually executed the program, but has deduced that the loop can repeat at most by these numbers, which for Count depend on the parameter values and therefore vary.

Two arrows leave the loop-head block, as a result of the conditional jump instruction "brge" at the end of this block. The arrows are labeled with their logical conditions. Thus the arrow from the loop head towards the return point is taken if the N flag is set, which means that the value in the register pair R17:R16 is less than 1 (from the "cpi" and "cpc" instructions in the loop-head block). The other arrow is taken if the N flag is clear, which means that R17:R18 holds a value greater or equal to 1.

The WCET bound given in the caption under the drawing also shows the total or summary bound including all ten calls (1487 cycles), and the range of WCET bounds for each call (from 86 to 162 cycles).

Summary flow-graph of Count

Flow-graph of Ones

The one-context form of a flow-graph drawing also shows total execution counts and times if the context in question is called more than once in the worst-case scenario. This happens here for example with the subprogram Ones.

The subprogram Ones has context-inde­pen­dent exe­cution bounds. The flow-graph drawing at the right shows these bounds. However, the subprogram is called a total of nine times in the worst-case scenario, as indicated in the label of the entry arrow and also in the caption at the bottom. (The reason why Bound-T here over-estimates the number of calls, which is really at most eight, is explained in the main text.)

The "count" and "time" in the box and arrow labels give the value for one execution before the semicolon and for all nine executions after the semicolon.

This flow-graph illustrates a feature of the flow-graph drawings that does not appear in the flow-graph of Count and main: one arrow is drawn with a thinner line than the other arrows. This is the arrow from the basic block at address 000148 to the block at 00014E. This arrow is drawn with a thin line because it is not executed at all in the worst-case execution scenario; this is also shown by its label "0", for zero executions.

Bound-T does not include any executions of this arrow in the worst-case scenario because the alternative path through the basic block at 00014C takes longer (2 cycles for the block, instead of 1 cycle for the arrow) and Bound-T has no logical reason or assertion to limit the number of executions of this basic block.

Arrow styles

Bound-T uses three different line styles for arrows in flow graphs:

  • bold style for arrows that are executed in the worst-case scenario.
  • thin style for arrows that are not executed in the worst-case scenario, because there are other execution paths that take more time.
  • dotted style for arrows that can never be executed because their conditions are false (in the present context).

This example program has no examples of the third kind of arrow, which is also called an infeasible path.

Flow-graph of Ones

Flow-graphs of Foo and Foo7

The flow-graphs of Foo and Foo7 are simple because they have no loops.

Flow-graph of Foo Flow-graph of Foo7

Flow-graphs of Count25 and Solve

The flow-graphs of Count25 and Solve are more complex because of loops and conditional statements.

Flow-graph of Foo Flow-graph of Solve

Valid HTML 4.01 Transitional