X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcombo.c;h=1701b58fad16e2bcc611568d7ab5d0f0e89aa008;hb=6b458d6a9cd084958049e18008160b7862f9ce62;hp=4d80dcf51619a171da332f3d7ffa8e19cca599c7;hpb=605982d0319ef990db956a787fe1e727f8076c3f;p=libfirm

diff --git a/ir/opt/combo.c b/ir/opt/combo.c
index 4d80dcf51..1701b58fa 100644
--- a/ir/opt/combo.c
+++ b/ir/opt/combo.c
@@ -23,13 +23,18 @@
  * @author  Michael Beck
  * @version $Id$
  *
+ * This is a slightly enhanced version of Cliff Clicks combo algorithm
+ * - support for commutative nodes is added, Add(a,b) and Add(b,a) ARE congruent
+ * - supports all Firm direct (by a data edge) identities except Mux
+ *   (Mux can be a 2-input or 1-input identity, only 2-input is implemented yet)
+ * - supports Confirm nodes (handle them like Copies but do NOT remove them)
+ * - support for global congruences is implemented but not tested yet
+ *
  * Note further that we use the terminology from Click's work here, which is different
  * in some cases from Firm terminology.  Especially, Click's type is a
  * Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
  */
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
 
 #include <assert.h>
 
@@ -50,6 +55,7 @@
 #include "irgmod.h"
 #include "iropt_dbg.h"
 #include "debug.h"
+#include "array_t.h"
 #include "error.h"
 
 #include "tv_t.h"
@@ -167,6 +173,7 @@ typedef struct environment_t {
 	int             lambda_input;   /**< Captured argument for lambda_partition(). */
 	char            nonstd_cond;    /**< Set, if a Condb note has a non-Cmp predecessor. */
 	char            modified;       /**< Set, if the graph was modified. */
+	char            commutative;    /**< Set, if commutation nodes should be handled specially. */
 #ifdef DEBUG_libfirm
 	partition_t     *dbg_list;      /**< List of all partitions. */
 #endif
@@ -186,6 +193,9 @@ typedef void *(*what_func)(const node_t *node, environment_t *env);
 /** The debug module handle. */
 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 
+/** The what reason. */
+DEBUG_ONLY(static const char *what_reason;)
+
 /** Next partition number. */
 DEBUG_ONLY(static unsigned part_nr = 0);
 
@@ -218,6 +228,54 @@ static void check_partition(const partition_t *T) {
 	}
 }  /* check_partition */
 
