NAME

compilers/imcc/reg_alloc.c

DESCRIPTION

Register allocator:

This is a brute force register allocator. It uses a graph-coloring algorithm, but the implementation is very kludgy.

It is a partial implementation of a Briggs-style register allocator The following parts are just missing:

 - Renumbering
 - Coaelesceing

Functions

PARROT_CANNOT_RETURN_NULL static unsigned int *ig_get_word(int i, int j, int N, NOTNULL(unsigned int *graph), NOTNULL(int *bit_ofs))

RT#48260: Not yet documented!!!

static void ig_set(int i, int j, int N, NOTNULL(unsigned int *graph))

RT#48260: Not yet documented!!!

int ig_test(int i, int j, int N, NOTNULL(unsigned int *graph))

RT#48260: Not yet documented!!!

PARROT_CANNOT_RETURN_NULL static unsigned int *ig_allocate(int N)

RT#48260: Not yet documented!!!

void imc_reg_alloc(PARROT_INTERP, NULLOK(IMC_Unit *unit))

imc_reg_alloc is the main loop of the allocation algorithm. It operates on a single compilation unit at a time.

void free_reglist(NOTNULL(IMC_Unit *unit))

RT#48260: Not yet documented!!!

void graph_coloring_reg_alloc(PARROT_INTERP, NOTNULL(IMC_Unit *unit))

RT#48260: Not yet documented!!!

static void make_stat(NOTNULL(IMC_Unit *unit), NULLOK(int *sets), NULLOK(int *cols))

some statistics about register usage printed with --verbose --verbose

static void imc_stat_init(NOTNULL(IMC_Unit *unit))

registes usage of .pir

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

and final

static int reg_sort_f(ARGIN(const void *a), ARGIN(const void *b))

sort list by line nr

static void sort_reglist(NOTNULL(IMC_Unit *unit))

RT#48260: Not yet documented!!!

static void build_reglist(Parrot_Interp interp, NOTNULL(IMC_Unit *unit))

make a linear list of IDENTs and VARs, set n_symbols TODO split the whole life analysis into 4, one per register kind registers of different kind never interfere, but the reglist has them all

Registers are now sorted according to the line on which their usage starts, which means that they are sorted by basic block numbers too.

Run through them and allocate all that don't overlap in one bunch.

static void rebuild_reglist(NOTNULL(IMC_Unit *unit))

Exclude all already allocated registers (< first_avail) from reglist. This reduced the size of the interference graph significantly

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

Creates the interference graph between the variables.

Data structure is a 2-d array 'interference_graph' bitmap where row/column indices represent the same index in the list of all symbols (unit->reglist) in the current compilation unit.

Two variables interfere when they are alive at the same time.

static void compute_du_chain(NOTNULL(IMC_Unit *unit))

Compute a DU-chain for each symbolic in a compilation unit

static void compute_one_du_chain(NOTNULL(SymReg *r), NOTNULL(IMC_Unit *unit))

RT#48260: Not yet documented!!!

static int interferes(PARROT_INTERP, NOTNULL(IMC_Unit *unit), NOTNULL(SymReg *r0), NOTNULL(SymReg *r1))

See if r0's chain interferes with r1.

We currently decide that two vars interfere if they are both alive at any point. This could be improved, requiring that one is alive at the point of _definition_ of the other.

static int ig_find_color(ARGIN(const IMC_Unit *unit), ARGIN(const char *avail))

find available color for register #x in available colors

static int try_allocate(PARROT_INTERP, NOTNULL(IMC_Unit *unit))

Color the graph, assigning registers to each symbol:

We just proceed popping items from the stack and assigning a free color to them.

If we run out of colors, then we need to spill the top node.

static void map_colors(NOTNULL(IMC_Unit *unit), int x, NOTNULL(unsigned int *graph), NOTNULL(char *avail), int typ, int already_allocated)

map_colors: calculates what colors can be assigned to the x-th symbol.

static int first_avail(NOTNULL(IMC_Unit *unit), int reg_set, NULLOK(Set **avail))

find first available register of the given reg_set

static void allocate_uniq(PARROT_INTERP, NOTNULL(IMC_Unit *unit), int usage)

allocate lexicals or non-volatile in ascending order

static void vanilla_reg_alloc(SHIM_INTERP, NOTNULL(IMC_Unit *unit))

RT#48260: Not yet documented!!!

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

RT#48260: Not yet documented!!!

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

RT#48260: Not yet documented!!!