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