+} /* get_leader */
+
+/**
+ * Returns non-zero if a mode_T node has only one reachable output.
+ */
+static int only_one_reachable_proj(ir_node *n)
+{
+ int i, k = 0;
+
+ for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
+ ir_node *proj = get_irn_out(n, i);
+ node_t *node;
+
+ /* skip non-control flow Proj's */
+ if (get_irn_mode(proj) != mode_X)
+ continue;
+
+ node = get_irn_node(proj);
+ if (node->type.tv == tarval_reachable) {
+ if (++k > 1)
+ return 0;
+ }
+ }
+ return 1;
+} /* only_one_reachable_proj */
+
+/**
+ * Return non-zero if the control flow predecessor node pred
+ * is the only reachable control flow exit of its block.
+ *
+ * @param pred the control flow exit
+ * @param block the destination block
+ */
+static int can_exchange(ir_node *pred, ir_node *block)
+{
+ if (is_Start(pred) || get_Block_entity(block) != NULL)
+ return 0;
+ else if (is_Jmp(pred))
+ return 1;
+ else if (is_Raise(pred)) {
+ /* Raise is a tuple and usually has only one reachable ProjX,
+ * but it must not be eliminated like a Jmp */
+ return 0;
+ }
+ else if (get_irn_mode(pred) == mode_T) {
+ /* if the predecessor block has more than one
+ reachable outputs we cannot remove the block */
+ return only_one_reachable_proj(pred);
+ }
+ return 0;
+} /* can_exchange */
+
+/**
+ * Block Post-Walker, apply the analysis results on control flow by
+ * shortening Phi's and Block inputs.
+ */
+static void apply_cf(ir_node *block, void *ctx)
+{
+ environment_t *env = (environment_t*)ctx;
+ node_t *node = get_irn_node(block);
+ int i, j, k, n;
+ ir_node **ins, **in_X;
+ ir_node *phi, *next;
+
+ n = get_Block_n_cfgpreds(block);
+
+ if (node->type.tv == tarval_unreachable) {
+ env->modified = 1;
+
+ for (i = n - 1; i >= 0; --i) {
+ ir_node *pred = get_Block_cfgpred(block, i);
+
+ if (! is_Bad(pred)) {
+ ir_node *pred_block = get_nodes_block(skip_Proj(pred));
+ if (!is_Bad(pred_block)) {
+ node_t *pred_bl = get_irn_node(pred_block);
+
+ if (pred_bl->flagged == 0) {
+ pred_bl->flagged = 3;
+
+ if (pred_bl->type.tv == tarval_reachable) {
+ /*
+ * We will remove an edge from block to its pred.
+ * This might leave the pred block as an endless loop
+ */
+ if (! is_backedge(block, i))
+ keep_alive(pred_bl->node);
+ }
+ }
+ }
+ }
+ }
+
+ if (block == get_irg_end_block(current_ir_graph)) {
+ /* Analysis found out that the end block is unreachable,
+ * hence we remove all its control flow predecessors. */
+ set_irn_in(block, 0, NULL);
+ }
+ return;
+ }
+
+ if (n == 1) {
+ /* only one predecessor combine */
+ ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0));
+
+ if (can_exchange(pred, block)) {
+ ir_node *new_block = get_nodes_block(pred);
+ DB((dbg, LEVEL_1, "Fuse %+F with %+F\n", block, new_block));
+ DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
+ exchange(block, new_block);
+ node->node = new_block;
+ env->modified = 1;
+ }
+ return;
+ }
+
+ NEW_ARR_A(ir_node *, in_X, n);
+ k = 0;
+ for (i = 0; i < n; ++i) {
+ ir_node *pred = get_Block_cfgpred(block, i);
+ node_t *node = get_irn_node(pred);
+
+ if (node->type.tv == tarval_reachable) {
+ in_X[k++] = pred;
+ } else {
+ DB((dbg, LEVEL_1, "Removing dead input %d from %+F (%+F)\n", i, block, pred));
+ if (! is_Bad(pred)) {
+ ir_node *pred_block = get_nodes_block(skip_Proj(pred));
+ if (!is_Bad(pred_block)) {
+ node_t *pred_bl = get_irn_node(pred_block);
+
+ if (!is_Bad(pred_bl->node) && pred_bl->flagged == 0) {
+ pred_bl->flagged = 3;
+
+ if (pred_bl->type.tv == tarval_reachable) {
+ /*
+ * We will remove an edge from block to its pred.
+ * This might leave the pred block as an endless loop
+ */
+ if (! is_backedge(block, i))
+ keep_alive(pred_bl->node);
+ }
+ }
+ }
+ }
+ }
+ }
+ if (k >= n)
+ return;
+
+ /* fix Phi's */
+ NEW_ARR_A(ir_node *, ins, n);
+ for (phi = get_Block_phis(block); phi != NULL; phi = next) {
+ node_t *node = get_irn_node(phi);
+
+ next = get_Phi_next(phi);
+ if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
+ /* this Phi is replaced by a constant */
+ ir_tarval *tv = node->type.tv;
+ ir_node *c = new_r_Const(current_ir_graph, tv);
+
+ set_irn_node(c, node);
+ node->node = c;
+ DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, c));
+ DBG_OPT_COMBO(phi, c, FS_OPT_COMBO_CONST);
+ exchange(phi, c);
+ env->modified = 1;
+ } else {
+ j = 0;
+ for (i = 0; i < n; ++i) {
+ node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
+
+ if (pred->type.tv == tarval_reachable) {
+ ins[j++] = get_Phi_pred(phi, i);
+ }
+ }
+ if (j == 1) {
+ /* this Phi is replaced by a single predecessor */
+ ir_node *s = ins[0];
+ node_t *phi_node = get_irn_node(phi);
+
+ node->node = s;
+ DB((dbg, LEVEL_1, "%+F is replaced by %+F because of cf change\n", phi, s));
+ DBG_OPT_COMBO(phi, s, FS_OPT_COMBO_FOLLOWER);
+ exchange(phi, s);
+ phi_node->node = s;
+ env->modified = 1;
+ } else {
+ set_irn_in(phi, j, ins);
+ env->modified = 1;
+ }
+ }
+ }
+
+ /* fix block */
+ if (k == 1) {
+ /* this Block has only one live predecessor */
+ ir_node *pred = skip_Proj(in_X[0]);
+
+ if (can_exchange(pred, block)) {
+ ir_node *new_block = get_nodes_block(pred);
+ DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
+ exchange(block, new_block);
+ node->node = new_block;
+ env->modified = 1;
+ return;
+ }
+ }
+ set_irn_in(block, k, in_X);
+ env->modified = 1;
+} /* apply_cf */
+
+/**
+ * Exchange a node by its leader.
+ * Beware: in rare cases the mode might be wrong here, for instance
+ * AddP(x, NULL) is a follower of x, but with different mode.
+ * Fix it here.
+ */
+static void exchange_leader(ir_node *irn, ir_node *leader)
+{
+ ir_mode *mode = get_irn_mode(irn);
+ if (mode != get_irn_mode(leader)) {
+ /* The conv is a no-op, so we are free to place it
+ * either in the block of the leader OR in irn's block.
+ * Probably placing it into leaders block might reduce
+ * the number of Conv due to CSE. */
+ ir_node *block = get_nodes_block(leader);
+ dbg_info *dbg = get_irn_dbg_info(irn);
+ ir_node *nlead = new_rd_Conv(dbg, block, leader, mode);
+
+ if (nlead != leader) {
+ /* Note: this newly create irn has no node info because
+ * it is created after the analysis. However, this node
+ * replaces the node irn and should not be visited again,
+ * so set its visited count to the count of irn.
+ * Otherwise we might visited this node more than once if
+ * irn had more than one user.
+ */
+ set_irn_node(nlead, NULL);
+ set_irn_visited(nlead, get_irn_visited(irn));
+ leader = nlead;
+ }
+ }
+ exchange(irn, leader);
+} /* exchange_leader */
+
+/**
+ * Check, if all users of a mode_M node are dead. Use
+ * the Def-Use edges for this purpose, as they still
+ * reflect the situation.
+ */
+static int all_users_are_dead(const ir_node *irn)
+{
+ int i, n = get_irn_n_outs(irn);
+
+ for (i = 1; i <= n; ++i) {
+ const ir_node *succ = irn->out[i].use;
+ const node_t *block = get_irn_node(get_nodes_block(succ));
+ const node_t *node;
+
+ if (block->type.tv == tarval_unreachable) {
+ /* block is unreachable */
+ continue;
+ }
+ node = get_irn_node(succ);
+ if (node->type.tv != tarval_top) {
+ /* found a reachable user */
+ return 0;
+ }
+ }
+ /* all users are unreachable */
+ return 1;
+} /* all_user_are_dead */
+
+/**
+ * Walker: Find reachable mode_M nodes that have only
+ * unreachable users. These nodes must be kept later.
+ */
+static void find_kept_memory(ir_node *irn, void *ctx)
+{
+ environment_t *env = (environment_t*)ctx;
+ node_t *node, *block;
+
+ if (get_irn_mode(irn) != mode_M)
+ return;
+
+ block = get_irn_node(get_nodes_block(irn));
+ if (block->type.tv == tarval_unreachable)
+ return;
+
+ node = get_irn_node(irn);
+ if (node->type.tv == tarval_top)
+ return;
+
+ /* ok, we found a live memory node. */
+ if (all_users_are_dead(irn)) {
+ DB((dbg, LEVEL_1, "%+F must be kept\n", irn));
+ ARR_APP1(ir_node *, env->kept_memory, irn);
+ }
+} /* find_kept_memory */