+ ir_node *curr_bl;
+ ir_node *start_irn;
+ firm_dbg_module_t *dbg = DBG_MODULE;
+
+ curr_bl = get_nodes_block(usage);
+
+ DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
+ /*
+ * If the usage is in a phi node, search the copy in the
+ * predecessor denoted by pos.
+ */
+ if(is_Phi(usage)) {
+ curr_bl = get_Block_cfgpred_block(curr_bl, pos);
+ start_irn = sched_last(curr_bl);
+ } else {
+ start_irn = sched_prev(usage);
+ }
+
+ /*
+ * Traverse the dominance tree upwards from the
+ * predecessor block of the usage.
+ */
+ while(curr_bl != NULL) {
+
+ /*
+ * If this block contains a copy, search the block
+ * instruction by instruction.
+ */
+ if(pset_find_ptr(copy_blocks, curr_bl)) {
+ ir_node *irn;
+
+ /* Look at each instruction from last to first. */
+ sched_foreach_reverse_from(start_irn, irn) {
+
+ /* Take the first copy we find. */
+ if(pset_find_ptr(copies, irn))
+ return irn;
+ }
+ }
+
+ if(pset_find_ptr(phi_blocks, curr_bl)) {
+ ir_node *phi = get_irn_link(curr_bl);
+
+ if(!phi) {
+ int i, n_preds = get_irn_arity(curr_bl);
+ ir_graph *irg = get_irn_irg(curr_bl);
+ ir_node **ins = xmalloc(n_preds * sizeof(ins[0]));
+
+ for(i = 0; i < n_preds; ++i)
+ ins[i] = new_r_Bad(irg);
+
+ phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
+ DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
+
+ set_irn_link(curr_bl, phi);
+ sched_add_after(curr_bl, phi);
+ free(ins);
+
+ for(i = 0; i < n_preds; ++i) {
+ ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
+ DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
+ set_irn_n(phi, i, arg);
+ }
+
+ if(phis)
+ pset_insert_ptr(phis, phi);
+ }
+
+ return phi;
+ }
+
+ /* If were not done yet, look in the immediate dominator */
+ curr_bl = get_Block_idom(curr_bl);
+ if(curr_bl)
+ start_irn = sched_last(curr_bl);
+ }
+
+ return NULL;
+}