Flow-graphs from Bound-T analysis of Intel-8051 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". Since this subprogram has no loops or branches at all, all arrows in its flow graph are executed once.

A box that has no arrows leaving it represents a basic block that ends by returning from the subprogram. In this flow-graph only the last block is a return block. No "return" instruction is visible in the last block because the compiler has optimized the tail call to Solve into a simple jump to Solve, which means that when the return instruction in Solve also returns from main.

Flow-graph of main

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 above showed 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 Foo (when Count takes at most 240 cycles) and when it is called from subprogram Solve (when Count takes at most 422 cycles). This is illustrated in the context-specific form of the call-graph drawing.

Flow graph of Count

The flow graph drawing on the right shows a summary of the nine calls of the Count subprogram including both execution contexts.

This subprogram is more complex than the main subprogram. This subprogram contains 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).

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 10 and 17 times in each of the nine calls to Count, for a total of 146 executions. Each execution of this block takes 2 cycles, which totals to 292 cycles for all nine 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 "cjne" in this block. The arrows are labeled with their logical conditions. Thus the arrow from the loop head to the return block (which contains just a "ret" instruction) is taken if register r2 (memory location d02) is zero; the other arrow is taken if r2 is not zero and leads to a large block that forms the body of the loop. The arrow back from this block to the loop head is unconditional and is thus labeled with the condition "true".

The WCET bound given in the caption under the drawing also shows the total or summary bound including all nine calls (3616 cycles), and the range of WCET bounds for each call (from 240 to 422 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 execution 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 "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 did not appear in the earlier examples: One arrow is drawn with a thinner line than the other arrows. This is the arrow that goes from the basic block at address 00E8 to the basic block at address 00ED. It is drawn with a thin line because it is not executed at all in the worst-case execution scenario; this is also shown in its label "0", for zero executions. The reason why it is not executed in the worst-case scenario is evident: the alternative arrow from the 00E8 block leads to a longer execution time, since the block at address 00EC is executed and not bypassed.

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 Solve

The flow graphs of Foo and Solve follow. The flow graph of Foo is simple because it has no loops. The flow graph of Solve is more complex because of the loop and conditional statements.

Flow-graph of Foo Flow-graph of Solve

Valid HTML 4.01 Transitional