added new licence header
[libfirm] / ir / be / becopyheur.c
1 /*
2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
3  *
4  * This file is part of libFirm.
5  *
6  * This file may be distributed and/or modified under the terms of the
7  * GNU General Public License version 2 as published by the Free Software
8  * Foundation and appearing in the file LICENSE.GPL included in the
9  * packaging of this file.
10  *
11  * Licensees holding valid libFirm Professional Edition licenses may use
12  * this file in accordance with the libFirm Commercial License.
13  * Agreement provided with the Software.
14  *
15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE.
18  */
19
20 /**
21  * Author:      Daniel Grund
22  * Date:                12.04.2005
23  * Copyright:   (c) Universitaet Karlsruhe
24  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
25
26  * Heuristic for minimizing copies using a queue which holds 'qnodes' not yet
27  * examined. A qnode has a 'target color', nodes out of the opt unit and
28  * a 'conflict graph'. 'Conflict graph' = "Interference graph' + 'conflict edges'
29  * A 'max indep set' is determined form these. We try to color this mis using a
30  * color-exchanging mechanism. Occuring conflicts are modeled with 'conflict edges'
31  * and the qnode is reinserted in the queue. The first qnode colored without
32  * conflicts is the best one.
33  */
34 #ifdef HAVE_CONFIG_H
35 #include "config.h"
36 #endif
37
38 #include "debug.h"
39 #include "xmalloc.h"
40 #include "becopyopt_t.h"
41 #include "becopystat.h"
42 #include "benodesets.h"
43 #include "bitset.h"
44 #include "raw_bitset.h"
45 #include "xmalloc.h"
46
47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
48
49 #define SEARCH_FREE_COLORS
50
51 #define SLOTS_PINNED_GLOBAL 64
52 #define SLOTS_CONFLICTS 8
53 #define SLOTS_CHANGED_NODES 32
54
55 #define list_entry_queue(lh) list_entry(lh, qnode_t, queue)
56 #define HASH_CONFLICT(c) (nodeset_hash(c.n1) ^ nodeset_hash(c.n2))
57
58 /**
59  * Modeling additional conflicts between nodes. NOT live range interference
60  */
61 typedef struct _conflict_t {
62         const ir_node *n1, *n2;
63 } conflict_t;
64
65 /**
66  * If an irn is changed, the changes first get stored in a node_stat_t,
67  * to allow undo of changes (=drop new data) in case of conflicts.
68  */
69 typedef struct _node_stat_t {
70         ir_node *irn;
71         int new_color;
72         int pinned_local :1;
73 } node_stat_t;
74
75 /**
76  * Represents a node in the optimization queue.
77  */
78 typedef struct _qnode_t {
79         struct list_head queue;         /**< chaining of unit_t->queue */
80         const unit_t *ou;                       /**< the opt unit this qnode belongs to */
81         int color;                                      /**< target color */
82         set *conflicts;                         /**< contains conflict_t's. All internal conflicts */
83         int mis_costs;                          /**< costs of nodes/copies in the mis. */
84         int mis_size;                           /**< size of the array below */
85         ir_node **mis;                          /**< the nodes of unit_t->nodes[] being part of the max independent set */
86         set *changed_nodes;                     /**< contains node_stat_t's. */
87 } qnode_t;
88
89 static pset *pinned_global;                     /**< optimized nodes should not be altered any more */
90
91 static INLINE int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
92 {
93         if(env->ifg)
94                 return be_ifg_connected(env->ifg, a, b);
95         else
96                 return values_interfere(env->birg->lv, a, b);
97 }
98
99 static int set_cmp_conflict_t(const void *x, const void *y, size_t size) {
100         const conflict_t *xx = x;
101         const conflict_t *yy = y;
102         return ! (xx->n1 == yy->n1 && xx->n2 == yy->n2);
103 }
104
105 /**
106  * If a local pinned conflict occurs, a new edge in the conflict graph is added.
107  * The next maximum independent set build, will regard it.
108  */
109 static INLINE void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
110         conflict_t c;
111         DBG((dbg, LEVEL_4, "\t      %+F -- %+F\n", n1, n2));
112
113         if ((int)n1 < (int)n2) {
114                 c.n1 = n1;
115                 c.n2 = n2;
116         } else {
117                 c.n1 = n2;
118                 c.n2 = n1;
119         }
120         set_insert(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c));
121 }
122
123 /**
124  * Checks if two nodes are in a conflict.
125  */
126 static INLINE int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
127         conflict_t c;
128         /* search for live range interference */
129         if (n1!=n2 && nodes_interfere(qn->ou->co->cenv, n1, n2))
130                 return 1;
131         /* search for recoloring conflicts */
132         if ((int)n1 < (int)n2) {
133                 c.n1 = n1;
134                 c.n2 = n2;
135         } else {
136                 c.n1 = n2;
137                 c.n2 = n1;
138         }
139         return (int) set_find(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c));
140 }
141
142 static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) {
143         return ((node_stat_t *)x)->irn != ((node_stat_t *)y)->irn;
144 }
145
146 /**
147  * Finds a node status entry of a node if existent. Otherwise return NULL
148  */
149 static INLINE node_stat_t *qnode_find_node(const qnode_t *qn, ir_node *irn) {
150         node_stat_t find;
151         find.irn = irn;
152         return set_find(qn->changed_nodes, &find, sizeof(find), nodeset_hash(irn));
153 }
154
155 /**
156  * Finds a node status entry of a node if existent. Otherwise it will return
157  * an initialized new entry for this node.
158  */
159 static INLINE node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, ir_node *irn) {
160         node_stat_t find;
161         find.irn = irn;
162         find.new_color = NO_COLOR;
163         find.pinned_local = 0;
164         return set_insert(qn->changed_nodes, &find, sizeof(find), nodeset_hash(irn));
165 }
166
167 /**
168  * Returns the virtual color of a node if set before, else returns the real color.
169  */
170 static INLINE int qnode_get_new_color(const qnode_t *qn, ir_node *irn) {
171         node_stat_t *found = qnode_find_node(qn, irn);
172         if (found)
173                 return found->new_color;
174         else
175                 return get_irn_col(qn->ou->co, irn);
176 }
177
178 /**
179  * Sets the virtual color of a node.
180  */
181 static INLINE void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int color) {
182         node_stat_t *found = qnode_find_or_insert_node(qn, irn);
183         found->new_color = color;
184         DBG((dbg, LEVEL_3, "\t      col(%+F) := %d\n", irn, color));
185 }
186
187 /**
188  * Checks if a node is local pinned. A node is local pinned, iff it belongs
189  * to the same optimization unit and has been optimized before the current
190  * processed node.
191  */
192 static INLINE int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) {
193         node_stat_t *found = qnode_find_node(qn, irn);
194         if (found)
195                 return found->pinned_local;
196         else
197                 return 0;
198 }
199
200 /**
201  * Local-pins a node, so optimizations of further nodes of the same opt unit
202  * can handle situations in which a color change would undo prior optimizations.
203  */
204 static INLINE void qnode_pin_local(const qnode_t *qn, ir_node *irn) {
205         node_stat_t *found = qnode_find_or_insert_node(qn, irn);
206         found->pinned_local = 1;
207         if (found->new_color == NO_COLOR)
208                 found->new_color = get_irn_col(qn->ou->co, irn);
209 }
210
211
212 /**
213  * Possible return values of qnode_color_irn()
214  */
215 #define CHANGE_SAVE NULL
216 #define CHANGE_IMPOSSIBLE (ir_node *)1
217 #define is_conflicting_node(n) (((int)n) > 1)
218
219 /**
220  * Performs virtual re-coloring of node @p n to color @p col. Virtual colors of
221  * other nodes are changed too, as required to preserve correctness. Function is
222  * aware of local and global pinning. Recursive.
223  *
224  * If irn == trigger the color @p col must be used. (the first recoloring)
225  * If irn != trigger an arbitrary free color may be used. If no color is free, @p col is used.
226  *
227  * @param  irn     The node to set the color for
228  * @param  col     The color to set
229  * @param  trigger The irn that caused the wish to change the color of the irn
230  *                 External callers must call with trigger = irn
231  *
232  * @return CHANGE_SAVE iff setting the color is possible, with all transitive effects.
233  *         CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured.
234  *         Else the first conflicting ir_node encountered is returned.
235  *
236  */
237 static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const ir_node *trigger) {
238         copy_opt_t *co = qn->ou->co;
239         const be_chordal_env_t *chordal_env = co->cenv;
240         const arch_register_class_t *cls = co->cls;
241         const arch_env_t *arch_env = co->aenv;
242         int irn_col = qnode_get_new_color(qn, irn);
243         ir_node *sub_res, *curr;
244         be_ifg_t *ifg = chordal_env->ifg;
245         void *iter = be_ifg_neighbours_iter_alloca(ifg);
246
247
248         DBG((dbg, LEVEL_3, "\t    %+F \tcaused col(%+F) \t%2d --> %2d\n", trigger, irn, irn_col, col));
249
250         /* If the target color is already set do nothing */
251         if (irn_col == col) {
252                 DBG((dbg, LEVEL_3, "\t      %+F same color\n", irn));
253                 return CHANGE_SAVE;
254         }
255
256         /* If the irn is pinned, changing color is impossible */
257         if (pset_find_ptr(pinned_global, irn) || qnode_is_pinned_local(qn, irn)) {
258                 DBG((dbg, LEVEL_3, "\t      %+F conflicting\n", irn));
259                 return irn;
260         }
261
262 #ifdef SEARCH_FREE_COLORS
263         /* If we resolve conflicts (recursive calls) we can use any unused color.
264          * In case of the first call @p col must be used.
265          */
266         if (irn != trigger) {
267                 bitset_t *free_cols = bitset_alloca(cls->n_regs);
268                 const arch_register_req_t *req;
269                 ir_node *curr;
270                 int free_col;
271
272                 /* Get all possible colors */
273                 bitset_copy(free_cols, co->cenv->ignore_colors);
274                 bitset_flip_all(free_cols);
275
276                 /* Exclude colors not assignable to the irn */
277                 req = arch_get_register_req(arch_env, irn, -1);
278                 if (arch_register_req_is(req, limited)) {
279                         bitset_t *limited = bitset_alloca(cls->n_regs);
280                         rbitset_copy_to_bitset(req->limited, limited);
281                         bitset_and(free_cols, limited);
282                 }
283
284                 /* Exclude the color of the irn, because it must _change_ its color */
285                 bitset_clear(free_cols, irn_col);
286
287                 /* Exclude all colors used by adjacent nodes */
288                 be_ifg_foreach_neighbour(ifg, iter, irn, curr)
289                         bitset_clear(free_cols, qnode_get_new_color(qn, curr));
290
291                 free_col = bitset_next_set(free_cols, 0);
292
293                 if (free_col != -1) {
294                         qnode_set_new_color(qn, irn, free_col);
295                         return CHANGE_SAVE;
296                 }
297         }
298 #endif /* SEARCH_FREE_COLORS */
299
300         /* If target color is not allocatable changing color is impossible */
301         if (!arch_reg_is_allocatable(arch_env, irn, -1, arch_register_for_index(cls, col))) {
302                 DBG((dbg, LEVEL_3, "\t      %+F impossible\n", irn));
303                 return CHANGE_IMPOSSIBLE;
304         }
305
306         /*
307          * If we arrive here changing color may be possible, but there may be conflicts.
308          * Try to color all conflicting nodes 'curr' with the color of the irn itself.
309          */
310         be_ifg_foreach_neighbour(ifg, iter, irn, curr) {
311                 DBG((dbg, LEVEL_3, "\t      Confl %+F(%d)\n", curr, qnode_get_new_color(qn, curr)));
312                 if (qnode_get_new_color(qn, curr) == col && curr != trigger) {
313                         sub_res = qnode_color_irn(qn, curr, irn_col, irn);
314                         if (sub_res != CHANGE_SAVE) {
315                                 be_ifg_neighbours_break(ifg, iter);
316                                 return sub_res;
317                         }
318                 }
319         }
320
321         /*
322          * If we arrive here, all conflicts were resolved.
323          * So it is save to change this irn
324          */
325         qnode_set_new_color(qn, irn, col);
326         return CHANGE_SAVE;
327 }
328
329
330 /**
331  * Tries to set the colors for all members of this queue node;
332  * to the target color qn->color
333  * @returns 1 iff all members colors could be set
334  *          0 else
335  */
336 static int qnode_try_color(const qnode_t *qn) {
337         int i;
338         for (i=0; i<qn->mis_size; ++i) {
339                 ir_node *test_node, *confl_node;
340
341                 test_node = qn->mis[i];
342                 DBG((dbg, LEVEL_3, "\t    Testing %+F\n", test_node));
343                 confl_node = qnode_color_irn(qn, test_node, qn->color, test_node);
344
345                 if (confl_node == CHANGE_SAVE) {
346                         DBG((dbg, LEVEL_3, "\t    Save --> pin local\n"));
347                         qnode_pin_local(qn, test_node);
348                 } else if (confl_node == CHANGE_IMPOSSIBLE) {
349                         DBG((dbg, LEVEL_3, "\t    Impossible --> remove from qnode\n"));
350                         qnode_add_conflict(qn, test_node, test_node);
351                 } else {
352                         if (qnode_is_pinned_local(qn, confl_node)) {
353                                 /* changing test_node would change back a node of current ou */
354                                 if (confl_node == qn->ou->nodes[0]) {
355                                         /* Adding a conflict edge between testnode and conflnode
356                                          * would introduce a root -- arg interference.
357                                          * So remove the arg of the qn */
358                                         DBG((dbg, LEVEL_3, "\t    Conflicting local with phi --> remove from qnode\n"));
359                                         qnode_add_conflict(qn, test_node, test_node);
360                                 } else {
361                                         DBG((dbg, LEVEL_3, "\t    Conflicting local --> add conflict\n"));
362                                         qnode_add_conflict(qn, confl_node, test_node);
363                                 }
364                         }
365                         if (pset_find_ptr(pinned_global, confl_node)) {
366                                 /* changing test_node would change back a node of a prior ou */
367                                 DBG((dbg, LEVEL_3, "\t    Conflicting global --> remove from qnode\n"));
368                                 qnode_add_conflict(qn, test_node, test_node);
369                         }
370                 }
371
372                 if (confl_node != CHANGE_SAVE)
373                         return 0;
374         }
375         return 1;
376 }
377
378 /**
379  * Determines a maximum weighted independent set with respect to
380  * the interference and conflict edges of all nodes in a qnode.
381  */
382 static INLINE void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) {
383         ir_node **safe, **unsafe;
384         int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
385         bitset_t *curr, *best;
386         int max, next, pos, curr_weight, best_weight = 0;
387
388         /* assign the nodes into two groups.
389          * safe: node has no interference, hence it is in every max stable set.
390          * unsafe: node has an interference
391          */
392         safe = alloca((ou->node_count-1) * sizeof(*safe));
393         safe_costs = 0;
394         safe_count = 0;
395         unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
396         unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
397         unsafe_count = 0;
398         for(i=1; i<ou->node_count; ++i) {
399                 int is_safe = 1;
400                 for(o=1; o<ou->node_count; ++o) {
401                         if (qnode_are_conflicting(qn, ou->nodes[i], ou->nodes[o])) {
402                                 if (i!=o) {
403                                         unsafe_costs[unsafe_count] = ou->costs[i];
404                                         unsafe[unsafe_count] = ou->nodes[i];
405                                         ++unsafe_count;
406                                 }
407                                 is_safe = 0;
408                                 break;
409                         }
410                 }
411                 if (is_safe) {
412                         safe_costs += ou->costs[i];
413                         safe[safe_count++] = ou->nodes[i];
414                 }
415         }
416
417
418
419         /* now compute the best set out of the unsafe nodes*/
420         best = bitset_alloca(unsafe_count);
421
422         if (unsafe_count > MIS_HEUR_TRIGGER) {
423                 /* Heuristic: Greedy trial and error form index 0 to unsafe_count-1 */
424                 for (i=0; i<unsafe_count; ++i) {
425                         bitset_set(best, i);
426                         /* check if it is a stable set */
427                         for (o=bitset_next_set(best, 0); o!=-1 && o<=i; o=bitset_next_set(best, o+1))
428                                 if (qnode_are_conflicting(qn, unsafe[i], unsafe[o])) {
429                                         bitset_clear(best, i); /* clear the bit and try next one */
430                                         break;
431                                 }
432                 }
433                 /* compute the weight */
434                 bitset_foreach(best, pos)
435                         best_weight += unsafe_costs[pos];
436         } else {
437                 /* Exact Algorithm: Brute force */
438                 curr = bitset_alloca(unsafe_count);
439                 bitset_set_all(curr);
440                 while ((max = bitset_popcnt(curr)) != 0) {
441                         /* check if curr is a stable set */
442                         for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
443                                 for (o=bitset_next_set(curr, i); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to ou_max_ind_set_costs(): NOT (curr, i+1) */
444                                                 if (qnode_are_conflicting(qn, unsafe[i], unsafe[o]))
445                                                         goto no_stable_set;
446
447                         /* if we arrive here, we have a stable set */
448                         /* compute the weigth of the stable set*/
449                         curr_weight = 0;
450                         bitset_foreach(curr, pos)
451                                 curr_weight += unsafe_costs[pos];
452
453                         /* any better ? */
454                         if (curr_weight > best_weight) {
455                                 best_weight = curr_weight;
456                                 bitset_copy(best, curr);
457                         }
458
459 no_stable_set:
460                         bitset_minus1(curr);
461                 }
462         }
463
464         /* transfer the best set into the qn */
465         qn->mis_size = 1+safe_count+bitset_popcnt(best);
466         qn->mis_costs = safe_costs+best_weight;
467         qn->mis[0] = ou->nodes[0]; /* the root is always in a max stable set */
468         next = 1;
469         for (i=0; i<safe_count; ++i)
470                 qn->mis[next++] = safe[i];
471         bitset_foreach(best, pos)
472                 qn->mis[next++] = unsafe[pos];
473 }
474
475 /**
476  * Creates a new qnode
477  */
478 static INLINE qnode_t *new_qnode(const unit_t *ou, int color) {
479         qnode_t *qn = xmalloc(sizeof(*qn));
480         qn->ou = ou;
481         qn->color = color;
482         qn->mis = xmalloc(ou->node_count * sizeof(*qn->mis));
483         qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS);
484         qn->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES);
485         return qn;
486 }
487
488 /**
489  * Frees space used by a queue node
490  */
491 static INLINE void free_qnode(qnode_t *qn) {
492         del_set(qn->conflicts);
493         del_set(qn->changed_nodes);
494         xfree(qn->mis);
495         xfree(qn);
496 }
497
498 /**
499  * Inserts a qnode in the sorted queue of the optimization unit. Queue is
500  * ordered by field 'size' (the size of the mis) in decreasing order.
501  */
502 static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) {
503         struct list_head *lh;
504
505         if (qnode_are_conflicting(qn, ou->nodes[0], ou->nodes[0])) {
506                 /* root node is not in qnode */
507                 free_qnode(qn);
508                 return;
509         }
510
511         qnode_max_ind_set(qn, ou);
512         /* do the insertion */
513         DBG((dbg, LEVEL_4, "\t  Insert qnode color %d with cost %d\n", qn->color, qn->mis_costs));
514         lh = &ou->queue;
515         while (lh->next != &ou->queue) {
516                 qnode_t *curr = list_entry_queue(lh->next);
517                 if (curr->mis_costs <= qn->mis_costs)
518                         break;
519                 lh = lh->next;
520         }
521         list_add(&qn->queue, lh);
522 }
523
524 /**
525  * Tries to re-allocate colors of nodes in this opt unit, to achieve lower
526  * costs of copy instructions placed during SSA-destruction and lowering.
527  * Works only for opt units with exactly 1 root node, which is the
528  * case for approximately 80% of all phi classes and 100% of register constrained
529  * nodes. (All other phi classes are reduced to this case.)
530  */
531 static void ou_optimize(unit_t *ou) {
532         int i;
533         qnode_t *curr = NULL, *tmp;
534         const arch_env_t *aenv = ou->co->aenv;
535         const arch_register_class_t *cls = ou->co->cls;
536         bitset_t *pos_regs = bitset_alloca(cls->n_regs);
537
538         DBG((dbg, LEVEL_1, "\tOptimizing unit:\n"));
539         for (i=0; i<ou->node_count; ++i)
540                 DBG((dbg, LEVEL_1, "\t %+F\n", ou->nodes[i]));
541
542         /* init queue */
543         INIT_LIST_HEAD(&ou->queue);
544
545         arch_get_allocatable_regs(aenv, ou->nodes[0], -1, pos_regs);
546
547         /* exclude ingore colors */
548         bitset_andnot(pos_regs, ou->co->cenv->ignore_colors);
549
550         assert(bitset_popcnt(pos_regs) != 0 && "No register is allowed for this node !!?");
551
552         /* create new qnode */
553         bitset_foreach(pos_regs, i)
554                 ou_insert_qnode(ou, new_qnode(ou, i));
555
556         /* search best */
557         while (!list_empty(&ou->queue)) {
558                 /* get head of queue */
559                 curr = list_entry_queue(ou->queue.next);
560                 list_del(&curr->queue);
561                 DBG((dbg, LEVEL_2, "\t  Examine qnode color %d with cost %d\n", curr->color, curr->mis_costs));
562
563                 /* try */
564                 if (qnode_try_color(curr))
565                         break;
566
567                 /* no success, so re-insert */
568                 del_set(curr->changed_nodes);
569                 curr->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES);
570                 ou_insert_qnode(ou, curr);
571         }
572
573         /* apply the best found qnode */
574         if (curr->mis_size >= 2) {
575                 node_stat_t *ns;
576                 int root_col = qnode_get_new_color(curr, ou->nodes[0]);
577                 DBG((dbg, LEVEL_1, "\t  Best color: %d  Costs: %d << %d << %d\n", curr->color, ou->min_nodes_costs, ou->all_nodes_costs - curr->mis_costs, ou->all_nodes_costs));
578                 /* globally pin root and all args which have the same color */
579                 pset_insert_ptr(pinned_global, ou->nodes[0]);
580                 for (i=1; i<ou->node_count; ++i) {
581                         ir_node *irn = ou->nodes[i];
582                         int nc = qnode_get_new_color(curr, irn);
583                         if (nc != NO_COLOR && nc == root_col)
584                                 pset_insert_ptr(pinned_global, irn);
585                 }
586
587                 /* set color of all changed nodes */
588                 for (ns = set_first(curr->changed_nodes); ns; ns = set_next(curr->changed_nodes)) {
589                         /* NO_COLOR is possible, if we had an undo */
590                         if (ns->new_color != NO_COLOR) {
591                                 DBG((dbg, LEVEL_1, "\t    color(%+F) := %d\n", ns->irn, ns->new_color));
592                                 set_irn_col(ou->co, ns->irn, ns->new_color);
593                         }
594                 }
595         }
596
597         /* free best qnode (curr) and queue */
598         free_qnode(curr);
599         list_for_each_entry_safe(qnode_t, curr, tmp, &ou->queue, queue)
600                 free_qnode(curr);
601 }
602
603 int co_solve_heuristic(copy_opt_t *co) {
604         unit_t *curr;
605         FIRM_DBG_REGISTER(dbg, "ir.be.copyoptheur");
606
607         ASSERT_OU_AVAIL(co);
608
609         pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL);
610         list_for_each_entry(unit_t, curr, &co->units, units)
611                 if (curr->node_count > 1)
612                         ou_optimize(curr);
613
614         del_pset(pinned_global);
615         return 0;
616 }