Handle infinity entries correctly when normalize a cost matrix.

[libfirm] / heuristical.c

diff --git a/heuristical.c b/heuristical.c
index 2ceae6e..75eee76 100644 (file)
--- a/heuristical.c
+++ b/heuristical.c
@@ -126,7 +126,11 @@ static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
                num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 
                if (min != 0) {
-                       pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
+                       if (src_vec->entries[src_index].data == INF_COSTS) {
+                               pbqp_matrix_set_row_value(mat, src_index, 0);
+                       } else {
+                               pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
+                       }
                        src_vec->entries[src_index].data = pbqp_add(
                                        src_vec->entries[src_index].data, min);
 
@@ -173,7 +177,11 @@ static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
                num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 
                if (min != 0) {
-                       pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
+                       if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
+                               pbqp_matrix_set_col_value(mat, tgt_index, 0);
+                       } else {
+                               pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
+                       }
                        tgt_vec->entries[tgt_index].data = pbqp_add(
                                        tgt_vec->entries[tgt_index].data, min);
 
@@ -208,11 +216,13 @@ static void reorder_node(pbqp_node *node)
        old_bucket_len   = ARR_LEN(old_bucket);
        old_bucket_index = node->bucket_index;
 
-       if (old_bucket_len <= old_bucket_index ||
-           old_bucket[old_bucket_index] != node) {
+       if (old_bucket_len <= old_bucket_index || old_bucket[old_bucket_index]
+                       != node) {
+               unsigned bucket_len = ARR_LEN(node_buckets[arity]);
+
                /* Old arity is new arity, so we have nothing to do. */
-               assert(old_bucket_index < ARR_LEN(node_buckets[arity]) &&
-                      node_buckets[arity][old_bucket_index] == node);
+               assert(old_bucket_index < bucket_len);
+               assert(node_buckets[arity][old_bucket_index] == node);
                return;
        }
 
@@ -343,7 +353,7 @@ void solve_pbqp_heuristical(pbqp *pbqp)
                } else if (ARR_LEN(node_buckets[2]) > 0) {
                        apply_RII(pbqp);
                } else if (ARR_LEN(node_buckets[3]) > 0) {
-                       panic("Please implement RN simplification");
+                       apply_RN(pbqp);
                } else {
                        break;
                }
@@ -425,7 +435,7 @@ void apply_RI(pbqp *pbqp)
 
        if (pbqp->dump_file) {
                char     txt[100];
-               sprintf(txt, "RI-Reduktion of Node n%d", node->index);
+               sprintf(txt, "RI-Reduction of Node n%d", node->index);
                dump_section(pbqp->dump_file, 2, txt);
                pbqp_dump_graph(pbqp);
                fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
@@ -514,7 +524,7 @@ void apply_RII(pbqp *pbqp)
 
        if (pbqp->dump_file) {
                char     txt[100];
-               sprintf(txt, "RII-Reduktion of Node n%d", node->index);
+               sprintf(txt, "RII-Reduction of Node n%d", node->index);
                dump_section(pbqp->dump_file, 2, txt);
                pbqp_dump_graph(pbqp);
                fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
@@ -606,13 +616,20 @@ void apply_RN(pbqp *pbqp)
        unsigned     edge_index;
        unsigned     edge_len   = ARR_LEN(node->edges);
        unsigned     node_index;
-       unsigned     node_len   = ARR_LEN(node_vec);
+       unsigned     node_len   = node_vec->len;
        unsigned     min_index  = 0;
        num          min        = INF_COSTS;
        int          is_src;
 
        assert(pbqp);
 
+       if (pbqp->dump_file) {
+               char     txt[100];
+               sprintf(txt, "RN-Reduction of Node n%d", node->index);
+               dump_section(pbqp->dump_file, 2, txt);
+               pbqp_dump_graph(pbqp);
+       }
+
        for (node_index = 0; node_index < node_len; ++node_index) {
                num value = 0;
 
@@ -640,6 +657,13 @@ void apply_RN(pbqp *pbqp)
                }
        }
 
+       if (pbqp->dump_file) {
+               fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
+                                       node->index, min_index);
+               fprintf(pbqp->dump_file, "Minimal cost of RN reduction: %d<br>\n",
+                                                       min);
+       }
+
        node->solution = min_index;
 
        /* Now that we found the local minimum set all other costs to infinity. */
@@ -651,7 +675,7 @@ void apply_RN(pbqp *pbqp)
 
        /* Add all incident edges to edge bucket, since they are now independent. */
        for (edge_index = 0; edge_index < edge_len; ++edge_index) {
-               insert_into_edge_bucket(node->edges[node_index]);
+               insert_into_edge_bucket(node->edges[edge_index]);
        }
 }