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))- TODO: Not yet documented!!!
static void ig_set(int i, int j, int N, NOTNULL(unsigned int *graph))- TODO: Not yet documented!!!
int ig_test(int i, int j, int N, NOTNULL(unsigned int *graph))- TODO: Not yet documented!!!
PARROT_CANNOT_RETURN_NULL static unsigned int *ig_allocate(int N)- TODO: 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))- TODO: Not yet documented!!!
void graph_coloring_reg_alloc(PARROT_INTERP, NOTNULL(IMC_Unit *unit))- TODO: 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(NOTNULL(const void *a), NOTNULL(const void *b))- sort list by line nr
static void sort_reglist(NOTNULL(IMC_Unit *unit))- TODO: 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))- TODO: 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(NOTNULL(const IMC_Unit *unit), NOTNULL(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))- TODO: Not yet documented!!!
static void allocate_lexicals(PARROT_INTERP, NOTNULL(IMC_Unit *unit))- TODO: Not yet documented!!!
static void allocate_non_volatile(PARROT_INTERP, NOTNULL(IMC_Unit *unit))- TODO: Not yet documented!!!
