From e60c154d86f52c9a99e9194e84665d2aec7c744f Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Tue, 26 Jul 2005 09:18:25 +0000 Subject: [PATCH] Bugfixes --- ir/be/bechordal.c | 2 +- ir/be/becopyilp.c | 53 ++++++++++++++++++++++++++++++++++------------- ir/be/becopyopt.c | 16 ++++++-------- ir/be/becopyopt.h | 7 +------ 4 files changed, 47 insertions(+), 31 deletions(-) diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index a033515b6..3416e40b5 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -561,7 +561,7 @@ void be_ra_chordal_check(be_chordal_env_t *chordal_env) { obstack_free(&ob, NULL); } -/* TODO #ifdef BUILD_GRAPH --> faster version of checker with edges */ +/* BETTER #ifdef BUILD_GRAPH --> faster version of checker with edges */ void be_ra_chordal_done(be_chordal_env_t *env) { diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index 58cd15913..c69d9c22d 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -237,11 +237,12 @@ static void pi_add_constr_B(problem_instance_t *pi, int color) { */ static void pi_add_constr_E(problem_instance_t *pi) { unit_t *curr; - bitset_t *root_regs, *arg_regs; + bitset_t *root_regs, *arg_regs, *work_regs; int cst_counter = 0; unsigned nregs = pi->co->chordal_env->cls->n_regs; root_regs = bitset_alloca(nregs); arg_regs = bitset_alloca(nregs); + work_regs = bitset_alloca(nregs); DBG((dbg, LEVEL_2, "Add E constraints...\n")); /* for all roots of optimization units */ @@ -267,12 +268,14 @@ static void pi_add_constr_E(problem_instance_t *pi) { mangle_var(buf, 'y', rootnr, argnr); y_idx = lpp_add_var(pi->curr_lp, buf, continous, curr->costs[i]); + //BETTER: y vars as binary or continous vars ?? /* set starting value */ //lpp_set_start_value(pi->curr_lp, y_idx, (get_irn_col(pi->co, root) != get_irn_col(pi->co, arg))); /* For all colors root and arg have in common, add 2 constraints to E */ - bitset_and(arg_regs, root_regs); - bitset_foreach(arg_regs, color) { + bitset_copy(work_regs, root_regs); + bitset_and(work_regs, arg_regs); + bitset_foreach(work_regs, color) { int root_idx, arg_idx, cst_idx; mangle_var(buf, 'x', rootnr, color); root_idx = lpp_get_var_idx(pi->curr_lp, buf); @@ -293,12 +296,33 @@ static void pi_add_constr_E(problem_instance_t *pi) { lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1); lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); } - /* TODO: - * \forall c \in p(v_i) \ p(v_j) - * y_ij >= x_ic - * \forall c \in p(v_j) \ p(v_i) - * y_ij >= x_jc + /* For all colors root and arg have "disjunct", add 1 constraints to E. + * If root gets a color the arg is not possible to get then they will + * definetly get different colors. So y has to be 1. + * Vice versa for arg. */ + bitset_copy(work_regs, root_regs); + bitset_xor(work_regs, arg_regs); + bitset_foreach(work_regs, color) { + int root_idx, arg_idx, cst_idx; + mangle_var(buf, 'x', rootnr, color); + root_idx = lpp_get_var_idx(pi->curr_lp, buf); + mangle_var(buf, 'x', argnr, color); + arg_idx = lpp_get_var_idx(pi->curr_lp, buf); + + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0); + if (bitset_is_set(root_regs, color)) { + /* add root-y <= 0 */ + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + } else { + assert(bitset_is_set(arg_regs, color) && "bitset_xor is buggy"); + /* add arg-y <= 0 */ + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + } + } } } } @@ -340,12 +364,13 @@ static void pi_add_constr_S(problem_instance_t *pi) { } /** - * TODO Matrix M: Multi-Arg-Use. Interrelates different \phi-functions + * Matrix M: Multi-Arg-Use. Interrelates different \phi-functions * in the same block, iff they use the same arg at the same pos. - * Only one can get the arg. + * Only one of the phis can get the arg. */ - -//static void pi_add_constr_M(problem_instance_t *pi) { +static void pi_add_constr_M(problem_instance_t *pi) { + //TODO pi_add_constr_M +} /** * Generate the initial problem matrices and vectors. @@ -364,7 +389,7 @@ static problem_instance_t *new_pi(const copy_opt_t *co) { /* problem size reduction */ pi_find_simplicials(pi); - //TODO If you wish to see it: dump_ifg_w/o_removed + //BETTER If you wish to see it: dump_ifg_w/o_removed if (pi->all_simplicial) return pi; @@ -375,7 +400,7 @@ static problem_instance_t *new_pi(const copy_opt_t *co) { pi_add_constr_B(pi, col); pi_add_constr_E(pi); pi_add_constr_S(pi); - //TODO pi_add_constr_M(pi); + pi_add_constr_M(pi); return pi; } diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index c544e9cc9..3267a7468 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -28,6 +28,7 @@ static firm_dbg_module_t *dbg = NULL; #define is_curr_reg_class(irn) (arch_get_irn_reg_class(co->chordal_env->arch_env, irn, arch_pos_make_out(0)) == co->chordal_env->cls) #define MIN(a,b) ((acosts = xmalloc((arity+1) * sizeof(*unit->costs)); unit->nodes[0] = root; unit->complete_costs = 0; - unit->avg_costs = 0; + unit->sort_key = 0; INIT_LIST_HEAD(&unit->queue); /* check all args */ @@ -116,7 +117,6 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) { int o, arg_pos = 0; if (nodes_interfere(co->chordal_env, root, arg)) assert(0 && "root and arg interfere"); - //TODO do not insert duplicate args DBG((dbg, LEVEL_1, "\t Member: %n %N\n", arg, arg)); /* check if arg has occurred at a prior position in the arg/list */ @@ -127,9 +127,6 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) { } if (!arg_pos) { /* a new argument */ - /* TODO Think about the next 2 lines. (inserting in arg-order) */ - if (is_optimizable(co->chordal_env->arch_env, arg)) - co_append_unit(co, arg); /* insert node, set costs */ unit->nodes[unit->node_count] = arg; unit->costs[unit->node_count] = co->get_costs(root, arg, i); @@ -154,15 +151,14 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) { /* TODO add ou's for 2-addr-code instructions */ - for(i=1; inode_count; ++i) + for(i=1; inode_count; ++i) { + unit->sort_key = MAX(unit->sort_key, unit->costs[i]); unit->complete_costs += unit->costs[i]; - - assert(unit->node_count > 1); - unit->avg_costs = (100 * unit->complete_costs) / (unit->node_count-1); + } /* insert according to average costs */ tmp = &co->units; - while (tmp->next != &co->units && list_entry_units(tmp->next)->avg_costs > unit->avg_costs) + while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key) tmp = tmp->next; list_add(&unit->units, tmp); diff --git a/ir/be/becopyopt.h b/ir/be/becopyopt.h index e68717102..eda9d0e55 100644 --- a/ir/be/becopyopt.h +++ b/ir/be/becopyopt.h @@ -7,10 +7,6 @@ * Header for copy optimization problem. Analysis and set up of the problem. */ -/* - * TODO: get_nodes_block(get_irn_n(get_nodes_block(phi), i)); --> get_ifgblock_nodeblock - */ - #ifndef _BECOPYOPT_H #define _BECOPYOPT_H @@ -65,8 +61,7 @@ typedef struct _unit_t { int complete_costs; /**< sum of all costs[i] */ int minimal_costs; /**< a lower bound for this ou, considering only ifg (not coloring conflicts) */ - //TODO Think of the ordering. - int avg_costs; /**< average costs. controls the order of ou's. */ + int sort_key; /**< maximum costs. controls the order of ou's. */ /* for heuristic */ struct list_head queue; /**< list of (mis/color) sorted by size of mis */ -- 2.20.1