+/**
+ * check that all leader nodes in the partition have the same opcode.
+ */
+static void check_opcode(const partition_t *Z) {
+	node_t       *node;
+	opcode_key_t key;
+	int          first = 1;
+
+	list_for_each_entry(node_t, node, &Z->Leader, node_list) {
+		ir_node *irn = node->node;
+
+		if (first) {
+			key.code   = get_irn_opcode(irn);
+			key.mode   = get_irn_mode(irn);
+			key.arity  = get_irn_arity(irn);
+			key.u.proj = 0;
+			key.u.ent  = NULL;
+
+			switch (get_irn_opcode(irn)) {
+			case iro_Proj:
+				key.u.proj = get_Proj_proj(irn);
+				break;
+			case iro_Sel:
+				key.u.ent = get_Sel_entity(irn);
+				break;
+			default:
+				break;
+			}
+			first = 0;
+		} else {
+			assert(key.code   == get_irn_opcode(irn));
+			assert(key.mode   == get_irn_mode(irn));
+			assert(key.arity  == get_irn_arity(irn));
+
+			switch (get_irn_opcode(irn)) {
+			case iro_Proj:
+				assert(key.u.proj == get_Proj_proj(irn));
+				break;
+			case iro_Sel:
+				assert(key.u.ent == get_Sel_entity(irn));
+				break;
+			default:
+				break;
+			}
+		}
+	}
+}  /* check_opcode */
+
 static void check_all_partitions(environment_t *env) {
 	partition_t *P;
 	node_t      *node;
@@ -225,6 +283,8 @@ static void check_all_partitions(environment_t *env) {
 #ifdef DEBUG_libfirm
 	for (P = env->dbg_list; P != NULL; P = P->dbg_next) {
 		check_partition(P);
+		if (! P->type_is_T_or_C)
+			check_opcode(P);
 		list_for_each_entry(node_t, node, &P->Follower, node_list) {
 			node_t *leader = identity(node);
 
@@ -261,7 +321,7 @@ static void check_list(const node_t *list, const partition_t *Z) {
 #endif /* CHECK_PARTITIONS */
 
 #ifdef DEBUG_libfirm
-static INLINE lattice_elem_t get_partition_type(const partition_t *X);
+static inline lattice_elem_t get_partition_type(const partition_t *X);
 
 /**
  * Dump partition to output.
@@ -306,21 +366,21 @@ static void do_dump_list(const char *msg, const node_t *node, int ofs) {
 	DB((dbg, LEVEL_3, "\n}\n"));
 
 #undef GET_LINK
-}
+}  /* do_dump_list */
 
 /**
  * Dumps a race list.
  */
 static void dump_race_list(const char *msg, const node_t *list) {
 	do_dump_list(msg, list, offsetof(node_t, race_next));
-}
+}  /* dump_race_list */
 
 /**
  * Dumps a local list.
  */
 static void dump_list(const char *msg, const node_t *list) {
 	do_dump_list(msg, list, offsetof(node_t, next));
-}
+}  /* dump_list */
 
 /**
  * Dump all partitions.
@@ -331,13 +391,26 @@ static void dump_all_partitions(const environment_t *env) {
 	DB((dbg, LEVEL_2, "All partitions\n===============\n"));
 	for (P = env->dbg_list; P != NULL; P = P->dbg_next)
 		dump_partition("", P);
-}
+}  /* dump_all_partitions */
+
+/**
+ * Sump a split list.
+ */
+static void dump_split_list(const partition_t *list) {
+	const partition_t *p;
+
+	DB((dbg, LEVEL_2, "Split by %s produced = {\n", what_reason));
+	for (p = list; p != NULL; p = p->split_next)
+		DB((dbg, LEVEL_2, "part%u, ", p->nr));
+	DB((dbg, LEVEL_2, "\n}\n"));
+}  /* dump_split_list */
 
 #else
 #define dump_partition(msg, part)
 #define dump_race_list(msg, list)
 #define dump_list(msg, list)
 #define dump_all_partitions(env)
+#define dump_split_list(list)
 #endif
 
 #if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
@@ -361,7 +434,7 @@ static void verify_type(const lattice_elem_t old_type, const lattice_elem_t new_
 		return;
 	}
 	panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type);
-}
+}  /* verify_type */
 #else
 #define verify_type(old_type, new_type)
 #endif
@@ -402,7 +475,7 @@ static void listmap_term(listmap_t *map) {
  * @param map  the listmap
  * @param id   the id to search for
  *
- * @return the asociated listmap entry for the given id
+ * @return the associated listmap entry for the given id
  */
 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 	listmap_entry_t key, *entry;
@@ -428,7 +501,7 @@ 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);
+	return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
 }  /* opcode_hash */
 
 /**
@@ -475,7 +548,7 @@ static void sort_irn_outs(node_t *node) {
  *
  * @return the associated type of this node
  */
