alle ops are now pinned

[libfirm] / ir / be / becopyopt.c

diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c
index 0118ae9..c9ec52c 100644 (file)
--- a/ir/be/becopyopt.c
+++ b/ir/be/becopyopt.c
@@ -18,6 +18,7 @@
 #include "irloop_t.h"
 
 #include "xmalloc.h"
+#include "beutil.h"
 #include "bechordal_t.h"
 #include "becopyopt.h"
 #include "becopystat.h"
@@ -35,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;
@@ -74,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;
@@ -135,7 +151,7 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) {
        INIT_LIST_HEAD(&unit->queue);
 
        /* check all args */
-       if (is_Phi(root) && mode_is_datab(get_irn_mode(root))) {
+       if (is_Phi(root) && is_firm_be_mode(get_irn_mode(root))) {
                for (i=0; i<arity; ++i) {
                        int o, arg_pos = 0;
                        ir_node *arg = get_irn_n(root, i);
@@ -256,7 +272,7 @@ int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
        int i, max;
        for(i=0, max=get_irn_n_outs(irn); i<max; ++i) {
                ir_node *n = get_irn_out(irn, i);
-               if (((is_Phi(n) && mode_is_datab(get_irn_mode(n))) ||
+               if (((is_Phi(n) && is_firm_be_mode(get_irn_mode(n))) ||
                         is_Perm(get_arch_env(co), n)) && (irn == n || !nodes_interfere(co->chordal_env, irn, n)))
                        return 1;
        }