Flow-graphs from Bound-T analysis of SPARC/ERC32 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 procedure Count, which has different execution bounds when it is called from procedure Foo7 (when Count takes at most 202 cycles), when it is called from procedure Foo (when Count takes at most 249 cycles) and when it is called from procedure Solve (when Count takes at most 766 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 procedure including all three execution contexts.

This procedure is more complex than the Main procedure. The Count procedure 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 4 and 16 times in each of the ten calls to Count, giving a total of 137 executions when the ten calls are summed. Each execution of this block takes 2 cycles, which totals to 274 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 levels lower than the loop-head block is the block at address 02001590 (hex) which contains the loop termination test. Two arrows leave this block as the result of the conditional jump instruction "bg" at the end of this block. The arrows are labeled with their logical conditions. Thus the arrow that exits the loop is taken if one or both of the N and Z flags is set, which means that register R16 is less or equal to zero before the "bg" instruction. Conversely, the loop-continuing arrow is taken if both N and Z are clear, which means that R16 is positive.

You may wonder why the two blocks to which these two arrows lead both start with the same instruction, the "mov r8,r1" at address 0200159C. This results from the fact that the "bg" instruction at the end of the source block for these arrows executes a delayed branch which means that the instruction after the "bg" is always executed, whether the branch condition is true or false, and only then does the branch "take effect" and choose between the instructions at 02001588 (branch taken) or 020015A0 (branch not taken). Bound-T models this delayed branch by splitting the control flow immediately after the "bg" but putting the next instruction ("mov r8,r1") in both descendant blocks.

The WCET bound given in the caption under the drawing shows the total or summary bound including all ten calls (6579 cycles), and the range of WCET bounds for each call (from 202 to 766 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. These are the arrows that enter and leave the basic block at address 0200151C (thanks to delayed branches there are actually two such block; we mean the right-hand one of the two). 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 (right-hand) basic block at 0200151C is never part of the worst-case execution scenario. The reason is that the alternative (left-hand) path through Ones always takes longer, whatever the value of the X parameter.

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 Count25 Flow-graph of Solve

Valid HTML 4.01 Transitional