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.

/* A node in the graph. For each node we maintain a list of predecessor nodes and successor nodes.
 */
struct node {
	nodeId_t index;		/* the id of the basic_block */
	uint32_t pre;		/* preorder */
	uint32_t rpost;		/* reverse postorder */
	struct node_list preds; /* predecessor nodes */
	struct node_list succs; /* 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. Instead we store the node ids in a node_list which is simply a dynamic array. Each node_link looks like this:

enum {
	EDGE_TYPE_UNCLASSIFIED = 0,
	EDGE_TYPE_TREE = 1,
	EDGE_TYPE_BACKWARD = 2,
	EDGE_TYPE_FORWARD = 4,
	EDGE_TYPE_CROSS = 8
};
struct node_link {
	nodeId_t node_index;
	unsigned char edge_type;
};

For predecessor nodes the node_index is the id of the predecessor node. For successor nodes the node_index is the id of the successor node.