+/**
+ * Performs virtual re-coloring of node @p n to color @p col. Virtual colors of
+ * other nodes are changed too, as required to preserve correctness. Function is
+ * aware of local and global pinning. Recursive.
+ * @param irn The node to set the color for
+ * @param col The color to set.
+ * @param trigger The irn that caused the wish to change the color of the irn
+ * @param changed_nodes An obstack on which all ir_nodes get growed on, which are changed
+ * @return CHANGE_SAVE iff setting the color is possible, with all transiteve effects.
+ * CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured.
+ * CHANGE_NYI iff an unhandled situation occurs.
+ * Else the first conflicting ir_node encountered is returned.
+ *
+ * ASSUMPTION: Assumes that a life range of a single value can't be spilt into
+ * several smaller intervals where other values can live in between.
+ */
+static ir_node *_pu_color_irn(phi_unit_t *pu, ir_node *irn, int col, const ir_node *trigger, struct obstack *changed_nodes) {
+ ir_node *res;
+ struct obstack confl_ob;
+ ir_node **confl, *cn;
+ int i, irn_col;
+
+ obstack_init(&confl_ob);
+ irn_col = pu_get_new_color(pu, irn);
+
+ if (irn_col == col)
+ goto ret_save;
+ if (pset_find_ptr(pinned_global, irn) || pu_is_node_pinned(pu, irn)) {
+ DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Pinned\n", trigger, irn, col));
+ res = irn;
+ goto ret_confl;
+ }
+
+ /* get all nodes which would conflict with this change */
+ {
+ struct obstack q;
+ int in, out;
+
+ /* setup the queue */
+ obstack_init(&q);
+ obstack_ptr_grow(&q, get_nodes_block(irn));
+ in = 1;
+ out = 0;
+
+ /* process the queue */
+ while (out < in) {
+ ir_node *curr_bl, *sub_bl;
+ int i, max;
+
+ curr_bl = ((ir_node **)obstack_base(&q))[out++];
+
+ /* Add to the result all nodes in the block which live in target color
+ * and interfere with the irn */
+ for (i = 0, max = get_irn_n_outs(curr_bl); i < max; ++i) {
+ ir_node *n = get_irn_out(curr_bl, i);
+ if (!is_allocatable_irn(n))
+ continue;
+ if (n != trigger && pu_get_new_color(pu, n) == col && phi_ops_interfere(irn, n))
+ obstack_ptr_grow(&confl_ob, n);
+ }
+
+ /* If irn lives out check i-dominated blocks where the irn lives in */
+ /* Fill the queue */
+ if (is_live_out(curr_bl, irn)) {
+ dominates_for_each(curr_bl, sub_bl)
+ if (is_live_in(sub_bl, irn)) {
+ obstack_ptr_grow(&q, sub_bl);
+ in++;
+ }
+ }
+ }
+ obstack_free(&q, NULL);
+ obstack_ptr_grow(&confl_ob, NULL);
+ confl = (ir_node **) obstack_finish(&confl_ob);
+ }
+
+ /* process all nodes which would conflict with this change */
+ for (i = 0, cn = confl[0]; cn; cn = confl[++i]) {
+ ir_node *sub_res;
+
+ /* try to color the conflicting node cn with the color of the irn itself */
+ DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: Subcheck\n", trigger, irn, col));
+ sub_res = _pu_color_irn(pu, cn, irn_col, irn, changed_nodes);
+ if (sub_res != CHANGE_SAVE) {
+ res = sub_res;
+ goto ret_confl;
+ }
+ }
+ /* if we arrive here all sub changes can be applied, so it's save to change this irn */
+
+ret_save:
+ DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Save\n", trigger, irn, col));
+ obstack_free(&confl_ob, NULL);
+ pu_set_new_color(pu, irn, col);
+ obstack_ptr_grow(changed_nodes, irn);
+ return CHANGE_SAVE;
+
+ret_confl:
+ DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Conflict\n", trigger, irn, col));
+ obstack_free(&confl_ob, NULL);
+ return res;