+static void congruence_def(ir_nodeset_t *live_nodes, ir_node *node)
+{
+ const arch_register_req_t *req;
+
+ if (get_irn_mode(node) == mode_T) {
+ const ir_edge_t *edge;
+ foreach_out_edge(node, edge) {
+ ir_node *def = get_edge_src_irn(edge);
+ congruence_def(live_nodes, def);
+ }
+ return;
+ }
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ return;
+
+ /* should be same constraint? */
+ req = arch_get_register_req_out(node);
+ if (req->type & arch_register_req_type_should_be_same) {
+ ir_node *insn = skip_Proj(node);
+ int arity = get_irn_arity(insn);
+ int i;
+ unsigned node_idx = get_irn_idx(node);
+ node_idx = uf_find(congruence_classes, node_idx);
+
+ for (i = 0; i < arity; ++i) {
+ ir_node *live;
+ ir_node *op;
+ int op_idx;
+ ir_nodeset_iterator_t iter;
+ bool interferes = false;
+
+ if (!rbitset_is_set(&req->other_same, i))
+ continue;
+
+ op = get_irn_n(insn, i);
+ op_idx = get_irn_idx(op);
+ op_idx = uf_find(congruence_classes, op_idx);
+
+ /* do we interfere with the value */
+ foreach_ir_nodeset(live_nodes, live, iter) {
+ int lv_idx = get_irn_idx(live);
+ lv_idx = uf_find(congruence_classes, lv_idx);
+ if (lv_idx == op_idx) {
+ interferes = true;
+ break;
+ }
+ }
+ /* don't put in same affinity class if we interfere */
+ if (interferes)
+ continue;
+
+ node_idx = uf_union(congruence_classes, node_idx, op_idx);
+ DB((dbg, LEVEL_3, "Merge %+F and %+F congruence classes\n",
+ node, op));
+ /* one should_be_same is enough... */
+ break;
+ }
+ }
+}
+
+static void create_congurence_class(ir_node *block, void *data)
+{
+ ir_nodeset_t live_nodes;
+ ir_node *node;
+
+ (void) data;
+ ir_nodeset_init(&live_nodes);
+ be_liveness_end_of_block(lv, cls, block, &live_nodes);
+
+ /* check should be same constraints */
+ sched_foreach_reverse(block, node) {
+ if (is_Phi(node))
+ break;
+
+ congruence_def(&live_nodes, node);
+ be_liveness_transfer(cls, node, &live_nodes);
+ }
+
+ /* check phi congruence classes */
+ sched_foreach_reverse_from(node, node) {
+ int i;
+ int arity;
+ int node_idx;
+ assert(is_Phi(node));
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+
+ node_idx = get_irn_idx(node);
+ node_idx = uf_find(congruence_classes, node_idx);
+
+ arity = get_irn_arity(node);
+ for (i = 0; i < arity; ++i) {
+ bool interferes = false;
+ ir_nodeset_iterator_t iter;
+ ir_node *live;
+ ir_node *phi;
+ ir_node *op = get_Phi_pred(node, i);
+ int op_idx = get_irn_idx(op);
+ op_idx = uf_find(congruence_classes, op_idx);
+
+ /* do we interfere with the value */
+ foreach_ir_nodeset(&live_nodes, live, iter) {
+ int lv_idx = get_irn_idx(live);
+ lv_idx = uf_find(congruence_classes, lv_idx);
+ if (lv_idx == op_idx) {
+ interferes = true;
+ break;
+ }
+ }
+ /* don't put in same affinity class if we interfere */
+ if (interferes)
+ continue;
+ /* any other phi has the same input? */
+ sched_foreach(block, phi) {
+ ir_node *oop;
+ int oop_idx;
+ if (!is_Phi(phi))
+ break;
+ if (!arch_irn_consider_in_reg_alloc(cls, phi))
+ continue;
+ oop = get_Phi_pred(phi, i);
+ if (oop == op)
+ continue;
+ oop_idx = get_irn_idx(oop);
+ oop_idx = uf_find(congruence_classes, oop_idx);
+ if (oop_idx == op_idx) {
+ interferes = true;
+ break;
+ }
+ }
+ if (interferes)
+ continue;
+
+ node_idx = uf_union(congruence_classes, node_idx, op_idx);
+ DB((dbg, LEVEL_3, "Merge %+F and %+F congruence classes\n",
+ node, op));
+ }
+ }
+}
+
+static void merge_congruence_prefs(ir_node *node, void *data)
+{
+ allocation_info_t *info;
+ allocation_info_t *head_info;
+ unsigned node_idx = get_irn_idx(node);
+ unsigned node_set = uf_find(congruence_classes, node_idx);
+ unsigned r;
+
+ (void) data;
+
+ /* head of congruence class or not in any class */
+ if (node_set == node_idx)
+ return;
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ return;
+
+ head_info = get_allocation_info(get_idx_irn(irg, node_set));
+ info = get_allocation_info(node);
+
+ for (r = 0; r < n_regs; ++r) {
+ head_info->prefs[r] += info->prefs[r];
+ }
+}
+
+static void set_congruence_prefs(ir_node *node, void *data)
+{
+ allocation_info_t *info;
+ allocation_info_t *head_info;
+ unsigned node_idx = get_irn_idx(node);
+ unsigned node_set = uf_find(congruence_classes, node_idx);
+
+ (void) data;
+
+ /* head of congruence class or not in any class */
+ if (node_set == node_idx)
+ return;
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ return;
+
+ head_info = get_allocation_info(get_idx_irn(irg, node_set));
+ info = get_allocation_info(node);
+
+ memcpy(info->prefs, head_info->prefs, n_regs * sizeof(info->prefs[0]));
+}
+
+static void combine_congruence_classes(void)
+{
+ size_t n = get_irg_last_idx(irg);
+ congruence_classes = XMALLOCN(int, n);
+ uf_init(congruence_classes, n);
+
+ /* create congruence classes */
+ irg_block_walk_graph(irg, create_congurence_class, NULL, NULL);
+ /* merge preferences */
+ irg_walk_graph(irg, merge_congruence_prefs, NULL, NULL);
+ irg_walk_graph(irg, set_congruence_prefs, NULL, NULL);
+}
+
+
+
+
+