X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=2fcb990d5cba1c3cf21446da243f532866278de8;hb=3a2cc1d47466d98f2f09a22425d122051a37a5e7;hp=bda3cfde604eb640132beba9c52818b666726c80;hpb=d19c3aa9e733f5c41956c7e0cbad8e1d03c76798;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index bda3cfde6..2fcb990d5 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -2,7 +2,11 @@ * Chordal register allocation. * @author Sebastian Hack * @date 8.12.2004 + * + * Copyright (C) Universitaet Karlsruhe + * Released under the GPL */ + #ifdef HAVE_CONFIG_H #include "config.h" #endif @@ -10,6 +14,7 @@ #include #include "obst.h" +#include "pset.h" #include "list.h" #include "bitset.h" #include "iterator.h" @@ -25,148 +30,37 @@ #include "beutil.h" #include "besched.h" -#include "bera_t.h" #include "benumb_t.h" #include "besched_t.h" #include "belive_t.h" -#include "bechordal_t.h" +#include "bearch.h" +#include "bechordal_t.h" +#include "bechordal_draw.h" +#define DBG_LEVEL 0 +#define NO_COLOR (-1) #undef DUMP_INTERVALS #undef DUMP_PRESSURE -#define DUMP_IFG +#undef DUMP_IFG -#define BUILD_GRAPH - -#ifdef USE_OLD_PHI_INTERFERENCE -#undef BUILD_GRAPH -#define BUILD_GRAPH +#if defined(DUMP_IFG) && !defined(BUILD_GRAPH) +#error Must define BUILD_GRAPH to be able to dump it. #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; -/** - * 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. */ -#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; - double font_scale; -} be_chordal_dump_params_t; - -static const be_chordal_dump_params_t dump_params = { - 30, - 10, - 4 -}; - -static void draw_interval_graphs(ir_node *block, - struct list_head *border_head, - const be_chordal_dump_params_t *params) -{ - int i; - int x_dist = params->x_dist; - int y_dist = params->y_dist; - ir_graph *irg = get_irn_irg(block); - - FILE *f; - char buf[1024]; - - ir_snprintf(buf, sizeof(buf), "intv_%s_bl%N.eps", - get_entity_name(get_irg_entity(irg)), block); - - if((f = fopen(buf, "wt")) != NULL) { - border_t *b; - int *seen = xcalloc(get_graph_node_count(irg), sizeof(seen[0])); - int last_pos = list_empty(border_head) ? 0 : list_entry(border_head->prev, border_t, list)->step; - int max_col = 0; - - list_for_each_entry_reverse(border_t, b, border_head, list) { - const ir_node *irn = b->irn; - int col = get_irn_color(irn); - max_col = max_col > col ? max_col : col; - } - - fprintf(f, "%%!PS-Adobe-2.0\n"); - fprintf(f, "%%%%BoundingBox: -10 -10 %d %d\n", - x_dist * last_pos + x_dist, y_dist * max_col + y_dist); - fprintf(f, "/mainfont /Courier findfont %f scalefont def\n", params->font_scale); - fprintf(f, "mainfont setfont\n"); - fprintf(f, "0.2 setlinewidth\n"); - - for(i = 0; i <= last_pos; ++i) { - fprintf(f, "0 0 0 setrgbcolor\n"); - fprintf(f, "%d %d moveto\n", i * x_dist, -2); - fprintf(f, "%d %d lineto\n", i * x_dist, max_col * y_dist + 2); - fprintf(f, "stroke\n"); - } - fprintf(f, "0.5 setlinewidth\n"); - - list_for_each_entry_reverse(border_t, b, border_head, list) { - const ir_node *irn = b->irn; - int nr = get_irn_graph_nr(irn); - - if(b->is_def) - seen[nr] = b->step; - else { - int col = get_irn_color(irn); - - int pos = last_pos - seen[nr]; - int end_pos = last_pos - b->step; - int live_in = is_live_in(block, irn); - int live_end = is_live_end(block, irn); - int y_val = y_dist * col; - - int red = 0; - int green = live_end; - int blue = live_in; - - fprintf(f, "0 0 0 setrgbcolor\n"); - fprintf(f, "%d %d moveto\n", x_dist * pos + 2, y_val + 2); - ir_fprintf(f, "(%n/%d%s) show\n", irn, nr, is_phi_operand(irn) ? "*" : ""); - fprintf(f, "%d %d %d setrgbcolor\n", red, green, blue); - fprintf(f, "%d %d moveto\n", x_dist * pos, y_val); - fprintf(f, "%d %d lineto\n", (x_dist * end_pos) - 5, y_val); - fprintf(f, "stroke\n"); - } - } - - free(seen); - fclose(f); - } -} - #ifdef BUILD_GRAPH -typedef struct _if_edge_t { - int src, tgt; -} if_edge_t; - #define IF_EDGE_HASH(e) ((e)->src) +#define IF_NODE_HASH(n) ((n)->nnr) static int if_edge_cmp(const void *p1, const void *p2, size_t size) { @@ -176,6 +70,14 @@ static int if_edge_cmp(const void *p1, const void *p2, size_t size) return !(e1->src == e2->src && e1->tgt == e2->tgt); } +static int if_node_cmp(const void *p1, const void *p2, size_t size) +{ + const if_node_t *n1 = p1; + const if_node_t *n2 = p2; + + return n1->nnr != n2->nnr; +} + static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt) { /* Bring the smaller entry to src. */ @@ -190,41 +92,107 @@ static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt) return edge; } -static INLINE void add_if(const env_t *env, int src, int tgt) +static INLINE void add_if(const be_chordal_env_t *env, int src, int tgt) { if_edge_t edge; + if_node_t node, *src_node, *tgt_node; + /* insert edge */ edge_init(&edge, src, tgt); - set_insert(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge)); + set_insert(env->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)); + + /* insert nodes */ + node.nnr = src; + node.neighb = pset_new_ptr(8); + src_node = set_insert(env->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); + node.nnr = tgt; + node.neighb = pset_new_ptr(8); + tgt_node = set_insert(env->nodes, &node, sizeof(node), IF_NODE_HASH(&node)); + + /* insert neighbors into nodes */ + pset_insert_ptr(src_node->neighb, tgt_node); + pset_insert_ptr(tgt_node->neighb, src_node); } -static INLINE int are_connected(const env_t *env, int src, int tgt) +static INLINE int are_connected(const be_chordal_env_t *env, int src, int tgt) { if_edge_t edge; edge_init(&edge, src, tgt); - return set_find(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL; + return set_find(env->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL; } -static void dump_ifg(set *edges, const char *filename) +int ifg_has_edge(const be_chordal_env_t *env, const if_node_t *n1, const if_node_t* n2) { + return are_connected(env, n1->nnr, n2->nnr); +} + +#ifdef DUMP_IFG + +static void dump_ifg(const be_chordal_env_t *env) { FILE *f; + set *edges = env->edges; + ir_graph *irg = env->irg; + char filename[128]; + + ir_snprintf(filename, sizeof(filename), "ifg_%s_%F.dot", env->cls->name, irg); if((f = fopen(filename, "wt")) != NULL) { + bitset_pos_t pos; + int n_edges = 0; if_edge_t *edge; + bitset_t *bs = bitset_malloc(get_graph_node_count(irg)); - fprintf(f, "graph G {\n"); + ir_fprintf(f, "graph \"%F\" {\n", irg); + fprintf(f, "\tnode [shape=box,style=filled]\n"); for(edge = set_first(edges); edge; edge = set_next(edges)) { - fprintf(f, "i\tn%d -- n%d\n", edge->src, edge->tgt); + bitset_set(bs, edge->src); + bitset_set(bs, edge->tgt); + n_edges++; + } + + fprintf(f, "\tx [label=\"nodes: %u, edges: %d\"]\n", bitset_popcnt(bs), n_edges); + + bitset_foreach(bs, pos) { + int nr = (int) pos; + ir_node *irn = get_irn_for_graph_nr(irg, nr); + + ir_fprintf(f, "\tn%d [label=\"%+F\"]\n", nr, irn); + } + + for(edge = set_first(edges); edge; edge = set_next(edges)) { + fprintf(f, "\tn%d -- n%d [len=5]\n", edge->src, edge->tgt); } fprintf(f, "}\n"); fclose(f); + + bitset_free(bs); } } +#endif /* DUMP_IFG */ + #endif /* BUILD_GRAPH */ +static void check_border_list(struct list_head *head) +{ + border_t *x; + list_for_each_entry(border_t, x, head, list) { + assert(x->magic == BORDER_FOURCC); + } +} + +static void check_heads(be_chordal_env_t *env) +{ + pmap_entry *ent; + for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) { + /* ir_printf("checking border list of block %+F\n", ent->key); */ + check_border_list(ent->value); + } +} + + /** * Add an interval border to the list of a block's list * of interval border. @@ -237,7 +205,7 @@ static void dump_ifg(set *edges, const char *filename) * @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, +static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head, ir_node *irn, unsigned step, unsigned pressure, unsigned is_def, unsigned is_real) { @@ -250,6 +218,7 @@ static INLINE border_t *border_add(env_t *env, struct list_head *head, /* also allocate the def and tie it to the use. */ def = obstack_alloc(&env->obst, sizeof(*def)); + memset(def, 0, sizeof(*def)); b->other_end = def; def->other_end = b; @@ -260,10 +229,8 @@ static INLINE border_t *border_add(env_t *env, struct list_head *head, */ set_irn_link(irn, def); -#ifdef DEBUG_libfirm b->magic = BORDER_FOURCC; def->magic = BORDER_FOURCC; -#endif } /* @@ -274,23 +241,29 @@ static INLINE border_t *border_add(env_t *env, struct list_head *head, else { b = get_irn_link(irn); -#ifdef DEBUG_libfirm assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"); -#endif } - + b->pressure = pressure; b->is_def = is_def; b->is_real = is_real; b->irn = irn; b->step = step; + check_heads(env); list_add_tail(&b->list, head); - DBG((dbg, LEVEL_5, "\t\t%s adding %n, step: %d\n", + check_heads(env); + DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step)); + return b; } +static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn) +{ + return arch_irn_has_reg_class(env->arch_env, irn, arch_pos_make_out(0), env->cls); +} + /** * Annotate the register pressure to the nodes and compute * the liveness intervals. @@ -307,7 +280,7 @@ static void pressure(ir_node *block, void *env_ptr) #define border_use(irn, step, real) \ border_add(env, head, irn, step, ++pressure, 0, real) - env_t *env = env_ptr; + be_chordal_env_t *env = env_ptr; bitset_t *live = env->live; ir_node *irn; @@ -315,27 +288,29 @@ static void pressure(ir_node *block, void *env_ptr) unsigned step = 0; unsigned pressure = 0; struct list_head *head; - pset *live_in = get_live_in(block); - pset *live_end = get_live_end(block); + pset *live_in = put_live_in(block, pset_new_ptr_default()); + pset *live_end = put_live_end(block, pset_new_ptr_default()); + const arch_register_class_t *cls = env->cls; - DBG((dbg, LEVEL_1, "Computing pressure in block %n\n", block)); + DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block)); bitset_clear_all(live); /* Set up the border list in the block info */ - head = &get_ra_block_info(block)->border_head; + head = obstack_alloc(&env->obst, sizeof(*head)); INIT_LIST_HEAD(head); + assert(pmap_get(env->border_heads, block) == NULL); + pmap_insert(env->border_heads, block, head); /* * Make final uses of all values live out of the block. - * They are neccessary to build up real intervals. + * They are necessary 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))); + DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn))); bitset_set(live, get_irn_graph_nr(irn)); - if(!is_Phi(irn) && is_allocatable_irn(irn)) + if(has_reg_class(env, irn)) border_use(irn, step, 0); } - ++step; /* @@ -343,30 +318,23 @@ static void pressure(ir_node *block, void *env_ptr) * relevant for the interval borders. */ sched_foreach_reverse(block, irn) { - DBG((dbg, LEVEL_1, "\tinsn: %n, pressure: %d\n", irn, pressure)); + DBG((dbg, LEVEL_1, "\tinsn: %+F, 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)) { + /* + * If the node defines some value, which can put into a + * register of the current class, make a border for it. + */ + if(has_reg_class(env, irn)) { + bitset_pos_t elm; 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); - } - } + bitset_foreach(live, elm) + add_if(env, nr, (int) elm); #endif } @@ -377,10 +345,10 @@ static void pressure(ir_node *block, void *env_ptr) for(i = 0, n = get_irn_arity(irn); i < n; ++i) { ir_node *op = get_irn_n(irn, i); - if(is_allocatable_irn(op)) { + if(has_reg_class(env, op)) { int nr = get_irn_graph_nr(op); - DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op)); + DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op)); if(!bitset_is_set(live, nr)) { border_use(op, step, 1); @@ -389,7 +357,6 @@ static void pressure(ir_node *block, void *env_ptr) } } } - ++step; } @@ -397,7 +364,7 @@ static void pressure(ir_node *block, void *env_ptr) * 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)) { + if(has_reg_class(env, irn)) { /* Mark the value live in. */ bitset_set(live, get_irn_graph_nr(irn)); @@ -406,36 +373,42 @@ static void pressure(ir_node *block, void *env_ptr) border_def(irn, step, 0); } } + + check_heads(env); + + del_pset(live_in); + del_pset(live_end); } static void assign(ir_node *block, void *env_ptr) { - env_t *env = env_ptr; + be_chordal_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); + const arch_register_class_t *cls = env->cls; /* 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); + /*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); + struct list_head *head = get_block_border_head(env, block); + pset *live_in = put_live_in(block, pset_new_ptr_default()); + + check_heads(env); + 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, "Assigning colors for block %+F\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", + DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use", b->irn, get_irn_graph_nr(b->irn))); } @@ -445,14 +418,16 @@ static void assign(ir_node *block, void *env_ptr) * 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); + if(has_reg_class(env, irn)) { + const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0); + int col; + + assert(reg && "Node must have been assigned a register"); + col = arch_register_get_index(reg); /* 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)); @@ -465,7 +440,7 @@ static void assign(ir_node *block, void *env_ptr) * will work. */ list_for_each_entry_reverse(border_t, b, head, list) { - const ir_node *irn = b->irn; + ir_node *irn = b->irn; int nr = get_irn_graph_nr(irn); /* @@ -473,346 +448,60 @@ static void assign(ir_node *block, void *env_ptr) * color. */ if(b->is_def && !is_live_in(block, irn)) { - ra_node_info_t *ri = get_ra_node_info(irn); + const arch_register_t *reg; 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 + col = bitset_next_clear(colors, 0); + reg = arch_register_for_index(env->cls, col); - /* 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"); + assert(arch_get_irn_register(env->arch_env, irn, 0) == NULL + && "This node must not have been assigned a register yet"); + assert(!bitset_is_set(live, nr) && "Value's definition 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)); + arch_set_irn_register(env->arch_env, irn, 0, reg); + DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", + arch_register_get_name(reg), col, irn)); } /* Clear the color upon a use. */ else if(!b->is_def) { - int col = get_irn_color(irn); + const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0); + int col; + assert(reg && "Register must have been assigned"); + + col = arch_register_get_index(reg); 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; - struct obstack *obst = &env->obst; - void *obstack_level = obstack_base(obst); - bitset_t *live = env->live; - bitset_t *colors = env->colors; - bitset_t *in_colors = env->in_colors; - 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; - int block_nr = get_block_graph_nr(block); - 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); - pset *live_end = get_live_end(block); - - /* - * Check, if this block has already been processed, if true, return - * immediately. - */ - if(bitset_is_set(env->processed, block_nr)) - return; - - /* - * Ensure, that the immediate dominator of this block is allocated - * before this block, since the values live in at this block are - * defined in the dominators of this block. Coloring the dominators - * thus is vital before coloring this block. - */ - if(idom) - block_alloc(idom, env); - - /* Clear the live and allocate the color bitset. */ - bitset_clear_all(live); - bitset_clear_all(colors); - bitset_clear_all(in_colors); - - 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, "Making 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_add(env, &head, 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, "insn: %n\n", irn)); - DBG((dbg, LEVEL_2, "live: %b\n", live)); - - 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_add(env, &head, irn, step, 1); - -#ifdef BUILD_GRAPH - { - unsigned long elm; - bitset_foreach(live, elm) { - int live_nr = (int) elm; - ir_node *live_irn = get_irn_for_graph_nr(irg, live_nr); - if(is_phi_operand(live_irn)) { - 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_add(env, &head, op, step, 0); - bitset_set(live, nr); - } - } - } - } - - ++step; - } - - bitset_clear_all(live); - - /* - * 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)); - - /* Add the def */ - border_add(env, &head, irn, step, 1); - } - } - - DBG((dbg, LEVEL_4, "usedef chain for block %n\n", block)); - 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))); - } - - /* - * 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, "colors in use: %b\n", colors)); - - /* - * Try to assign live out values colors which are not used by live - * in values. - */ - if(is_live_out(block, irn)) { - bitset_copy(tmp_colors, colors); - bitset_or(tmp_colors, in_colors); - col = bitset_next_clear(tmp_colors, 0); - DBG((dbg, LEVEL_5, "next clear in only outs %b: %d\n", tmp_colors, col)); - } - - /* 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; - ri->pressure = bitset_popcnt(colors); - - 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; - - /* Mark this block has processed. */ - bitset_set(env->processed, block_nr); - - /* Reset the obstack to its initial level */ - obstack_free(obst, obstack_level); + del_pset(live_in); } -#endif - void be_ra_chordal_init(void) { - dbg = firm_dbg_register(DBG_BERA); - firm_dbg_set_mask(dbg, -1); + dbg = firm_dbg_register(DBG_CHORDAL); + firm_dbg_set_mask(dbg, DBG_LEVEL); } -void be_ra_chordal(ir_graph *irg) +be_chordal_env_t *be_ra_chordal(ir_graph *irg, + const arch_env_t *arch_env, + const arch_register_class_t *cls) { int node_count = get_graph_node_count(irg); - env_t *env = malloc(sizeof(*env)); + int colors_n = arch_register_class_n_regs(cls); + be_chordal_env_t *env = malloc(sizeof(*env)); if(get_irg_dom_state(irg) != dom_consistent) compute_doms(irg); @@ -820,57 +509,127 @@ void be_ra_chordal(ir_graph *irg) obstack_init(&env->obst); #ifdef BUILD_GRAPH - env->graph = new_set(if_edge_cmp, node_count); + env->edges = new_set(if_edge_cmp, node_count); + env->nodes = new_set(if_node_cmp, node_count); #endif env->live = bitset_obstack_alloc(&env->obst, node_count); - env->colors = bitset_obstack_alloc(&env->obst, TEST_COLORS); - env->in_colors = bitset_obstack_alloc(&env->obst, TEST_COLORS); - env->colors_n = TEST_COLORS; + env->colors = bitset_obstack_alloc(&env->obst, colors_n); + env->in_colors = bitset_obstack_alloc(&env->obst, colors_n); + env->colors_n = colors_n; + env->cls = cls; + env->arch_env = arch_env; + env->irg = irg; + env->border_heads = pmap_create(); /* First, determine the pressure */ dom_tree_walk_irg(irg, pressure, NULL, env); /* Insert probable spills */ - be_ra_chordal_spill(irg); + be_ra_chordal_spill(env); /* Assign the colors */ dom_tree_walk_irg(irg, assign, NULL, env); #ifdef DUMP_IFG + dump_ifg(env); +#endif + +#ifdef DUMP_INTERVALS { char buf[128]; + plotter_t *plotter; + + ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg); + plotter = new_plotter_ps(buf); - ir_snprintf(buf, sizeof(buf), "ifg_%s.dot", get_entity_name(get_irg_entity(irg))); - dump_ifg(env->graph, buf); + draw_interval_tree(&draw_chordal_def_opts, env, plotter, arch_env, cls); + plotter_free(plotter); } #endif + return env; +} + +void be_ra_chordal_check(be_chordal_env_t *chordal_env) { + const arch_env_t *arch_env; + struct obstack ob; + pmap_entry *pme; + ir_node **nodes, *n1, *n2; + int i, o; + + arch_env = chordal_env->arch_env; + + /* Collect all irns */ + obstack_init(&ob); + pmap_foreach(chordal_env->border_heads, pme) { + border_t *curr; + struct list_head *head = pme->value; + list_for_each_entry(border_t, curr, head, list) + if (curr->is_def && curr->is_real) + if (arch_get_irn_reg_class(arch_env, curr->irn, arch_pos_make_out(0)) == chordal_env->cls) + obstack_ptr_grow(&ob, curr->irn); + } + obstack_ptr_grow(&ob, NULL); + nodes = (ir_node **) obstack_finish(&ob); - set_irg_ra_link(irg, env); + /* Check them */ + for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) { + const arch_register_t *n1_reg, *n2_reg; + + n1_reg = arch_get_irn_register(arch_env, n1, 0); + if (!arch_reg_is_allocatable(arch_env, n1, arch_pos_make_out(0), n1_reg)) { + DBG((dbg, 0, "Register assigned to %+F is not allowed\n", n1)); + assert(0 && "Register constraint does not hold"); + } + for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) { + n2_reg = arch_get_irn_register(arch_env, n2, 0); + if (nodes_interfere(chordal_env, n1, n2) && n1_reg == n2_reg) { + DBG((dbg, 0, "Values %+F and %+F interfere and have the same regiseter assigned\n", n1, n2)); + assert(0 && "Interfering values have the same color!"); + } + } + } + obstack_free(&ob, NULL); } -void be_ra_chordal_done(ir_graph *irg) -{ - env_t *env = get_irg_ra_link(irg); +/* BETTER #ifdef BUILD_GRAPH --> faster version of checker with edges */ +void be_ra_chordal_done(be_chordal_env_t *env) +{ #ifdef BUILD_GRAPH - free(env->graph); + { + if_node_t *ifn; + for(ifn = set_first(env->nodes); ifn; ifn = set_next(env->nodes)) + free(ifn->neighb); + free(env->nodes); + free(env->edges); + } #endif + pmap_destroy(env->border_heads); obstack_free(&env->obst, NULL); free(env); } -int phi_ops_interfere(const ir_node *a, const ir_node *b) -{ -#ifdef BUILD_GRAPH - ir_graph *irg = get_irn_irg(a); - env_t *env = get_irg_ra_link(irg); - assert(irg == get_irn_irg(b) && "Both nodes must be in the same graph"); +int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b) +{ +#ifdef BUILD_GRAPH return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b)); #else return values_interfere(a, b); #endif /* BUILD_GRAPH */ } + +#ifdef BUILD_GRAPH + +set *be_ra_get_ifg_edges(const be_chordal_env_t *env) { + return env->edges; +} + +set *be_ra_get_ifg_nodes(const be_chordal_env_t *env) { + return env->nodes; +} + +#endif