+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 senv[2];
+ node_t *g, *h, *node, *t;
+ int max_input, transitions, winner, shf;
+ unsigned n;
+ DEBUG_ONLY(static int run = 0;)
+
+ DB((dbg, LEVEL_2, "Run %d ", run++));
+ if (list_empty(&X->Follower)) {
+ /* if the partition has NO follower, we can use the fast
+ splitting algorithm. */
+ return split_no_followers(X, gg, env);
+ }
+ /* else do the race */
+
+ dump_partition("Splitting ", X);
+ dump_list("by list ", gg);
+
+ 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);
+
+ senv[0].initial = g;
+ senv[0].unwalked = NULL;
+ senv[0].walked = NULL;
+ senv[0].index = 0;
+ senv[0].side = 1;
+
+ 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(&senv[0])) {
+ winner = 0;
+ break;
+ }
+ if (step(&senv[1])) {
+ winner = 1;
+ break;
+ }
+ }
+ assert(senv[winner].initial == NULL);
+ assert(senv[winner].unwalked == NULL);
+
+ /* clear flags from walked/unwalked */
+ 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 ", senv[winner].walked);
+
+ /* Move walked_{winner} to a new partition, X'. */
+ X_prime = new_partition(env);
+ max_input = 0;
+ n = 0;
+ for (node = senv[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 & 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 != 0) {
+ *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;
+} /* type_is_neither_top_nor_const */
+
+/**
+ * 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;
+
+ /* 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)
+ 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)) {
+ unsigned code = get_irn_opcode(succ);
+ if (code == iro_Sub || 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 */
+
+/**
+ * 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)) {
+ unsigned 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.
+ *
+ * @param env the environment
+ */
+static void cause_splits(environment_t *env)
+{
+ partition_t *X, *Z, *N;
+ int idx;