removed broken include

[libfirm] / ir / be / becopyopt.c

diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c
index 93ef6e0..c9ec52c 100644 (file)
--- a/ir/be/becopyopt.c
+++ b/ir/be/becopyopt.c
@@ -36,7 +36,6 @@ static firm_dbg_module_t *dbg = NULL;
 /**
  * Determines a maximum weighted independent set with respect to
  * the interference and conflict edges of all nodes in a qnode.
- * TODO: This runs in n! in worst case. Use a heuristic iff n>???
  */
 static int ou_max_ind_set_costs(unit_t *ou) {
        be_chordal_env_t *chordal_env = ou->co->chordal_env;
@@ -75,31 +74,47 @@ static int ou_max_ind_set_costs(unit_t *ou) {
        }
 
 
-
-       /* now brute force the best set out of the unsafe nodes*/
-       curr = bitset_alloca(unsafe_count);
-
-       bitset_set_all(curr);
-       while ((max = bitset_popcnt(curr)) != 0) {
-               /* check if curr is a stable set */
-               for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
-                       for (o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */
-                                       if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
-                                               goto no_stable_set;
-
-               /* if we arrive here, we have a stable set */
-               /* compute the weigth of the stable set*/
-               curr_weight = 0;
-               bitset_foreach(curr, pos)
-                       curr_weight += unsafe_costs[pos];
-
-               /* any better ? */
-               if (curr_weight > best_weight) {
-                       best_weight = curr_weight;
+       /* now compute the best set out of the unsafe nodes*/
+       if (unsafe_count > MIS_HEUR_TRIGGER) {
+               bitset_t *best = bitset_alloca(unsafe_count);
+               /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
+               for (i=0; i<unsafe_count; ++i) {
+                       bitset_set(best, i);
+                       /* check if it is a stable set */
+                       for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
+                               if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
+                                       bitset_clear(best, i); /* clear the bit and try next one */
+                                       break;
+                               }
                }
+               /* compute the weight */
+               bitset_foreach(best, pos)
+                       best_weight += unsafe_costs[pos];
+       } else {
+               /* Exact Algorithm: Brute force */
+               curr = bitset_alloca(unsafe_count);
+               bitset_set_all(curr);
+               while ((max = bitset_popcnt(curr)) != 0) {
+                       /* check if curr is a stable set */
+                       for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
+                               for (o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */
+                                               if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
+                                                       goto no_stable_set;
+
+                       /* if we arrive here, we have a stable set */
+                       /* compute the weigth of the stable set*/
+                       curr_weight = 0;
+                       bitset_foreach(curr, pos)
+                               curr_weight += unsafe_costs[pos];
+
+                       /* any better ? */
+                       if (curr_weight > best_weight) {
+                               best_weight = curr_weight;
+                       }
 
-no_stable_set:
-               bitset_minus1(curr);
+       no_stable_set:
+                       bitset_minus1(curr);
+               }
        }
 
        return safe_costs+best_weight;