removed broken include

[libfirm] / ir / be / becopyopt.c

diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c
index f8c5283..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"
@@ -73,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;
@@ -134,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);
@@ -255,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;
        }
@@ -275,8 +292,10 @@ int get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) {
                /* for phis the copies are placed in the corresponding pred-block */
                loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
        }
-       if (loop)
-               cost = 2*get_loop_depth(loop);
+       if (loop) {
+               int d = get_loop_depth(loop);
+               cost = d*d;
+       }
        return cost+1;
 }