#include "bitset.h"
#include "iterator.h"
#include "bipartite.h"
+#include "hungarian.h"
#include "irmode_t.h"
#include "irgraph_t.h"
#include "beutil.h"
#include "besched.h"
-#include "benumb_t.h"
#include "besched_t.h"
#include "belive_t.h"
#include "benode_t.h"
#include "beifg.h"
#include "beinsn_t.h"
#include "bestatevent.h"
+#include "beirg_t.h"
#include "bechordal_t.h"
#include "bechordal_draw.h"
bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
bitset_t *tmp = bitset_alloca(env->cls->n_regs);
ir_node *bl = get_nodes_block(irn);
+ be_lv_t *lv = env->birg->lv;
be_insn_t *insn;
int i, j;
2) lives through the node.
3) is constrained to a register occuring in out constraints.
*/
- if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
+ if(op->has_constraints && values_interfere(lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
/*
only create the copy if the operand is no copy.
this is necessary since the assure constraints phase inserts
sched_add_before(insn->irn, copy);
set_irn_n(insn->irn, op->pos, copy);
DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
- be_liveness_update(env->lv, op->carrier);
+ be_liveness_update(lv, op->carrier);
}
}
}
int n_defs = be_insn_n_defs(insn);
bitset_t *bs = bitset_alloca(env->cls->n_regs);
int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
+ be_lv_t *lv = env->birg->lv;
int i, j;
int n_total;
const be_operand_t *op = &insn->ops[i];
- if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
+ if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
bitset_clear_all(bs);
bitset_copy(bs, op->regs);
bitset_and(bs, out_op->regs);
ir_node *perm = NULL;
bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
bitset_t *bs = bitset_alloca(env->cls->n_regs);
+ be_lv_t *lv = env->birg->lv;
DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
int i;
Make the Perm, recompute liveness and re-scan the insn since the
in operands are now the Projs of the Perm.
*/
- perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
+ perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
/* Registers are propagated by insert_Perm_after(). Clean them here! */
if(perm) {
the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
the live sets may change.
*/
- // be_liveness_recompute(env->lv);
+ // be_liveness_recompute(lv);
obstack_free(&env->obst, insn);
*the_insn = insn = chordal_scan_insn(env, insn->irn);
be_insn_t *insn = chordal_scan_insn(env, irn);
ir_node *res = insn->next_insn;
int be_silent = *silent;
+ be_lv_t *lv = env->birg->lv;
if(insn->pre_colored) {
int i;
int n_regs = env->cls->n_regs;
bitset_t *bs = bitset_alloca(n_regs);
ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
- bipartite_t *bp = bipartite_new(n_regs, n_regs);
+ hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
+// bipartite_t *bp = bipartite_new(n_regs, n_regs);
int *assignment = alloca(n_regs * sizeof(assignment[0]));
pmap *partners = pmap_create();
DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
long col;
const ir_edge_t *edge;
ir_node *perm = NULL;
+ int match_res, cost;
/*
prepare the constraint handling of this node.
DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
bitset_foreach(bs, col)
- bipartite_add(bp, n_alloc, col);
+ hungarian_add(bp, n_alloc, col, 1);
+// bipartite_add(bp, n_alloc, col);
n_alloc++;
}
assert(is_Proj(proj));
- if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
+ if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
assert(n_alloc < n_regs);
alloc_nodes[n_alloc] = proj;
pmap_insert(partners, proj, NULL);
arch_put_non_ignore_regs(aenv, env->cls, bs);
bitset_andnot(bs, env->ignore_colors);
bitset_foreach(bs, col)
- bipartite_add(bp, n_alloc, col);
+ hungarian_add(bp, n_alloc, col, 1);
+// bipartite_add(bp, n_alloc, col);
n_alloc++;
}
}
/* Compute a valid register allocation. */
- bipartite_matching(bp, assignment);
+ hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
+ match_res = hungarian_solve(bp, assignment, &cost, 1);
+ assert(match_res == 0 && "matching failed");
+ //bipartite_matching(bp, assignment);
/* Assign colors obtained from the matching. */
for(i = 0; i < n_alloc; ++i) {
continue;
arch_set_irn_register(aenv, nodes[j], reg);
- pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
+ (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
}
}
}
}
- bipartite_free(bp);
+ //bipartite_free(bp);
+ hungarian_free(bp);
pmap_destroy(partners);
}
be_chordal_env_t *env = alloc_env->chordal_env;
bitset_t *live = alloc_env->live;
ir_node *irn;
+ be_lv_t *lv = env->birg->lv;
DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
int i, n;
unsigned step = 0;
unsigned pressure = 0;
struct list_head *head;
- pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
- pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
+ pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
+ pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
bitset_clear_all(live);
bitset_t *in_colors = alloc_env->in_colors;
const arch_env_t *arch_env = env->birg->main_env->arch_env;
struct list_head *head = get_block_border_head(env, block);
- pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
+ be_lv_t *lv = env->birg->lv;
+ pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
const ir_node *irn;
border_t *b;
* Assign a color, if it is a local def. Global defs already have a
* color.
*/
- if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
+ if(b->is_def && !be_is_live_in(lv, block, irn)) {
const arch_register_t *reg;
int col = NO_COLOR;
{
be_chordal_alloc_env_t env;
char buf[256];
+ be_irg_t *birg = chordal_env->birg;
int colors_n = arch_register_class_n_regs(chordal_env->cls);
ir_graph *irg = chordal_env->irg;
+ be_assure_dom_front(birg);
+ be_assure_liveness(birg);
assure_doms(irg);
env.chordal_env = chordal_env;
/* Assign the colors */
dom_tree_walk_irg(irg, assign, NULL, &env);
- be_numbering_done(irg);
-
if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
plotter_t *plotter;
ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
projects / libfirm / blobdiff