+} /* split_no_followers */
+
+/**
+ * Make the Follower -> Leader transition for a node.
+ *
+ * @param n the node
+ */
+static void follower_to_leader(node_t *n) {
+ assert(n->is_follower == 1);
+
+ DB((dbg, LEVEL_2, "%+F make the follower -> leader transition\n", n->node));
+ n->is_follower = 0;
+ move_edges_to_leader(n);
+ list_del(&n->node_list);
+ list_add_tail(&n->node_list, &n->part->Leader);
+ ++n->part->n_leader;
+} /* follower_to_leader */
+
+/**
+ * The environment for one race step.
+ */
+typedef struct step_env {
+ node_t *initial; /**< The initial node list. */
+ node_t *unwalked; /**< The unwalked node list. */
+ node_t *walked; /**< The walked node list. */
+ int index; /**< Next index of Follower use_def edge. */
+ unsigned side; /**< side number. */
+} step_env;
+
+/**
+ * Return non-zero, if a input is a real follower
+ *
+ * @param irn the node to check
+ * @param input number of the input
+ */
+static int is_real_follower(const ir_node *irn, int input) {
+ node_t *pred;
+
+ switch (get_irn_opcode(irn)) {
+ case iro_Confirm:
+ if (input == 1) {
+ /* ignore the Confirm bound input */
+ return 0;
+ }
+ break;
+ case iro_Mux:
+ if (input == 0) {
+ /* ignore the Mux sel input */
+ return 0;
+ }
+ break;
+ case iro_Phi: {
+ /* dead inputs are not follower edges */
+ ir_node *block = get_nodes_block(irn);
+ node_t *pred = get_irn_node(get_Block_cfgpred(block, input));
+
+ if (pred->type.tv == tarval_unreachable)
+ return 0;
+ break;
+ }
+ case iro_Sub:
+ case iro_Shr:
+ case iro_Shl:
+ case iro_Shrs:
+ case iro_Rotl:
+ if (input == 1) {
+ /* only a Sub x,0 / Shift x,0 might be a follower */
+ return 0;
+ }
+ break;
+ case iro_Add:
+ case iro_Or:
+ case iro_Eor:
+ pred = get_irn_node(get_irn_n(irn, input));
+ if (is_tarval(pred->type.tv) && tarval_is_null(pred->type.tv))
+ return 0;
+ break;
+ case iro_Mul:
+ pred = get_irn_node(get_irn_n(irn, input));
+ if (is_tarval(pred->type.tv) && tarval_is_one(pred->type.tv))
+ return 0;
+ break;
+ case iro_And:
+ pred = get_irn_node(get_irn_n(irn, input));
+ if (is_tarval(pred->type.tv) && tarval_is_all_one(pred->type.tv))
+ return 0;
+ break;
+ case iro_Min:
+ case iro_Max:
+ /* all inputs are followers */
+ return 1;
+ default:
+ assert(!"opcode not implemented yet");
+ break;
+ }
+ return 1;
+} /* is_real_follower */
+
+/**
+ * Do one step in the race.
+ */
+static int step(step_env *env) {
+ node_t *n;
+
+ if (env->initial != NULL) {
+ /* Move node from initial to unwalked */
+ n = env->initial;
+ env->initial = n->race_next;
+
+ n->race_next = env->unwalked;
+ env->unwalked = n;
+
+ return 0;
+ }
+
+ while (env->unwalked != NULL) {
+ /* let n be the first node in unwalked */
+ n = env->unwalked;
+ while (env->index < n->n_followers) {
+ const ir_def_use_edge *edge = &n->node->out[1 + env->index];
+
+ /* let m be n.F.def_use[index] */
+ node_t *m = get_irn_node(edge->use);
+
+ assert(m->is_follower);
+ /*
+ * Some inputs, like the get_Confirm_bound are NOT
+ * real followers, sort them out.
+ */
+ if (! is_real_follower(m->node, edge->pos)) {
+ ++env->index;
+ continue;
+ }
+ ++env->index;
+
+ /* only followers from our partition */
+ if (m->part != n->part)
+ continue;
+
+ if ((m->flagged & env->side) == 0) {
+ m->flagged |= env->side;
+
+ if (m->flagged != 3) {
+ /* visited the first time */
+ /* add m to unwalked not as first node (we might still need to
+ check for more follower node */
+ m->race_next = n->race_next;
+ n->race_next = m;
+ return 0;
+ }
+ /* else already visited by the other side and on the other list */
+ }
+ }
+ /* move n to walked */
+ env->unwalked = n->race_next;
+ n->race_next = env->walked;
+ env->walked = n;
+ env->index = 0;
+ }
+ return 1;
+} /* step */
+
+/**
+ * Clear the flags from a list and check for
+ * nodes that where touched from both sides.
+ *
+ * @param list the list
+ */
+static int clear_flags(node_t *list) {
+ int res = 0;
+ node_t *n;
+
+ for (n = list; n != NULL; n = n->race_next) {
+ if (n->flagged == 3) {
+ /* we reach a follower from both sides, this will split congruent
+ * inputs and make it a leader. */
+ follower_to_leader(n);
+ res = 1;
+ }
+ n->flagged = 0;
+ }
+ return res;
+} /* clear_flags */
+
+/**
+ * Split a partition by a local list using the race.
+ *
+ * @param pX pointer to the partition to split, might be changed!
+ * @param gg a (non-empty) node list
+ * @param env the environment
+ *
+ * @return a new partition containing the nodes of gg
+ */
+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;