+ int a;
+ ir_node *op;
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+
+ op = get_Phi_pred(node, p);
+ /* no need to do anything for Unknown inputs */
+ if (!arch_irn_consider_in_reg_alloc(cls, op))
+ continue;
+
+ /* we have permuted all values into the correct registers so we can
+ simply query which value occupies the phis register in the
+ predecessor */
+ a = arch_register_get_index(arch_get_irn_register(node));
+ op = pred_info->assignments[a];
+ set_Phi_pred(node, p, op);
+ }
+}
+
+/**
+ * Set preferences for a phis register based on the registers used on the
+ * phi inputs.
+ */
+static void adapt_phi_prefs(ir_node *phi)
+{
+ int i;
+ int arity = get_irn_arity(phi);
+ ir_node *block = get_nodes_block(phi);
+ allocation_info_t *info = get_allocation_info(phi);
+
+ for (i = 0; i < arity; ++i) {
+ ir_node *op = get_irn_n(phi, i);
+ const arch_register_t *reg = arch_get_irn_register(op);
+ ir_node *pred_block;
+ block_info_t *pred_block_info;
+ float weight;
+ unsigned r;
+
+ if (reg == NULL)
+ continue;
+ /* we only give the bonus if the predecessor already has registers
+ * assigned, otherwise we only see a dummy value
+ * and any conclusions about its register are useless */
+ pred_block = get_Block_cfgpred_block(block, i);
+ pred_block_info = get_block_info(pred_block);
+ if (!pred_block_info->processed)
+ continue;
+
+ /* give bonus for already assigned register */
+ weight = get_block_execfreq(execfreqs, pred_block);
+ r = arch_register_get_index(reg);
+ info->prefs[r] += weight * AFF_PHI;
+ }
+}
+
+/**
+ * After a phi has been assigned a register propagate preference inputs
+ * to the phi inputs.
+ */
+static void propagate_phi_register(ir_node *phi, unsigned assigned_r)
+{
+ int i;
+ ir_node *block = get_nodes_block(phi);
+ int arity = get_irn_arity(phi);
+
+ for (i = 0; i < arity; ++i) {
+ ir_node *op = get_Phi_pred(phi, i);
+ allocation_info_t *info = get_allocation_info(op);
+ ir_node *pred_block = get_Block_cfgpred_block(block, i);
+ unsigned r;
+ float weight
+ = get_block_execfreq(execfreqs, pred_block) * AFF_PHI;
+
+ if (info->prefs[assigned_r] >= weight)
+ continue;
+
+ /* promote the prefered register */
+ for (r = 0; r < n_regs; ++r) {
+ if (r == assigned_r) {
+ info->prefs[r] = AFF_PHI * weight;
+ } else {
+ info->prefs[r] -= AFF_PHI * weight;
+ }
+ }
+
+ if (is_Phi(op))
+ propagate_phi_register(op, assigned_r);
+ }
+}
+
+static void assign_phi_registers(ir_node *block)
+{
+ int n_phis = 0;
+ int n;
+ int res;
+ int *assignment;
+ ir_node *node;
+ hungarian_problem_t *bp;
+
+ /* count phi nodes */
+ sched_foreach(block, node) {
+ if (!is_Phi(node))
+ break;
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+ ++n_phis;
+ }
+
+ if (n_phis == 0)
+ return;
+
+ /* build a bipartite matching problem for all phi nodes */
+ bp = hungarian_new(n_phis, n_regs, HUNGARIAN_MATCH_PERFECT);
+ n = 0;
+ sched_foreach(block, node) {
+ unsigned r;
+
+ allocation_info_t *info;
+ if (!is_Phi(node))
+ break;
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+
+ /* give boni for predecessor colorings */
+ adapt_phi_prefs(node);
+ /* add stuff to bipartite problem */
+ info = get_allocation_info(node);
+ DB((dbg, LEVEL_3, "Prefs for %+F: ", node));
+ for (r = 0; r < n_regs; ++r) {
+ float costs;
+
+ if (!rbitset_is_set(normal_regs, r))
+ continue;
+
+ costs = info->prefs[r];
+ costs = costs < 0 ? -logf(-costs+1) : logf(costs+1);
+ costs *= 100;
+ costs += 10000;
+ hungarian_add(bp, n, r, costs);
+ DB((dbg, LEVEL_3, " %s(%f)", arch_register_for_index(cls, r)->name,
+ info->prefs[r]));
+ }
+ DB((dbg, LEVEL_3, "\n"));
+ ++n;
+ }
+
+ //hungarian_print_cost_matrix(bp, 7);
+ hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
+
+ assignment = ALLOCAN(int, n_regs);
+ res = hungarian_solve(bp, assignment, NULL, 0);
+ assert(res == 0);
+
+ /* apply results */
+ n = 0;
+ sched_foreach(block, node) {
+ unsigned r;
+ const arch_register_t *reg;
+
+ if (!is_Phi(node))
+ break;
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+
+ r = assignment[n++];
+ assert(rbitset_is_set(normal_regs, r));
+ reg = arch_register_for_index(cls, r);
+ DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name));
+ use_reg(node, reg);
+
+ /* adapt preferences for phi inputs */
+ propagate_phi_register(node, r);
+ }
+}
+
+/**
+ * Walker: assign registers to all nodes of a block that
+ * need registers from the currently considered register class.
+ */
+static void allocate_coalesce_block(ir_node *block, void *data)
+{
+ int i;
+ ir_nodeset_t live_nodes;
+ ir_nodeset_iterator_t iter;
+ ir_node *node;
+ int n_preds;
+ block_info_t *block_info;
+ block_info_t **pred_block_infos;
+ ir_node **phi_ins;
+ unsigned *forbidden_regs; /**< collects registers which must
+ not be used for optimistic splits */
+
+ (void) data;
+ DB((dbg, LEVEL_2, "* Block %+F\n", block));
+
+ /* clear assignments */
+ block_info = get_block_info(block);
+ assignments = block_info->assignments;
+
+ ir_nodeset_init(&live_nodes);
+
+ /* gather regalloc infos of predecessor blocks */
+ n_preds = get_Block_n_cfgpreds(block);
+ pred_block_infos = ALLOCAN(block_info_t*, n_preds);
+ for (i = 0; i < n_preds; ++i) {
+ ir_node *pred = get_Block_cfgpred_block(block, i);
+ block_info_t *pred_info = get_block_info(pred);
+ pred_block_infos[i] = pred_info;
+ }
+
+ phi_ins = ALLOCAN(ir_node*, n_preds);
+
+ /* collect live-in nodes and preassigned values */
+ be_lv_foreach(lv, block, be_lv_state_in, i) {