+
+/*
+ A node is unserializable if:
+ - it has only one killer and this one is Sink
+ - it kills no other values
+ In this case there is no serialization which could
+ reduce the registerpressure
+*/
+#define IS_UNSERIALIZABLE_NODE(rss_node) \
+ ( \
+ ( \
+ (plist_count(rss_node->pkiller_list) == 1) && \
+ is_Sink(rss_node->killer) && \
+ (rss_node->kill_count == 0) \
+ ) || \
+ be_is_Barrier(rss_node->irn) || \
+ be_is_Keep(rss_node->irn) \
+ )
+
+ /* for all u in sat_vals */
+ for (i = 0; i < n; ++i) {
+ rss_irn_t *u = get_rss_irn(rss, val_arr[i]);
+ plist_element_t *el;
+
+ /* ignore nodes where serialization does not help */
+ if (IS_UNSERIALIZABLE_NODE(u)) {
+ DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", u->irn));
+ continue;
+ }
+
+ /* accumulate all descendants of all pkiller(u) */
+ bitset_clear_all(bs_ukilldesc);
+ foreach_plist(u->pkiller_list, el) {
+ ir_node *irn = plist_element_get_value(el);
+ rss_irn_t *node = get_rss_irn(rss, irn);
+
+ if (! is_Sink(irn))
+ bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, irn));
+ else
+ continue;
+
+ for (k = ARR_LEN_SAFE(node->descendants) - 1; k >= 0; --k) {
+ if (! is_Sink(node->descendants[k]))
+ bitset_set(bs_ukilldesc, BLOCK_IDX_MAP(rss, node->descendants[k]));
+ }
+ }
+
+ /* for all v in sat_vals */
+ for (j = 0; j < n; ++j) {
+ ir_node *v_irn = val_arr[j];
+ rss_irn_t *v = get_rss_irn(rss, v_irn);
+ unsigned v_height = get_irn_height(rss->h, v_irn);
+ int omega1, omega2, is_pkiller;
+
+ /* v cannot be serialized with itself
+ * ignore nodes where serialization does not help */
+ if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
+#ifdef DEBUG_libfirm
+ if (i != j)
+ DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
+#endif
+ continue;
+ }
+
+ /* get descendants of v */
+ bitset_clear_all(bs_vdesc);
+ bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v_irn));
+ for (k = ARR_LEN_SAFE(v->descendants) - 1; k >= 0; --k) {
+ if (! is_Sink(v->descendants[k]))
+ bitset_set(bs_vdesc, BLOCK_IDX_MAP(rss, v->descendants[k]));
+ }
+
+ /* if v is in pkiller(u) */
+ is_pkiller = plist_has_value(u->pkiller_list, v_irn);
+
+ /* for all vv in pkiller(u) */
+ foreach_plist(u->pkiller_list, el) {
+ ir_node *vv_irn = plist_element_get_value(el);
+ int add_edge;
+
+ if (is_Sink(vv_irn) || is_cfop(vv_irn))
+ continue;
+
+ if (is_pkiller)
+ add_edge = vv_irn != v_irn && skip_Proj(vv_irn) != skip_Proj(v_irn);
+ else
+ add_edge = ! heights_reachable_in_block(rss->h, skip_Proj(vv_irn), skip_Proj(v_irn));
+
+ /*
+ As we add an edge from vv -> v, we have to make sure,
+ that there exists no path from v to vv.
+ */
+
+ if (add_edge) {
+ unsigned vv_height = get_irn_height(rss->h, vv_irn);
+ unsigned critical_path_cost;
+ unsigned mu1, mu2;
+
+ /*
+ mu1 = | descendants(v) cut sat_vals |
+ the number of saturating values which cannot
+ be simultaneously alive with u
+ */
+ bitset_copy(bs_tmp, bs_vdesc);
+ mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
+
+ /*
+ mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
+ */
+ if (is_pkiller) {
+ bitset_copy(bs_tmp, bs_ukilldesc);
+ mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
+ }
+ else {
+ mu2 = 0;
+ }
+
+ /* omega1 = mu1 - mu2 */
+ omega1 = mu1 - mu2;
+
+ if (omega1 != 0)
+ has_omega1 = 1;
+
+ /* omega2 = increase of critical path */
+ critical_path_cost =
+ v_height /* longest path from v to sink */
+ + rss->max_height - vv_height /* longest path from source to vv */
+ + 1; /* edge */
+
+ /*
+ If critical_path_cost > max_height -> the new edge
+ would increase the longest critical path by the difference.
+ */
+ omega2 = critical_path_cost > rss->max_height ? critical_path_cost - rss->max_height : 0;
+
+ /* this keeps track of the edge with the best benefit */
+ if (omega1 >= num_regs - n && omega1 < best_benefit) {
+ min_benefit_edge.src = v_irn;
+ min_benefit_edge.tgt = vv_irn;
+
+ ser_u_omega1 = u;
+ ser_v_omega1 = v;
+
+ best_benefit = omega1;
+ ser->new_killer = is_pkiller;
+ }
+
+ /* this keeps track of the edge with the best omega1 costs where omega2 == 0 */
+ if (omega2 == 0 && omega1 >= num_regs - n && omega1 < best_benefit_omega20) {
+ min_omega20_edge.src = v_irn;
+ min_omega20_edge.tgt = vv_irn;
+
+ ser_u_omega20 = u;
+ ser_v_omega20 = v;
+
+ best_benefit_omega20 = omega1;
+ ser->new_killer = is_pkiller;
+ }
+
+ best_omega2 = MIN(best_omega2, omega2);
+
+ DBG((rss->dbg, LEVEL_2, "\t\tfound %+F -> %+F (w1 %d, w2 %d)\n",
+ v_irn, vv_irn, omega1, omega2));
+ } /* if add_edge */
+ } /* for all vv in pkiller(u) */
+ } /* for all v in sat_vals */
+ } /* for all u in sat_vals */
+
+ if (! has_omega1)
+ return NULL;
+
+ if (best_omega2 == 0) {
+ ser->u = ser_u_omega20;
+ ser->v = ser_v_omega20;
+ ser->edge->src = min_omega20_edge.src;
+ ser->edge->tgt = min_omega20_edge.tgt;
+ ser->omega1 = best_benefit_omega20;
+ ser->omega2 = best_omega2;
+ }
+ else {
+ ser->u = ser_u_omega1;
+ ser->v = ser_v_omega1;
+ ser->edge->src = min_benefit_edge.src;
+ ser->edge->tgt = min_benefit_edge.tgt;
+ ser->omega1 = best_benefit;
+ ser->omega2 = best_omega2;
+ }
+
+ return ser;
+
+#undef IS_UNSERIALIZABLE_NODE