+ ir_edge_t *edge;
+ op_t *op = get_irn_link(irn);
+ pset *visited_users = pset_new_ptr_default();
+ int paths = 0;
+
+ if(op->is_remat) return;
+
+ pset_insert_ptr(visited, irn);
+
+ if(is_Phi(irn)) {
+ int n;
+ pset *visited_operands = pset_new_ptr(get_irn_arity(irn));
+
+ /* visit all operands */
+ for(n=get_irn_arity(irn)-1; n>=0; --n) {
+ ir_node *arg = get_irn_n(irn, n);
+ ilp_var_t copy = op->attr.live_range.args.copies[n];
+
+ if(!has_reg_class(si, arg)) continue;
+ if(pset_find_ptr(visited_operands, arg)) continue;
+ pset_insert_ptr(visited_operands, arg);
+
+ if(arg == target) {
+ if(++paths > MAX_PATHS && pset_count(copies) != 0) {
+ del_pset(visited_operands);
+ del_pset(visited_users);
+ pset_remove_ptr(visited, irn);
+ return paths;
+ }
+ pset_insert(copies, INT_TO_PTR(copy), copy);
+ write_copy_path_cst(si, copies, any_interfere);
+ pset_remove(copies, INT_TO_PTR(copy), copy);
+ } else if(!pset_find_ptr(visited, arg)) {
+ pset_insert(copies, INT_TO_PTR(copy), copy);
+ paths += find_copy_path(si, arg, target, any_interfere, copies, visited);
+ pset_remove(copies, INT_TO_PTR(copy), copy);
+
+ if(paths > MAX_PATHS) {
+ if(pset_count(copies) == 0) {
+ ilp_cst_t cst;
+ char buf[256];
+
+ ir_snprintf(buf, sizeof(buf), "always_copy-%d-%d", any_interfere, copy);
+ cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0);
+ lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, copy, 1.0);
+ DBG((si->dbg, LEVEL_1, "ALWAYS COPYING %d FOR INTERFERENCE %d\n", copy, any_interfere));
+
+ paths = 0;
+ } else {
+ del_pset(visited_operands);
+ del_pset(visited_users);
+ pset_remove_ptr(visited, irn);
+ return paths;
+ }
+ }
+ }
+ }
+
+ del_pset(visited_operands);
+ }
+
+ /* visit all uses which are phis */
+ foreach_out_edge(irn, edge) {
+ ir_node *user = edge->src;
+ int pos = edge->pos;
+ op_t *op = get_irn_link(user);
+ ilp_var_t copy;
+
+ if(!is_Phi(user)) continue;
+ if(!has_reg_class(si, user)) continue;
+ if(pset_find_ptr(visited_users, user)) continue;
+ pset_insert_ptr(visited_users, user);
+
+ copy = op->attr.live_range.args.copies[pos];
+
+ if(user == target) {
+ if(++paths > MAX_PATHS && pset_count(copies) != 0) {
+ del_pset(visited_users);
+ pset_remove_ptr(visited, irn);
+ return paths;
+ }
+ pset_insert(copies, INT_TO_PTR(copy), copy);
+ write_copy_path_cst(si, copies, any_interfere);
+ pset_remove(copies, INT_TO_PTR(copy), copy);
+ } else if(!pset_find_ptr(visited, user)) {
+ pset_insert(copies, INT_TO_PTR(copy), copy);
+ paths += find_copy_path(si, user, target, any_interfere, copies, visited);
+ pset_remove(copies, INT_TO_PTR(copy), copy);
+
+ if(paths > MAX_PATHS) {
+ if(pset_count(copies) == 0) {
+ ilp_cst_t cst;
+ char buf[256];
+
+ ir_snprintf(buf, sizeof(buf), "always_copy-%d-%d", any_interfere, copy);
+ cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0);
+ lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, copy, 1.0);
+ DBG((si->dbg, LEVEL_1, "ALWAYS COPYING %d FOR INTERFERENCE %d\n", copy, any_interfere));
+
+ paths = 0;
+ } else {
+ del_pset(visited_users);
+ pset_remove_ptr(visited, irn);
+ return paths;
+ }
+ }
+ }
+ }
+
+ del_pset(visited_users);
+ pset_remove_ptr(visited, irn);
+ return paths;
+}
+
+static void
+gen_copy_constraints(spill_ilp_t * si, ir_node * a, ir_node * b, ilp_var_t any_interfere)
+{
+ pset * copies = pset_new_ptr_default();
+ pset * visited = pset_new_ptr_default();
+
+ find_copy_path(si, a, b, any_interfere, copies, visited);
+
+ del_pset(visited);
+ del_pset(copies);
+}
+
+
+static void
+memcopyhandler(spill_ilp_t * si)
+{
+ interference_t *interference;
+ char buf[256];
+ /* teste Speicherwerte auf Interferenz */
+
+ /* analyze phi classes */
+ phi_class_compute(si->chordal_env->irg);
+
+ DBG((si->dbg, LEVEL_2, "\t calling interferencewalker\n"));
+ irg_block_walk_graph(si->chordal_env->irg, luke_interferencewalker, NULL, si);
+
+ /* now lets emit the ILP unequations for the crap */
+ set_foreach(si->interferences, interference) {
+ irnlist_t *irnlist;
+ ilp_var_t interfere,
+ any_interfere;
+ ilp_cst_t any_interfere_cst,
+ cst;
+ const ir_node *a = interference->a;
+ const ir_node *b = interference->b;
+
+ /* any_interf <= \sum interf */
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N", a, b);
+ any_interfere_cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+ any_interfere = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
+
+ lpp_set_factor_fast(si->lpp, any_interfere_cst, any_interfere, 1.0);
+
+ list_for_each_entry(irnlist_t, irnlist, &interference->blocklist, list) {
+ const ir_node *bb = irnlist->irn;
+ spill_bb_t *spill_bb = get_irn_link(bb);
+ spill_t *spilla,
+ *spillb,
+ query;
+ char buf[256];
+
+ query.irn = a;
+ spilla = set_find_spill(spill_bb->ilp, a);
+ assert(spilla);
+
+ query.irn = b;
+ spillb = set_find_spill(spill_bb->ilp, b);
+ assert(spillb);
+
+ /* interfere <-> (mem_in_a or spill_a) and (mem_in_b or spill_b): */
+ /* 1: mem_in_a + mem_in_b + spill_a + spill_b - interfere <= 1 */
+ /* 2: - mem_in_a - spill_a + interfere <= 0 */
+ /* 3: - mem_in_b - spill_b + interfere <= 0 */
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N", bb, a, b);
+ interfere = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
+
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-1", bb, a, b);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 1);
+
+ lpp_set_factor_fast(si->lpp, cst, interfere, -1.0);
+ if(spilla->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spilla->mem_in, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spilla->spill, 1.0);
+ if(spillb->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spillb->mem_in, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spillb->spill, 1.0);
+
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-2", bb, a, b);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+
+ lpp_set_factor_fast(si->lpp, cst, interfere, 1.0);
+ if(spilla->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spilla->mem_in, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, spilla->spill, -1.0);
+
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-3", bb, a, b);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+
+ lpp_set_factor_fast(si->lpp, cst, interfere, 1.0);
+ if(spillb->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spillb->mem_in, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, spillb->spill, -1.0);
+
+
+ lpp_set_factor_fast(si->lpp, any_interfere_cst, interfere, -1.0);
+
+ /* any_interfere >= interf */
+ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N-%N", a, b, bb);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+
+ lpp_set_factor_fast(si->lpp, cst, interfere, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0);
+ }
+
+ /* now that we know whether the two values interfere in memory we can drop constraints to enforce copies */
+ gen_copy_constraints(si,a,b,any_interfere);
+ }
+}
+
+
+static INLINE int
+is_zero(double x)
+{
+ return fabs(x) < 0.00001;