2008-08-22 Zoltan Varga <vargaz@gmail.com>

[mono.git] / mono / mini / dominators.c

diff --git a/mono/mini/dominators.c b/mono/mini/dominators.c
index a733189d1d10a841eec9e11af0d4e135e66c823a..7f1b5826c6aec7fb6ef0ada6611cf2f42607dc63 100644 (file)
--- a/mono/mini/dominators.c
+++ b/mono/mini/dominators.c
@@ -9,11 +9,19 @@
  */
 #include <string.h>
 #include <mono/metadata/debug-helpers.h>
+#include <mono/metadata/mempool.h>
+#include <mono/metadata/mempool-internals.h>
 
 #include "mini.h"
 
 //#define DEBUG_DOMINATORS
 
+/*
+ * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
+ * it is the entry bblock.
+ */
+#define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
+
 /*
  * Compute dominators and immediate dominators using the algorithm in the
  * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper, 
@@ -23,28 +31,22 @@
 static void
 compute_dominators (MonoCompile *cfg)
 {
-       int i, j, bitsize;
+       int bindex, i, bitsize;
        char* mem;
-       gboolean *in_worklist;
-       MonoBasicBlock **worklist;
-       guint32 l_begin, l_end;
+       MonoBasicBlock *entry;
        MonoBasicBlock **doms;
+       gboolean changed;
 
        g_assert (!(cfg->comp_done & MONO_COMP_DOM));
 
        bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
-       in_worklist = g_new0 (gboolean, cfg->num_bblocks);
-       worklist = g_new (MonoBasicBlock*, cfg->num_bblocks + 1);
-       l_begin = 0;
-       l_end = 0;
 
        mem = mono_mempool_alloc0 (cfg->mempool, bitsize * cfg->num_bblocks);
 
-       /* the first is always the entry */
-       worklist [l_end ++] = cfg->bblocks [0];
+       entry = cfg->bblocks [0];
 
        doms = g_new0 (MonoBasicBlock*, cfg->num_bblocks);
-       doms [cfg->bblocks [0]->dfn] = cfg->bblocks [0];
+       doms [entry->dfn] = entry;
 
 #ifdef DEBUG_DOMINATORS
        for (i = 0; i < cfg->num_bblocks; ++i) {
@@ -57,63 +59,54 @@ compute_dominators (MonoCompile *cfg)
        }
 #endif
 
-       while (l_begin != l_end) {
-               MonoBasicBlock *bb = worklist [l_begin ++];
-               MonoBasicBlock *idom;
-
-               in_worklist [bb->dfn] = FALSE;
+       changed = TRUE;
+       while (changed) {
+               changed = FALSE;
 
-               if (l_begin == cfg->num_bblocks + 1)
-                       l_begin = 0;
+               for (bindex = 0; bindex < cfg->num_bblocks; ++bindex) {
+                       MonoBasicBlock *bb = cfg->bblocks [bindex];
+                       MonoBasicBlock *idom;
 
-               idom = NULL;
-               for (i = 0; i < bb->in_count; ++i) {
-                       MonoBasicBlock *in_bb = bb->in_bb [i];
-                       if (doms [in_bb->dfn]) {
-                               idom = in_bb;
-                               break;
-                       }
-               }
-               if (bb != cfg->bblocks [0])
-                       g_assert (idom);
-                       
-               while (i < bb->in_count) {
-                       MonoBasicBlock *in_bb = bb->in_bb [i];
-
-                       if (in_bb->dfn && doms [in_bb->dfn]) {
-                               /* Intersect */
-                               MonoBasicBlock *f1 = idom;
-                               MonoBasicBlock *f2 = in_bb;
-
-                               while (f1 != f2) {
-                                       if (f1->dfn < f2->dfn)
-                                               f2 = doms [f2->dfn];
-                                       else
-                                               f1 = doms [f1->dfn];
+                       idom = NULL;
+                       for (i = 0; i < bb->in_count; ++i) {
+                               MonoBasicBlock *in_bb = bb->in_bb [i];
+                               if ((in_bb != bb) && doms [in_bb->dfn]) {
+                                       idom = in_bb;
+                                       break;
                                }
+                       }
+                       if (bb != cfg->bblocks [0])
+                               g_assert (idom);
+
+                       while (i < bb->in_count) {
+                               MonoBasicBlock *in_bb = bb->in_bb [i];
+
+                               if (HAS_DFN (in_bb, entry) && doms [in_bb->dfn]) {
+                                       /* Intersect */
+                                       MonoBasicBlock *f1 = idom;
+                                       MonoBasicBlock *f2 = in_bb;
+
+                                       while (f1 != f2) {
+                                               if (f1->dfn < f2->dfn)
+                                                       f2 = doms [f2->dfn];
+                                               else
+                                                       f1 = doms [f1->dfn];
+                                       }
 
-                               idom = f1;
+                                       idom = f1;
+                               }
+                               i ++;
                        }
-                       i ++;
-               }
 
-               if (idom != doms [bb->dfn]) {
-                       if (bb == cfg->bblocks [0])
-                               doms [bb->dfn] = bb;
-                       else
-                               doms [bb->dfn] = idom;
-                                       
-                       for (j = 0; j < bb->out_count; ++j) {
-                               MonoBasicBlock *out_bb = bb->out_bb [j];
-                               if (!in_worklist [out_bb->dfn]) {
-#ifdef DEBUG_DOMINATORS
-                                       printf ("\tADD %d to worklist.\n", out_bb->dfn);
-#endif
-                                       worklist [l_end ++] = out_bb;
-                                       if (l_end == cfg->num_bblocks + 1)
-                                               l_end = 0;
-                                       in_worklist [out_bb->dfn] = TRUE;
+                       if (idom != doms [bb->dfn]) {
+                               if (bb == cfg->bblocks [0])
+                                       doms [bb->dfn] = bb;
+                               else {
+                                       doms [bb->dfn] = idom;
+                                       changed = TRUE;
                                }
+
+                               //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
                        }
                }
        }
@@ -135,15 +128,13 @@ compute_dominators (MonoCompile *cfg)
 
                        bb->idom = doms [bb->dfn];
                        if (bb->idom)
-                               bb->idom->dominated = g_list_prepend (bb->idom->dominated, bb);
+                               bb->idom->dominated = g_slist_prepend_mempool (cfg->mempool, bb->idom->dominated, bb);
                }
 
                /* The entry bb */
                mono_bitset_set_fast (dominators, 0);
        }
 
-       g_free (worklist);
-       g_free (in_worklist);
        g_free (doms);
 
        cfg->comp_done |= MONO_COMP_DOM | MONO_COMP_IDOM;
@@ -159,6 +150,8 @@ compute_dominators (MonoCompile *cfg)
 #endif
 }
 
+#if 0
+
 static void
 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
 {
@@ -187,6 +180,8 @@ check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
        }
 } 
 
+#endif
+
 /**
  * Compute dominance frontiers using the algorithm from the same paper.
  */
@@ -265,7 +260,7 @@ df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
        int i;
 
        mono_bitset_foreach_bit (set, i, m->num_bblocks) {
-               mono_bitset_union (dest, m->bblocks [i]->dfrontier);
+               mono_bitset_union_fast (dest, m->bblocks [i]->dfrontier);
        }
 }
 
@@ -425,7 +420,6 @@ clear_idominators (MonoCompile *cfg)
     
        for (i = 0; i < cfg->num_bblocks; ++i) {
                if (cfg->bblocks[i]->dominated) {
-                       g_list_free (cfg->bblocks[i]->dominated);        
                        cfg->bblocks[i]->dominated = NULL;
                }
        }