19 #include "bechordal.h"
22 #include "phiclass_t.h"
23 #include "bephicoal_t.h"
25 #define DEBUG_LVL 0 //SET_LEVEL_2
28 #define INITIAL_SLOTS_PINNED_GLOBAL 256
29 #define INITIAL_SLOTS_CHANGED_NODES 32
31 /* some things for readable code */
32 #define CHANGE_SAVE NULL
33 #define CHANGE_IMPOSSIBLE (ir_node *)1
34 #define CHANGE_NYI (ir_node *)2
35 #define is_conflicting_node(n) (((int)n) > 2)
38 * Models conflicts between nodes. These may be life range conflicts or
39 * pinning conflicts, which may occur while changing colors
41 typedef struct _conflict_t {
46 * If an irn is changed, the changes first get stored in a node_stat_t,
47 * to allow undo of changes in case of conflicts.
49 typedef struct _node_stat_t {
53 char status; /**< Bit 0: pinned, Bit 1: removed */
56 #define _set_pinned(nodestat) nodestat->status |= 1
57 #define _set_removed(nodestat) nodestat->status |= 2
58 #define _clear_pinned(nodestat) nodestat->status &= 255 ^ 1
59 #define _clear_removed(nodestat) nodestat->status &= 255 ^ 2
60 #define _is_pinned(nodestat) (nodestat->status & 1)
61 #define _is_removed(nodestat) (nodestat->status & 2)
64 * Central data structure. Contains infos needed during coalescing of the
65 * corresponding phi class.
67 typedef struct _phi_unit_t {
68 unsigned char node_count; /**< size of the nodes-array */
69 unsigned char conflict_count; /**< size of the conflicts-array */
70 unsigned char conflict_count_org; /**< initial size of the conflicts-array */
71 ir_node **nodes; /**< [0] is the phi node. [1..node_count-1] the arguments of the phi not interfering with it */
72 conflict_t *conflicts; /**< pairs of conflicting ir_nodes. */
73 set *changed_nodes; /**< contains node_stat_t's. */
76 static firm_dbg_module_t *dbgphi = NULL;
79 * Contains already optimized ir_nodes of phi-units fully processed.
80 * So one can perform a check not to switch them twice or more.
82 static pset *pinned_global = NULL;
84 static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) {
85 return ((node_stat_t *)x)->irn != ((node_stat_t *)y)->irn;
89 * Finds a node status entry of a node if existent.
91 static INLINE node_stat_t *pu_find_node(phi_unit_t *pu, ir_node *irn) {
94 return set_find(pu->changed_nodes, &find, sizeof(find), HASH_PTR(irn));
98 * Finds a node status entry of a node if existent. Otherwise it will return
99 * an initialized new entry for this node.
101 static INLINE node_stat_t *pu_find_or_insert_node(phi_unit_t *pu, ir_node *irn) {
104 find.color = NO_COLOR;
105 find.undo_color = NO_COLOR;
107 return set_insert(pu->changed_nodes, &find, sizeof(find), HASH_PTR(irn));
111 * @return The virtual color of a node, if set before, else just the real color.
113 static INLINE int pu_get_new_color(phi_unit_t *pu, ir_node *irn) {
114 node_stat_t *found = pu_find_node(pu, irn);
118 return get_irn_color(irn);
122 * Sets the virtual color of a node.
124 static INLINE void pu_set_new_color(phi_unit_t *pu, ir_node *irn, int color) {
125 node_stat_t *found = pu_find_or_insert_node(pu, irn);
126 found->undo_color = found->color;
127 found->color = color;
128 DBG((dbgphi, LEVEL_4, "%n %d\n", irn, color));
132 * Sets the virtual color of a node to the color it had,
133 * before the last call to pu_set_new_color
135 static INLINE void pu_undo_color(phi_unit_t *pu, ir_node *irn) {
136 node_stat_t *ns = pu_find_node(pu, irn);
137 assert(ns && "Nodes whose colors are undone must be in pu->changed_nodes");
138 ns->color = ns->undo_color;
139 DBG((dbgphi, LEVEL_3, "\t\tUndo: col(%n) := %d\n", irn, ns->undo_color));
143 * Checks if a node is removed from consideration respectively building
144 * a maximum independent set.
146 static INLINE int pu_is_node_removed(phi_unit_t *pu, ir_node *irn) {
147 node_stat_t *found = pu_find_node(pu, irn);
149 return _is_removed(found);
155 * Removes a node from the base set, out of which a maximum independet
156 * set gets build from.
158 static INLINE void pu_remove_node(phi_unit_t *pu, ir_node *irn) {
159 node_stat_t *found = pu_find_or_insert_node(pu, irn);
161 DBG((dbgphi, LEVEL_4, "%n\n", irn));
165 * Checks if a node is local pinned; i.e. it belongs to the same phi unit and
166 * has been optimized before the current processed one.
168 static INLINE int pu_is_node_pinned(phi_unit_t *pu, ir_node *irn) {
169 node_stat_t *found = pu_find_node(pu, irn);
171 return _is_pinned(found);
177 * Local-pins a node, so optimizations of further nodes of the same phi unit
178 * can handle situations in which a color change would undo prior optimizations.
180 static INLINE void pu_pin_node(phi_unit_t *pu, ir_node *irn) {
181 node_stat_t *found = pu_find_or_insert_node(pu, irn);
183 DBG((dbgphi, LEVEL_4, "%n\n", irn));
187 * If a local pinned conflict occurs, a new edge in the conflict graph is added.
188 * The next maximum independent set build, will regard it.
190 static INLINE void pu_add_conflict(phi_unit_t *pu, ir_node *n1, ir_node *n2) {
191 int count = pu->conflict_count;
193 DBG((dbgphi, LEVEL_3, "\t %n -- %n\n", n1, n2));
194 assert(count != 255 && "Too much conflicts. Can hold max 255 entries");
195 if ((count & 15) == 0)
196 pu->conflicts = realloc(pu->conflicts, (count + 16)*sizeof(*pu->conflicts));
198 if ((int)n1 < (int)n2) {
199 pu->conflicts[count].n1 = n1;
200 pu->conflicts[count].n2 = n2;
202 pu->conflicts[count].n1 = n2;
203 pu->conflicts[count].n2 = n1;
206 pu->conflict_count++;
210 * Checks if two nodes are in a conflict.
212 static INLINE int pu_are_conflicting(phi_unit_t *pu, ir_node *n1, ir_node *n2) {
213 const ir_node *o1, *o2;
216 if ((int)n1 < (int)n2) {
224 for (i = 0; i < pu->conflict_count; ++i)
225 if (pu->conflicts[i].n1 == o1 && pu->conflicts[i].n2 == o2)
231 * Checks if a node is a member of a phi unit.
232 * Other nodes should not be pinned global.
234 static INLINE int pu_is_global_pinnable(phi_unit_t *pu, ir_node *irn) {
236 for (i = 0; i < pu->node_count; ++i)
237 if (pu->nodes[i] == irn)
243 * Determines a maximum independent set with respect to the conflict edges
244 * in pu->conflicts and the nodes beeing all non-removed nodes of pu->nodes.
245 * TODO: make this 'un-greedy'
246 * ATTENTION: be aware that phi nodes find their way into the set. For 1 phi
247 * in greedy version this is no prob, cause it comes first at [0].
249 static int pu_get_mis(phi_unit_t *pu, struct obstack *res) {
253 DBG((dbgphi, LEVEL_2, "\t Max indep set:\n"));
254 for (i = 0; i < pu->node_count; ++i) {
256 if (pu_is_node_removed(pu, pu->nodes[i]))
258 mis = (ir_node**) obstack_base(res);
259 for (o = 0; o < size; ++o)
260 if (pu_are_conflicting(pu, pu->nodes[i], mis[o])) {
266 DBG((dbgphi, LEVEL_2, "\t\t%n\n", pu->nodes[i]));
267 obstack_ptr_grow(res, pu->nodes[i]);
275 * Performs virtual re-coloring of node @p n to color @p col. Virtual colors of
276 * other nodes are changed too, as required to preserve correctness. Function is
277 * aware of local and global pinning. Recursive.
278 * @param irn The node to set the color for
279 * @param col The color to set.
280 * @param trigger The irn that caused the wish to change the color of the irn
281 * @param changed_nodes An obstack on which all ir_nodes get growed on, which are changed
282 * @return CHANGE_SAVE iff setting the color is possible, with all transiteve effects.
283 * CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured.
284 * CHANGE_NYI iff an unhandled situation occurs.
285 * Else the first conflicting ir_node encountered is returned.
287 * ASSUMPTION: Assumes that a life range of a single value can't be spilt into
288 * several smaller intervals where other values can live in between.
289 * This should be true in SSA.
291 static ir_node *_pu_color_irn(phi_unit_t *pu, ir_node *irn, int col, const ir_node *trigger, struct obstack *changed_nodes) {
293 struct obstack confl_ob;
294 ir_node **confl, *cn;
297 DBG((dbgphi, LEVEL_3, "\t\t%n \tcaused col(%n) \t%2d --> %2d\n", trigger, irn, pu_get_new_color(pu, irn), col));
298 obstack_init(&confl_ob);
299 irn_col = pu_get_new_color(pu, irn);
303 if (pset_find_ptr(pinned_global, irn) || pu_is_node_pinned(pu, irn)) {
308 /* get all nodes which would conflict with this change */
314 irn_bl = get_nodes_block(irn);
316 /* first check for a conflicting node which is 'living in' the irns block */
319 pset *live_ins = get_live_in(irn_bl);
320 for (n = pset_first(live_ins); n; n = pset_next(live_ins))
321 if (is_allocatable_irn(n) && n != trigger && pu_get_new_color(pu, n) == col && phi_ops_interfere(irn, n)) {
322 DBG((dbgphi, LEVEL_4, "\t\t %n\ttroubles\n", n));
323 obstack_ptr_grow(&confl_ob, n);
324 pset_break(live_ins);
329 /* setup the queue of blocks. */
331 obstack_ptr_grow(&q, irn_bl);
335 /* process the queue. The code below checks for every block dominated
336 * by the irns one, and in which the irn is live, if there are
337 * conflicting nodes */
339 ir_node *curr_bl, *sub_bl;
342 curr_bl = ((ir_node **)obstack_base(&q))[out++];
344 /* Add to the result all nodes in the block, which have
345 * the target color and interfere with the irn */
346 for (i = 0, max = get_irn_n_outs(curr_bl); i < max; ++i) {
347 ir_node *n = get_irn_out(curr_bl, i);
348 if (is_allocatable_irn(n) && n != trigger && pu_get_new_color(pu, n) == col && phi_ops_interfere(irn, n)) {
349 DBG((dbgphi, LEVEL_4, "\t\t %n\ttroubles\n", n));
350 obstack_ptr_grow(&confl_ob, n);
354 /* If irn lives out check i-dominated blocks where the irn lives in */
356 if (is_live_out(curr_bl, irn)) {
357 dominates_for_each(curr_bl, sub_bl)
358 if (is_live_in(sub_bl, irn)) {
359 obstack_ptr_grow(&q, sub_bl);
364 obstack_free(&q, NULL);
365 obstack_ptr_grow(&confl_ob, NULL);
366 confl = (ir_node **) obstack_finish(&confl_ob);
369 /* process all nodes which would conflict with this change */
370 for (i = 0, cn = confl[0]; cn; cn = confl[++i]) {
373 /* try to color the conflicting node cn with the color of the irn itself */
374 sub_res = _pu_color_irn(pu, cn, irn_col, irn, changed_nodes);
375 if (sub_res != CHANGE_SAVE) {
380 /* if we arrive here all sub changes can be applied, so it's save to change this irn */
383 DBG((dbgphi, LEVEL_3, "\t\t%n save\n", irn));
384 obstack_free(&confl_ob, NULL);
385 pu_set_new_color(pu, irn, col);
386 obstack_ptr_grow(changed_nodes, irn);
390 DBG((dbgphi, LEVEL_3, "\t\t%n conflicting\n", irn));
391 obstack_free(&confl_ob, NULL);
395 static ir_node *pu_color_irn(phi_unit_t *pu, ir_node *irn, int col) {
397 struct obstack ob_undo;
399 obstack_init(&ob_undo);
400 res = _pu_color_irn(pu, irn, col, irn, &ob_undo);
402 if (res != CHANGE_SAVE) { /* undo virtual changes caused by the last call */
404 ir_node *undo_node, **undo_nodes;
406 obstack_ptr_grow(&ob_undo, NULL);
407 undo_nodes = obstack_finish(&ob_undo);
408 for (i = 0, undo_node = undo_nodes[0]; undo_node; undo_node = undo_nodes[++i])
409 pu_undo_color(pu, undo_node);
412 obstack_free(&ob_undo, NULL);
417 * Tries to set as much members of a phi unit as possible to color @p col.
418 * All changes taken together are guaranteed to be conflict free.
420 static int pu_try_color(phi_unit_t *pu, int col, int b_size) {
421 struct obstack ob_mis;
422 int i, redo, mis_size;
425 obstack_init(&ob_mis);
429 /* get a max independent set regarding current conflicts */
430 mis_size = pu_get_mis(pu, &ob_mis);
431 mis = obstack_finish(&ob_mis);
433 /* shortcut: if mis size is worse than best, then mis won't be better. */
434 if (mis_size < b_size)
437 /* check if its possible to set the color for all members of the maximum set*/
438 for (i = 0; i < mis_size; ++i) {
439 ir_node *test_node, *confl_node;
442 DBG((dbgphi, LEVEL_2, "\t Testing %n\n", test_node));
443 confl_node = pu_color_irn(pu, test_node, col);
445 if (confl_node == CHANGE_SAVE) {
446 DBG((dbgphi, LEVEL_2, "\t Save\n"));
447 pu_pin_node(pu, test_node);
448 } else if (confl_node == CHANGE_NYI) {
449 DBG((dbgphi, 0, "\t NYI\n"));
450 } else if (confl_node == CHANGE_IMPOSSIBLE) {
451 /* TODO: this may happen due to reg constraints --> remove from set ?? */
453 DBG((dbgphi, LEVEL_2, "\t Conflicting\n"));
454 assert(is_conflicting_node(confl_node));
456 if (pu_is_node_pinned(pu, confl_node)) {
457 /* changing test_node would change back a node of current phi unit */
458 pu_add_conflict(pu, confl_node, test_node);
461 if (pset_find_ptr(pinned_global, confl_node)) {
462 /* changing test_node would change back a node of a prior phi unit */
463 pu_remove_node(pu, test_node);
468 if (confl_node != CHANGE_SAVE) {
469 /* shortcut: color not possible for phi node (phi comes first) ==> exit */
474 /* break iteration over current mis, because it will change */
478 obstack_free(&ob_mis, mis);
482 obstack_free(&ob_mis, NULL);
487 * Tries to re-allocate colors of nodes in this phi unit, to achieve a lower
488 * number of copy instructions placed during phi destruction. Optimized version.
489 * Works only for phi-classes/phi-units with exactly 1 phi node, which is the
490 * case for approximately 80% of all phi classes. All other phi classes are
491 * reduced to this case.
493 static void pu_coal_1_phi(phi_unit_t *pu) {
494 int size, col, b_size, b_color;
497 /* init best search result */
502 /* find optimum of all colors */
503 for (col = MAX_COLORS-1; col >= 0; --col) {
504 DBG((dbgphi, 1, "\tTrying color %d\n", col));
505 size = pu_try_color(pu, col, b_size);
507 /* did we find a better max ind. set? */
509 DBG((dbgphi, 1, "\tBetter size: %d\n", size));
512 b_changes = pu->changed_nodes;
516 del_set(pu->changed_nodes);
519 /* reset the phi unit to original state for next color */
520 pu->changed_nodes = new_set(set_cmp_node_stat_t, INITIAL_SLOTS_CHANGED_NODES);
521 pu->conflict_count = pu->conflict_count_org;
523 /* shortcut: if all members can be colored we are (very) happy */
524 if (b_size == pu->node_count)
528 /* now apply the found optimum */
531 DBG((dbgphi, 1, "\tBest color: %d Copies: %d/%d\n", b_color, pu->node_count-b_size, pu->node_count-1));
532 for (ns = set_first(b_changes); ns; ns = set_next(b_changes)) {
533 /* NO_COLOR is possible, if we had an undo; so the irn stays in the
534 * pu->changed_nodes with new color set to NO_COLOR. */
535 if (ns->color != NO_COLOR) {
536 DBG((dbgphi, 1, "\t color(%n) := %d\n", ns->irn, ns->color));
537 set_irn_color(ns->irn, ns->color);
538 if (pu_is_global_pinnable(pu, ns->irn) && ns->color == pu_get_new_color(pu, pu->nodes[0]))
539 pset_insert_ptr(pinned_global, ns->irn);
544 DBG((dbgphi, 1, "\tBest color: none\n"));
550 * Prepares a phi class for further processing as one or more phi units.
551 * Calls the worker-functions for all units.
552 * @param pc The phi class to process.
553 * @param root_phi In case of recursive call this is the phi node not beeing
554 * an argument in the phi1unit.
555 * Else this has to be NULL.
557 static void coal_phi_class(pset *pc, ir_node *root_phi) {
559 ir_node *n, *phi = NULL;
561 /* unfortunately there _can_ be >1 phi nodes in a phi1unit,
562 * so we have an if... */
567 /* get the phi count of this class. May result in phi_count == 1 */
568 for (n = pset_first(pc); n; n = pset_next(pc))
575 /* the 'simple' case */
576 if (phi_count == 1) {
584 DBG((dbgphi, 1, "\tPhi-1 unit:\n"));
585 pu = calloc(1, sizeof(*pu));
587 /* build member set not containing phi interferers */
588 DBG((dbgphi, 1, "\t %n\n", phi));
589 obstack_ptr_grow(&ob, phi);
592 for (n = pset_first(pc); n; n = pset_next(pc)) {
595 if (!phi_ops_interfere(phi, n)) {
596 DBG((dbgphi, 1, "\t %n\n", n));
597 obstack_ptr_grow(&ob, n);
600 DBG((dbgphi, 1, "\t %n \tdropped\n", n));
603 tmp = obstack_finish(&ob);
604 pu->nodes = malloc(pu->node_count * sizeof(*pu->nodes));
605 memcpy(&pu->nodes[0], tmp, pu->node_count * sizeof(*tmp));
606 obstack_free(&ob, NULL);
608 /* init conlict graph to life range interference */
609 DBG((dbgphi, 1, "\tInitial conflicts:\n"));
610 for (i = 0; i < pu->node_count; ++i)
611 for (o = i+1; o < pu->node_count; ++o)
612 if (phi_ops_interfere(pu->nodes[i], pu->nodes[o]))
613 pu_add_conflict(pu, pu->nodes[i], pu->nodes[o]);
614 pu->conflict_count_org = pu->conflict_count;
616 /* init changed nodes */
617 pu->changed_nodes = new_set(set_cmp_node_stat_t, INITIAL_SLOTS_CHANGED_NODES);
622 free(pu->changed_nodes);
625 } else { /* the 'not so easy' case */
626 DBG((dbgphi, 1, "\tPhi-n unit:\n"));
628 /* copy pc into big_pc... */
629 pset *copy = pset_new_ptr(32);
630 for (n = pset_first(pc); n; n = pset_next(pc)) {
631 DBG((dbgphi, 1, "\t %n\n", n));
632 pset_insert_ptr(copy, n);
635 /* ... because we want to build small 'connected graphs' and
636 * delete their members from the copy */
637 while (pset_count(copy) > 0) {
638 /* build all connected sets from the copy */
639 int last = 0, first = 0;
640 ir_node **queue = calloc(pset_count(copy), sizeof(*queue));
642 /* pick some node out of copy, place into queue */
643 n = pset_first(copy);
645 pset_remove_ptr(copy, n);
648 DBG((dbgphi, 1, "\tConnected:\n"));
649 pset *connected = pset_new_ptr(8);
650 while (first < last) {
651 /* pick n out of the queue into connected set */
653 pset_insert_ptr(connected, n);
654 DBG((dbgphi, 1, "\t %n\n", n));
657 /* check if pre/successors are 'connected' with n */
661 /* insert all args of n, which are in the phi class to the queue */
662 for(i=0; i < get_irn_arity(n); ++i) {
663 other = get_irn_n(n, i);
664 if (pset_find_ptr(copy, other) && !values_interfere(n, other)) {
665 queue[last++] = other;
666 pset_remove_ptr(copy, other);
669 /* same for outs of n */
670 for(i=0; i < get_irn_n_outs(n); ++i) {
671 other = get_irn_out(n, i);
672 if (pset_find_ptr(copy, other) && !values_interfere(n, other)) {
673 queue[last++] = other;
674 pset_remove_ptr(copy, other);
680 /* Now we have a "connected graph" build from copy==pc.
681 * Remove 1-phi-units from the connected set for
682 * passing to optimizer */
683 while (pset_count(connected) > 0) {
687 /* search a phi node */
688 for (n = pset_first(connected); n; n = pset_next(connected))
693 pset_break(connected);
695 /* if there are only non-phi nodes left quit */
699 /* Build a 1-phi-unit with this phi */
700 DBG((dbgphi, 1, "\t Phi-1-unit:\n"));
701 phi1unit = pset_new_ptr(8);
702 pset_insert_ptr(phi1unit, phi);
703 pset_remove_ptr(connected, phi);
704 DBG((dbgphi, 1, "\t\t%n\n", phi));
705 /* insert all arguments of phi, which are in the connected set
706 * to the 1-phi-unit */
707 for(i=0; i < get_irn_arity(phi); ++i) {
708 ir_node *arg = get_irn_n(phi, i);
709 if (pset_find_ptr(connected, arg)) {
710 DBG((dbgphi, 1, "\t\t%n\n", arg));
711 pset_insert_ptr(phi1unit, arg);
712 pset_remove_ptr(connected, arg);
716 /* finally the call for coalescing the 1-phi-unit */
717 if (pset_count(phi1unit) > 1) /* ==1 can happen if the connected set contains only a single phi node */
718 coal_phi_class(phi1unit, phi);
730 void be_phi_coalesce(pset *all_phi_classes) {
733 pinned_global = pset_new_ptr(INITIAL_SLOTS_PINNED_GLOBAL);
735 for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes))
736 coal_phi_class(pc, NULL);
738 del_pset(pinned_global);
742 void be_phi_coal_init(void) {
743 dbgphi = firm_dbg_register("ir.be.phicoal");
744 firm_dbg_set_mask(dbgphi, DEBUG_LVL);