Improved dump for RM.

[libfirm] / optimal.c

diff --git a/optimal.c b/optimal.c
index c93ad9c..9d6d2b6 100644 (file)
--- a/optimal.c
+++ b/optimal.c
@@ -348,6 +348,14 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
        pbqp->num_rm++;
 #endif
 
+#if    KAPS_DUMP
+       if (pbqp->dump_file) {
+               char txt[100];
+               sprintf(txt, "Merging n%d into n%d", src_node->index, tgt_node->index);
+               dump_section(pbqp->dump_file, 3, txt);
+       }
+#endif
+
        /* Reconnect the source's edges with the target node. */
        for (edge_index = 0; edge_index < edge_len; ++edge_index) {
                pbqp_edge   *old_edge = src_node->edges[edge_index];
@@ -414,11 +422,20 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
                        }
                }
 
+               new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+
                add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
 
+               if (new_edge == NULL) {
+                       reorder_node_after_edge_insertion(tgt_node);
+                       reorder_node_after_edge_insertion(other_node);
+               }
+
                delete_edge(old_edge);
 
                new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+               simplify_edge(pbqp, new_edge);
+
                insert_into_rm_bucket(new_edge);
        }
 
@@ -505,6 +522,14 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
        pbqp->num_rm++;
 #endif
 
+#if    KAPS_DUMP
+       if (pbqp->dump_file) {
+               char txt[100];
+               sprintf(txt, "Merging n%d into n%d", tgt_node->index, src_node->index);
+               dump_section(pbqp->dump_file, 3, txt);
+       }
+#endif
+
        /* Reconnect the target's edges with the source node. */
        for (edge_index = 0; edge_index < edge_len; ++edge_index) {
                pbqp_edge   *old_edge = tgt_node->edges[edge_index];
@@ -571,11 +596,20 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
                        }
                }
 
+               new_edge = get_edge(pbqp, src_node->index, other_node->index);
+
                add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
 
+               if (new_edge == NULL) {
+                       reorder_node_after_edge_insertion(src_node);
+                       reorder_node_after_edge_insertion(other_node);
+               }
+
                delete_edge(old_edge);
 
                new_edge = get_edge(pbqp, src_node->index, other_node->index);
+               simplify_edge(pbqp, new_edge);
+
                insert_into_rm_bucket(new_edge);
        }
 
@@ -611,16 +645,17 @@ void apply_RM(pbqp *pbqp, pbqp_node *node)
                pbqp_edge *edge = edge_bucket_pop(&rm_bucket);
                assert(edge);
 
+               /* If the edge is not deleted: Try a merge. */
                if (edge->src == node)
                        merge_target_into_source(pbqp, edge);
-               else
+               else if (edge->tgt == node)
                        merge_source_into_target(pbqp, edge);
        }
 
        merged_node = node;
 }
 
-void reorder_node(pbqp_node *node)
+void reorder_node_after_edge_deletion(pbqp_node *node)
 {
        unsigned    degree     = pbqp_node_get_degree(node);
        /* Assume node lost one incident edge. */
@@ -631,11 +666,23 @@ void reorder_node(pbqp_node *node)
        /* Same bucket as before */
        if (degree > 2) return;
 
-       if (!node_bucket_contains(node_buckets[old_degree], node)) {
-               /* Old arity is new arity, so we have nothing to do. */
-               assert(node_bucket_contains(node_buckets[degree], node));
-               return;
-       }
+       /* Delete node from old bucket... */
+       node_bucket_remove(&node_buckets[old_degree], node);
+
+       /* ..and add to new one. */
+       node_bucket_insert(&node_buckets[degree], node);
+}
+
+void reorder_node_after_edge_insertion(pbqp_node *node)
+{
+       unsigned    degree     = pbqp_node_get_degree(node);
+       /* Assume node lost one incident edge. */
+       unsigned    old_degree = degree - 1;
+
+       if (!buckets_filled) return;
+
+       /* Same bucket as before */
+       if (old_degree > 2) return;
 
        /* Delete node from old bucket... */
        node_bucket_remove(&node_buckets[old_degree], node);
@@ -665,7 +712,7 @@ void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
        assert(tgt_node);
 
        /* If edge are already deleted, we have nothing to do. */
-       if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
+       if (is_deleted(edge))
                return;
 
 #if    KAPS_DUMP
@@ -1041,7 +1088,7 @@ void apply_RI(pbqp *pbqp)
        }
 #endif
 
-       reorder_node(other_node);
+       reorder_node_after_edge_deletion(other_node);
 
 #if KAPS_STATISTIC
        pbqp->num_r1++;
@@ -1177,8 +1224,8 @@ void apply_RII(pbqp *pbqp)
                /* Free local matrix. */
                obstack_free(&pbqp->obstack, mat);
 
-               reorder_node(src_node);
-               reorder_node(tgt_node);
+               reorder_node_after_edge_deletion(src_node);
+               reorder_node_after_edge_deletion(tgt_node);
        }
 
 #if    KAPS_DUMP