+ ir_snprintf(buf, sizeof(buf), "req_remat2_%N_%N_arg_%N", tmp, bb, remat_arg);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+ }
+ }
+
+ pset_foreach(live, irn) {
+ const op_t *op = get_irn_link(irn);
+ const ir_node *remat;
+ int n_remats = 0;
+
+ cst = ILP_UNDEF;
+
+ foreach_post_remat(bb, remat) {
+ int n;
+
+ for (n=get_irn_arity(remat)-1; n>=0; --n) {
+ const ir_node *arg = get_irn_n(remat, n);
+
+ if(arg == irn) {
+ const op_t *remat_op = get_irn_link(remat);
+
+ if(cst == ILP_UNDEF) {
+ /* sum remat2s <= 1 + n_remats*live_range */
+ ir_snprintf(buf, sizeof(buf), "dying_lr_%N_%N", irn, bb);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
+ }
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+ ++n_remats;
+ break;
+ }
+ }
+ }
+ if(cst != ILP_UNDEF && op->attr.live_range.ilp != ILP_UNDEF) {
+ lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -n_remats);
+ }
+ }
+
+ /* first live ranges from reg_ins */
+ pset_foreach(live, irn) {
+ op_t *op = get_irn_link(irn);
+
+ if(op->attr.live_range.ilp != ILP_UNDEF) {
+
+ spill = set_find_spill(spill_bb->ilp, irn);
+ assert(spill && spill->irn == irn);
+
+ ir_snprintf(buf, sizeof(buf), "first_lr_%N_%N", irn, bb);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
+ lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
+
+ foreach_post_remat(bb, tmp) {
+ op_t *remat_op = get_irn_link(tmp);
+
+ if(remat_op->attr.remat.remat->value == irn) {
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
+ }
+ }
+ }
+ }
+
+ /* walk forward now and compute constraints for placing spills */
+ /* this must only be done for values that are not defined in this block */
+ pset_foreach(live, irn) {
+ /*
+ * if value is defined in this block we can anways place the spill directly after the def
+ * -> no constraint necessary
+ */
+ if(!is_Phi(irn) && get_nodes_block(irn) == bb) {
+ assert(0);
+ }
+
+
+ spill = set_find_spill(spill_bb->ilp, irn);
+ assert(spill);
+
+ ir_snprintf(buf, sizeof(buf), "req_spill_%N_%N", irn, bb);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
+
+ lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
+ if(is_diverge_edge(bb)) lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
+
+ if(!is_Phi(irn)) {
+ sched_foreach_op(bb, tmp) {
+ op_t *op = get_irn_link(tmp);
+
+ if(is_Phi(tmp)) continue;
+ assert(!is_Proj(tmp));
+
+ if(op->is_remat) {
+ const ir_node *value = op->attr.remat.remat->value;
+
+ if(value == irn) {
+ /* only collect remats up to the first real use of a value */
+ lpp_set_factor_fast(si->lpp, cst, op->attr.remat.ilp, -1.0);
+ }
+ } else {
+ int n;
+
+ for (n=get_irn_arity(tmp)-1; n>=0; --n) {
+ ir_node *arg = get_irn_n(tmp, n);
+
+ if(arg == irn) {
+ /* if a value is used stop collecting remats */
+ goto next_live;
+ }
+ }
+ }
+ }
+ }
+next_live: ;
+ }
+
+ del_pset(live);
+}
+
+typedef struct _irnlist_t {
+ struct list_head list;
+ ir_node *irn;
+} irnlist_t;
+
+typedef struct _interference_t {
+ struct list_head blocklist;
+ ir_node *a;
+ ir_node *b;
+} interference_t;
+
+static int
+cmp_interference(const void *a, const void *b, size_t size)
+{
+ const interference_t *p = a;
+ const interference_t *q = b;
+ (void) size;
+
+ return !(p->a == q->a && p->b == q->b);
+}
+
+static interference_t *
+set_find_interference(set * set, ir_node * a, ir_node * b)
+{
+ interference_t query;
+
+ query.a = (a>b)?a:b;
+ query.b = (a>b)?b:a;
+
+ return set_find(set, &query, sizeof(query), HASH_PTR(PTR_TO_INT(a) ^ PTR_TO_INT(b)));
+}
+
+static interference_t *
+set_insert_interference(spill_ilp_t * si, set * set, ir_node * a, ir_node * b, ir_node * bb)
+{
+ interference_t query,
+ *result;
+ irnlist_t *list = obstack_alloc(si->obst, sizeof(*list));
+
+ list->irn = bb;
+
+ result = set_find_interference(set, a, b);
+ if(result) {
+
+ list_add(&list->list, &result->blocklist);
+ return result;
+ }
+
+ query.a = (a>b)?a:b;
+ query.b = (a>b)?b:a;
+
+ result = set_insert(set, &query, sizeof(query), HASH_PTR(PTR_TO_INT(a) ^ PTR_TO_INT(b)));
+
+ INIT_LIST_HEAD(&result->blocklist);
+ list_add(&list->list, &result->blocklist);
+
+ return result;
+}
+
+static
+int values_interfere_in_block(const spill_ilp_t *si, const ir_node *bb, const ir_node *a, const ir_node *b)
+{
+ const ir_edge_t *edge;
+
+ if (get_nodes_block(a) != bb && get_nodes_block(b) != bb) {
+ /* both values are live in, so they interfere */
+ return 1;
+ }
+
+ /* ensure a dominates b */
+ if (value_dominates(b, a)) {
+ const ir_node *t;
+ t = b;
+ b = a;
+ a = t;
+ }
+ assert(get_nodes_block(b) == bb && "at least b should be defined here in this block");
+