Control Flow Graph

Control Flow Graph generation and related analyses. More...

Data Structures
struct	t_cfgReg
struct	t_bbNode
struct	t_basicBlock
struct	t_cfg

Macros
#define	CFG_MAX_DEFS   1
	Maximum number of temporary register definitions for each node.
#define	CFG_MAX_USES   2
	Maximum number of temporary register uses for each node.

Basic Blocks
t_bbNode *	bbInsertInstruction (t_basicBlock *block, t_instruction *instr)
t_bbNode *	bbInsertInstructionBefore (t_basicBlock *block, t_instruction *instr, t_bbNode *ip)
t_bbNode *	bbInsertInstructionAfter (t_basicBlock *block, t_instruction *instr, t_bbNode *ip)

Control Flow Graph construction
t_cfg *	programToCFG (t_program *program)
int	cfgIterateNodes (t_cfg *graph, void *context, int(*callback)(t_bbNode *node, int nodeIndex, void *context))
void	cfgToProgram (t_program *program, t_cfg *graph)
void	deleteCFG (t_cfg *graph)

Data Flow Analysis
void	cfgComputeLiveness (t_cfg *graph)
t_listNode *	bbGetLiveIn (t_basicBlock *bblock)
t_listNode *	bbGetLiveOut (t_basicBlock *bblock)

Utilities
void	cfgDump (t_cfg *graph, FILE *fout, bool verbose)

Detailed Description

Control Flow Graph generation and related analyses.

These functions and data structures allow to build, inspect and partially modify a Control Flow Graph (CFG) representation of a program. A program can be converted to and from a CFG, and a CFG can be analyzed to compute the liveness of each register. These facilities are used by the register allocation process.

---

Data Structure Documentation

t_cfgReg

struct t_cfgReg

Data structure which uniquely identifies a register used or defined by a node in a basic block.

Definition at line 32 of file cfg.h.

Data Fields
t_listNode *	mcRegWhitelist	Physical register whitelist. Used by the register allocator.
t_regID	tempRegID	Register identifier.

t_bbNode

struct t_bbNode

Node in a basic block. Represents an instruction, the temporary registers it uses and/or defines, and live temporary registers in/out of the node.

Definition at line 44 of file cfg.h.

Data Fields
t_cfgReg *	defs[CFG_MAX_DEFS]	Set of registers defined by this node ('def' set). NULL slots are ignored.
t_listNode *	in	Set of registers live at the entry of the node ('in' set).
t_instruction *	instr	Pointer to the instruction associated with this node.
t_listNode *	out	Set of registers live at the exit of the node ('out' set).
t_basicBlock *	parent	Pointer to the containing basic block.
t_cfgReg *	uses[CFG_MAX_USES]	Set of registers used by this node ('use' set). NULL slots are ignored.

t_basicBlock

struct t_basicBlock

Structure representing a basic block, i.e. a segment of contiguous instructions with no branches in the middle. The use of basic blocks allows – without loss of generality – to minimize the number of edges in the Control Flow Graph, increasing the performance of code analysis.

Definition at line 63 of file cfg.h.

Data Fields
t_listNode *	nodes	List of instructions in the block.
t_cfg *	parent	The containing basic block.
t_listNode *	pred	List of predecessors to this basic block.
t_listNode *	succ	List of successors to this basic block.

t_cfg

struct t_cfg

Data structure describing a control flow graph.

Definition at line 71 of file cfg.h.

Data Fields
t_listNode *	blocks	List of all the basic blocks, in program order.
t_basicBlock *	endingBlock	Unique final basic block. The control flow must eventually reach here. This block is always empty, and is not part of the 'blocks' list.
t_listNode *	registers	List of all temporary registers used in the program.

Macro Definition Documentation

CFG_MAX_DEFS

#define CFG_MAX_DEFS   1

Maximum number of temporary register definitions for each node.

Definition at line 25 of file cfg.h.

CFG_MAX_USES

#define CFG_MAX_USES   2

Maximum number of temporary register uses for each node.

