From 321855ff2c234518e0ac8d794903eb78d23fc1fa Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Fri, 15 Jul 2011 14:01:30 +0200 Subject: [PATCH] lpp: call the constraint types lpp_{less|greater}_equal because they are a {less|greater} equal operation --- ir/be/beblocksched.c | 4 +- ir/be/becopyilp2.c | 8 +-- ir/be/beprefalloc.c | 113 +++++++++++++++++++++++++++++++++++++++++++ ir/lpp/lpp.c | 12 ++--- ir/lpp/lpp.h | 4 +- 5 files changed, 127 insertions(+), 14 deletions(-) diff --git a/ir/be/beblocksched.c b/ir/be/beblocksched.c index acf396d2d..a398d4a5f 100644 --- a/ir/be/beblocksched.c +++ b/ir/be/beblocksched.c @@ -584,7 +584,7 @@ static void collect_egde_frequency_ilp(ir_node *block, void *data) entry->block = block; entry->next = NULL; entry->prev = NULL; - entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1); + entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1); set_irn_link(block, entry); if (block == startblock) @@ -599,7 +599,7 @@ static void collect_egde_frequency_ilp(ir_node *block, void *data) int i; snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block)); - cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, arity - 1); + cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1); for (i = 0; i < arity; ++i) { double execfreq; diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c index f87719ba7..395b6b5bc 100644 --- a/ir/be/becopyilp2.c +++ b/ir/be/becopyilp2.c @@ -152,7 +152,7 @@ static void build_interference_cstr(ilp_env_t *ienv) /* for all colors */ for (col=0; collp, NULL, lpp_less, 0.0); + int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_less_equal, 0.0); root_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', root_nr, col)); arg_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', arg_nr, col)); @@ -382,7 +382,7 @@ static void build_clique_star_cstr(ilp_env_t *ienv) int var_idx, cst_idx, center_nr, member_nr; char buf[16]; - cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, pset_count(clique)-1); + cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, pset_count(clique)-1); center_nr = get_irn_idx(center); pset_foreach(clique, member) { @@ -439,7 +439,7 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) /* And a path of length 2 is covered by a clique star constraint. */ if (len > 2) { /* finally build the constraint */ - int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, 1.0); + int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, 1.0); for (i=1; i #include #include +#include "lpp.h" #include "error.h" #include "execfreq.h" @@ -1105,6 +1106,108 @@ static void determine_live_through_regs(unsigned *bitset, ir_node *node) } } +static void solve_lpp(ir_nodeset_t *live_nodes, ir_node *node, + unsigned *forbidden_regs, unsigned *live_through_regs) +{ + unsigned *forbidden_edges = rbitset_malloc(n_regs * n_regs); + int *lpp_vars = XMALLOCNZ(int, n_regs*n_regs); + int arity = get_irn_arity(node); + int i; + unsigned l; + unsigned r; + + lpp_t *lpp = lpp_new("prefalloc", lpp_minimize); + //lpp_set_time_limit(lpp, 20); + lpp_set_log(lpp, stdout); + + /** mark some edges as forbidden */ + for (i = 0; i < arity; ++i) { + ir_node *op = get_irn_n(node, i); + const arch_register_t *reg; + const arch_register_req_t *req; + const unsigned *limited; + unsigned current_reg; + + if (!arch_irn_consider_in_reg_alloc(cls, op)) + continue; + + req = arch_get_register_req(node, i); + if (!(req->type & arch_register_req_type_limited)) + continue; + + limited = req->limited; + reg = arch_get_irn_register(op); + current_reg = arch_register_get_index(reg); + for (r = 0; r < n_regs; ++r) { + if (rbitset_is_set(limited, r)) + continue; + + rbitset_set(forbidden_edges, current_reg*n_regs + r); + } + } + + /* add all combinations, then remove not allowed ones */ + for (l = 0; l < n_regs; ++l) { + for (r = 0; r < n_regs; ++r) { + if (!rbitset_is_set(normal_regs, r)) + continue; + if (rbitset_is_set(forbidden_edges, l*n_regs + r)) + continue; + /* livethrough values may not use constrained output registers */ + if (rbitset_is_set(live_through_regs, l) + && rbitset_is_set(forbidden_regs, r)) + continue; + + double costs = l==r ? 9 : 8; + lpp_vars[l*n_regs+r] + = lpp_add_var(lpp, NULL, lpp_binary, costs); + assert(lpp_vars[l*n_regs+r] > 0); + } + } + /* add constraints */ + for (l = 0; l < n_regs; ++l) { + /* only 1 destination per register */ + int constraint = lpp_add_cst(lpp, NULL, lpp_equal, 1); + for (r = 0; r < n_regs; ++r) { + int var = lpp_vars[l*n_regs+r]; + if (var == 0) + continue; + lpp_set_factor_fast(lpp, constraint, var, 1); + } + /* each destination used by at most 1 value */ + constraint = lpp_add_cst(lpp, NULL, lpp_less_equal, 1); + } + + /* solve lpp */ + { + ir_graph *irg = get_irn_irg(node); + be_options_t *options = be_get_irg_options(irg); + unsigned *assignment; + lpp_solve(lpp, options->ilp_server, options->ilp_solver); + if (!lpp_is_sol_valid(lpp)) + panic("ilp solution not valid!"); + + assignment = ALLOCAN(unsigned, n_regs); + for (l = 0; l < n_regs; ++l) { + unsigned dest_reg = (unsigned)-1; + for (r = 0; r < n_regs; ++r) { + int var = lpp_vars[l*n_regs+r]; + if (var == 0) + continue; + double val = lpp_get_var_sol(lpp, var); + if (val == 1) { + assert(dest_reg == (unsigned)-1); + dest_reg = r; + } + } + assert(dest_reg != (unsigned)-1); + assignment[l] = dest_reg; + } + permute_values(live_nodes, node, assignment); + } + lpp_free(lpp); +} + /** * Enforce constraints at a node by live range splits. * @@ -1125,6 +1228,7 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, unsigned *live_through_regs = NULL; /* see if any use constraints are not met */ + bool double_width = false; bool good = true; for (i = 0; i < arity; ++i) { ir_node *op = get_irn_n(node, i); @@ -1138,6 +1242,8 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, /* are there any limitations for the i'th operand? */ req = arch_get_register_req(node, i); + if (req->width > 1) + double_width = true; if (!(req->type & arch_register_req_type_limited)) continue; @@ -1153,6 +1259,8 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, /* is any of the live-throughs using a constrained output register? */ be_foreach_definition(node, cls, value, + if (req_->width > 1) + double_width = true; if (! (req_->type & arch_register_req_type_limited)) continue; if (live_through_regs == NULL) { @@ -1172,6 +1280,11 @@ static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node, rbitset_alloca(live_through_regs, n_regs); } + if (double_width) { + solve_lpp(live_nodes, node, forbidden_regs, live_through_regs); + return; + } + /* at this point we have to construct a bipartite matching problem to see * which values should go to which registers * Note: We're building the matrix in "reverse" - source registers are diff --git a/ir/lpp/lpp.c b/ir/lpp/lpp.c index 9ec81583b..cfb7cc8c8 100644 --- a/ir/lpp/lpp.c +++ b/ir/lpp/lpp.c @@ -363,14 +363,14 @@ void lpp_check_startvals(lpp_t *lpp) fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val); } break; - case lpp_less: + case lpp_less_equal: if(sum > cst_val) { - fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val); + fprintf(stderr, "constraint %s unsatisfied: %g >= %g\n", cst->name, sum, cst_val); } break; - case lpp_greater: + case lpp_greater_equal: if(sum < cst_val) { - fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val); + fprintf(stderr, "constraint %s unsatisfied: %g <= %g\n", cst->name, sum, cst_val); } break; default: @@ -398,9 +398,9 @@ static const char *lpp_cst_op_to_str(lpp_cst_t cst) switch(cst) { case lpp_equal: return "="; - case lpp_less: + case lpp_less_equal: return "<="; - case lpp_greater: + case lpp_greater_equal: return ">="; default: return ""; diff --git a/ir/lpp/lpp.h b/ir/lpp/lpp.h index 29f9022b3..71e30d7a3 100644 --- a/ir/lpp/lpp.h +++ b/ir/lpp/lpp.h @@ -41,8 +41,8 @@ typedef enum _lpp_opt_t { typedef enum _lpp_cst_t { lpp_objective, lpp_equal, - lpp_less, - lpp_greater + lpp_less_equal, + lpp_greater_equal } lpp_cst_t; typedef enum _lpp_var_t { -- 2.20.1