Flow-graphs from Bound-T analysis of ARM7 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 55 cycles), when it is called from subprogram Foo (when Count takes at most 67 cycles) and when it is called from subprogram Solve (when Count takes at most 199 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).

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 17 times in each of the ten calls to Count, giving a total of 147 executions when the ten calls are summed. Each execution of this block takes 2 cycles, which totals to 292 cycles for 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 "ble" 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 "bx r14" instruction) is taken if register r0 is less or equal to zero; the other arrow is taken if r0 is greater than 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 ten calls (1714 cycles), and the range of WCET bounds for each call (from 55 to 199 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 eight 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 eight executions after the semicolon.

This flow-graph illustrates a feature of the flow-graph drawings that did not appear in the earlier examples: two arrows are drawn with a thinner line than the other arrows. There are the arrows that enter and leave the basic block at address 4254. These arrows are drawn with a thin line because they are not executed at all in the worst-case execution scenario; this is also shown by their label "0", for zero executions. In other words, the basic block at 4254 is always passed over, although it would contribute one cycle of execution time if it were executed. The reason is that the alternative arrow, which bypasses block 4254 by going directly from block 424C to block 4248, takes 2 cycles to execute. This is the "branch penalty" for reloading the pipeline. (The compiler has not made the best code here; instead of the "beq r0" branch that ends block 4C4C, it would have been better to make the instruction in block 4254 conditional, of the form "addne r1,r1,1". This would have saved 2 cycles per loop.)

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 Foo

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