Definition at line 27 of file cfg.h.

Function Documentation

bbGetLiveIn()

t_listNode * bbGetLiveIn

(

t_basicBlock *

bblock

)

Retrieve the list of live temporary registers entering the given block. Only valid after calling cfgComputeLiveness() on the graph.

Parameters

bblock

The basic block.

Returns

The list of registers. The list is dynamically allocated and the caller is responsible for freeing it.

Definition at line 477 of file cfg.c.

bbGetLiveOut()

t_listNode * bbGetLiveOut

(

t_basicBlock *

bblock

)

Retrieve the list of live temporary registers exiting the given block. Only valid after calling cfgComputeLiveness() on the graph.

Parameters

bblock

The basic block.

Returns

The list of registers. The list is dynamically allocated and the caller is responsible for freeing it.

Definition at line 465 of file cfg.c.

bbInsertInstruction()

t_bbNode * bbInsertInstruction	(	t_basicBlock *	block,
		t_instruction *	instr )

Inserts a new instruction at the end of a block.

Parameters

block	The block where to insert the instruction.
instr	The instruction to insert.

Returns

The newly created basic block node.

Definition at line 184 of file cfg.c.

bbInsertInstructionAfter()

t_bbNode * bbInsertInstructionAfter	(	t_basicBlock *	block,
		t_instruction *	instr,
		t_bbNode *	ip )

Inserts a new instruction after another inside a basic block.

Parameters

block	The block where to insert the instruction.
instr	The instruction to insert.
ip	The basic block node at the insertion point. Must not be NULL.

Returns

The newly created basic block node.

Definition at line 207 of file cfg.c.

bbInsertInstructionBefore()

t_bbNode * bbInsertInstructionBefore	(	t_basicBlock *	block,
		t_instruction *	instr,
		t_bbNode *	ip )

Inserts a new instruction before another inside a basic block.

Parameters

block	The block where to insert the instruction.
instr	The instruction to insert.
ip	The basic block node at the insertion point. Must not be NULL.

Returns

The newly created basic block node.

Definition at line 193 of file cfg.c.

cfgComputeLiveness()

void cfgComputeLiveness

(

t_cfg *

graph

)

Computes graph-level liveness information of temporary registers.

Parameters

graph

The control flow graph.

Definition at line 639 of file cfg.c.

cfgDump()

void cfgDump	(	t_cfg *	graph,
		FILE *	fout,
		bool	verbose )

Print debug information about the control flow graph.

Parameters

graph	The graph to log information about.
fout	The output file.
verbose	Pass a non-zero value to also print additional information about the liveness of the registers.

Definition at line 775 of file cfg.c.

cfgIterateNodes()

int cfgIterateNodes	(	t_cfg *	graph,
		void *	context,
		int(*	callback )(t_bbNode *node, int nodeIndex, void *context) )

Iterates through the nodes in a control flow graph.

Parameters

graph	The graph that must be iterated over.
context	The context pointer that will be passed to the callback function.
callback	The callback function that will be called at each node found. The arguments of the callback are as follows: block: the current block node: the current node nodeIndex: an index, increasing at each new node context: the same context passed to cfgIterateNodes The callback can return a non-zero value to stop the iteration process.

Returns

The value returned by the last callback invocation.

Definition at line 437 of file cfg.c.

cfgToProgram()

void cfgToProgram	(	t_program *	program,
		t_cfg *	graph )

Rebuilds a program from the given CFG.

Parameters

program	The program to be modified.
graph	The control flow graph to be linearized and transformed into a new program.

Definition at line 413 of file cfg.c.

deleteCFG()

void deleteCFG

(

t_cfg *

graph

)

Frees a control flow graph.

Parameters

graph

The graph to be freed.

Definition at line 235 of file cfg.c.

programToCFG()

t_cfg * programToCFG

(

t_program *

program

)

Creates a new control flow graph (CFG) from a program.

Parameters

program

The program to be analyzed and converted into a CFG.

Returns

The new control flow graph, or NULL in case of error.

Definition at line 370 of file cfg.c.