From b3b1029730614fa10c8dc9db6ce8954062d46925 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Mon, 13 Jun 2005 15:13:24 +0000 Subject: [PATCH] Killed an ugly bug. Set default not to use ILP. Improvements in copystat module. --- ir/be/becopyilp.c | 25 +++++++++------- ir/be/becopyopt.c | 39 ++++++++++++++---------- ir/be/becopyopt.h | 19 ++++++++++-- ir/be/becopyoptmain.c | 31 ++++++++----------- ir/be/becopystat.c | 69 +++++++++++++++++++++++++------------------ ir/be/becopystat.h | 60 +++++++++++++++++-------------------- ir/be/bemain.c | 21 +++++-------- ir/be/lpp_local.c | 6 ++-- 8 files changed, 145 insertions(+), 125 deletions(-) diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index 63c9fba2a..e1dcabe52 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -24,10 +24,11 @@ #include "becopyopt.h" #include "becopystat.h" -#define DUMP_MPS +#undef DUMP_MPS #define DEBUG_LVL SET_LEVEL_1 static firm_dbg_module_t *dbg = NULL; +#define EPSILON 0.00001 #define SLOTS_LIVING 32 /** @@ -122,7 +123,7 @@ static void pi_find_simplicials(problem_instance_t *pi) { list_add(&s->chain, &pi->simplicials); pset_insert_ptr(pi->removed, irn); redo = 1; - DBG((dbg, LEVEL_2, " Removed %n\n", irn)); + DBG((dbg, LEVEL_2, " Removed %n %d\n", irn, get_irn_graph_nr(irn))); } } } @@ -415,7 +416,6 @@ static void pi_set_start_sol(problem_instance_t *pi) { static void pi_solve_ilp(problem_instance_t *pi, void (*lpp_solve)(lpp_t *)) { pi_set_start_sol(pi); lpp_solve(pi->curr_lp); - DBG((dbg, LEVEL_1, "Solution time: %f\n", lpp_get_sol_time(pi->curr_lp))); } /** @@ -462,27 +462,30 @@ static void pi_apply_solution(problem_instance_t *pi) { DBG((dbg, LEVEL_2, "Applying solution...\n")); #ifdef DO_STAT - //TODO stat + curr_vals[I_ILP_ITER] += lpp_get_iter_cnt(pi->curr_lp); + curr_vals[I_ILP_TIME] += lpp_get_sol_time(pi->curr_lp); #endif sol = xmalloc((pi->last_x_var+1) * sizeof(*sol)); state = lpp_get_solution(pi->curr_lp, sol, 1, pi->last_x_var); if (state != optimal) { printf("Solution state is not 'optimal': %d\n", state); - if (state < feasible) - assert(0); + assert(state >= feasible && "The solution should at least be feasible!"); } - for (i=0; ilast_x_var; ++i) - if (sol[i] == 1.0) { /* split varibale name into components */ - int nnr, col; - char var_name[64]; + for (i=0; ilast_x_var; ++i) { + int nnr, col; + char var_name[64]; + + if (sol[i] > 1-EPSILON) { /* split varibale name into components */ lpp_get_var_name(pi->curr_lp, 1+i, var_name, sizeof(var_name)); if (split_var(var_name, &nnr, &col) == 2) { - DBG((dbg, LEVEL_2, " x%d = %d\n", nnr, col)); + DBG((dbg, LEVEL_2, "Irn %n Idx %d Var %s Val %f\n", get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr), i, var_name, sol[i])); + DBG((dbg, LEVEL_2, "x%d = %d\n", nnr, col)); set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr), col); } else assert(0 && "This should be a x-var"); } + } } void co_ilp_opt(copy_opt_t *co) { diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index 0c404544e..e256cac04 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -122,20 +122,28 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) { INIT_LIST_HEAD(&unit->queue); /* check all args */ - for (i=0; ichordal_env, root, arg)) { - DBG((dbg, LEVEL_1, "\t Member: %n\n", arg)); - if (is_optimizable(arg)) - co_append_unit(co, arg); - unit->nodes[unit->node_count++] = arg; - } else - unit->interf++; + if (is_Phi(root)) { + for (i=0; ichordal_env, root, arg)) { + DBG((dbg, LEVEL_1, "\t Member: %n\n", arg)); + if (is_optimizable(arg)) + co_append_unit(co, arg); + unit->nodes[unit->node_count++] = arg; + } else + unit->interf++; + } } - } - unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes)); + unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes)); + } else if (is_Copy(root)) { + assert(!nodes_interfere(co->chordal_env, root, get_Copy_src(root))); + unit->nodes[unit->node_count++] = get_Copy_src(root); + unit->nodes = xrealloc(unit->nodes, 2 * sizeof(*unit->nodes)); + } else + assert(0 && "This is not an optimizable node!"); + list_add_tail(&unit->units, &co->units); /* Init ifg_mis_size to node_count. So get_lower_bound returns correct results. */ unit->ifg_mis_size = get_ifg_mis_size(unit); @@ -196,13 +204,12 @@ int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) { int i, max; for(i=0, max=get_irn_n_outs(irn); ichordal_env, irn, n))) + if ((is_Phi(n) || is_Perm(n)) && (irn == n || !nodes_interfere(co->chordal_env, irn, n))) return 1; } return 0; } - int co_get_copy_count(const copy_opt_t *co) { int i, res = 0; unit_t *curr; @@ -265,7 +272,7 @@ void co_check_allocation(copy_opt_t *co) { for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) if (nodes_interfere(co->chordal_env, n1, n2) && get_irn_col(co, n1) == get_irn_col(co, n2)) { - DBG((dbg, 0, "Error: %n %d and %n %d have the same color %d.\n", n1, get_irn_graph_nr(n1), n2, get_irn_graph_nr(n2), get_irn_col(co, n1))); + DBG((dbg, 0, "Error in graph %s: %n %d and %n %d have the same color %d.\n", co->name, n1, get_irn_graph_nr(n1), n2, get_irn_graph_nr(n2), get_irn_col(co, n1))); assert(0 && "Interfering values have the same color!"); } } diff --git a/ir/be/becopyopt.h b/ir/be/becopyopt.h index cf49abdcf..4ad0411c2 100644 --- a/ir/be/becopyopt.h +++ b/ir/be/becopyopt.h @@ -30,9 +30,9 @@ #include "bechordal_t.h" #include "bearch.h" -/* TODO is_Copy */ -#define is_Copy(irn) 0 #define DEBUG_IRG "-scanner.c__init_td__gp" +//TODO is_Perm +#define is_Perm(irn) 0 /** * Data representing the problem of copy minimization. @@ -78,6 +78,19 @@ copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env); */ void free_copy_opt(copy_opt_t *co); +/** + * A copy is a proj haning out of perm node + */ +#define is_Copy(irn) (is_Proj(irn) && is_Perm(get_Proj_pred(irn))) + +/** + * returns the corresponding argument of the perm node for a copy + */ +#define get_Copy_src(irn) (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn))) + +/** + * Checks if a node is optimizable, viz. is a target of a 'copy-op' + */ #define is_optimizable(irn) (is_Phi(irn) || is_Copy(irn)) /** @@ -85,13 +98,13 @@ void free_copy_opt(copy_opt_t *co); */ int is_optimizable_arg(const copy_opt_t *co, ir_node *irn); + /** * Returns the current number of copies needed */ int co_get_copy_count(const copy_opt_t *co); /** - * IMPORTANT: Available only iff heuristic has run! * Returns a lower bound for the number of copies needed based on interfering * arguments and the size of a max indep. set (only ifg-edges) of the other args. */ diff --git a/ir/be/becopyoptmain.c b/ir/be/becopyoptmain.c index 26828d80b..73b6ebf2d 100644 --- a/ir/be/becopyoptmain.c +++ b/ir/be/becopyoptmain.c @@ -12,34 +12,34 @@ #include "config.h" #endif +#include "debug.h" #include "becopyopt.h" #include "becopystat.h" #include "becopyoptmain.h" #define DO_HEUR -#define DO_ILP +#undef DO_ILP #define DEBUG_LVL SET_LEVEL_1 static firm_dbg_module_t *dbg = NULL; void be_copy_opt_init(void) { + dbg = firm_dbg_register("ir.be.copyopt"); + firm_dbg_set_mask(dbg, LEVEL_1); } void be_copy_opt(be_chordal_env_t *chordal_env) { copy_opt_t *co; int lb, copies; - dbg = firm_dbg_register("ir.be.copyopt"); - firm_dbg_set_mask(dbg, DEBUG_LVL); - co = new_copy_opt(chordal_env); - DBG((dbg, LEVEL_1, "\n\n ===> %s <===\n\n", co->name)); + DBG((dbg, LEVEL_1, "===> %s <===\n", co->name)); co_check_allocation(co); #ifdef DO_STAT copies = co_get_copy_count(co); curr_vals[I_COPIES_INIT] += copies; - DBG((dbg, 1, "Init copies: %3d\n", copies)); + DBG((dbg, LEVEL_1, "Init copies: %3d\n", copies)); #endif #ifdef DO_HEUR @@ -48,31 +48,26 @@ void be_copy_opt(be_chordal_env_t *chordal_env) { #ifdef DO_STAT copies = co_get_copy_count(co); curr_vals[I_COPIES_HEUR] += copies; - DBG((dbg, 1, "Heur copies: %3d\n", copies)); + DBG((dbg, LEVEL_1, "Heur copies: %3d\n", copies)); #endif - DBG((dbg, 1, "Heur copies: %3d\n", co_get_copy_count(co))); #endif #ifdef DO_ILP lb = co_get_lower_bound(co); copies = co_get_copy_count(co); -//TODO remove checks and enable lb - if (copies=lb && "At least one computation of these two is boooogy"); -// if (copies > lb) { + if (copies > lb) { co_ilp_opt(co); co_check_allocation(co); -// } - copies = co_get_copy_count(co); - assert(copies>=lb && "At least one computation of these two is boooogy"); + } #ifdef DO_STAT copies = co_get_copy_count(co); - curr_vals[I_COPIES_HEUR] += copies; - DBG((dbg, 1, "Opt copies: %3d\n", copies)); + curr_vals[I_COPIES_OPT] += copies; + DBG((dbg, LEVEL_1, "Opt copies: %3d\n", copies)); + assert(copies>=lb && "At least one computation of these two is boooogy"); #endif - DBG((dbg, 1, "Opt copies: %3d\n", co_get_copy_count(co))); #endif free_copy_opt(co); diff --git a/ir/be/becopystat.c b/ir/be/becopystat.c index e9458e573..3f9d7c760 100644 --- a/ir/be/becopystat.c +++ b/ir/be/becopystat.c @@ -21,14 +21,15 @@ static pset *all_phi_nodes; static pset *all_phi_classes; static pset *all_copy_nodes; -void stat_init(void) { +void copystat_init(void) { all_phi_nodes = pset_new_ptr_default(); all_phi_classes = pset_new_ptr_default(); all_copy_nodes = pset_new_ptr_default(); phi_class_init(); + } -void stat_reset(void) { +void copystat_reset(void) { int i; for (i = 0; i < ASIZE; ++i) curr_vals[i] = 0; @@ -53,8 +54,9 @@ static void stat_walker(ir_node *node, void *env) { /** * Collect phi node data */ -static void stat_phi_node(ir_node *phi) { +static void stat_phi_node(be_chordal_env_t *chordal_env, ir_node *phi) { int arity, i; + assert(is_Phi(phi)); /* count all phi phis */ curr_vals[I_PHI_CNT]++; @@ -72,16 +74,17 @@ static void stat_phi_node(ir_node *phi) { ir_node *block_of_arg, *block_ith_pred; ir_node *arg = get_irn_n(phi, i); + if (phi != arg) { + curr_vals[I_COPIES_MAX]++; /* if arg!=phi this is a possible copy */ + if (nodes_interfere(chordal_env, phi, arg)) + curr_vals[I_COPIES_IF]++; + } + if (arg == phi) { curr_vals[I_PHI_ARG_SELF]++; continue; } - curr_vals[I_COPIES_MAX]++; /* if arg!=phi this is a possible copy */ - - if (values_interfere(phi, arg)) - curr_vals[I_COPIES_IF]++; - if (iro_Const == get_irn_opcode(arg)) { curr_vals[I_PHI_ARG_CONST]++; continue; @@ -101,17 +104,19 @@ static void stat_phi_node(ir_node *phi) { /** * Collect register-constrained node data */ -//TODO stat_copy_node -static void stat_copy_node(ir_node *root) { +static void stat_copy_node(be_chordal_env_t *chordal_env, ir_node *root) { curr_vals[I_CPY_CNT]++; -// if (values_interfere(root, arg)) -// curr_vals[I_COPIES_IF]++; + curr_vals[I_COPIES_MAX]++; + if (nodes_interfere(chordal_env, root, get_Copy_src(root))) { + curr_vals[I_COPIES_IF]++; + assert(0 && "A Perm pair (in/out) should never interfere!"); + } } /** * Collect phi class data */ -static void stat_phi_class(pset *pc) { +static void stat_phi_class(be_chordal_env_t *chordal_env, pset *pc) { int i, o, size, if_free; ir_node **members, *p; @@ -136,7 +141,7 @@ static void stat_phi_class(pset *pc) { if_free = 1; for (i = 0; i < size-1; ++i) for (o = i+1; o < size; ++o) - if (values_interfere(members[i], members[o])) { + if (nodes_interfere(chordal_env, members[i], members[o])) { if_free = 0; curr_vals[I_CLS_IF_CNT]++; } @@ -147,27 +152,35 @@ static void stat_phi_class(pset *pc) { xfree(members); } -void stat_collect_irg(ir_graph *irg) { - ir_node *n; - pset *pc; - +void copystat_collect_irg(ir_graph *irg) { irg_walk_graph(irg, stat_walker, NULL, NULL); curr_vals[I_BLOCKS] -= 2; /* substract 2 for start and end block */ - all_phi_classes = phi_class_compute_by_phis(all_phi_nodes); +} - for (n = pset_first(all_phi_nodes); n; n = pset_next(all_phi_nodes)) - stat_phi_node(n); +#define is_curr_reg_class(irn) (arch_get_irn_reg_class(chordal_env->arch_env, irn, arch_pos_make_out(0)) == chordal_env->cls) - for (n = pset_first(all_copy_nodes); n; n = pset_next(all_copy_nodes)) - stat_copy_node(n); +void copystat_collect_cls(be_chordal_env_t *chordal_env) { + ir_node *n; + pset *pc; - for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes)) - stat_phi_class(pc); + for (n = pset_first(all_phi_nodes); n; n = pset_next(all_phi_nodes)) + if (is_curr_reg_class(n)) + stat_phi_node(chordal_env, n); + for (n = pset_first(all_copy_nodes); n; n = pset_next(all_copy_nodes)) + if (is_curr_reg_class(n)) + stat_copy_node(chordal_env, n); + + for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes)) { + ir_node *member = pset_first(pc); + pset_break(pc); + if (is_curr_reg_class(member)) + stat_phi_class(chordal_env, pc); + } } -void stat_dump(ir_graph *irg) { +void copystat_dump(ir_graph *irg) { int i; char buf[1024]; @@ -187,8 +200,8 @@ void stat_dump(ir_graph *irg) { fclose(out); } -//TODO stat_dump_pretty -void stat_dump_pretty(ir_graph *irg) { +//TODO copystat_dump_pretty +void copystat_dump_pretty(ir_graph *irg) { int i; FILE *out = ffopen(get_entity_name(get_irg_entity(irg)), "pretty", "wt"); diff --git a/ir/be/becopystat.h b/ir/be/becopystat.h index 0aa055bc1..c5346e240 100644 --- a/ir/be/becopystat.h +++ b/ir/be/becopystat.h @@ -4,13 +4,12 @@ * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ -#undef DO_STAT - -#ifdef DO_STAT - #ifndef _BECOPYSTAT_H #define _BECOPYSTAT_H +#define DO_STAT +#ifdef DO_STAT + #include "irgraph.h" #define MAX_ARITY 10 @@ -18,7 +17,7 @@ #define MAX_PHASE 2 /** - * For an explanation of these values see phi_stat_dump_pretty + * For an explanation of these values see phi_copystat_dump_pretty */ enum vals_t { I_ALL_NODES = 0, @@ -34,6 +33,9 @@ enum vals_t { I_PHI_ARITY_S, I_PHI_ARITY_E = I_PHI_ARITY_S+MAX_ARITY, + /* copy nodes */ + I_CPY_CNT, /* number of copynodes */ + /* phi classes */ I_CLS_CNT, /* number of phi classes */ I_CLS_IF_FREE, /* number of pc having no interference */ @@ -42,50 +44,42 @@ enum vals_t { I_CLS_SIZE_S, I_CLS_SIZE_E = I_CLS_SIZE_S+MAX_CLS_SIZE, - /* TODO copy nodes */ - I_CPY_CNT, /* number of copynodes */ - - /* TODO ilp values */ - I_ILP_TIME, /* !external set! solving time in 10th seconds */ + /* ilp values */ + I_ILP_TIME, /* !external set! solving time in seconds */ I_ILP_ITER, /* !external set! number of simplex iterations */ /* copy instructions */ I_COPIES_MAX, /* max number of copies possible */ + I_COPIES_IF, /* number of copies inevitable due to root-arg-interf */ I_COPIES_INIT, /* !external set! number of copies in initial allocation */ I_COPIES_HEUR, /* !external set! number of copies after heuristic */ I_COPIES_OPT, /* !external set! number of copies after ilp */ - I_COPIES_LB, /* !external set! the lower bound used for number of copies */ - I_COPIES_IF, /* number of copies inevitable due to root-arg-interf */ ASIZE }; /** - * Holds current values. Values are added till next phi_stat_reset + * Holds current values. Values are added till next copystat_reset */ int curr_vals[ASIZE]; -void stat_init(void); +void copystat_init(void); +void copystat_reset(void); +void copystat_collect_irg(ir_graph *irg); +void copystat_collect_cls(be_chordal_env_t *chordal_env); +void copystat_dump(ir_graph *irg); +void copystat_dump_pretty(ir_graph *irg); -/** - * Resets the array holding the data - */ -void stat_reset(void); - -/** - * Collect common irg data - */ -void stat_collect_irg(ir_graph *irg); +#else /* DO_STAT */ -/** - * Dumps the current contents of the internal values to a file. - */ -void stat_dump(ir_graph *irg); +#define copy_copystat_init(); +#define copystat_reset(); +#define copystat_collect_irg(irg); +#define copystat_collect_cls(env); +#define copystat_dump(irg); +#define copystat_dump(irg); +#define copystat_dump_pretty(irg); -/** - * Dumps the current contents of the values array and annotations to a file. - */ -void stat_dump_pretty(ir_graph *irg); +#endif /* DO_STAT */ -#endif -#endif +#endif /* _BECOPYSTAT_H */ diff --git a/ir/be/bemain.c b/ir/be/bemain.c index 175951572..aab1b0f32 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -49,9 +49,7 @@ void be_init(void) be_numbering_init(); be_ra_chordal_init(); be_copy_opt_init(); -#ifdef DO_STAT - stat_init(); -#endif + copystat_init(); } static be_main_env_t *be_init_env(be_main_env_t *env) @@ -115,9 +113,8 @@ static void be_main_loop(void) /* Liveness analysis */ be_liveness(irg); -#ifdef DO_STAT - stat_reset(); -#endif + copystat_reset(); + copystat_collect_irg(irg); /* Perform the following for each register class. */ for(j = 0, m = isa->get_n_reg_class(); j < m; ++j) { be_chordal_env_t *chordal_env; @@ -126,19 +123,15 @@ static void be_main_loop(void) chordal_env = be_ra_chordal(irg, env.arch_env, cls); #ifdef DUMP_ALLOCATED - dump_allocated_irg(&arch_env, irg, ""); -#endif -#ifdef DO_STAT - stat_collect_irg(irg); + dump_allocated_irg(env.arch_env, irg, ""); #endif + copystat_collect_cls(chordal_env); be_copy_opt(chordal_env); - be_ssa_destruction(&session, chordal_env); + //TODO be_ssa_destruction(&session, chordal_env); be_ra_chordal_done(chordal_env); } -#ifdef DO_STAT - stat_dump(irg); -#endif + copystat_dump(irg); be_numbering_done(irg); } } diff --git a/ir/be/lpp_local.c b/ir/be/lpp_local.c index fd96a1af4..8639569bb 100644 --- a/ir/be/lpp_local.c +++ b/ir/be/lpp_local.c @@ -22,7 +22,7 @@ #include "ilcplex/cplex.h" #define LOGFILE stdout - +#define TIME_LIMIT 30 /* in sec. 0 for none */ static char cpx_cst_encoding[4] = {'?', 'E', 'L', 'G'}; static char cpx_var_encoding[4] = {'?', '?', 'C', 'B'}; @@ -147,6 +147,8 @@ static void cpx_solve(cpx_t *cpx) { CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON); CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, CPX_MIPEMPHASIS_BESTBOUND); CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG); + if (TIME_LIMIT) + CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, TIME_LIMIT); /* solve */ gettimeofday(&tvb, NULL); @@ -172,7 +174,7 @@ static void cpx_solve(cpx_t *cpx) { case CPX_STAT_OPTIMAL: lpp->sol_state = optimal; break; default: lpp->sol_state = unknown; } - assert(lpp->sol_state == optimal); + assert(lpp->sol_state == optimal || lpp->sol_state == feasible); /* get variable solution values */ values = alloca(numcols * sizeof(*values)); -- 2.20.1