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
static unsigned int *ig_get_word- RT#48260: Not yet documented!!!
static void ig_set- RT#48260: Not yet documented!!!
unsigned int ig_test- RT#48260: Not yet documented!!!
static unsigned int *ig_allocate- RT#48260: Not yet documented!!!
void imc_reg_alloc- imc_reg_alloc is the main loop of the allocation algorithm. It operates on a single compilation unit at a time.
void free_reglist- RT#48260: Not yet documented!!!
void graph_coloring_reg_alloc- RT#48260: Not yet documented!!!
static void make_stat- some statistics about register usage printed with --verbose --verbose
static void imc_stat_init- registes usage of .pir
static void print_stat- and final
static int reg_sort_f- sort list by line nr
static void sort_reglist- RT#48260: Not yet documented!!!
static void build_reglist- 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- Exclude all already allocated registers (< first_avail) from reglist. This reduced the size of the interference graph significantly
static void build_interference_graph- 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- Compute a DU-chain for each symbolic in a compilation unit
static void compute_one_du_chain- RT#48260: Not yet documented!!!
static int interferes- 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- find available color for register #x in available colors
static int try_allocate- 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- map_colors: calculates what colors can be assigned to the x-th symbol.
static int first_avail- find first available register of the given reg_set
static void allocate_uniq- allocate lexicals or non-volatile in ascending order
static void vanilla_reg_alloc- RT#48260: Not yet documented!!!
static void allocate_lexicals- RT#48260: Not yet documented!!!
static void allocate_non_volatile- RT#48260: Not yet documented!!!
