NAME 
compilers/imcc/reg_alloc_bc.c - by Bill Coffman
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 bits_per_int(void)- RT#48260: Not yet documented!!!
static unsigned int *ig_get_word(int i, int j, int N, unsigned int *edgebits, int *bit_ofs)- RT#48260: Not yet documented!!!
static void ig_set(int i, int j, int N, unsigned int *edgebits)- RT#48260: Not yet documented!!!
int ig_test(int i, int j, int N, unsigned int *edgebits)- RT#48260: Not yet documented!!!
static unsigned int *ig_allocate(int N)- RT#48260: Not yet documented!!!
void imc_reg_alloc(PARROT_INTERP, 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(IMC_Unit *unit)- RT#48260: Not yet documented!!!
static void make_stat(IMC_Unit *unit, int *sets, int *cols)- some statistics about register usage printed with --verbose --verbose
static void imc_stat_init(IMC_Unit *unit)- RT#48260: Not yet documented!!!
static void print_stat(Parrot_Interp interp, IMC_Unit *unit)- RT#48260: Not yet documented!!!
static int reg_sort_f(const void *a, const void *b)- sort list by line nr
static void sort_reglist(IMC_Unit *unit)- RT#48260: Not yet documented!!!
static void build_reglist(Parrot_Interp interp, IMC_Unit *unit, int first)- 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 interfer, but the reglist has them all
static void build_interference_graph(Parrot_Interp interp, IMC_Unit *unit, graph *G)- 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(IMC_Unit *unit)- Compute a DU-chain for each symbolic in a compilation unit
static void compute_one_du_chain(SymReg *r, IMC_Unit *unit)- RT#48260: Not yet documented!!!
static void compute_spilling_costs(Parrot_Interp interp, IMC_Unit *unit)- Computes the cost of spilling each symbol. This is estimated by the number of times the symbol appears, weighted by X*loop_depth
static int interferes(PARROT_INTERP, IMC_Unit *unit, SymReg *r0, 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 void allocate_wanted_regs(IMC_Unit *unit)- try to allocate as much as possible, an optimization ...
static void update_life(Parrot_Interp interp, IMC_Unit *unit, Instruction *ins, SymReg *r, int needs_fetch, int needs_store, int add)- update bb and life_info after spilling this saves 4 costy routines NOTE {lhs_, }use_count are not set again, this is save, when no further optimization pass follows
PARROT_INLINE static void spill(PARROT_INTERP, IMC_Unit *unit, int spilled)- Rewrites the unit instructions, inserting spill code in every ocurrence of the symbol. XXX this has tremendous potential for optimization. Spilling multiple variables would help tremendously.
static int spill_registers(Parrot_Interp interp, IMC_Unit *unit, graph *G)- Use colors from G to allocate registers and spill the high colors.
static void compute_spill_benefit(Parrot_Interp interp, IMC_Unit *unit, graph *G)- Computes the cost of spilling each symbol. This is estimated by the number of times the symbol appears, weighted by X*loop_depth
static void apply_coloring(PARROT_INTERP, IMC_Unit *unit, graph *G)- Use colors from G to allocate registers and spill the high colors.
static int degree_comparator(const void *u, const void *v)- RT#48260: Not yet documented!!!
static int ig_init_graph(PARROT_INTERP, IMC_Unit *unit, graph *G)- RT#48260: Not yet documented!!!
static void ig_clear_graph(IMC_Unit *unit, graph *G)- RT#48260: Not yet documented!!!
static void ig_precolor(PARROT_INTERP, IMC_Unit *unit, graph *G)- Set colors in G to pre-allocated values, from allocate_wanted_regs
static int ig_find_color(SHIM_INTERP, IMC_Unit *unit, int x, const char *avail)- find available color for register #x in available colors
static int ig_color_node(PARROT_INTERP, IMC_Unit *unit, graph *G, int j)- select first available color, over 17
static void ig_remove_node(PARROT_INTERP, IMC_Unit *unit, graph *G, int j)- RT#48260: Not yet documented!!!
static void ig_color_graph(PARROT_INTERP, IMC_Unit *unit, graph *G)- The Matula Maximum Minimum Degree coloring algorithm (Degeneracy Coloring).
- Sort by degrees, remove lowest degree nodes, adjust other degrees, iterate. This algorithm for coloring, was adapted by Chaitin for register allocation. Briggs later made more modifications. The interesting part is spilling, which really has nothing to do with theoretical graph coloring. Stay tuned to this channel as the saga continues ...
