+ 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 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);
+
+ /* pred must be a direct jump to us */
+ if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred))
+ continue;
+
+ preds[k].pred = pred;
+ preds[k].index = i;
+ ++k;
+ }
+
+ 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);
+
+ if (bl != NULL) {
+ ir_node *irn = get_idx_irn(irg, idx);
+
+ if (!irn_visited_else_mark(irn)) {
+ ARR_APP1(ir_node *, bl->roots, irn);
+ }
+ }
+ }
+ }
+ /*
+ * Now sort the roots to normalize them as good as possible.
+ * Else, we will split identical blocks if we start which different roots.
+ */
+ for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) {
+ size_t i, n = ARR_LEN(bl->roots);
+
+#if 1
+ /* TODO: is this really needed? The roots are already in
+ idx-order by construction, which might be good enough. */
+ qsort(bl->roots, n, sizeof(bl->roots[0]), cmp_nodes);
+#endif
+
+ DB((dbg, LEVEL_2, " Adding Roots for block %+F\n ", bl->block));
+ /* ok, add them sorted */
+ for (i = 0; i < n; ++i) {
+ DB((dbg, LEVEL_2, "%+F, ", bl->roots[i]));
+ create_node(bl->roots[i], bl, env);
+ }
+ DB((dbg, LEVEL_2, "\n"));
+ DEL_ARR_F(bl->roots);
+ bl->roots = NULL;
+ }
+} /* add_roots */
+#endif /* GENERAL_SHAPE */
+
+/* Combines congruent end blocks into one. */
+int shape_blocks(ir_graph *irg)
+{
+ environment_t env;
+ partition_t *part;
+ block_t *bl;
+ int res, n;
+
+ /* register a debug mask */
+ FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
+
+ DEBUG_ONLY(part_nr = 0;)
+ DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));
+
+ /* works better, when returns are placed at the end of the blocks */
+ normalize_n_returns(irg);
+
+ obstack_init(&env.obst);
+ INIT_LIST_HEAD(&env.partitions);
+ INIT_LIST_HEAD(&env.ready);
+ env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4);
+
+ n = get_irg_last_idx(irg);
+ env.live_outs = NEW_ARR_F(ir_node *, n);
+ memset(env.live_outs, 0, sizeof(*env.live_outs) * n);
+
+ env.all_blocks = NULL;
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+
+#ifdef GENERAL_SHAPE
+ /*
+ * Detect, which nodes are live-out only: these are the roots of our blocks.
+ * Build phi lists.
+ */
+ irg_walk_graph(irg, clear_phi_links, find_liveouts, &env);
+#endif
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
+
+ inc_irg_visited(irg);
+#ifdef GENERAL_SHAPE
+ /*
+ * Detect all control flow meets and create partitions.
+ */
+ irg_block_walk_graph(irg, NULL, check_for_cf_meet, &env);
+
+ /* add root nodes to the partition blocks */
+ add_roots(irg, &env);
+#else
+ partition_for_end_block(get_irg_end_block(irg), &env);
+#endif
+
+ propagate_live_troughs(&env);