+ unsigned has_constraints : 1;
+};
+
+typedef struct {
+ operand_t *ops;
+ int n_ops;
+ int use_start;
+ ir_node *next_insn;
+ ir_node *irn;
+ unsigned in_constraints : 1;
+ unsigned out_constraints : 1;
+ unsigned has_constraints : 1;
+ unsigned pre_colored : 1;
+} insn_t;
+
+#define insn_n_defs(insn) ((insn)->use_start)
+#define insn_n_uses(insn) ((insn)->n_ops - (insn)->use_start)
+
+static insn_t *scan_insn(be_chordal_env_t *env, ir_node *irn, struct obstack *obst)
+{
+ const arch_env_t *arch_env = env->birg->main_env->arch_env;
+ operand_t o;
+ insn_t *insn;
+ int i, n;
+ int pre_colored = 0;
+
+ insn = obstack_alloc(obst, sizeof(insn[0]));
+ memset(insn, 0, sizeof(insn[0]));
+
+ insn->irn = irn;
+ insn->next_insn = sched_next(irn);
+ if(get_irn_mode(irn) == mode_T) {
+ ir_node *p;
+
+ for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
+ if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
+ arch_get_register_req(arch_env, &o.req, p, -1);
+ o.carrier = p;
+ o.irn = irn;
+ o.pos = -(get_Proj_proj(p) + 1);
+ o.partner = NULL;
+ o.has_constraints = arch_register_req_is(&o.req, limited);
+ obstack_grow(obst, &o, sizeof(o));
+ insn->n_ops++;
+ insn->out_constraints |= o.has_constraints;
+ pre_colored += arch_get_irn_register(arch_env, p) != NULL;
+ }
+ }
+
+ insn->next_insn = p;
+ }
+
+ else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
+ arch_get_register_req(arch_env, &o.req, irn, -1);
+ o.carrier = irn;
+ o.irn = irn;
+ o.pos = -1;
+ o.partner = NULL;
+ o.has_constraints = arch_register_req_is(&o.req, limited);
+ obstack_grow(obst, &o, sizeof(o));
+ insn->n_ops++;
+ insn->out_constraints |= o.has_constraints;
+ pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
+ }
+
+ insn->pre_colored = pre_colored == insn->n_ops && insn->n_ops > 0;
+ insn->use_start = insn->n_ops;
+
+ for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
+ ir_node *op = get_irn_n(irn, i);
+
+ if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
+ arch_get_register_req(arch_env, &o.req, irn, i);
+ o.carrier = op;
+ o.irn = irn;
+ o.pos = i;
+ o.partner = NULL;
+ o.has_constraints = arch_register_req_is(&o.req, limited);
+ obstack_grow(obst, &o, sizeof(o));
+ insn->n_ops++;
+ insn->in_constraints |= o.has_constraints;
+ }
+ }
+
+ insn->has_constraints = insn->in_constraints | insn->out_constraints;
+ insn->ops = obstack_finish(obst);
+
+ /* Compute the admissible registers bitsets. */
+ for(i = 0; i < insn->n_ops; ++i) {
+ operand_t *op = &insn->ops[i];
+
+ assert(op->req.cls == env->cls);
+ op->regs = bitset_obstack_alloc(obst, env->cls->n_regs);
+
+ if(arch_register_req_is(&op->req, limited))
+ op->req.limited(op->req.limited_env, op->regs);
+ else
+ arch_put_non_ignore_regs(env->birg->main_env->arch_env, env->cls, op->regs);
+ }
+
+ return insn;
+}
+
+static bitset_t *get_decisive_partner_regs(bitset_t *bs, const operand_t *o1, const operand_t *o2)
+{
+ bitset_t *res = bs;
+
+ if(!o1) {
+ bitset_copy(bs, o2->regs);
+ return bs;
+ }
+
+ if(!o2) {
+ bitset_copy(bs, o1->regs);
+ return bs;
+ }
+
+ assert(o1->req.cls == o2->req.cls);
+
+ if(bitset_contains(o1->regs, o2->regs))
+ bitset_copy(bs, o1->regs);
+ else if(bitset_contains(o2->regs, o1->regs))
+ bitset_copy(bs, o2->regs);
+ else
+ res = NULL;
+
+ return res;
+}
+
+static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, insn_t *insn)
+{
+ const be_chordal_env_t *env = alloc_env->chordal_env;
+ const arch_env_t *aenv = env->birg->main_env->arch_env;
+ firm_dbg_module_t *dbg = alloc_env->constr_dbg;
+
+ int n_uses = insn_n_uses(insn);
+ int n_defs = insn_n_defs(insn);
+ int max_pairs = MIN(n_uses, n_defs);
+ bitset_t *bs = bitset_alloca(env->cls->n_regs);
+ bipartite_t *bp = bipartite_new(n_defs, n_uses);
+ int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));