X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_blocks.c;h=0154be69d5c30eefdfa3fa34d3e4b3b687044dc6;hb=7547cf525ad54f59d2dc3f39d4b257911c94989b;hp=7ae3bfb6c4bd03f5254a2947f509f5611ef7b861;hpb=3b8f0cc2197221d6c1c424e9359790654c718b5c;p=libfirm

diff --git a/ir/opt/opt_blocks.c b/ir/opt/opt_blocks.c
index 7ae3bfb6c..0154be69d 100644
--- a/ir/opt/opt_blocks.c
+++ b/ir/opt/opt_blocks.c
@@ -23,20 +23,28 @@
  * @author  Michael Beck
  * @version $Id$
  *
- * This phase find congruent blocks. Works currently for
- * predecessors of the end block only.
+ * This phase find congruent blocks.
  * Two block are congruent, if they contains only equal calculations.
  */
 #include "config.h"
-#include "ircons.h"
+
 #include "iroptimize.h"
+#include "ircons.h"
+#include "irgmod.h"
 #include "irgraph_t.h"
 #include "irnode_t.h"
 #include "iropt_t.h"
+#include "array_t.h"
 #include "trouts.h"
+#include "irgwalk.h"
 #include "set.h"
+#include "irpass.h"
 #include "debug.h"
 
+/* define this for general block shaping: congruent blocks
+   are found not only before the end block but anywhere in the graph */
+#define GENERAL_SHAPE
+
 typedef struct partition_t     partition_t;
 typedef struct block_t         block_t;
 typedef struct node_t          node_t;
@@ -45,6 +53,7 @@ typedef struct phi_t           phi_t;
 typedef struct opcode_key_t    opcode_key_t;
 typedef struct listmap_entry_t listmap_entry_t;
 typedef struct environment_t   environment_t;
