- add comment explaining the connection betwenn the race and Follower -> Leader trans...

[libfirm] / ir / opt / combo.c

diff --git a/ir/opt/combo.c b/ir/opt/combo.c
index 019338b..1701b58 100644 (file)
--- a/ir/opt/combo.c
+++ b/ir/opt/combo.c
@@ -1081,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;)
 
@@ -1120,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) {
@@ -1183,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;
                }
        }
 
@@ -1197,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 (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;
        }