+ * @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;
+} /* 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)) {
+ ir_opcode 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)) {
+ 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.
+ *
+ * @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);
+
+ 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, *n;
+ node_t *touched = Z->touched;
+ node_t *touched_aa = NULL;
+ node_t *touched_ab = NULL;
+ unsigned n_touched_aa = 0;
+ unsigned n_touched_ab = 0;
+
+ 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 = n) {
+ node_t *left = get_irn_node(get_irn_n(e->node, 0));
+ node_t *right = get_irn_node(get_irn_n(e->node, 1));
+
+ assert(e->is_follower == 0);
+ e->on_touched = 0;
+ n = e->next;
+
+ /*
+ * Note: op(a, a) is NOT congruent to op(a, b).
+ * So, we must split the touched list.
+ */
+ if (left->part == right->part) {
+ e->next = touched_aa;
+ touched_aa = e;
+ ++n_touched_aa;
+ } else {
+ e->next = touched_ab;
+ touched_ab = e;
+ ++n_touched_ab;
+ }
+ }
+ assert(n_touched_aa + n_touched_ab == Z->n_touched);
+ Z->touched = NULL;
+ Z->n_touched = 0;
+
+ if (0 < n_touched_aa && n_touched_aa < Z->n_leader) {
+ partition_t *Z_prime = Z;
+ DB((dbg, LEVEL_2, "Split part%d by touched_aa\n", Z_prime->nr));
+ split(&Z_prime, touched_aa, env);
+ } else
+ assert(n_touched_aa <= Z->n_leader);
+
+ if (0 < n_touched_ab && n_touched_ab < Z->n_leader) {
+ partition_t *Z_prime = Z;
+ DB((dbg, LEVEL_2, "Split part%d by touched_ab\n", Z_prime->nr));
+ split(&Z_prime, touched_ab, env);
+ } else
+ assert(n_touched_ab <= 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 */
+ 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