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

PARROT_WARN_UNUSED_RESULT static int check_invoke_type(PARROT_INTERP, NOTNULL(const IMC_Unit *unit), NOTNULL(const Instruction *ins))

TODO: Not yet documented!!!

void find_basic_blocks(PARROT_INTERP, NOTNULL(struct _IMC_Unit *unit), int first)

TODO: Not yet documented!!!

static void bb_check_set_addr(PARROT_INTERP, NOTNULL(IMC_Unit *unit), NOTNULL(Basic_block *bb), NOTNULL(SymReg *label))

TODO: Not yet documented!!!

void build_cfg(PARROT_INTERP, NOTNULL(struct _IMC_Unit *unit))

Once the basic blocks have been computed, build_cfg computes the dependencies between them.

static void bb_findadd_edge(PARROT_INTERP, NOTNULL(IMC_Unit *unit), NOTNULL(Basic_block *from), NOTNULL(SymReg *label))

find the placement of the label, and link the two nodes

PARROT_WARN_UNUSED_RESULT int blocks_are_connected(NOTNULL(const Basic_block *from), NOTNULL(const Basic_block *to))

TODO: Not yet documented!!!

static void bb_add_edge(NOTNULL(IMC_Unit *unit), NOTNULL(Basic_block *from), NOTNULL(Basic_block *to))

TODO: Not yet documented!!!

static void bb_remove_edge(NOTNULL(IMC_Unit *unit), NOTNULL(Edge *edge))

TODO: Not yet documented!!!

static void free_edge(NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

PARROT_WARN_UNUSED_RESULT int edge_count(NOTNULL(const struct _IMC_Unit *unit))

TODO: Not yet documented!!!

void life_analysis(PARROT_INTERP, NOTNULL(const struct _IMC_Unit *unit))

TODO: Not yet documented!!!

static void analyse_life_symbol(NOTNULL(const struct _IMC_Unit *unit), NOTNULL(SymReg *r))

TODO: Not yet documented!!!

void free_life_info(NOTNULL(const struct _IMC_Unit *unit), NOTNULL(SymReg *r))

TODO: Not yet documented!!!

static void analyse_life_block(NOTNULL(Basic_block *bb), NOTNULL(SymReg *r))

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(NOTNULL(Basic_block *bb), NOTNULL(SymReg *r), int i)

TODO: Not yet documented!!!

void compute_dominators(PARROT_INTERP, NOTNULL(struct _IMC_Unit *unit))

Computes the dominators tree of the CFG. Basic block A dominates B, if each path to B passes through A

s. gcc:flow.c compute_dominators

void compute_dominance_frontiers(PARROT_INTERP, NOTNULL(struct _IMC_Unit *unit))

Algorithm to find dominance frontiers described in paper "A Simple, Fast Dominance Algorithm", Cooper et al. (2001)

static void free_dominators(NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

static void free_dominance_frontiers(NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

static void sort_loops(PARROT_INTERP, NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

void find_loops(PARROT_INTERP, NOTNULL(struct _IMC_Unit *unit))

Searches for loops in the CFG. We search for edges that go from a node to one of its dominators.

PARROT_WARN_UNUSED_RESULT int natural_preheader(NOTNULL(const struct _IMC_Unit *unit), NOTNULL(const Loop_info *loop_info))

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(PARROT_INTERP, NOTNULL(IMC_Unit *unit), NOTNULL(const Edge *e))

Increases the loop_depth of all the nodes in a loop

static void free_loops(NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

void search_predecessors_not_in(NOTNULL(const Basic_block *node), NOTNULL(Set *s))

TODO: Not yet documented!!!

static void init_basic_blocks(NOTNULL(IMC_Unit *unit))

TODO: Not yet documented!!!

void clear_basic_blocks(NOTNULL(struct _IMC_Unit *unit))

TODO: Not yet documented!!!

PARROT_CANNOT_RETURN_NULL PARROT_WARN_UNUSED_RESULT static Basic_block *make_basic_block(PARROT_INTERP, NOTNULL(IMC_Unit *unit), NOTNULL(Instruction *ins))

TODO: Not yet documented!!!

PARROT_MALLOC PARROT_CANNOT_RETURN_NULL Life_range *make_life_range(NOTNULL(SymReg *r), int idx)

TODO: Not yet documented!!!