From d19c3aa9e733f5c41956c7e0cbad8e1d03c76798 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Wed, 26 Jan 2005 10:06:50 +0000 Subject: [PATCH] Splitted in two phases pressure/liveness and assignment --- ir/be/bechordal.c | 382 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 360 insertions(+), 22 deletions(-) diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index cb8f22a9f..bda3cfde6 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -15,9 +15,9 @@ #include "iterator.h" #include "irmode_t.h" +#include "irgraph_t.h" #include "irprintf_t.h" #include "irgwalk.h" -#include "irgraph.h" #include "irdump.h" #include "irdom.h" #include "debug.h" @@ -29,6 +29,7 @@ #include "benumb_t.h" #include "besched_t.h" #include "belive_t.h" +#include "bechordal_t.h" @@ -43,29 +44,34 @@ #define BUILD_GRAPH #endif +#ifdef DEBUG_libfirm +#include "fourcc.h" + +/* Make a fourcc for border checking. */ +#define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D') + +#endif /* DEBUG_libfirm */ #define TEST_COLORS 2048 static firm_dbg_module_t *dbg; -/** An interval border. */ -typedef struct _border_t { - struct list_head list; /**< list head for queuing. */ - const ir_node *irn; /**< The node. */ - unsigned step; /**< The number equal to the interval border. */ - unsigned is_def : 1; /**< Does this border denote a use or a def. */ -} border_t; - +/** + * Environment for each of the chordal register allocator phases + */ typedef struct _env_t { struct obstack obst; /**< An obstack for temporary storage. */ +#ifdef BUILD_GRAPH set *graph; /**< The interference graph. */ - bitset_t *live; /**< A live bitset to use in every block. */ - bitset_t *processed; /**< A set marking processed blocks. */ +#endif + + bitset_t *live; /**< A liveness bitset. */ bitset_t *colors; /**< The color mask. */ bitset_t *in_colors; /**< Colors used by live in values. */ int colors_n; /**< The number of colors. */ } env_t; + typedef struct _be_chordal_dump_params_t { int x_dist; int y_dist; @@ -217,19 +223,343 @@ static void dump_ifg(set *edges, const char *filename) } -#endif /* USE_OLD_PHI_INTERFERENCE || BUILD_GRAPH */ +#endif /* BUILD_GRAPH */ +/** + * Add an interval border to the list of a block's list + * of interval border. + * @note You always have to create the use before the def. + * @param env The environment. + * @param head The list head to enqueue the borders. + * @param irn The node (value) the border belongs to. + * @param pressure The pressure at this point in time. + * @param step A time step for the border. + * @param is_def Is the border a use or a def. + * @return The created border. + */ static INLINE border_t *border_add(env_t *env, struct list_head *head, - const ir_node *irn, int step, int is_def) + ir_node *irn, unsigned step, unsigned pressure, + unsigned is_def, unsigned is_real) { - border_t *b = obstack_alloc(&env->obst, sizeof(*b)); + border_t *b; + + if(!is_def) { + border_t *def; + + b = obstack_alloc(&env->obst, sizeof(*b)); + + /* also allocate the def and tie it to the use. */ + def = obstack_alloc(&env->obst, sizeof(*def)); + b->other_end = def; + def->other_end = b; + + /* + * Set the link field of the irn to the def. + * This strongly relies on the fact, that the use is always + * made before the def. + */ + set_irn_link(irn, def); + +#ifdef DEBUG_libfirm + b->magic = BORDER_FOURCC; + def->magic = BORDER_FOURCC; +#endif + } + + /* + * If the def is encountered, the use was made and so was the + * the def node (see the code above). It was placed into the + * link field of the irn, so we can get it there. + */ + else { + b = get_irn_link(irn); + +#ifdef DEBUG_libfirm + assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"); +#endif + } + + b->is_def = is_def; + b->is_real = is_real; b->irn = irn; b->step = step; list_add_tail(&b->list, head); + DBG((dbg, LEVEL_5, "\t\t%s adding %n, step: %d\n", + is_def ? "def" : "use", irn, step)); + return b; } +/** + * Annotate the register pressure to the nodes and compute + * the liveness intervals. + * @param block The block to do it for. + * @param env_ptr The environment. + */ +static void pressure(ir_node *block, void *env_ptr) +{ +/* Convenience macro for a def */ +#define border_def(irn, step, real) \ + border_add(env, head, irn, step, pressure--, 1, real) + +/* Convenience macro for a use */ +#define border_use(irn, step, real) \ + border_add(env, head, irn, step, ++pressure, 0, real) + + env_t *env = env_ptr; + bitset_t *live = env->live; + ir_node *irn; + + int i, n; + unsigned step = 0; + unsigned pressure = 0; + struct list_head *head; + pset *live_in = get_live_in(block); + pset *live_end = get_live_end(block); + + DBG((dbg, LEVEL_1, "Computing pressure in block %n\n", block)); + bitset_clear_all(live); + + /* Set up the border list in the block info */ + head = &get_ra_block_info(block)->border_head; + INIT_LIST_HEAD(head); + + /* + * Make final uses of all values live out of the block. + * They are neccessary to build up real intervals. + */ + for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) { + DBG((dbg, LEVEL_3, "\tMaking live: %n/%d\n", irn, get_irn_graph_nr(irn))); + bitset_set(live, get_irn_graph_nr(irn)); + if(!is_Phi(irn) && is_allocatable_irn(irn)) + border_use(irn, step, 0); + } + + ++step; + + /* + * Determine the last uses of a value inside the block, since they are + * relevant for the interval borders. + */ + sched_foreach_reverse(block, irn) { + DBG((dbg, LEVEL_1, "\tinsn: %n, pressure: %d\n", irn, pressure)); + DBG((dbg, LEVEL_2, "\tlive: %b\n", live)); + + /* Erase the color of each node encountered. */ + set_irn_color(irn, NO_COLOR); + + /* + * If the node defines a datab value, i.e. something, registers must + * be allocated for, add a new def border to the border list. + */ + if(is_allocatable_irn(irn)) { + int nr = get_irn_graph_nr(irn); + + bitset_clear(live, nr); + border_def(irn, step, 1); + +#ifdef BUILD_GRAPH + { + unsigned long elm; + bitset_foreach(live, elm) { + int live_nr = (int) elm; + add_if(env, nr, live_nr); + } + } +#endif + } + + /* + * If the node is no phi node we can examine the uses. + */ + if(!is_Phi(irn)) { + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + + if(is_allocatable_irn(op)) { + int nr = get_irn_graph_nr(op); + + DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op)); + + if(!bitset_is_set(live, nr)) { + border_use(op, step, 1); + bitset_set(live, nr); + } + } + } + } + + ++step; + } + + /* + * Add initial defs for all values live in. + */ + for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) { + if(is_allocatable_irn(irn)) { + + /* Mark the value live in. */ + bitset_set(live, get_irn_graph_nr(irn)); + + /* Add the def */ + border_def(irn, step, 0); + } + } +} + +static void assign(ir_node *block, void *env_ptr) +{ + env_t *env = env_ptr; + struct obstack *obst = &env->obst; + bitset_t *live = env->live; + bitset_t *colors = env->colors; + bitset_t *in_colors = env->in_colors; + + /* The used colors will remain on the obstack. */ + bitset_t *used_colors = bitset_obstack_alloc(obst, env->colors_n); + + /* Mark the obstack level and allocate the temporary tmp_colors */ + void *obstack_level = obstack_base(obst); + bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n); + + const ir_node *irn; + border_t *b; + struct list_head *head = &get_ra_block_info(block)->border_head; + pset *live_in = get_live_in(block); + + bitset_clear_all(live); + bitset_clear_all(colors); + bitset_clear_all(in_colors); + + DBG((dbg, LEVEL_4, "Assigning colors for block %n\n", block)); + DBG((dbg, LEVEL_4, "\tusedef chain for block\n")); + list_for_each_entry(border_t, b, head, list) { + DBG((dbg, LEVEL_4, "\t%s %n/%d\n", b->is_def ? "def" : "use", + b->irn, get_irn_graph_nr(b->irn))); + } + + /* + * Add initial defs for all values live in. + * Since their colors have already been assigned (The dominators were + * allocated before), we have to mark their colors as used also. + */ + for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) { + if(is_allocatable_irn(irn)) { + int col = get_irn_color(irn); + + /* Mark the color of the live in value as used. */ + assert(is_color(col) && "Node must have been assigned a color."); + bitset_set(colors, col); + bitset_set(in_colors, col); + bitset_set(used_colors, col); + + /* Mark the value live in. */ + bitset_set(live, get_irn_graph_nr(irn)); + } + } + + /* + * Mind that the sequence of defs from back to front defines a perfect + * elimination order. So, coloring the definitions from first to last + * will work. + */ + list_for_each_entry_reverse(border_t, b, head, list) { + const ir_node *irn = b->irn; + int nr = get_irn_graph_nr(irn); + + /* + * Assign a color, if it is a local def. Global defs already have a + * color. + */ + if(b->is_def && !is_live_in(block, irn)) { + ra_node_info_t *ri = get_ra_node_info(irn); + int col = NO_COLOR; + + DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors)); + + /* + * Try to assign live out values colors which are not used by live + * in values. + */ +#if 0 + if(is_live_out(block, irn)) { + int next_clear; + + bitset_copy(tmp_colors, colors); + bitset_or(tmp_colors, in_colors); + next_clear = bitset_next_clear(tmp_colors, 0); + col = next_clear != -1 ? next_clear : NO_COLOR; + + DBG((dbg, LEVEL_5, "next clear in only outs %b: %d\n", tmp_colors, col)); + } +#endif + + /* If a color is not yet assigned, do it now. */ + if(!is_color(col)) + col = bitset_next_clear(colors, 0); + + assert(!is_color(get_irn_color(irn)) && "Color must not have assigned"); + assert(!bitset_is_set(live, nr) && "Value def must not have been encountered"); + + bitset_set(colors, col); + bitset_set(used_colors, col); + bitset_set(live, nr); + + ri->color = col; + + DBG((dbg, LEVEL_1, "\tassigning color %d to %n\n", col, irn)); + } + + /* Clear the color upon a use. */ + else if(!b->is_def) { + int col = get_irn_color(irn); + + assert(bitset_is_set(live, nr) && "Cannot have a non live use"); + assert(is_color(col) && "A color must have been assigned"); + + bitset_clear(colors, col); + bitset_clear(live, nr); + } + } + +#ifdef DUMP_INTERVALS + draw_interval_graphs(block, &head, &dump_params); +#endif + +#ifdef DUMP_PRESSURE + { + char buf[128]; + FILE *f; + + ir_snprintf(buf, sizeof(buf), "pres_%s_bl_%N.txt", + get_entity_name(get_irg_entity(irg)), block); + + if((f = fopen(buf, "wt")) != NULL) { + sched_foreach_reverse(block, irn) { + if(is_allocatable_irn(irn)) + ir_fprintf(f, "\"%n\" %d %d\n", irn, sched_get_time_step(irn), + get_ra_node_info(irn)->pressure); + + } + fclose(f); + } + } +#endif + + + /* + * Allocate the used colors array in the blocks ra info structure and + * fill it. + */ + get_ra_block_info(block)->used_colors = used_colors; + + /* Free the auxillary data on the obstack. */ + obstack_free(obst, obstack_level); +} + + +#if 0 static void block_alloc(ir_node *block, void *env_ptr) { env_t *env = env_ptr; @@ -241,16 +571,15 @@ static void block_alloc(ir_node *block, void *env_ptr) bitset_t *used_colors = bitset_malloc(env->colors_n); bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n); ir_graph *irg = get_irn_irg(block); + int also_assign = env->assign; int i, n; - unsigned step = 0; int block_nr = get_block_graph_nr(block); const ir_node *irn; border_t *b; - struct list_head head; + struct list_head *head = &get_ra_block_info(block)->border_head; pset *live_in = get_live_in(block); pset *live_end = get_live_end(block); - ir_node *idom = get_Block_idom(block); /* * Check, if this block has already been processed, if true, return @@ -472,6 +801,8 @@ static void block_alloc(ir_node *block, void *env_ptr) obstack_free(obst, obstack_level); } +#endif + void be_ra_chordal_init(void) { dbg = firm_dbg_register(DBG_BERA); @@ -493,13 +824,18 @@ void be_ra_chordal(ir_graph *irg) #endif env->live = bitset_obstack_alloc(&env->obst, node_count); - env->processed = bitset_obstack_alloc(&env->obst, get_graph_block_count(irg)); env->colors = bitset_obstack_alloc(&env->obst, TEST_COLORS); env->in_colors = bitset_obstack_alloc(&env->obst, TEST_COLORS); env->colors_n = TEST_COLORS; - irg_block_walk_graph(irg, block_alloc, NULL, env); - obstack_free(&env->obst, NULL); + /* First, determine the pressure */ + dom_tree_walk_irg(irg, pressure, NULL, env); + + /* Insert probable spills */ + be_ra_chordal_spill(irg); + + /* Assign the colors */ + dom_tree_walk_irg(irg, assign, NULL, env); #ifdef DUMP_IFG { @@ -520,12 +856,14 @@ void be_ra_chordal_done(ir_graph *irg) #ifdef BUILD_GRAPH free(env->graph); #endif + + obstack_free(&env->obst, NULL); free(env); } int phi_ops_interfere(const ir_node *a, const ir_node *b) { -#ifdef USE_OLD_PHI_INTERFERENCE +#ifdef BUILD_GRAPH ir_graph *irg = get_irn_irg(a); env_t *env = get_irg_ra_link(irg); @@ -534,5 +872,5 @@ int phi_ops_interfere(const ir_node *a, const ir_node *b) return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b)); #else return values_interfere(a, b); -#endif /* USE_OLD_PHI_INTERFERENCE */ +#endif /* BUILD_GRAPH */ } -- 2.20.1