+ INIT_LIST_HEAD(&tmp);
+
+ /* Remove gg from X.Leader and put into g */
+ g = NULL;
+ for (node = gg; node != NULL; node = node->next) {
+ assert(node->part == X);
+ assert(node->is_follower == 0);
+
+ list_del(&node->node_list);
+ list_add_tail(&node->node_list, &tmp);
+ node->race_next = g;
+ g = node;
+ }
+ /* produce h */
+ h = NULL;
+ list_for_each_entry(node_t, node, &X->Leader, node_list) {
+ node->race_next = h;
+ h = node;
+ }
+ /* restore X.Leader */
+ list_splice(&tmp, &X->Leader);
+
+ env1.initial = g;
+ env1.unwalked = NULL;
+ env1.walked = NULL;
+ env1.index = 0;
+ env1.side = 1;
+
+ env2.initial = h;
+ env2.unwalked = NULL;
+ env2.walked = NULL;
+ env2.index = 0;
+ env2.side = 2;
+
+ for (;;) {
+ if (step(&env1)) {
+ winner = &env1;
+ break;
+ }
+ if (step(&env2)) {
+ winner = &env2;
+ break;
+ }
+ }
+ assert(winner->initial == NULL);
+ assert(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);
+
+ dump_race_list("winner ", 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) {
+ list_del(&node->node_list);
+ node->part = X_prime;
+ if (node->is_follower) {
+ list_add_tail(&node->node_list, &X_prime->Follower);
+ } else {
+ list_add_tail(&node->node_list, &X_prime->Leader);
+ ++n;
+ }
+ if (node->max_user_input > max_input)
+ max_input = node->max_user_input;
+ }
+ X_prime->n_leader = n;
+ X_prime->max_user_inputs = max_input;
+ X->n_leader -= X_prime->n_leader;
+
+ /* for now, copy the type info tag, it will be adjusted in split_by(). */
+ X_prime->type_is_T_or_C = X->type_is_T_or_C;
+
+ /*
+ * Even if a follower was not checked by both sides, it might have
+ * loose its congruence, so we need to check this case for all follower.
+ */
+ list_for_each_entry_safe(node_t, node, t, &X_prime->Follower, node_list) {
+ if (identity(node) == node) {
+ follower_to_leader(node);
+ transitions = 1;
+ }
+ }
+
+ check_partition(X);
+ check_partition(X_prime);
+
+ /* X' is the smaller part */
+ add_to_worklist(X_prime, 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) {
+ X_prime->cprop_next = env->cprop;
+ env->cprop = X_prime;
+ X_prime->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) {
+ *pX = X_prime;
+ return X;
+ }
+
+ return X_prime;
+} /* split */
+
+/**
+ * Returns non-zero if the i'th input of a Phi node is live.
+ *
+ * @param phi a Phi-node
+ * @param i an input number
+ *
+ * @return non-zero if the i'th input of the given Phi node is live
+ */
+static int is_live_input(ir_node *phi, int i) {
+ if (i >= 0) {
+ ir_node *block = get_nodes_block(phi);
+ ir_node *pred = get_Block_cfgpred(block, i);
+ lattice_elem_t type = get_node_type(pred);
+
+ return type.tv != tarval_unreachable;
+ }
+ /* else it's the control input, always live */
+ return 1;
+} /* is_live_input */
+
+/**
+ * Return non-zero if a type is a constant.
+ */
+static int is_constant_type(lattice_elem_t type) {
+ if (type.tv != tarval_bottom && type.tv != tarval_top)
+ return 1;
+ return 0;
+} /* is_constant_type */
+
+/**
+ * Check whether a type is neither Top or a constant.
+ * Note: U is handled like Top here, R is a constant.
+ *
+ * @param type the type to check
+ */
+static int type_is_neither_top_nor_const(const lattice_elem_t type) {
+ if (is_tarval(type.tv)) {
+ if (type.tv == tarval_top)
+ return 0;
+ if (tarval_is_constant(type.tv))
+ return 0;
+ } else {
+ /* is a symconst */
+ return 0;
+ }
+ return 1;
+}
+
+/**
+ * Collect nodes to the touched list.
+ *
+ * @param list the list which contains the nodes that must be evaluated
+ * @param idx the index of the def_use edge to evaluate
+ * @param env the environment
+ */
+static void collect_touched(list_head *list, int idx, environment_t *env) {
+ node_t *x, *y;
+ int end_idx = env->end_idx;
+
+ list_for_each_entry(node_t, x, list, node_list) {
+ int num_edges;
+
+ if (idx == -1) {
+ /* leader edges start AFTER follower edges */
+ x->next_edge = x->n_followers + 1;
+ }
+ num_edges = get_irn_n_outs(x->node);
+
+ /* 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 > idx)
+ break;
+
+ ++x->next_edge;
+
+ succ = edge->use;
+
+ /* 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)
+ continue;
+
+ y = get_irn_node(succ);
+ assert(get_irn_n(succ, idx) == x->node);
+
+ /* ignore block edges touching followers */
+ if (idx == -1 && y->is_follower)
+ continue;
+
+ if (is_constant_type(y->type)) {
+ ir_opcode code = get_irn_opcode(succ);
+ if (code == iro_Sub || code == iro_Eor || code == iro_Cmp)
+ 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) &&
+ (! is_Phi(y->node) || is_live_input(y->node, idx))) {
+ add_to_touched(y, env);
+ }
+ }
+ }
+} /* collect_touched */
+
+/**
+ * Split the partitions if caused by the first entry on the worklist.
+ *
+ * @param env the environment
+ */
+static void cause_splits(environment_t *env) {
+ partition_t *X, *Z, *N;
+ int idx;
+
+ /* remove the first partition from the worklist */
+ X = env->worklist;
+ env->worklist = X->wl_next;
+ X->on_worklist = 0;
+
+ dump_partition("Cause_split: ", X);
+
+ /* 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 */
+ env->touched = NULL;
+
+ collect_touched(&X->Leader, idx, env);
+ collect_touched(&X->Follower, idx, 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);
+ }
+ }
+} /* cause_splits */
+
+/**
+ * Implements split_by_what(): Split a partition by characteristics given
+ * by the what function.
+ *
+ * @param X the partition to split
+ * @param What a function returning an Id for every node of the partition X
+ * @param P a list to store the result partitions
+ * @param env the environment
+ *
+ * @return *P
+ */
+static partition_t *split_by_what(partition_t *X, what_func What,
+ partition_t **P, environment_t *env) {
+ node_t *x, *S;
+ listmap_t map;
+ listmap_entry_t *iter;
+ partition_t *R;
+
+ /* Let map be an empty mapping from the range of What to (local) list of Nodes. */
+ listmap_init(&map);
+ list_for_each_entry(node_t, x, &X->Leader, node_list) {
+ void *id = What(x, env);
+ listmap_entry_t *entry;
+
+ if (id == NULL) {
+ /* input not allowed, ignore */
+ continue;