X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=1d727c010ea0e2be9df52152dd2705a13cd595c5;hb=df2faee01a5832057bb3ca0ba5f67e979c916e19;hp=e0e13b2b3d157ed079114dc2608eb73a6a7d9785;hpb=6c3146b96bc65d9de18f3f2b59faf33b8b9935d6;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index e0e13b2b3..1d727c010 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -22,7 +22,6 @@ * @brief More experiments on coalescing. * @author Sebastian Hack * @date 14.04.2006 - * @version $Id$ */ #include "config.h" @@ -40,19 +39,19 @@ #include "debug.h" #include "bitfiddle.h" -#include "irphase_t.h" #include "irgraph_t.h" #include "irnode_t.h" #include "irprintf.h" +#include "util.h" #include "irtools.h" - +#include "irnodemap.h" +#include "be_t.h" #include "bemodule.h" #include "beabi.h" #include "benode.h" #include "becopyopt.h" #include "becopyopt_t.h" #include "bechordal_t.h" -#include "beirg.h" #define DUMP_BEFORE 1 #define DUMP_AFTER 2 @@ -95,8 +94,6 @@ static const lc_opt_table_entry_t options[] = { #define INFEASIBLE(cost) ((cost) == INT_MAX) -static be_ifg_dump_dot_cb_t ifg_dot_cb; - typedef unsigned col_t; typedef struct co2_irn_t co2_irn_t; @@ -109,7 +106,8 @@ typedef struct { } col_cost_pair_t; typedef struct { - ir_phase ph; + ir_nodemap map; + struct obstack obst; copy_opt_t *co; bitset_t *allocatable_regs; co2_irn_t *touched; @@ -177,30 +175,42 @@ typedef struct { #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs) -#define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) -#define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) +static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node) +{ + co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node); + if (ci == NULL) { + ci = OALLOCZ(&env->obst, co2_irn_t); + + INIT_LIST_HEAD(&ci->changed_list); + ci->touched_next = env->touched; + ci->orig_col = get_irn_col(node); + env->touched = ci; + ci->irn = node; + ci->aff = NULL; + + ir_nodemap_insert(&env->map, node, ci); + } + return ci; +} -static void *co2_irn_init(ir_phase *ph, const ir_node *irn) +static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node) { - co2_t *env = (co2_t *) ph; - affinity_node_t *a = get_affinity_info(env->co, irn); - size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t); - co2_irn_t *ci = phase_alloc(ph, size); - - memset(ci, 0, size); - INIT_LIST_HEAD(&ci->changed_list); - ci->touched_next = env->touched; - ci->orig_col = get_irn_col(irn); - env->touched = ci; - ci->irn = irn; - ci->aff = a; + co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node); + if (ci == NULL) { + ci = OALLOCZ(&env->obst, co2_cloud_irn_t); - if (a) { - co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci; - INIT_LIST_HEAD(&cci->cloud_list); - cci->mst_parent = cci; - } + INIT_LIST_HEAD(&ci->inh.changed_list); + ci->inh.touched_next = env->touched; + ci->inh.orig_col = get_irn_col(node); + env->touched = &ci->inh; + ci->inh.irn = node; + ci->inh.aff = get_affinity_info(env->co, node); + + INIT_LIST_HEAD(&ci->cloud_list); + ci->mst_parent = ci; + ir_nodemap_insert(&env->map, node, ci); + } return ci; } @@ -208,8 +218,8 @@ static void *co2_irn_init(ir_phase *ph, const ir_node *irn) static int cmp_clouds_gt(const void *a, const void *b) { - const co2_cloud_t * const *p = a; - const co2_cloud_t * const *q = b; + const co2_cloud_t * const *p = (const co2_cloud_t*const*)a; + const co2_cloud_t * const *q = (const co2_cloud_t*const*)b; double c = CLOUD_WEIGHT(*p); double d = CLOUD_WEIGHT(*q); return QSORT_CMP(d, c); @@ -221,8 +231,8 @@ static int cmp_clouds_gt(const void *a, const void *b) */ static int col_cost_pair_lt(const void *a, const void *b) { - const col_cost_pair_t *p = a; - const col_cost_pair_t *q = b; + const col_cost_pair_t *p = (const col_cost_pair_t*)a; + const col_cost_pair_t *q = (const col_cost_pair_t*)b; int c = p->costs; int d = q->costs; return QSORT_CMP(c, d); @@ -230,8 +240,8 @@ static int col_cost_pair_lt(const void *a, const void *b) static int cmp_edges(const void *a, const void *b) { - const edge_t *p = a; - const edge_t *q = b; + const edge_t *p = (const edge_t*)a; + const edge_t *q = (const edge_t*)b; return QSORT_CMP(q->costs, p->costs); } @@ -251,8 +261,8 @@ static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci) { if (ci->adm_cache == NULL) { const arch_register_req_t *req; - ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs); - req = arch_get_register_req_out(ci->irn); + ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs); + req = arch_get_irn_register_req(ci->irn); if (arch_register_req_is(req, limited)) { int i, n; @@ -292,7 +302,7 @@ static inline int is_constrained(co2_t *env, co2_irn_t *ci) static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs) { - const arch_register_req_t *req = arch_get_register_req_out(irn); + const arch_register_req_t *req = arch_get_irn_register_req(irn); if (arch_register_req_is(req, limited)) { unsigned n_regs = env->co->cls->n_regs; @@ -323,17 +333,15 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co const ir_node *irn = ci->irn; be_ifg_t *ifg = env->co->cenv->ifg; int n_regs = env->co->cls->n_regs; - bitset_t *forb = bitset_alloca(n_regs); affinity_node_t *a = ci->aff; - unsigned elm; const ir_node *pos; neighbours_iter_t it; int i; /* Put all forbidden colors into the aux bitset. */ - admissible_colors(env, ci, forb); - bitset_flip_all(forb); + bitset_t *const admissible = bitset_alloca(n_regs); + admissible_colors(env, ci, admissible); for (i = 0; i < n_regs; ++i) { col_costs[i].col = i; @@ -341,8 +349,6 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co } if (a) { - neighb_t *n; - co_gs_foreach_neighb(a, n) { if (color_is_fix(env, n->irn)) { col_t col = get_col(env, n->irn); @@ -366,7 +372,7 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co be_ifg_neighbours_break(&it); /* Set the costs to infinity for each color which is not allowed at this node. */ - bitset_foreach(forb, elm) { + bitset_foreach_clear(admissible, elm) { col_costs[elm].costs = INT_MAX; } @@ -391,16 +397,12 @@ static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pai static void reject_coloring(struct list_head *h) { - co2_irn_t *pos; - list_for_each_entry(co2_irn_t, pos, h, changed_list) pos->tmp_fixed = 0; } static void materialize_coloring(struct list_head *h) { - co2_irn_t *pos; - list_for_each_entry(co2_irn_t, pos, h, changed_list) { pos->orig_col = pos->tmp_col; pos->tmp_fixed = 0; @@ -611,13 +613,11 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) be_ifg_t *ifg = env->co->cenv->ifg; bitset_t *bs = bitset_alloca(n_regs); - unsigned elm; const ir_node *irn; neighbours_iter_t it; admissible_colors(env, &ci->inh, bs); - bitset_flip_all(bs); - bitset_foreach(bs, elm) + bitset_foreach_clear(bs, elm) badness[elm] = ci->costs; /* Use constrained/fixed interfering neighbors to influence the color badness */ @@ -626,7 +626,7 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) admissible_colors(env, ni, bs); if (bitset_popcount(bs) == 1) { - unsigned c = bitset_next_set(bs, 0); + size_t c = bitset_next_set(bs, 0); badness[c] += ci->costs; } @@ -769,7 +769,6 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i be_ifg_t *ifg = env->co->cenv->ifg; co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); int costs = 0; - neighb_t *n; if (ci->cloud) return; @@ -812,8 +811,7 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) { - co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0])); - co2_cloud_irn_t *ci; + co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t); int i; DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn)); @@ -828,7 +826,7 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom; /* Also allocate space for the node sequence and compute that sequence. */ - cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0])); + cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb); i = 0; list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) { @@ -844,14 +842,13 @@ static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth) { const ir_node *irn = ci->inh.irn; int *front = FRONT_BASE(ci, col); - int i, ok; + int i; struct list_head changed; INIT_LIST_HEAD(&changed); DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col)); - ok = change_color_single(ci->cloud->env, irn, col, &changed, depth); - // assert(ok && "Color changing may not fail while committing the coloring"); + change_color_single(ci->cloud->env, irn, col, &changed, depth); materialize_coloring(&changed); for (i = 0; i < ci->mst_n_childs; ++i) { @@ -883,7 +880,6 @@ static void process_cloud(co2_cloud_t *cloud) obstack_init(&cloud->obst); for (i = 0; i < cloud->n_memb; ++i) { co2_cloud_irn_t *ci = cloud->seq[i]; - neighb_t *n; co_gs_foreach_neighb(ci->inh.aff, n) { co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn); @@ -897,7 +893,7 @@ static void process_cloud(co2_cloud_t *cloud) } } } - edges = obstack_finish(&cloud->obst); + edges = (edge_t*)obstack_finish(&cloud->obst); qsort(edges, n_edges, sizeof(edges[0]), cmp_edges); /* Compute the maximum spanning tree using Kruskal/Union-Find */ @@ -927,7 +923,7 @@ static void process_cloud(co2_cloud_t *cloud) cloud->mst_root = cloud->master; q = new_pdeq1(cloud->master); while (!pdeq_empty(q)) { - co2_cloud_irn_t *ci = pdeq_getl(q); + co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q); int ofs = ci->index * cloud->n_memb; int end = ofs + cloud->n_memb; int i; @@ -953,7 +949,7 @@ static void process_cloud(co2_cloud_t *cloud) } obstack_ptr_grow(&cloud->obst, NULL); - ci->mst_childs = obstack_finish(&cloud->obst); + ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst); } del_pdeq(q); free(mst_edges); @@ -961,7 +957,7 @@ static void process_cloud(co2_cloud_t *cloud) DBG((env->dbg, LEVEL_3, "mst:\n")); for (i = 0; i < cloud->n_memb; ++i) { - DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]); + DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];) DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn)); } @@ -1000,7 +996,6 @@ static void process_cloud(co2_cloud_t *cloud) static int cloud_costs(co2_cloud_t *cloud) { int i, costs = 0; - neighb_t *n; for (i = 0; i < cloud->n_memb; ++i) { co2_irn_t *ci = (co2_irn_t *) cloud->seq[i]; @@ -1014,10 +1009,18 @@ static int cloud_costs(co2_cloud_t *cloud) return costs / 2; } +static void writeback_colors(co2_t *env) +{ + co2_irn_t *irn; + + for (irn = env->touched; irn; irn = irn->touched_next) { + const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col); + arch_set_irn_register((ir_node*)irn->irn, reg); + } +} + static void process(co2_t *env) { - affinity_node_t *a; - co2_cloud_t *pos; co2_cloud_t **clouds; int n_clouds; int i; @@ -1049,19 +1052,6 @@ static void process(co2_t *env) all_costs += clouds[i]->costs; final_costs += cloud_costs(clouds[i]); - - /* Dump the IFG if the user demanded it. */ - if (dump_flags & DUMP_CLOUD) { - char buf[256]; - FILE *f; - - ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i); - f = fopen(buf, "wt"); - if (f != NULL) { - be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env); - fclose(f); - } - } } DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs)); @@ -1069,164 +1059,12 @@ static void process(co2_t *env) xfree(clouds); } -static void writeback_colors(co2_t *env) -{ - co2_irn_t *irn; - - for (irn = env->touched; irn; irn = irn->touched_next) { - const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col); - arch_set_irn_register((ir_node*)irn->irn, reg); - } -} - - -/* - ___ _____ ____ ____ ___ _____ ____ _ - |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ - | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | - | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| | - |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | - |_| |___/ -*/ - -static const char *get_dot_color_name(size_t col) -{ - static const char *const names[] = { - "blue", - "red", - "green", - "yellow", - "cyan", - "magenta", - "orange", - "chocolate", - "beige", - "navy", - "darkgreen", - "darkred", - "lightPink", - "chartreuse", - "lightskyblue", - "linen", - "pink", - "lightslateblue", - "mintcream", - "red", - "darkolivegreen", - "mediumblue", - "mistyrose", - "salmon", - "darkseagreen", - "mediumslateblue" - "moccasin", - "tomato", - "forestgreen", - "darkturquoise", - "palevioletred" - }; - - return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white"; -} - -static const char *get_dot_shape_name(co2_irn_t *ci) -{ - const arch_register_req_t *req = arch_get_register_req_out(ci->irn); - - if (arch_register_req_is(req, limited)) - return "diamond"; - - if (ci->fixed) - return "rectangle"; - - if (ci->tmp_fixed) - return "hexagon"; - - return "ellipse"; -} - -static void ifg_dump_graph_attr(FILE *f, void *self) -{ - (void) self; - fprintf(f, "overlay=false"); -} - -static int ifg_is_dump_node(void *self, ir_node *irn) -{ - const arch_register_req_t *req = arch_get_register_req_out(irn); - (void)self; - return !(req->type & arch_register_req_type_ignore); -} - -static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) -{ - co2_t *env = self; - co2_irn_t *ci = get_co2_irn(env, irn); - int peri = 1; - - char buf[128] = ""; - - if (ci->aff) { - co2_cloud_irn_t *cci = (void *) ci; - if (cci->cloud && cci->cloud->mst_root == cci) - peri = 2; - - if (cci->cloud && cci->cloud->mst_root) - ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn); - } - - ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri, - get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci)); -} - -static void ifg_dump_at_end(FILE *file, void *self) +static int co_solve_heuristic_new(copy_opt_t *co) { - co2_t *env = self; - affinity_node_t *a; - - co_gs_foreach_aff_node(env->co, a) { - co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn); - int idx = get_irn_idx(a->irn); - neighb_t *n; - - if (ai->mst_parent != ai) - fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn)); - - co_gs_foreach_neighb(a, n) { - int nidx = get_irn_idx(n->irn); - co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn); - - if (idx < nidx) { - const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red"; - const char *arr = "arrowhead=dot arrowtail=dot"; - - if (ci->mst_parent == ai) - arr = "arrowtail=normal"; - else if (ai->mst_parent == ci) - arr = "arrowhead=normal"; - - fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color); - } - } - } -} - - -static be_ifg_dump_dot_cb_t ifg_dot_cb = { - ifg_is_dump_node, - ifg_dump_graph_attr, - ifg_dump_node_attr, - NULL, - NULL, - ifg_dump_at_end -}; - -int co_solve_heuristic_new(copy_opt_t *co) -{ - char buf[256]; co2_t env; - FILE *f; - phase_init(&env.ph, co->cenv->irg, co2_irn_init); + ir_nodemap_init(&env.map, co->irg); + obstack_init(&env.obst); env.touched = NULL; env.visited = 0; env.co = co; @@ -1236,32 +1074,15 @@ int co_solve_heuristic_new(copy_opt_t *co) FIRM_DBG_REGISTER(env.dbg, "firm.be.co2"); INIT_LIST_HEAD(&env.cloud_head); - if (dump_flags & DUMP_BEFORE) { - ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name); - f = fopen(buf, "wt"); - if (f != NULL) { - be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); - fclose(f); - } - } - process(&env); - if (dump_flags & DUMP_AFTER) { - ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name); - f = fopen(buf, "wt"); - if (f != NULL) { - be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); - fclose(f); - } - } - writeback_colors(&env); - phase_deinit(&env.ph); + obstack_free(&env.obst, NULL); + ir_nodemap_destroy(&env.map); return 0; } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2) void be_init_copyheur2(void) { lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");