From 4794cb5f95f18ed6afee5c1cc33aaf5f39d3e4a2 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Fri, 24 Mar 2006 10:36:45 +0000 Subject: [PATCH] Renaming of a type. Comments. QuickFix for heuristic/ou problem with reg constraints and the order of the units. --- ir/be/becopyheur.c | 2 + ir/be/becopyilp1.c | 10 ---- ir/be/becopyilp2.c | 24 +++++----- ir/be/becopyopt.c | 114 +++++++++++++++++++++++++++++++++++++++----- ir/be/becopyopt.h | 3 +- ir/be/becopyopt_t.h | 19 +++++--- 6 files changed, 132 insertions(+), 40 deletions(-) diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index 941c05ba1..a859c5845 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -582,6 +582,8 @@ int co_solve_heuristic(copy_opt_t *co) { unit_t *curr; dbg = firm_dbg_register("ir.be.copyoptheur"); + ASSERT_OU_AVAIL(co); + pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL); list_for_each_entry(unit_t, curr, &co->units, units) if (curr->node_count > 1) diff --git a/ir/be/becopyilp1.c b/ir/be/becopyilp1.c index ba7f15a09..2a0aca4ba 100644 --- a/ir/be/becopyilp1.c +++ b/ir/be/becopyilp1.c @@ -13,8 +13,6 @@ #include "config.h" #endif /* HAVE_CONFIG_H */ -#ifdef WITH_ILP - #include "becopyilp_t.h" #define DEBUG_LVL 1 @@ -35,11 +33,3 @@ static void ilp1_apply(ilp_env_t *ienv) { int co_solve_ilp1(copy_opt_t *co, double time_limit) { return 1; } - - -#else /* WITH_ILP */ - -static void only_that_you_can_compile_without_WITH_ILP_defined(void) { -} - -#endif /* WITH_ILP */ diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c index f1703fb7d..946322dd6 100644 --- a/ir/be/becopyilp2.c +++ b/ir/be/becopyilp2.c @@ -30,8 +30,6 @@ #include "config.h" #endif /* HAVE_CONFIG_H */ -#ifdef WITH_ILP - #include #include "pdeq.h" @@ -142,6 +140,12 @@ static void build_interference_cstr(ilp_env_t *ienv) { } } + +/** + * TODO: Remove the dependency of the opt-units data structure + * by walking over all affinity edges. Graph structure + * does not provide this walker, yet. + */ static void build_affinity_cstr(ilp_env_t *ienv) { unit_t *curr; int n_colors = arch_register_class_n_regs(ienv->co->cls); @@ -249,7 +253,7 @@ static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counte * At most 1 node of the clique can be colored equally with the external node. */ static void build_clique_star_cstr(ilp_env_t *ienv) { - affinity_t *aff; + affinity_node_t *aff; /* for each node with affinity edges */ co_gs_foreach_aff_node(ienv->co, aff) { @@ -358,7 +362,7 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, ir_node *irn) { be_ifg_t *ifg = ienv->co->cenv->ifg; int i, len; ir_node **curr_path; - affinity_t *aff; + affinity_node_t *aff; neighb_t *nbr; /* do not walk backwards or in circles */ @@ -423,7 +427,7 @@ end: * Then at least one of these affinity edges must break. */ static void build_path_cstr(ilp_env_t *ienv) { - affinity_t *aff_info; + affinity_node_t *aff_info; /* for each node with affinity edges */ co_gs_foreach_aff_node(ienv->co, aff_info) { @@ -500,6 +504,9 @@ int co_solve_ilp2(copy_opt_t *co, double time_limit) { ilp_env_t *ienv; local_env_t my; + ASSERT_OU_AVAIL(co); //See build_clique_st + ASSERT_GS_AVAIL(co); + my.time_limit = time_limit; my.first_x_var = -1; my.last_x_var = -1; @@ -516,10 +523,3 @@ int co_solve_ilp2(copy_opt_t *co, double time_limit) { return sol_state == lpp_optimal; } - -#else /* WITH_ILP */ - -static void only_that_you_can_compile_without_WITH_ILP_defined(void) { -} - -#endif /* WITH_ILP */ diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index 58ef680e1..1b1c52b02 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -30,6 +30,9 @@ #include "becopyopt_t.h" #include "becopystat.h" + +#define QUICK_AND_DIRTY_HACK + /****************************************************************************** _____ _ / ____| | | @@ -71,6 +74,7 @@ copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node void free_copy_opt(copy_opt_t *co) { xfree(co->name); + free(co); } int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) { @@ -326,7 +330,7 @@ static void co_collect_units(ir_node *irn, void *env) { unit->node_count = 2; unit->nodes[0] = irn; unit->nodes[1] = other; - unit->costs[1] = co->get_costs(irn, other, -120480); + unit->costs[1] = co->get_costs(irn, other, -1); } } else assert(0 && "This is not an optimizable node!"); @@ -344,7 +348,6 @@ static void co_collect_units(ir_node *irn, void *env) { /* Determine the minimal costs this unit will cause: min_nodes_costs */ unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit); - /* Insert the new ou according to its sort_key */ tmp = &co->units; while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key) @@ -355,19 +358,94 @@ static void co_collect_units(ir_node *irn, void *env) { } } +#ifdef QUICK_AND_DIRTY_HACK + +static int compare_ous(const void *k1, const void *k2) { + const unit_t *u1 = *((const unit_t **) k1); + const unit_t *u2 = *((const unit_t **) k2); + int i, o, u1_has_constr, u2_has_constr; + arch_register_req_t req; + const arch_env_t *aenv = u1->co->aenv; + + /* Units with constraints come first */ + u1_has_constr = 0; + for (i=0; inode_count; ++i) { + arch_get_register_req(aenv, &req, u1->nodes[i], -1); + if (arch_register_req_is(&req, limited)) { + u1_has_constr = 1; + break; + } + } + + u2_has_constr = 0; + for (i=0; inode_count; ++i) { + arch_get_register_req(aenv, &req, u2->nodes[i], -1); + if (arch_register_req_is(&req, limited)) { + u2_has_constr = 1; + break; + } + } + + if (u1_has_constr != u2_has_constr) + return u2_has_constr - u1_has_constr; + + /* Now check, whether the two units are connected */ + for (i=0; inode_count; ++i) + for (o=0; onode_count; ++o) + if (u1->nodes[i] == u2->nodes[o]) + return 0; + + /* After all, the sort key decides. Greater keys come first. */ + return u2->sort_key - u1->sort_key; + +} + +/** + * Sort the ou's according to constraints and their sort_key + */ +static void co_sort_units(copy_opt_t *co) { + int i, count = 0; + unit_t *tmp, *ou, **ous; + + /* get the number of ous, remove them form the list and fill the array */ + list_for_each_entry(unit_t, ou, &co->units, units) + count++; + ous = alloca(count * sizeof(*ous)); + + i = 0; + list_for_each_entry_safe(unit_t, ou, tmp, &co->units, units) { + ous[i++] = ou; + list_del(&ou->units); + } + + assert(count == i); + + qsort(ous, count, sizeof(*ous), compare_ous); + + /* reinsert into list in correct order */ + for (i=0; iunits, &co->units); +} +#endif + void co_build_ou_structure(copy_opt_t *co) { DBG((dbg, LEVEL_1, "\tCollecting optimization units\n")); INIT_LIST_HEAD(&co->units); irg_walk_graph(co->irg, co_collect_units, NULL, co); +#ifdef QUICK_AND_DIRTY_HACK + co_sort_units(co); +#endif } void co_free_ou_structure(copy_opt_t *co) { unit_t *curr, *tmp; + ASSERT_OU_AVAIL(co); list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) { xfree(curr->nodes); xfree(curr->costs); xfree(curr); } + co->units.next = NULL; } /* co_solve_heuristic() is implemented in becopyheur.c */ @@ -376,6 +454,8 @@ int co_get_max_copy_costs(const copy_opt_t *co) { int i, res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) { res += curr->inevitable_costs; for (i=1; inode_count; ++i) @@ -388,6 +468,8 @@ int co_get_inevit_copy_costs(const copy_opt_t *co) { int res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) res += curr->inevitable_costs; return res; @@ -397,6 +479,8 @@ int co_get_copy_costs(const copy_opt_t *co) { int i, res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) { int root_col = get_irn_col(co, curr->nodes[0]); DBG((dbg, LEVEL_1, " %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col)); @@ -415,6 +499,9 @@ int co_get_copy_costs(const copy_opt_t *co) { int co_get_lower_bound(const copy_opt_t *co) { int res = 0; unit_t *curr; + + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) res += curr->inevitable_costs + curr->min_nodes_costs; return res; @@ -431,20 +518,20 @@ int co_get_lower_bound(const copy_opt_t *co) { |_| |___/ ******************************************************************************/ -static int compare_affinity_t(const void *k1, const void *k2, size_t size) { - const affinity_t *n1 = k1; - const affinity_t *n2 = k2; +static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) { + const affinity_node_t *n1 = k1; + const affinity_node_t *n2 = k2; return (n1->irn != n2->irn); } static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) { - affinity_t new_node, *node; + affinity_node_t new_node, *node; neighb_t new_nbr, *nbr; int allocnew; new_node.irn = n1; - new_node.count = 0; + new_node.degree = 0; new_node.neighbours = NULL; node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); @@ -463,7 +550,7 @@ static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) { nbr->costs = 0; nbr->next = node->neighbours; node->neighbours = nbr; - node->count++; + node->degree++; } /* now nbr points to n1's neighbour-entry of n2 */ @@ -510,25 +597,30 @@ static void build_graph_walker(ir_node *irn, void *env) { void co_build_graph_structure(copy_opt_t *co) { obstack_init(&co->obst); - co->nodes = new_set(compare_affinity_t, 32); + co->nodes = new_set(compare_affinity_node_t, 32); irg_walk_graph(co->irg, build_graph_walker, NULL, co); } void co_free_graph_structure(copy_opt_t *co) { + ASSERT_GS_AVAIL(co); + del_set(co->nodes); obstack_free(&co->obst, NULL); + co->nodes = NULL; } /* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */ int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) { - affinity_t new_node, *n; + affinity_node_t new_node, *n; + + ASSERT_GS_AVAIL(co); new_node.irn = irn; n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); if (n) { - return (n->count > 0); + return (n->degree > 0); } else return 0; } diff --git a/ir/be/becopyopt.h b/ir/be/becopyopt.h index d13c36770..c245e10b3 100644 --- a/ir/be/becopyopt.h +++ b/ir/be/becopyopt.h @@ -136,11 +136,12 @@ int co_solve_ilp1(copy_opt_t *co, double time_limit); * Solves the problem using mixed integer programming * @returns 1 iff solution state was optimal * Uses the OU and the GRAPH data structure + * Dependency of the OU structure can be removed */ int co_solve_ilp2(copy_opt_t *co, double time_limit); /** - * Checks if a node is optimizable, viz. has somthing to do with coalescing. + * Checks if a node is optimizable, viz has something to do with coalescing. * Uses the GRAPH data structure */ int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn); diff --git a/ir/be/becopyopt_t.h b/ir/be/becopyopt_t.h index 2be79b028..dc8f838c1 100644 --- a/ir/be/becopyopt_t.h +++ b/ir/be/becopyopt_t.h @@ -36,6 +36,9 @@ struct _copy_opt_t { }; /* Helpers */ +#define ASSERT_OU_AVAIL(co) assert((co)->units.next && "Representation as optimization-units not build") +#define ASSERT_GS_AVAIL(co) assert((co)->nodes && "Representation as graph not build") + #define get_irn_col(co, irn) arch_register_get_index(arch_get_irn_register((co)->aenv, irn)) #define set_irn_col(co, irn, col) arch_set_irn_register((co)->aenv, irn, arch_register_for_index((co)->cls, col)) #define is_curr_reg_class(co, irn) (arch_get_irn_reg_class((co)->aenv, irn, -1) == (co)->cls) @@ -96,24 +99,26 @@ typedef struct _unit_t { ******************************************************************************/ typedef struct _neighb_t neighb_t; -typedef struct _affinity_t affinity_t; +typedef struct _affinity_node_t affinity_node_t; struct _neighb_t { neighb_t *next; /** the next neighbour entry*/ ir_node *irn; /** the neighbour itself */ - int costs; /** the costs of the edge (node_t->irn, neighb_t->irn) */ + int costs; /** the costs of the edge (affinity_node_t->irn, neighb_t->irn) */ }; -struct _affinity_t { +struct _affinity_node_t { ir_node *irn; /** a node with affinity edges */ - int count; /** number of affinity edges in the linked list below */ + int degree; /** number of affinity edges in the linked list below */ neighb_t *neighbours; /** a linked list of all affinity neighbours */ }; -static INLINE affinity_t *get_affinity_info(const copy_opt_t *co, ir_node *irn) { - affinity_t find; +static INLINE affinity_node_t *get_affinity_info(const copy_opt_t *co, ir_node *irn) { + affinity_node_t find; + + ASSERT_GS_AVAIL(co); find.irn = irn; return set_find(co->nodes, &find, sizeof(find), HASH_PTR(irn)); @@ -126,4 +131,6 @@ static INLINE affinity_t *get_affinity_info(const copy_opt_t *co, ir_node *irn) #define co_gs_foreach_neighb(aff_node, neighb) for (neighb = aff_node->neighbours; neighb; neighb = neighb->next) + + #endif -- 2.20.1