Control Flow Graph

Data Structures

• The basic blocks themselves do not have the graph structure.
• Each basic block has a unique nodeId, which can be used to efficiently retrieve the basic block from the proc that owns it.
• Our graph structure only knows about nodeIds. So it is a separate structure that can be built any time.
• We will also store additional info against basic blocks as auxiliary data - either separately or by attaching to graph node. This way different analysis runs can define their own data.

MIR comparison

• In MIR the basic block has the graph structure embedded.

struct bb {
  size_t index, pre, rpost, bfs; /* preorder, reverse post order, breadth first order */
  unsigned int flag;             /* used for CCP */
  DLIST_LINK (bb_t) bb_link;
  DLIST (in_edge_t) in_edges;
  /* The out edges order: optional fall through bb, optional label bb,
     optional exit bb.  There is always at least one edge.  */
  DLIST (out_edge_t) out_edges;
  DLIST (bb_insn_t) bb_insns;
  size_t freq;
  bitmap_t in, out, gen, kill; /* var bitmaps for different data flow problems */
  bitmap_t dom_in, dom_out;    /* additional var bitmaps LICM */
  loop_node_t loop_node;
  int max_int_pressure, max_fp_pressure;
};

• in_edges are I think what we call predecessors of a basic block.
• out_edges are the successors of a basic block.
• bb_insns are the instructions.

Compare this to our basic block:

/* Basic block */
struct basic_block {
	nodeId_t index; /* The index of the block is a key to enable retrieving the block from its container */
	struct instruction_list *insns;
};

In our case the CFG info is stored separately. Each basic block has a corresponding node in the graph.

struct node {
	nodeId_t index; /* the id of the basic_block */
	uint32_t pre; /* preorder */
	uint32_t rpost; /* reverse postorder? */
	struct edge_list in_edges; /* in_edges come from predecessor nodes */
	struct edge_list out_edges; /* out_edges lead to successor nodes */
};

In MIR the edge type is as below:

struct edge {
  bb_t src, dst;
  DLIST_LINK (in_edge_t) in_link;
  DLIST_LINK (out_edge_t) out_link;
  unsigned char back_edge_p;
  unsigned char skipped_p; /* used for CCP */
};

• It has pointers to basic blocks, source and dest.
• Link fields are I think for the linked list in the basic block's in and out edges list.

We do not have an edge structure as yet. In our case the list of edges is stored in an array as shown below.

enum {
	EDGE_TYPE_UNCLASSIFIED = 0,
	EDGE_TYPE_TREE = 1,
	EDGE_TYPE_BACKWARD = 2,
	EDGE_TYPE_FORWARD = 4,
	EDGE_TYPE_CROSS = 8
};
struct edge {
	nodeId_t to_index; /* destination edge */
	unsigned char edge_type;
};