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 allRegisters 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!!!