-static INLINE lattice_elem_t get_node_type(const ir_node *irn) {
+static inline lattice_elem_t get_node_type(const ir_node *irn) {
 	return get_irn_node(irn)->type;
 }  /* get_node_type */
 
@@ -486,7 +559,7 @@ static INLINE lattice_elem_t get_node_type(const ir_node *irn) {
  *
  * @return the associated type of this node
  */
-static INLINE tarval *get_node_tarval(const ir_node *irn) {
+static inline tarval *get_node_tarval(const ir_node *irn) {
 	lattice_elem_t type = get_node_type(irn);
 
 	if (is_tarval(type.tv))
@@ -497,8 +570,9 @@ static INLINE tarval *get_node_tarval(const ir_node *irn) {
 /**
  * Add a partition to the worklist.
  */
-static INLINE void add_to_worklist(partition_t *X, environment_t *env) {
+static inline void add_to_worklist(partition_t *X, environment_t *env) {
 	assert(X->on_worklist == 0);
+	DB((dbg, LEVEL_2, "Adding part%d to worklist\n", X->nr));
 	X->wl_next     = env->worklist;
 	X->on_worklist = 1;
 	env->worklist  = X;
@@ -511,7 +585,7 @@ static INLINE void add_to_worklist(partition_t *X, environment_t *env) {
  *
  * @return a newly allocated partition
  */
-static INLINE partition_t *new_partition(environment_t *env) {
+static inline partition_t *new_partition(environment_t *env) {
 	partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 
 	INIT_LIST_HEAD(&part->Leader);
@@ -541,7 +615,7 @@ static INLINE partition_t *new_partition(environment_t *env) {
 /**
  * Get the first node from a partition.
  */
-static INLINE node_t *get_first_node(const partition_t *X) {
+static inline node_t *get_first_node(const partition_t *X) {
 	return list_entry(X->Leader.next, node_t, node_list);
 }  /* get_first_node */
 
@@ -553,7 +627,7 @@ static INLINE node_t *get_first_node(const partition_t *X) {
  *
  * @return the type of the first element of the partition
  */
-static INLINE lattice_elem_t get_partition_type(const partition_t *X) {
+static inline lattice_elem_t get_partition_type(const partition_t *X) {
 	const node_t *first = get_first_node(X);
 	return first->type;
 }  /* get_partition_type */
@@ -627,7 +701,6 @@ static void create_initial_partitions(ir_node *irn, void *ctx) {
 		/* check if all Cond's have a Cmp predecessor. */
 		if (get_irn_mode(irn) == mode_b && !is_Cmp(skip_Proj(get_Cond_selector(irn))))
 			env->nonstd_cond = 1;
-
 	}
 }  /* create_initial_partitions */
 
@@ -638,7 +711,7 @@ static void create_initial_partitions(ir_node *irn, void *ctx) {
  * @param y    a node
  * @param env  the environment
  */
-static INLINE void add_to_touched(node_t *y, environment_t *env) {
+static inline void add_to_touched(node_t *y, environment_t *env) {
 	if (y->on_touched == 0) {
 		partition_t *part = y->part;
 
@@ -907,7 +980,7 @@ static int is_real_follower(const ir_node *irn, int input) {
 		break;
 	}
 	return 1;
-}
+}  /* is_real_follower */
 
 /**
  * Do one step in the race.
@@ -1008,9 +1081,9 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) {
 	partition_t *X = *pX;
 	partition_t *X_prime;
 	list_head   tmp;
-	step_env    env1, env2, *winner;
+	step_env    senv[2];
 	node_t      *g, *h, *node, *t;
-	int         max_input, transitions;
+	int         max_input, transitions, winner, shf;
 	unsigned    n;
 	DEBUG_ONLY(static int run = 0;)
 
@@ -1047,44 +1120,60 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) {
 	/* restore X.Leader */
 	list_splice(&tmp, &X->Leader);
 
-	env1.initial       = g;
-	env1.unwalked      = NULL;
-	env1.walked        = NULL;
-	env1.index         = 0;
-	env1.side          = 1;
+	senv[0].initial   = g;
+	senv[0].unwalked  = NULL;
+	senv[0].walked    = NULL;
+	senv[0].index     = 0;
+	senv[0].side      = 1;
 
-	env2.initial       = h;
-	env2.unwalked      = NULL;
-	env2.walked        = NULL;
-	env2.index         = 0;
-	env2.side          = 2;
+	senv[1].initial   = h;
+	senv[1].unwalked  = NULL;
+	senv[1].walked    = NULL;
+	senv[1].index     = 0;
+	senv[1].side      = 2;
 
+	/*
+	 * Some informations on the race that are not stated clearly in Click's
+	 * thesis.
+	 * 1) A follower stays on the side that reach him first.
+	 * 2) If the other side reches a follower, if will be converted to
+	 *    a leader. /This must be done after the race is over, else the
+	 *    edges we are iterating on are renumbered./
+	 * 3) /New leader might end up on both sides./
+	 * 4) /If one side ends up with new Leaders, we must ensure that
+	 *    they can split out by opcode, hence we have to put _every_
+	 *    partition with new Leader nodes on the cprop list, as
+	 *    opcode splitting is done by split_by() at the end of
+	 *    constant propagation./
+	 */
 	for (;;) {
-		if (step(&env1)) {
-			winner = &env1;
+		if (step(&senv[0])) {
+			winner = 0;
 			break;
 		}
-		if (step(&env2)) {
-			winner = &env2;
+		if (step(&senv[1])) {
+			winner = 1;
 			break;
 		}
 	}
-	assert(winner->initial == NULL);
-	assert(winner->unwalked == NULL);
+	assert(senv[winner].initial == NULL);
+	assert(senv[winner].unwalked == NULL);
 
 	/* clear flags from walked/unwalked */
-	transitions  = clear_flags(env1.unwalked);
-	transitions |= clear_flags(env1.walked);
-	transitions |= clear_flags(env2.unwalked);
-	transitions |= clear_flags(env2.walked);
+	shf = winner;
+	transitions  = clear_flags(senv[0].unwalked) << shf;
+	transitions |= clear_flags(senv[0].walked)   << shf;
+	shf ^= 1;
+	transitions |= clear_flags(senv[1].unwalked) << shf;
+	transitions |= clear_flags(senv[1].walked)   << shf;
 
-	dump_race_list("winner ", winner->walked);
+	dump_race_list("winner ", senv[winner].walked);
 
 	/* Move walked_{winner} to a new partition, X'. */
 	X_prime   = new_partition(env);
 	max_input = 0;
 	n         = 0;
-	for (node = winner->walked; node != NULL; node = node->race_next) {
+	for (node = senv[winner].walked; node != NULL; node = node->race_next) {
 		list_del(&node->node_list);
 		node->part = X_prime;
 		if (node->is_follower) {
@@ -1110,7 +1199,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) {
 	list_for_each_entry_safe(node_t, node, t, &X_prime->Follower, node_list) {
 		if (identity(node) == node) {
 			follower_to_leader(node);
-			transitions = 1;
+			transitions |= 1;
 		}
 	}
 
@@ -1124,20 +1213,28 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) {
 	 * If there where follower to leader transitions, ensure that the nodes
 	 * can be split out if necessary.
 	 */
-	if (transitions) {
-		/* place partitions on the cprop list */
-                if (X_prime->on_cprop == 0) {
+	if (transitions & 1) {
+		/* place winner partition on the cprop list */
+		if (X_prime->on_cprop == 0) {
 			X_prime->cprop_next = env->cprop;
 			env->cprop          = X_prime;
 			X_prime->on_cprop   = 1;
 		}
 	}
+	if (transitions & 2) {
+		/* place other partition on the cprop list */
+		if (X->on_cprop == 0) {
+			X->cprop_next = env->cprop;
+			env->cprop    = X;
+			X->on_cprop   = 1;
+		}
+	}
 
 	dump_partition("Now ", X);
 	dump_partition("Created new ", X_prime);
 
 	/* we have to ensure that the partition containing g is returned */
-	if (winner == &env2) {
+	if (winner != 0) {
 		*pX = X_prime;
 		return X;
 	}
@@ -1191,7 +1288,7 @@ static int type_is_neither_top_nor_const(const lattice_elem_t type) {
 		return 0;
 	}
 	return 1;
-}
+}  /* type_is_neither_top_nor_const */
 
 /**
  * Collect nodes to the touched list.
@@ -1226,6 +1323,11 @@ static void collect_touched(list_head *list, int idx, environment_t *env) {
 
 			succ = edge->use;
 
+			/* only non-commutative nodes */
+			if (env->commutative &&
+			    (idx == 0 || idx == 1) && is_op_commutative(get_irn_op(succ)))
+				continue;
+
 			/* ignore the "control input" for non-pinned nodes
 			if we are running in GCSE mode */
 			if (idx < end_idx && get_irn_pinned(succ) != op_pin_state_pinned)
@@ -1240,7 +1342,7 @@ static void collect_touched(list_head *list, int idx, environment_t *env) {
 
 			if (is_constant_type(y->type)) {
 				ir_opcode code = get_irn_opcode(succ);
-				if (code == iro_Sub || code == iro_Eor || code == iro_Cmp)
+				if (code == iro_Sub || code == iro_Cmp)
 					add_to_cprop(y, env);
 			}
 
@@ -1254,6 +1356,57 @@ static void collect_touched(list_head *list, int idx, environment_t *env) {
 	}
 }  /* collect_touched */
 
+/**
+ * Collect commutative nodes to the touched list.
+ *
+ * @param list  the list which contains the nodes that must be evaluated
+ * @param env   the environment
+ */
+static void collect_commutative_touched(list_head *list, environment_t *env) {
+	node_t  *x, *y;
+
+	list_for_each_entry(node_t, x, list, node_list) {
+		int num_edges;
+
+		num_edges = get_irn_n_outs(x->node);
+
+		x->next_edge = x->n_followers + 1;
+
+		/* for all edges in x.L.def_use_{idx} */
+		while (x->next_edge <= num_edges) {
+			const ir_def_use_edge *edge = &x->node->out[x->next_edge];
+			ir_node               *succ;
+
+			/* check if we have necessary edges */
+			if (edge->pos > 1)
+				break;
+
+			++x->next_edge;
+			if (edge->pos < 0)
+				continue;
+
+			succ = edge->use;
+
+			/* only commutative nodes */
+			if (!is_op_commutative(get_irn_op(succ)))
+				continue;
+
+			y = get_irn_node(succ);
+			if (is_constant_type(y->type)) {
+				ir_opcode code = get_irn_opcode(succ);
+				if (code == iro_Eor)
+					add_to_cprop(y, env);
+			}
+
+			/* Partitions of constants should not be split simply because their Nodes have unequal
+			   functions or incongruent inputs. */
+			if (type_is_neither_top_nor_const(y->type)) {
+				add_to_touched(y, env);
+			}
+		}
+	}
+}  /* collect_commutative_touched */
+
 /**
  * Split the partitions if caused by the first entry on the worklist.
  *
@@ -1270,6 +1423,44 @@ static void cause_splits(environment_t *env) {
 
 	dump_partition("Cause_split: ", X);
 
+	if (env->commutative) {
+		/* handle commutative nodes first */
+
+		/* empty the touched set: already done, just clear the list */
+		env->touched = NULL;
+
+		collect_commutative_touched(&X->Leader, env);
+		collect_commutative_touched(&X->Follower, env);
+
+		for (Z = env->touched; Z != NULL; Z = N) {
+			node_t   *e;
+			node_t   *touched  = Z->touched;
+			unsigned n_touched = Z->n_touched;
+
+			assert(Z->touched != NULL);
+
+			/* beware, split might change Z */
+			N = Z->touched_next;
+
+			/* remove it from the touched set */
+			Z->on_touched = 0;
+
+			/* Empty local Z.touched. */
+			for (e = touched; e != NULL; e = e->next) {
+				assert(e->is_follower == 0);
+				e->on_touched = 0;
+			}
+			Z->touched   = NULL;
+			Z->n_touched = 0;
+
+			if (0 < n_touched && n_touched < Z->n_leader) {
+				DB((dbg, LEVEL_2, "Split part%d by touched\n", Z->nr));
+				split(&Z, touched, env);
+			} else
+				assert(n_touched <= Z->n_leader);
+		}
+	}
+
 	/* combine temporary leader and follower list */
 	for (idx = -1; idx <= X->max_user_inputs; ++idx) {
 		/* empty the touched set: already done, just clear the list */
@@ -1352,7 +1543,7 @@ static partition_t *split_by_what(partition_t *X, what_func What,
 		S = iter->list;
 
 		/* Add SPLIT( X, S ) to P. */
-		DB((dbg, LEVEL_2, "Split part%d by what\n", X->nr));
+		DB((dbg, LEVEL_2, "Split part%d by WHAT = %s\n", X->nr, what_reason));
 		R = split(&X, S, env);
 		R->split_next = *P;
 		*P            = R;
@@ -1405,7 +1596,13 @@ static void *lambda_partition(const node_t *node, environment_t *env) {
 	int     i = env->lambda_input;
 
 	if (i >= get_irn_arity(node->node)) {
-		/* we are outside the allowed range */
+		/*
+		 * We are outside the allowed range: This can happen even
+		 * if we have split by opcode first: doing so might move Followers
+		 * to Leaders and those will have a different opcode!
+		 * Note that in this case the partition is on the cprop list and will be
+		 * split again.
+		 */
 		return NULL;
 	}
 
@@ -1420,6 +1617,58 @@ static void *lambda_partition(const node_t *node, environment_t *env) {
 	return p->part;
 }  /* lambda_partition */
 
+/** lambda n.(n[i].partition) for commutative nodes */
+static void *lambda_commutative_partition(const node_t *node, environment_t *env) {
+	ir_node     *irn     = node->node;
+	ir_node     *skipped = skip_Proj(irn);
+	ir_node     *pred, *left, *right;
+	node_t      *p;
+	partition_t *pl, *pr;
+	int         i = env->lambda_input;
+
+	if (i >= get_irn_arity(node->node)) {
+		/*
+		 * We are outside the allowed range: This can happen even
+		 * if we have split by opcode first: doing so might move Followers
+		 * to Leaders and those will have a different opcode!
+		 * Note that in this case the partition is on the cprop list and will be
+		 * split again.
+		 */
+		return NULL;
+	}
+
+	/* ignore the "control input" for non-pinned nodes
+	   if we are running in GCSE mode */
+	if (i < env->end_idx && get_irn_pinned(skipped) != op_pin_state_pinned)
+		return NULL;
+
+	if (i == -1) {
+		pred = get_irn_n(skipped, i);
+		p    = get_irn_node(pred);
+		return p->part;
+	}
+
+	if (is_op_commutative(get_irn_op(irn))) {
+		/* normalize partition order by returning the "smaller" on input 0,
+		   the "bigger" on input 1. */
+		left  = get_binop_left(irn);
+		pl    = get_irn_node(left)->part;
+		right = get_binop_right(irn);
+		pr    = get_irn_node(right)->part;
+
+		if (i == 0)
+			return pl < pr ? pl : pr;
+		else
+		return pl > pr ? pl : pr;
+	} else {
+		/* a not split out Follower */
+		pred = get_irn_n(irn, i);
+		p    = get_irn_node(pred);
+
+		return p->part;
+	}
+}  /* lambda_commutative_partition */
+
 /**
  * Returns true if a type is a constant.
  */
@@ -1449,8 +1698,9 @@ static void split_by(partition_t *X, environment_t *env) {
 		return;
 	}
 
-	DB((dbg, LEVEL_2, "WHAT = lambda n.(n.type) on part%d\n", X->nr));
+	DEBUG_ONLY(what_reason = "lambda n.(n.type)";)
 	P = split_by_what(X, lambda_type, &P, env);
+	dump_split_list(P);
 
 	/* adjust the type tags, we have split partitions by type */
 	for (I = P; I != NULL; I = I->split_next) {
@@ -1467,8 +1717,9 @@ static void split_by(partition_t *X, environment_t *env) {
 			if (! Y->type_is_T_or_C) {
 				partition_t *Q = NULL;
 
-				DB((dbg, LEVEL_2, "WHAT = lambda n.(n.opcode) on part%d\n", Y->nr));
+				DEBUG_ONLY(what_reason = "lambda n.(n.opcode)";)
 				Q = split_by_what(Y, lambda_opcode, &Q, env);
+				dump_split_list(Q);
 
 				do {
 					partition_t *Z = Q;
@@ -1478,6 +1729,11 @@ static void split_by(partition_t *X, environment_t *env) {
 						const node_t *first = get_first_node(Z);
 						int          arity  = get_irn_arity(first->node);
 						partition_t  *R, *S;
+						what_func    what = lambda_partition;
+						DEBUG_ONLY(char buf[64];)
+
+						if (env->commutative && is_op_commutative(get_irn_op(first->node)))
+							what = lambda_commutative_partition;
 
 						/*
 						 * BEWARE: during splitting by input 2 for instance we might
@@ -1494,8 +1750,10 @@ static void split_by(partition_t *X, environment_t *env) {
 								R = R->split_next;
 								if (Z_prime->n_leader > 1) {
 									env->lambda_input = input;
-									DB((dbg, LEVEL_2, "WHAT = lambda n.(n[%d].partition) on part%d\n", input, Z_prime->nr));
-									S = split_by_what(Z_prime, lambda_partition, &S, env);
+									DEBUG_ONLY(snprintf(buf, sizeof(buf), "lambda n.(n[%d].partition)", input);)
+									DEBUG_ONLY(what_reason = buf;)
+									S = split_by_what(Z_prime, what, &S, env);
+									dump_split_list(S);
 								} else {
 									Z_prime->split_next = S;
 									S                   = Z_prime;
@@ -1767,7 +2025,8 @@ static void compute_Sub(node_t *node) {
 		tv = get_mode_null(mode);
 
 		/* if the node was ONCE evaluated by all constants, but now
-		   this breakes AND we cat by partition a different result, switch to bottom.
+		   this breaks AND we get from the argument partitions a different
+		   result, switch to bottom.
 		   This happens because initially all nodes are in the same partition ... */
 		if (node->by_all_const && node->type.tv != tv)
 			tv = tarval_bottom;
@@ -1808,7 +2067,8 @@ static void compute_Eor(node_t *node) {
 		tv = get_mode_null(mode);
 
 		/* if the node was ONCE evaluated by all constants, but now
-		   this breakes AND we cat by partition a different result, switch to bottom.
+		   this breaks AND we get from the argument partitions a different
+		   result, switch to bottom.
 		   This happens because initially all nodes are in the same partition ... */
 		if (node->by_all_const && node->type.tv != tv)
 			tv = tarval_bottom;
@@ -1889,7 +2149,8 @@ not_equal:
 #endif
 
 		/* if the node was ONCE evaluated by all constants, but now
-		   this breakes AND we cat by partition a different result, switch to bottom.
+		   this breaks AND we get from the argument partitions a different
+		   result, switch to bottom.
 		   This happens because initially all nodes are in the same partition ... */
 		if (node->by_all_const && node->type.tv != tv)
 			tv = tarval_bottom;
@@ -2049,18 +2310,18 @@ static void compute_Confirm(node_t *node) {
  * @param node  the node
  */
 static void compute_Max(node_t *node) {
-	ir_node        *op   = node->node;
-	node_t         *l    = get_irn_node(get_binop_left(op));
-	node_t         *r    = get_irn_node(get_binop_right(op));
-	lattice_elem_t a     = l->type;
-	lattice_elem_t b     = r->type;
+	ir_node        *op = node->node;
+	node_t         *l  = get_irn_node(get_binop_left(op));
+	node_t         *r  = get_irn_node(get_binop_right(op));
+	lattice_elem_t a   = l->type;
+	lattice_elem_t b   = r->type;
 
 	if (a.tv == tarval_top || b.tv == tarval_top) {
 		node->type.tv = tarval_top;
 	} else if (is_con(a) && is_con(b)) {
 		/* both nodes are constants, we can probably do something */
 		if (a.tv == b.tv) {
-			/* this case handles symconsts as well */
+			/* this case handles SymConsts as well */
 			node->type = a;
 		} else {
 			ir_mode *mode   = get_irn_mode(op);
@@ -2093,18 +2354,18 @@ static void compute_Max(node_t *node) {
  * @param node  the node
  */
 static void compute_Min(node_t *node) {
-	ir_node        *op   = node->node;
-	node_t         *l    = get_irn_node(get_binop_left(op));
-	node_t         *r    = get_irn_node(get_binop_right(op));
-	lattice_elem_t a     = l->type;
-	lattice_elem_t b     = r->type;
+	ir_node        *op = node->node;
+	node_t         *l  = get_irn_node(get_binop_left(op));
+	node_t         *r  = get_irn_node(get_binop_right(op));
+	lattice_elem_t a   = l->type;
+	lattice_elem_t b   = r->type;
 
 	if (a.tv == tarval_top || b.tv == tarval_top) {
 		node->type.tv = tarval_top;
 	} else if (is_con(a) && is_con(b)) {
 		/* both nodes are constants, we can probably do something */
 		if (a.tv == b.tv) {
-			/* this case handles symconsts as well */
+			/* this case handles SymConsts as well */
 			node->type = a;
 		} else {
 			ir_mode *mode   = get_irn_mode(op);
@@ -2272,7 +2533,7 @@ static node_t *identity_Sub(node_t *node) {
 	if (b->type.tv == get_mode_null(mode))
 		return get_irn_node(get_Sub_left(sub));
 	return node;
-}  /* identity_Mul */
+}  /* identity_Sub */
 
 /**
  * Calculates the Identity for And nodes.
@@ -2437,9 +2698,8 @@ static void segregate_def_use_chain_1(const ir_node *follower, node_t *leader) {
 }  /* segregate_def_use_chain_1 */
 
 /**
- * Node follower is a (new) follower of leader, segregate Leader
- * out edges. If follower is a n-congruent Input identity, all follower
- * inputs congruent to follower are also leader.
+ * Node follower is a (new) follower segregate its Leader
+ * out edges.
  *
  * @param follower  the follower IR node
  */
@@ -2551,9 +2811,6 @@ static void propagate(environment_t *env) {
 		if (old_type_was_T_or_C) {
 			node_t *y, *tmp;
 
-			if (Y->on_worklist == 0)
-				add_to_worklist(Y, env);
-
 			/* check if some nodes will make the leader -> follower transition */
 			list_for_each_entry_safe(node_t, y, tmp, &Y->Leader, node_list) {
 				if (y->type.tv != tarval_top && ! is_con(y->type)) {
@@ -2611,7 +2868,7 @@ static int can_exchange(ir_node *pred) {
 		int i, k;
 
 		/* if the predecessor block has more than one
-		reachable outputs we cannot remove the block */
+		   reachable outputs we cannot remove the block */
 		k = 0;
 		for (i = get_irn_n_outs(pred) - 1; i >= 0; --i) {
 			ir_node *proj = get_irn_out(pred, i);
@@ -2786,6 +3043,27 @@ static void apply_cf(ir_node *block, void *ctx) {
 		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 fre to place in
+		 * either in the block of the leader OR in irn's block.
+		 * Propably 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);
+
+		leader = new_rd_Conv(dbg, current_ir_graph, block, leader, mode);
+	}
+	exchange(irn, leader);
 }
 
 /**
@@ -2860,19 +3138,19 @@ static void apply_result(ir_node *irn, void *ctx) {
 					node->node = c;
 					DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
 					DBG_OPT_COMBO(irn, c, FS_OPT_COMBO_CONST);
-					exchange(irn, c);
+					exchange_leader(irn, c);
 					env->modified = 1;
 				}
 			} else if (is_entity(node->type.sym.entity_p)) {
 				if (! is_SymConst(irn)) {
-					/* can be replaced by a Symconst */
+					/* can be replaced by a SymConst */
 					ir_node *symc = new_r_SymConst(current_ir_graph, block->node, get_irn_mode(irn), node->type.sym, symconst_addr_ent);
 					set_irn_node(symc, node);
 					node->node = symc;
 
 					DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, symc));
 					DBG_OPT_COMBO(irn, symc, FS_OPT_COMBO_CONST);
-					exchange(irn, symc);
+					exchange_leader(irn, symc);
 					env->modified = 1;
 				}
 			} else if (is_Confirm(irn)) {
@@ -2886,7 +3164,7 @@ static void apply_result(ir_node *irn, void *ctx) {
 						DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_FOLLOWER);
 					else
 						DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_CONGRUENT);
-					exchange(irn, leader);
+					exchange_leader(irn, leader);
 					env->modified = 1;
 				}
 			}
@@ -2912,7 +3190,7 @@ static void apply_end(ir_node *end, environment_t *env) {
 		if (! is_Block(ka))
 			node = get_irn_node(get_nodes_block(ka));
 
-		if (node->type.tv != tarval_unreachable)
+		if (node->type.tv != tarval_unreachable && !is_Bad(ka))
 			in[j++] = ka;
 	}
 	if (j != n) {
@@ -2977,7 +3255,6 @@ void combo(ir_graph *irg) {
 
 	/* register a debug mask */
 	FIRM_DBG_REGISTER(dbg, "firm.opt.combo");
-	//firm_dbg_set_mask(dbg, SET_LEVEL_3);
 
 	DB((dbg, LEVEL_1, "Doing COMBO for %+F\n", irg));
 
@@ -2994,12 +3271,12 @@ void combo(ir_graph *irg) {
 	env.end_idx        = get_opt_global_cse() ? 0 : -1;
 	env.lambda_input   = 0;
 	env.nonstd_cond    = 0;
+	env.commutative    = 1;
 	env.modified       = 0;
 
 	assure_irg_outs(irg);
 	assure_cf_loop(irg);
 
-
 	/* we have our own value_of function */
 	set_value_of_func(get_node_tarval);