X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmini%2Fdominators.c;h=7f1b5826c6aec7fb6ef0ada6611cf2f42607dc63;hb=279b47e476642431c7f96e105ed32f133d6ed5a3;hp=a733189d1d10a841eec9e11af0d4e135e66c823a;hpb=948dbf8d4581ac17f5420cc4f7dc375e3c502576;p=mono.git

diff --git a/mono/mini/dominators.c b/mono/mini/dominators.c
index a733189d1d1..7f1b5826c6a 100644
--- 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;
 		}
 	}