OTAWA Manual

Content

4 Control Flow Graphs

OTAWA provides several high-level program representations like Abstract Syntax Trees (AST) or Context Trees (CT). Yet, the Control Flow Graph (CFG) explained here is certainly the most used in the IPET approach.

4.1 Principle of the CFG

A CFG is a graph used to represent the program control flow. The nodes of the graph are blocks of code, called basic blocks, while the edges shows how the execution of the program passes from one block to another one.

There are many different ways to split the code into CFG blocks. The only rule to keep sound basic blocks is that, whatever the execution of a program before the execution of the block:

  1. the first instruction of the block is the first executed and,

  2. when the first instruction is executed, all the following instructions are ever executed subsequently in order.

If we cut the program according to this rule and if we take the maximal sequence of instructions to form block, we get a minimal CFG.

4.2 Getting the CFG

To use the CFG, we must first include the right header file defining the main classes involved (CFGInfo, CFG, BasicBlock).

#include <otawa/cfg.h>

The CFG are built by any code processor implementing the feature CFG_INFO_FEATURE (CFGBuilder is used as a usual default). To get the CFG of a specific function, a CFGInfo object may retrieved from the framework using the CFGInfo::ID property.

ws->require(CFG_INFO_FEATURE);
CFGInfo *info = CFGInfo::ID(ws);

Then, we can ask for the CFG of a specific function, f:

CFG *cfg = info->findCFG("f");

If the function can not be found, the returned value is null. Either the function is not contained in the current program, or the OTAWA CFG builder has not succeeded in its analysis. The function recognition is performed using several sources :

  1. the target of a call instruction is considered as a function entry,

  2. the binary format (currently ELF) contains label definitions whose type are explicit functions,

  3. in the future, OTAWA will also use debugging information from the program.

4.3 Getting the basic blocks

There are many ways to examine the basic blocks of a CFG. First, the CFG class provides a simple unordered iterator CFG::BBIterator to handle all the basic blocks of a CFG. The sample below computes the length in instructions of a CFG.

int length = 0;
for(CFG::BBIterator bb(cfg); bb; bb++)
  length += bb->countInstructions();

Another way to access the basic blocks is to exploration of the graph. This graph has a unique entry (method cfg→entry()) and a unique exit (method cfg→exit()). Both methods returns a BasicBlock *, two syntactic basic block that does not match any code1. They may be used to traverse the CFG forward or backward according to the program control flow.

Then, each basic block is connected to some other ones by directed edges. The input edges may examined with the BasicBlock::InIterator() and the output edges with the BasicBlock::OutIterator(). The edges are represented by the Edge class that provides the following information:

In OTAWA, there are several kinds of edge:

Be careful! As the source BB is ever defined, the target BB of an edge is undefined (null) in the following cases:

In the following example, we use the graph traversal to test if there is a path between two basic blocks, from bb1 to bb2. The PROCESSED property is used to mark the traversed BB and avoid to be caught in loops.

Identifier<bool> PROCESSED("", false);
BasicBlock *queue[MAX], *bb;
int h =0, t = 1;
for(queue[0] = bb1; h < t && queue[h] != bb2; h++) {
  for(BasicBlock::OutIterator edge(queue[h]); edge; edge++)
    if(edge->target() && !PROCESSED(edge->target())) {
      queue[t] = edge->target();
      PROCESSED(queue[t]) = true;
      t++;
    }
}
if(h < t)
  cout << "path from bb1 to bb2 !\n";
else
  cout << "no path from bb1 to bb2.\n";

4.4 Working with a basic block

The basic blocks provides a lot of methods to get information (refer to the API documentation for more details). First, a list of accessors to known the nature of the basic block:

BB instrinsic properties may also be accessed:

To visit instructions in the BB, one may use the BasicBlock::InstIter class as in the example below that computes the size of the BB:

int size = 0;
for(BasicBlock::InstIter inst(bb); inst; inst++)
  size += inst->size();

1 the unity of the graph ends makes easier some algorithm applied on the CFG