NAME 
compilers/imcc/cfg.c
DESCRIPTION
A basic block is the longest sequence of instructions that we are sure will be executed sequentially: no branches, no labels.
The control-flow graph is a directed graph that reflects the flow of execution between blocks.
Functions
static int check_invoke_type
Given an invoke-type instruction,
returns the type of the invocation.
void find_basic_blocks
Finds all basic blocks in the given IMC_Unit,
expanding PCC calls if first is true.
static void bb_check_set_addr
Looks for a void build_cfg
Once the basic blocks have been computed,
build_cfg computes the dependencies between them.
static void bb_findadd_edge
Finds the placement of the given label and links its containing block to the given basic block.
int blocks_are_connected
Returns true or false whether the given blocks are linked.
static void bb_add_edge
Adds an edge between the two given blocks.
static void bb_remove_edge
Removes the given edge from the graph.
static void free_edge
Frees the memory of an IMC_Unit's edge list.
int edge_count
Counts and returns the number of edges in the specified IMC_Unit.
void life_analysis
This driver routine calls analyse_life_symbol for each reglist in the specified IMC_Unit.
static void analyse_life_symbol
Analyzes the lifetime for a given symbol.
void free_life_info
Frees memory of the life analysis info structures.
static void analyse_life_block
Studies the state of the var r in the block bb.Its job is to set the flags LF_use,
or LF_read,
and record the intervals inside the block where the var is alive.
static void propagate_need
Follows the uses of the given symbol through all of the basic blocks of the unit.
void compute_dominators
Computes the dominators tree of the CFG.
Basic block A dominates B if each path to B passes through ASee gcc:flow.c compute_dominators
void compute_dominance_frontiers
Algorithm to find dominance frontiers described in paper "A Simple,
Fast Dominance Algorithm",
Cooper et al.
(2001)
static void free_dominators
Frees the memory in the given unit related to all dominators.
static void free_dominance_frontiers
Frees the memory in the given unit related to all dominance frontiers.
static void sort_loops
Sorts the loops found in the CFG of the current unit.
void find_loops
Searches for loops in the CFG.
We search for edges that go from a node to one of its dominators.
int natural_preheader
For loop_info,
finds the natural preheader of the loop,
if any,
and returns its index,
otherwise returns -1.
A natural preheader exists if there is only one predecessor to the loop header outside of the loop body,
and if it always transfers control directly to the header.
static void mark_loop
Increases the loop_depth of all the nodes in a loop.
static void free_loops
Frees the memory associated with the loops in this unit.
void search_predecessors_not_in
Searches for predecessor edges for this node not in the given set (and adds them).
static void init_basic_blocks
Initializes the basic blocks memory for this unit.
void clear_basic_blocks
Frees all of the blocks and CFG memory allocated for this unit.
static Basic_block *make_basic_block
Creates,
initializes,
and returns a new Basic_block.
Life_range *make_life_range
Creates and returns a Life_range for the given register at the specified index.
set_addr op in the current unit referring to the given label.
