-static int get_ifg_mis_size(unit_t *ou) {
- int all_size, curr_size, i, o;
- int *which;
- ir_node **curr, **all = alloca(ou->node_count * sizeof(*all));
-
- /* all contains all nodes */
- all_size = 0;
- for (i=0; i<ou->node_count; ++i)
- all[all_size++] = ou->nodes[i];
-
- /* which[i] says which element to take out of all[] and put into curr[i] */
- which = alloca(all_size*sizeof(*which));
- for (curr_size=0; curr_size<all_size; ++curr_size)
- which[curr_size] = curr_size;
-
- /* stores the currently examined set */
- curr = alloca(all_size*sizeof(*curr));
-
- while (1) { /* this loop will terminate because at least a single node will be a max indep. set */
- /* build current set */
- for (i=0; i<curr_size; ++i)
- curr[i] = all[which[all_size-curr_size+i]];
-
- /* check current set */
- for (i=0; i<curr_size; ++i)
- for (o=i+1; o<curr_size; ++o)
- if (nodes_interfere(ou->co->chordal_env, curr[i], curr[o]))
- goto conflict_found;
-
- /* We had no conflict. This is the (one) max indep. set */
- return curr_size;
-
-conflict_found:
- /* We had a conflict. Generate next set */
- if (which[all_size-curr_size+1] == all_size-curr_size+1) {
- curr_size--;
- for (i=0; i<curr_size; ++i)
- which[all_size-curr_size+i] = i;
- } else {
- int redo = 1;
- while (redo) {
- int pos = all_size;
- do {
- pos--;
- } while (!(which[pos] = (which[pos]+1) % all_size));
-
- for (i=pos+1; i<all_size; ++i)
- which[i] = MIN(which[i-1]+1, all_size-1);
-
- redo = 0;
- for (i=all_size-curr_size; i<all_size-1; ++i)
- if (which[i]>=which[i+1]) {
- redo = 1;
- break;
- }
+static int ou_max_ind_set_costs(unit_t *ou) {
+ be_chordal_env_t *chordal_env = ou->co->chordal_env;
+ ir_node **safe, **unsafe;
+ int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
+ bitset_t *curr;
+ int max, pos, curr_weight, best_weight = 0;
+
+ /* assign the nodes into two groups.
+ * safe: node has no interference, hence it is in every max stable set.
+ * unsafe: node has an interference
+ */
+ safe = alloca((ou->node_count-1) * sizeof(*safe));
+ safe_costs = 0;
+ safe_count = 0;
+ unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
+ unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
+ unsafe_count = 0;
+ for(i=1; i<ou->node_count; ++i) {
+ int is_safe = 1;
+ for(o=1; o<ou->node_count; ++o) {
+ if (i==o)
+ continue;
+ if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
+ unsafe_costs[unsafe_count] = ou->costs[i];
+ unsafe[unsafe_count] = ou->nodes[i];
+ ++unsafe_count;
+ is_safe = 0;
+ break;