+typedef struct pred_t          pred_t;
 
 /** An opcode map key. */
 struct opcode_key_t {
@@ -52,8 +61,12 @@ struct opcode_key_t {
 	ir_mode     *mode;  /**< The mode of all nodes in the partition. */
 	int         arity;  /**< The arity of this opcode (needed for Phi etc. */
 	union {
-		long      proj;   /**< For Proj nodes, its proj number */
-		ir_entity *ent;   /**< For Sel Nodes, its entity */
+		long            proj;   /**< For Proj nodes, its proj number */
+		ir_entity       *ent;   /**< For Sel nodes, its entity */
+		ir_tarval       *tv;    /**< For Const nodes, its tarval */
+		symconst_symbol sym;    /**< For SymConst nodes, its symbol .*/
+		void            *addr;  /**< Alias all addresses. */
+		int             intVal; /**< For Conv/Div nodes: strict/remainderless. */
 	} u;
 };
 
@@ -74,16 +87,18 @@ struct block_t {
 	list_head  nodes;        /**< Wait-queue of nodes that must be checked for congruence. */
 	block_t    *next;        /**< Next block of a split list. */
 	ir_node    *block;       /**< Pointer to the associated IR-node block. */
-	node_t     *roots;       /**< The list of all root nodes. */
+	ir_node    **roots;      /**< An array of all root nodes. */
+	node_t     *cf_root;     /**< The control flow root node of this block. */
 	pair_t     *input_pairs; /**< The list of inputs to this block. */
 	phi_t      *phis;        /**< The list of Phis in this block. */
+	block_t    *all_next;    /**< Links all created blocks. */
+	int        meet_input;   /**< Input number of this block in the meet-block. */
 };
 
 /** A node. */
 struct node_t {
 	list_head  node_list;    /**< Double linked list of block inside a partition. */
 	ir_node    *node;        /**< Pointer to the associated IR-node or NULL for block inputs. */
-	node_t     *next;        /**< Link to the next node in the root set. */
 	char       is_input;     /**< Set if this node is an input from other block. */
 };
 
@@ -92,10 +107,12 @@ struct environment_t {
 	list_head       partitions;     /**< list of partitions. */
 	list_head       ready;          /**< list of ready partitions. */
 	set             *opcode2id_map; /**< The opcodeMode->id map. */
+	ir_node         **live_outs;    /**< Live out only nodes. */
+	block_t         *all_blocks;    /**< List of all created blocks. */
 	struct obstack  obst;           /** obstack for temporary data */
 };
 
-/** A node, input index pair. */
+/** A (node, input index) pair. */
 struct pair_t {
 	pair_t  *next;    /**< Points to the next pair entry. */
 	ir_node *irn;     /**< The IR-node. */
@@ -110,6 +127,12 @@ struct phi_t {
 	ir_node **ins;    /**< A new in array once allocated. */
 };
 
+/** Describes a predecessor input. */
+struct pred_t {
+	ir_node *pred;  /**< The predecessor. */
+	int     index;  /**< Its input index. */
+};
+
 /**
  * An entry in the list_map.
  */
@@ -125,6 +148,8 @@ typedef struct listmap_t {
 	listmap_entry_t *values; /**< List of all values in the map. */
 } listmap_t;
 
+#define get_Block_entry(block)  ((block_t *)get_irn_link(block))
+
 /** The debug module handle. */
 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 
@@ -135,7 +160,8 @@ DEBUG_ONLY(static unsigned part_nr = 0);
 /**
  * Dump partition to output.
  */
-static void dump_partition(const char *msg, const partition_t *part) {
+static void dump_partition(const char *msg, const partition_t *part)
+{
 	const block_t *block;
 	int           first = 1;
 
@@ -150,7 +176,8 @@ static void dump_partition(const char *msg, const partition_t *part) {
 /**
  * Dumps a list.
  */
-static void dump_list(const char *msg, const block_t *block) {
+static void dump_list(const char *msg, const block_t *block)
+{
 	const block_t *p;
 	int           first = 1;
 
@@ -169,7 +196,8 @@ static void dump_list(const char *msg, const block_t *block) {
 /**
  * Compare two pointer values of a listmap.
  */
-static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
+static int listmap_cmp_ptr(const void *elt, const void *key, size_t size)
+{
 	const listmap_entry_t *e1 = elt;
 	const listmap_entry_t *e2 = key;
 
@@ -182,7 +210,8 @@ static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
  *
  * @param map  the listmap
  */
-static void listmap_init(listmap_t *map) {
+static void listmap_init(listmap_t *map)
+{
 	map->map    = new_set(listmap_cmp_ptr, 16);
 	map->values = NULL;
 }  /* listmap_init */
@@ -192,7 +221,8 @@ static void listmap_init(listmap_t *map) {
  *
  * @param map  the listmap
  */
-static void listmap_term(listmap_t *map) {
+static void listmap_term(listmap_t *map)
+{
 	del_set(map->map);
 }  /* listmap_term */
 
@@ -204,7 +234,8 @@ static void listmap_term(listmap_t *map) {
  *
  * @return the associated listmap entry for the given id
  */
-static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
+static listmap_entry_t *listmap_find(listmap_t *map, void *id)
+{
 	listmap_entry_t key, *entry;
 
 	key.id   = id;
@@ -227,32 +258,36 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
  *
  * @return a hash value for the given opcode map entry
  */
-static unsigned opcode_hash(const opcode_key_t *entry) {
-	return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
+static unsigned opcode_hash(const opcode_key_t *entry)
+{
+	/* assume long >= int */
+	return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.addr) + entry->arity;
 }  /* opcode_hash */
 
 /**
  * Compare two entries in the opcode map.
  */
-static int cmp_opcode(const void *elt, const void *key, size_t size) {
+static int cmp_opcode(const void *elt, const void *key, size_t size)
+{
 	const opcode_key_t *o1 = elt;
 	const opcode_key_t *o2 = key;
 
 	(void) size;
 	return o1->code != o2->code || o1->mode != o2->mode ||
 	       o1->arity != o2->arity ||
-	       o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
+	       o1->u.proj != o2->u.proj || o1->u.addr != o2->u.addr;
 }  /* cmp_opcode */
 
 /**
  * Creates a new empty partition and put in on the
  * partitions list.
  *
- * @param meet_block  the control flow meet block of thi partition
+ * @param meet_block  the control flow meet block of this partition
  * @param env         the environment
  */
-static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
-	partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
+static partition_t *create_partition(ir_node *meet_block, environment_t *env)
+{
+	partition_t *part = OALLOC(&env->obst, partition_t);
 
 	INIT_LIST_HEAD(&part->blocks);
 	part->meet_block = meet_block;
@@ -266,22 +301,33 @@ static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
  * Allocate a new block in the given partition.
  *
  * @param block      the IR-node
+ * @param meet_input Input number of this block in the meet-block
  * @param partition  the partition to add to
  * @param env        the environment
  */
-static block_t *create_block(ir_node *block, partition_t *partition, environment_t *env) {
-	block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
+static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env)
+{
+	block_t *bl = OALLOC(&env->obst, block_t);
+
+	set_irn_link(block, bl);
 
 	INIT_LIST_HEAD(&bl->nodes);
 	bl->next        = NULL;
 	bl->block       = block;
-	bl->roots       = NULL;
+	bl->roots       = NEW_ARR_F(ir_node *, 0);
+	bl->cf_root     = NULL;
 	bl->input_pairs = NULL;
 	bl->phis        = NULL;
+	bl->meet_input  = meet_input;
 
+	/* put it into the list of partition blocks */
 	list_add_tail(&bl->block_list, &partition->blocks);
 	++partition->n_blocks;
 
+	/* put in into the list of all blocks */
+	bl->all_next    = env->all_blocks;
+	env->all_blocks = bl;
+
 	return bl;
 }  /* create_block */
 
@@ -292,11 +338,11 @@ static block_t *create_block(ir_node *block, partition_t *partition, environment
  * @param block  the block to add to
  * @param env    the environment
  */
-static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
-	node_t *node = obstack_alloc(&env->obst, sizeof(*node));
+static node_t *create_node(ir_node *irn, block_t *block, environment_t *env)
+{
+	node_t *node = OALLOC(&env->obst, node_t);
 
 	node->node     = irn;
-	node->next     = NULL;
 	node->is_input = 0;
 
 	list_add_tail(&node->node_list, &block->nodes);
@@ -312,8 +358,9 @@ static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
  * @param idx    the index of the block input in node's predecessors
  * @param env    the environment
  */
-static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) {
-	pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair));
+static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env)
+{
+	pair_t *pair = OALLOC(&env->obst, pair_t);
 
 	pair->next  = block->input_pairs;
 	pair->irn   = irn;
@@ -330,8 +377,9 @@ static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env)
  * @param phi    the Phi node
  * @param env    the environment
  */
-static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
-	phi_t *node = obstack_alloc(&env->obst, sizeof(*node));
+static void add_phi(block_t *block, ir_node *phi, environment_t *env)
+{
+	phi_t *node = OALLOC(&env->obst, phi_t);
 
 	node->next = block->phis;
 	node->phi  = phi;
@@ -343,7 +391,8 @@ static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
 /**
  * Creates an opcode from a node.
  */
-static opcode_key_t *opcode(const node_t *node, environment_t *env) {
+static opcode_key_t *opcode(const node_t *node, environment_t *env)
+{
 	opcode_key_t key, *entry;
 	ir_node      *irn = node->node;
 
@@ -358,7 +407,7 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) {
 	}
 	key.mode   = get_irn_mode(node->node);
 	key.u.proj = 0;
-	key.u.ent  = NULL;
+	key.u.addr = NULL;
 
 	switch (key.code) {
 	case iro_Proj:
@@ -367,6 +416,24 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) {
 	case iro_Sel:
 		key.u.ent = get_Sel_entity(irn);
 		break;
+	case iro_SymConst:
+		key.u.sym = get_SymConst_symbol(irn);
+		break;
+	case iro_Const:
+		key.u.tv  = get_Const_tarval(irn);
+		break;
+	case iro_Conv:
+		key.u.intVal = get_Conv_strict(irn);
+		break;
+	case iro_Load:
+		key.mode = get_Load_mode(irn);
+		break;
+	case iro_Div:
+		key.u.intVal = get_Div_no_remainder(irn);
+		break;
+	case iro_Builtin:
+		key.u.intVal = get_Builtin_kind(irn);
+		break;
 	default:
 		break;
 	}
@@ -384,7 +451,8 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) {
  *
  * @return  a new partition containing the nodes of g
  */
-static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
+static partition_t *split(partition_t *Z, block_t *g, environment_t *env)
+{
 	partition_t *Z_prime;
 	block_t     *block;
 	unsigned    n = 0;
@@ -414,13 +482,29 @@ static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
 	return Z_prime;
 }  /* split */
 
+/**
+ * Return non-zero if pred should be tread as a input node.
+ */
+static int is_input_node(ir_node *pred, ir_node *irn, int index)
+{
+	/* for now, do NOT turn direct calls into indirect one */
+	if (index != 1)
+		return 1;
+	if (! is_SymConst_addr_ent(pred))
+		return 1;
+	if (! is_Call(irn))
+		return 1;
+	return 0;
+}  /* is_input_node */
+
 /**
  * Propagate nodes on all wait queues of the given partition.
  *
  * @param part  the partition
- * @param env    the environment
+ * @param env   the environment
  */
-void propagate_blocks(partition_t *part, environment_t *env) {
+static void propagate_blocks(partition_t *part, environment_t *env)
+{
 	block_t         *ready_blocks = NULL;
 	unsigned        n_ready       = 0;
 	block_t         *bl, *next;
@@ -429,7 +513,7 @@ void propagate_blocks(partition_t *part, environment_t *env) {
 
 	DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
 
-	/* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */
+	/* Let map be an empty mapping from the range of Opcodes to (local) list of blocks. */
 	listmap_init(&map);
 	list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
 		opcode_key_t    *id;
@@ -462,11 +546,14 @@ void propagate_blocks(partition_t *part, environment_t *env) {
 
 				if (block != bl->block) {
 					p_node = create_node(pred, bl, env);
-					/* do not threat Constants like live-ins */
-					if (! is_irn_constlike(irn)) {
+					if (is_input_node(pred, irn, i)) {
+						/* is a block live input */
 						p_node->is_input = 1;
 						if (! is_Phi(irn))
 							add_pair(bl, irn, i, env);
+					} else if (is_Phi(pred)) {
+						/* update the Phi list */
+						add_phi(bl, pred, env);
 					}
 				} else if (! irn_visited_else_mark(pred)) {
 					/* not yet visited, ok */
@@ -482,7 +569,7 @@ void propagate_blocks(partition_t *part, environment_t *env) {
 			DB((dbg, LEVEL_3, "  propagate Input %+F\n", node->node));
 		}
 
-		/* Add bl to map[opcode(bl)]. */
+		/* Add bl to map[opcode(n)]. */
 		id          = opcode(node, env);
 		entry       = listmap_find(&map, id);
 		bl->next    = entry->list;
@@ -528,7 +615,8 @@ void propagate_blocks(partition_t *part, environment_t *env) {
  *
  * @param env    the environment
  */
-void propagate(environment_t *env) {
+static void propagate(environment_t *env)
+{
 	partition_t *part, *next;
 
 	list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
@@ -541,6 +629,92 @@ void propagate(environment_t *env) {
 	}
 }  /* propagate */
 
+/**
+ * Map a block to the phi[block->input] live-trough.
+ */
+static void *live_throughs(const block_t *bl, const ir_node *phi)
+{
+	ir_node *input = get_Phi_pred(phi, bl->meet_input);
+
+	/* If this input is inside our block, this
+	   is a live-out and not a live trough.
+	   Live-outs are tested inside propagate, so map all of
+	   them to the "general" value NULL */
+	if (get_nodes_block(input) == bl->block)
+		return NULL;
+	return input;
+}  /* live_throughs */
+
+/**
+ * Split partition by live-outs and live-troughs.
+ *
+ * @param part  the partition
+ * @param env   the environment
+ */
+static void propagate_blocks_live_troughs(partition_t *part, environment_t *env)
+{
+	const ir_node   *meet_block = part->meet_block;
+	block_t         *bl, *next;
+	listmap_t       map;
+	listmap_entry_t *iter;
+	const ir_node   *phi;
+
+	DB((dbg, LEVEL_2, " Propagate live-troughs on part%u\n", part->nr));
+
+	for (phi = get_Block_phis(meet_block); phi != NULL; phi = get_Phi_next(phi)) {
+		/* propagate on all Phis of the meet-block */
+
+		if (part->n_blocks < 2) {
+			/* zero or one block left, kill this partition */
+			list_del(&part->part_list);
+			DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
+			return;
+		}
+
+		/* Let map be an empty mapping from the range of live-troughs to (local) list of blocks. */
+		listmap_init(&map);
+		list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
+			opcode_key_t    *id;
+			listmap_entry_t *entry;
+
+			/* Add bl to map[live_trough(bl)]. */
+			id          = live_throughs(bl, phi);
+			entry       = listmap_find(&map, id);
+			bl->next    = entry->list;
+			entry->list = bl;
+		}
+
+		/* for all sets S except one in the range of map do */
+		for (iter = map.values; iter != NULL; iter = iter->next) {
+			block_t *S;
+
+			if (iter->next == NULL) {
+				/* this is the last entry, ignore */
+				break;
+			}
+			S = iter->list;
+
+			/* Add SPLIT( X, S ) to P. */
+			split(part, S, env);
+		}
+		listmap_term(&map);
+	}
+}  /* propagate_blocks_live_troughs */
+
+/**
+ * Propagate live-troughs on all partitions on the partition list.
+ *
+ * @param env    the environment
+ */
+static void propagate_live_troughs(environment_t *env)
+{
+	partition_t *part, *next;
+
+	list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
+		propagate_blocks_live_troughs(part, env);
+	}
+}  /* propagate_live_troughs */
+
 /**
  * Apply analysis results by replacing all blocks of a partition
  * by one representative.
@@ -552,14 +726,15 @@ void propagate(environment_t *env) {
  *
  * @param part  the partition to process
  */
-static void apply(ir_graph *irg, partition_t *part) {
+static void apply(ir_graph *irg, partition_t *part)
+{
 	block_t *repr = list_entry(part->blocks.next, block_t, block_list);
 	block_t *bl;
-	ir_node *block, *end, *end_block;
-	ir_node **ins;
+	ir_node *block, *end, *meet_block, *p, *next;
+	ir_node **ins, **phi_ins;
 	phi_t   *repr_phi, *phi;
 	pair_t  *repr_pair, *pair;
-	int     i, j, n, block_nr;
+	int     i, j, k, n, block_nr, n_phis;
 
 	list_del(&repr->block_list);
 
@@ -675,7 +850,7 @@ static void apply(ir_graph *irg, partition_t *part) {
 		if (is_op_forking(cfop)) {
 			/* a critical edge */
 			ir_node *block = new_r_Block(irg, 1, &ins[i]);
-			ir_node *jmp   = new_r_Jmp(irg, block);
+			ir_node *jmp   = new_r_Jmp(block);
 			ins[i] = jmp;
 		}
 	}
@@ -694,61 +869,137 @@ static void apply(ir_graph *irg, partition_t *part) {
 	for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
 		ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
 		ir_mode *mode  = get_irn_mode(input);
-		ir_node *phi   = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode);
+		ir_node *phi   = new_r_Phi(block, n, repr_pair->ins, mode);
 
 		set_irn_n(repr_pair->irn, repr_pair->index, phi);
 		DEL_ARR_F(repr_pair->ins);
+
+		/* might be optimized away */
+		if (is_Phi(phi))
+			add_Block_phi(block, phi);
 	}
 
-	/* ... finally rewire the end block */
-	end_block = get_irg_end_block(irg);
-	n         = get_Block_n_cfgpreds(end_block);
+	/* ... finally rewire the meet block and fix its Phi-nodes */
+	meet_block = part->meet_block;
+	n         = get_Block_n_cfgpreds(meet_block);
 
 	ins = NEW_ARR_F(ir_node *, n);
 
+	n_phis = 0;
+	for (p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p)) {
+		++n_phis;
+	}
+
+	phi_ins = NEW_ARR_F(ir_node *, n_phis * n);
+
 	for (i = j = 0; i < n; ++i) {
-		ir_node *out = get_Block_cfgpred(end_block, i);
+		ir_node *pred = get_Block_cfgpred(meet_block, i);
 
 		list_for_each_entry(block_t, bl, &part->blocks, block_list) {
-			node_t *root;
+			if (bl->cf_root->node == pred)
+				goto continue_outer;
+		}
+		ins[j] = pred;
 
-			for (root = bl->roots; root != NULL; root = root->next) {
-				if (root->node == out)
-					goto found;
-			}
+		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p), ++k) {
+			phi_ins[k * n + j] = get_Phi_pred(p, i);
 		}
-		ins[j++] = out;
-found:
+		++j;
+
+continue_outer:
 		;
 	}
 
-	set_irn_in(end_block, j, ins);
-	DEL_ARR_F(ins);
+	/* fix phis */
+	if (j == 1) {
+		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
+			next = get_Phi_next(p);
 
-	/* control flow changed */
-	set_irg_outs_inconsistent(irg);
-	set_irg_extblk_inconsistent(irg);
-	set_irg_doms_inconsistent(irg);
-	/* Hmm, only the root loop is inconsistent */
-	set_irg_loopinfo_inconsistent(irg);
+			exchange(p, phi_ins[k * n]);
+		}
+		/* all Phis killed */
+		set_Block_phis(meet_block, NULL);
+	} else {
+		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
+			next = get_Phi_next(p);
+
+			set_irn_in(p, j, &phi_ins[k * n]);
+		}
+	}
+	DEL_ARR_F(phi_ins);
 
-	/* Calls might be removed. */
-	set_trouts_inconsistent();
+	/* fix inputs of the meet block */
+	set_irn_in(meet_block, j, ins);
+	DEL_ARR_F(ins);
 }  /* apply */
 
+/**
+ * Create a partition for a the end block.
+ *
+ * @param end_block  the end block
+ * @param env        the environment
+ */
+static void partition_for_end_block(ir_node *end_block, environment_t *env)
+{
+	partition_t *part = create_partition(end_block, env);
+	ir_node     *end;
+	int         i;
+
+	/* collect normal blocks */
+	for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
+		ir_node *pred = get_Block_cfgpred(end_block, i);
+		ir_node *block;
+		block_t *bl;
+		node_t  *node;
+
+		mark_irn_visited(pred);
+
+		block = get_nodes_block(pred);
+		bl    = create_block(block, i, part, env);
+		node  = create_node(pred, bl, env);
+
+		bl->cf_root = node;
+	}
+
+	/* collect all no-return blocks */
+	end = get_irg_end(get_irn_irg(end_block));
+	for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
+		ir_node *ka    = get_End_keepalive(end, i);
+		ir_node *block;
+		block_t *bl;
+		node_t  *node;
+
+		if (! is_Call(ka))
+			continue;
+		mark_irn_visited(ka);
+
+		/* found one */
+		block = get_nodes_block(ka);
+		bl    = create_block(block, -1, part, env);
+		node  = create_node(ka, bl, env);
+
+		bl->cf_root = node;
+	}
+
+	dump_partition("Created", part);
+}  /* partition_for_end_block */
+
+#ifdef GENERAL_SHAPE
 /**
  * Create a partition for a given meet block.
  *
- * @param block  the meet block
- * @param env    the environment
+ * @param block    the meet block
+ * @param preds    array of candidate predecessors
+ * @param n_preds  number of elements in preds
+ * @param env      the environment
  */
-static void partition_for_block(ir_node *block, environment_t *env) {
+static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env)
+{
 	partition_t *part = create_partition(block, env);
 	int         i;
 
-	/* collect normal blocks */
-	for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
-		ir_node *pred = get_Block_cfgpred(block, i);
+	for (i = n_preds - 1; i >= 0; --i) {
+		ir_node *pred = preds[i].pred;
 		ir_node *block;
 		block_t *bl;
 		node_t  *node;
@@ -756,49 +1007,201 @@ static void partition_for_block(ir_node *block, environment_t *env) {
 		mark_irn_visited(pred);
 
 		block = get_nodes_block(pred);
-		bl    = create_block(block, part, env);
+		bl    = create_block(block, preds[i].index, part, env);
 		node  = create_node(pred, bl, env);
 
-		node->next = bl->roots;
-		bl->roots  = node;
+		bl->cf_root = node;
 	}
 
-	if (block == get_irg_end_block(current_ir_graph)) {
-		/* collect all no-return blocks */
-		ir_node *end = get_irg_end(current_ir_graph);
-		for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
-			ir_node *ka    = get_End_keepalive(end, i);
-			ir_node *block;
-			block_t *bl;
-			node_t  *node;
-
-			if (! is_Call(ka))
-				continue;
-			mark_irn_visited(ka);
-
-			/* found one */
-			block = get_nodes_block(ka);
-			bl    = create_block(block, part, env);
-			node  = create_node(ka, bl, env);
-
-			node->next = bl->roots;
-			bl->roots  = node;
+	dump_partition("Created", part);
+}  /* 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        = 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 */
 
-	dump_partition("Created", part);
-}  /* partition for block */
+/**
+ * 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 = 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 = a;
+	const ir_node *const *pb = b;
+	const ir_node  *irn_a  = *pa;
+	const ir_node  *irn_b  = *pb;
+	ir_opcode      code_a  = get_irn_opcode(irn_a);
+	ir_opcode      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) {
+		int 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 melt_end_blocks(ir_graph *irg) {
-	ir_graph      *rem;
-	ir_node       *end_block;
+int shape_blocks(ir_graph *irg)
+{
 	environment_t env;
 	partition_t   *part;
-	int           res;
-
-	rem = current_ir_graph;
-	current_ir_graph = irg;
+	block_t       *bl;
+	int           res, n;
 
 	/* register a debug mask */
 	FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
@@ -809,29 +1212,79 @@ int melt_end_blocks(ir_graph *irg) {
 	/* works better, when returns are placed at the end of the blocks */
 	normalize_n_returns(irg);
 
-	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
-	inc_irg_visited(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);
 
-	end_block = get_irg_end_block(irg);
-	partition_for_block(end_block, &env);
+	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);
 	while (! list_empty(&env.partitions))
 		propagate(&env);
 
 	res = !list_empty(&env.ready);
+	//if (res) dump_ir_block_graph(irg, "-before");
+
 
 	list_for_each_entry(partition_t, part, &env.ready, part_list) {
 		dump_partition("Ready Partition", part);
 		apply(irg, part);
 	}
-	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
+	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+
+	if (res) {
+		/* control flow changed */
+		set_irg_outs_inconsistent(irg);
+		set_irg_extblk_inconsistent(irg);
+		set_irg_doms_inconsistent(irg);
+		set_irg_loopinfo_inconsistent(irg);
+
+		/* Calls might be removed. */
+		set_trouts_inconsistent();
+	}
+
+	for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) {
+		DEL_ARR_F(bl->roots);
+	}
+
+	DEL_ARR_F(env.live_outs);
 	del_set(env.opcode2id_map);
 	obstack_free(&env.obst, NULL);
-	current_ir_graph = rem;
 
 	return res;
-}  /* melt_end_blocks */
+}  /* shape_blocks */
+
+ir_graph_pass_t *shape_blocks_pass(const char *name)
+{
+	return def_graph_pass_ret(name ? name : "shape_blocks", shape_blocks);
+}  /* shape_blocks_pass */