+/**
+ * Inserts a spill of a value at the earliest possible location in a block.
+ * That is after the last use of the value or at the beginning of the block if
+ * there is no use
+ */
+static ir_node *insert_copy(belady_env_t *env, ir_node *block, ir_node *value) {
+ ir_node* node;
+ ir_graph *irg = get_irn_irg(block);
+ ir_node *copy = be_new_Copy(env->cls, irg, block, value);
+
+ ARR_APP1(ir_node*, env->copies, copy);
+
+ // walk schedule backwards until we find a usage, or until we have reached the first phi
+ // TODO can we do this faster somehow? This makes insert_copy O(n) in block_size...
+ sched_foreach_reverse(block, node) {
+ int i, arity;
+
+ if(is_Phi(node)) {
+ sched_add_after(node, copy);
+ goto placed;
+ }
+ if(value == node) {
+ sched_add_after(node, copy);
+ goto placed;
+ }
+ for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
+ ir_node *arg = get_irn_n(node, i);
+ if(arg == value) {
+ sched_add_after(node, copy);
+ goto placed;
+ }
+ }
+ }
+ // we didn't find a use or a phi yet, so place the copy at the beginning of the block
+ sched_add_before(sched_first(block), copy);
+
+placed:
+
+ return copy;
+}
+