+} /* partition_for_block */
+
+/**
+ * Walker: clear the links of all block phi lists and normal
+ * links.
+ */
+static void clear_phi_links(ir_node *irn, void *env)
+{
+ (void) env;
+ if (is_Block(irn)) {
+ set_Block_phis(irn, NULL);
+ set_irn_link(irn, NULL);
+ }
+} /* clear_phi_links */
+
+/**
+ * Walker, detect live-out nodes.
+ */
+static void find_liveouts(ir_node *irn, void *ctx)
+{
+ environment_t *env = (environment_t*)ctx;
+ ir_node **live_outs = env->live_outs;
+ ir_node *this_block;
+ int i;
+
+ if (is_Block(irn))
+ return;
+
+ /* ignore Keep-alives */
+ if (is_End(irn))
+ return;
+
+ this_block = get_nodes_block(irn);
+
+ if (is_Phi(irn)) {
+ /* update the Phi list */
+ add_Block_phi(this_block, irn);
+ }
+
+ for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
+ ir_node *pred_block;
+ ir_node *pred = get_irn_n(irn, i);
+ int idx = get_irn_idx(pred);
+
+ if (live_outs[idx] != NULL) {
+ /* already marked as live-out */
+ return;
+ }
+
+ pred_block = get_nodes_block(pred);
+ /* Phi nodes always refer to live-outs */
+ if (is_Phi(irn) || this_block != pred_block) {
+ /* pred is a live-out */
+ live_outs[idx] = pred_block;
+ }
+ }
+} /* find_liveouts */
+
+/**
+ * Check if the current block is the meet block of a its predecessors.
+ */
+static void check_for_cf_meet(ir_node *block, void *ctx)
+{
+ environment_t *env = (environment_t*)ctx;
+ int i, k, n;
+ pred_t *preds;
+
+ if (block == get_irg_end_block(get_irn_irg(block))) {
+ /* always create a partition for the end block */
+ partition_for_end_block(block, env);
+ return;
+ }
+
+ n = get_Block_n_cfgpreds(block);
+ if (n <= 1) {
+ /* Must have at least two predecessors */
+ return;
+ }
+
+ NEW_ARR_A(pred_t, preds, n);
+ k = 0;
+ for (i = n - 1; i >= 0; --i) {
+ ir_node *pred = get_Block_cfgpred(block, i);
+ ir_node *pred_block;
+
+ /* pred must be a direct jump to us */
+ if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred))
+ continue;
+
+ pred_block = get_nodes_block(skip_Proj(pred));
+
+ preds[k].pred = pred;
+ preds[k].index = i;
+ }
+
+ if (k > 1)
+ partition_for_block(block, preds, k, env);
+} /* check_for_cf_meet */
+
+/**
+ * Compare two nodes for root ordering.
+ */
+static int cmp_nodes(const void *a, const void *b)
+{
+ const ir_node *const *pa = (const ir_node*const*)a;
+ const ir_node *const *pb = (const ir_node*const*)b;
+ const ir_node *irn_a = *pa;
+ const ir_node *irn_b = *pb;
+ unsigned code_a = get_irn_opcode(irn_a);
+ unsigned code_b = get_irn_opcode(irn_b);
+ ir_mode *mode_a, *mode_b;
+ unsigned idx_a, idx_b;
+
+ /* try opcode first */
+ if (code_a != code_b)
+ return code_a - code_b;
+
+ /* try mode */
+ mode_a = get_irn_mode(irn_a);
+ mode_b = get_irn_mode(irn_b);
+
+ if (mode_a != mode_b)
+ return mode_a < mode_b ? -1 : +1;
+
+ /* last resort: index */
+ idx_a = get_irn_idx(irn_a);
+ idx_b = get_irn_idx(irn_b);
+
+ return (idx_a > idx_b) - (idx_a < idx_b);
+} /* cmp_nodes */
+
+/**
+ * Add the roots to all blocks.
+ */
+static void add_roots(ir_graph *irg, environment_t *env)
+{
+ unsigned idx, n = get_irg_last_idx(irg);
+ ir_node **live_outs = env->live_outs;
+ block_t *bl;
+
+ for (idx = 0; idx < n; ++idx) {
+ ir_node *block = live_outs[idx];
+
+ if (block != NULL && is_Block(block)) {
+ block_t *bl = get_Block_entry(block);