mono/mini/dominators.c

   1 /*
   2  * dominators.c: Dominator computation on the control flow graph
   3  *
   4  * Author:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *   Paolo Molaro (lupus@ximian.com)
   7  *
   8  * (C) 2003 Ximian, Inc.
   9  */
  10 #include <string.h>
  11 #include <mono/metadata/debug-helpers.h>
  12
  13 #include "mini.h"
  14
  15 //#define DEBUG_DOMINATORS
  16
  17 /*
  18  * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
  19  * it is the entry bblock.
  20  */
  21 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
  22
  23 static inline GSList*
  24 g_slist_prepend_mempool (MonoMemPool *mp, GSList   *list,
  25                                                  gpointer  data)
  26 {
  27   GSList *new_list;
  28
  29   new_list = mono_mempool_alloc (mp, sizeof (GSList));
  30   new_list->data = data;
  31   new_list->next = list;
  32
  33   return new_list;
  34 }
  35
  36 /*
  37  * Compute dominators and immediate dominators using the algorithm in the
  38  * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
  39  * Timothy J. Harvey, and Ken Kennedy:
  40  * http://citeseer.ist.psu.edu/cooper01simple.html
  41  */
  42 static void
  43 compute_dominators (MonoCompile *cfg)
  44 {
  45         int bindex, i, bitsize;
  46         char* mem;
  47         MonoBasicBlock *entry;
  48         MonoBasicBlock **doms;
  49         gboolean changed;
  50
  51         g_assert (!(cfg->comp_done & MONO_COMP_DOM));
  52
  53         bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
  54
  55         mem = mono_mempool_alloc0 (cfg->mempool, bitsize * cfg->num_bblocks);
  56
  57         entry = cfg->bblocks [0];
  58
  59         doms = g_new0 (MonoBasicBlock*, cfg->num_bblocks);
  60         doms [entry->dfn] = entry;
  61
  62 #ifdef DEBUG_DOMINATORS
  63         for (i = 0; i < cfg->num_bblocks; ++i) {
  64                 MonoBasicBlock *bb = cfg->bblocks [i];
  65
  66                 printf ("BB%d IN: ", bb->block_num);
  67                 for (j = 0; j < bb->in_count; ++j)
  68                         printf ("%d ", bb->in_bb [j]->block_num);
  69                 printf ("\n");
  70         }
  71 #endif
  72
  73         changed = TRUE;
  74         while (changed) {
  75                 changed = FALSE;
  76
  77                 for (bindex = 0; bindex < cfg->num_bblocks; ++bindex) {
  78                         MonoBasicBlock *bb = cfg->bblocks [bindex];
  79                         MonoBasicBlock *idom;
  80
  81                         idom = NULL;
  82                         for (i = 0; i < bb->in_count; ++i) {
  83                                 MonoBasicBlock *in_bb = bb->in_bb [i];
  84                                 if ((in_bb != bb) && doms [in_bb->dfn]) {
  85                                         idom = in_bb;
  86                                         break;
  87                                 }
  88                         }
  89                         if (bb != cfg->bblocks [0])
  90                                 g_assert (idom);
  91
  92                         while (i < bb->in_count) {
  93                                 MonoBasicBlock *in_bb = bb->in_bb [i];
  94
  95                                 if (HAS_DFN (in_bb, entry) && doms [in_bb->dfn]) {
  96                                         /* Intersect */
  97                                         MonoBasicBlock *f1 = idom;
  98                                         MonoBasicBlock *f2 = in_bb;
  99
 100                                         while (f1 != f2) {
 101                                                 if (f1->dfn < f2->dfn)
 102                                                         f2 = doms [f2->dfn];
 103                                                 else
 104                                                         f1 = doms [f1->dfn];
 105                                         }
 106
 107                                         idom = f1;
 108                                 }
 109                                 i ++;
 110                         }
 111
 112                         if (idom != doms [bb->dfn]) {
 113                                 if (bb == cfg->bblocks [0])
 114                                         doms [bb->dfn] = bb;
 115                                 else {
 116                                         doms [bb->dfn] = idom;
 117                                         changed = TRUE;
 118                                 }
 119
 120                                 //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
 121                         }
 122                 }
 123         }
 124
 125         /* Compute bb->dominators for each bblock */
 126         for (i = 0; i < cfg->num_bblocks; ++i) {
 127                 MonoBasicBlock *bb = cfg->bblocks [i];
 128                 MonoBasicBlock *cbb;
 129                 MonoBitSet *dominators;
 130
 131                 bb->dominators = dominators = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
 132                 mem += bitsize;
 133
 134                 mono_bitset_set_fast (dominators, bb->dfn);
 135
 136                 if (bb->dfn) {
 137                         for (cbb = doms [bb->dfn]; cbb->dfn; cbb = doms [cbb->dfn])
 138                                 mono_bitset_set_fast (dominators, cbb->dfn);
 139
 140                         bb->idom = doms [bb->dfn];
 141                         if (bb->idom)
 142                                 bb->idom->dominated = g_slist_prepend_mempool (cfg->mempool, bb->idom->dominated, bb);
 143                 }
 144
 145                 /* The entry bb */
 146                 mono_bitset_set_fast (dominators, 0);
 147         }
 148
 149         g_free (doms);
 150
 151         cfg->comp_done |= MONO_COMP_DOM | MONO_COMP_IDOM;
 152
 153 #ifdef DEBUG_DOMINATORS
 154         printf ("DTREE %s %d\n", mono_method_full_name (cfg->method, TRUE),
 155                 mono_method_get_header (cfg->method)->num_clauses);
 156         for (i = 0; i < cfg->num_bblocks; ++i) {
 157                 MonoBasicBlock *bb = cfg->bblocks [i];
 158                 printf ("BB%d(dfn=%d) (IDOM=BB%d): ", bb->block_num, bb->dfn, bb->idom ? bb->idom->block_num : -1);
 159                 mono_blockset_print (cfg, bb->dominators, NULL, -1);
 160         }
 161 #endif
 162 }
 163
 164 static void
 165 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
 166 {
 167         int i, j;
 168
 169         t->flags |= BB_VISITED;
 170
 171         if (mono_bitset_test_fast (t->dominators, x->dfn)) {
 172                 for (i = 0; i < t->out_count; ++i) {
 173                         if (!(t->flags & BB_VISITED)) {
 174                                 int found = FALSE;
 175                                 check_dominance_frontier (x, t->out_bb [i]);
 176
 177                                 for (j = 0; j < t->out_bb [i]->in_count; j++) {
 178                                         if (t->out_bb [i]->in_bb [j] == t)
 179                                                 found = TRUE;
 180                                 }
 181                                 g_assert (found);
 182                         }
 183                 }
 184         } else {
 185                 if (!mono_bitset_test_fast (x->dfrontier, t->dfn)) {
 186                         printf ("BB%d not in frontier of BB%d\n", t->block_num, x->block_num);
 187                         g_assert_not_reached ();
 188                 }
 189         }
 190 }
 191
 192 /**
 193  * Compute dominance frontiers using the algorithm from the same paper.
 194  */
 195 static void
 196 compute_dominance_frontier (MonoCompile *cfg)
 197 {
 198         char *mem;
 199         int i, j, bitsize;
 200
 201         g_assert (!(cfg->comp_done & MONO_COMP_DFRONTIER));
 202
 203         for (i = 0; i < cfg->num_bblocks; ++i)
 204                 cfg->bblocks [i]->flags &= ~BB_VISITED;
 205
 206         bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
 207         mem = mono_mempool_alloc0 (cfg->mempool, bitsize * cfg->num_bblocks);
 208
 209         for (i = 0; i < cfg->num_bblocks; ++i) {
 210                 MonoBasicBlock *bb = cfg->bblocks [i];
 211                 bb->dfrontier = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
 212                 mem += bitsize;
 213         }
 214
 215         for (i = 0; i < cfg->num_bblocks; ++i) {
 216                 MonoBasicBlock *bb = cfg->bblocks [i];
 217
 218                 if (bb->in_count > 1) {
 219                         for (j = 0; j < bb->in_count; ++j) {
 220                                 MonoBasicBlock *p = bb->in_bb [j];
 221
 222                                 if (p->dfn || (p == cfg->bblocks [0])) {
 223                                         while (p != bb->idom) {
 224                                                 mono_bitset_set_fast (p->dfrontier, bb->dfn);
 225                                                 p = p->idom;
 226                                         }
 227                                 }
 228                         }
 229                 }
 230         }
 231
 232 #if 0
 233         for (i = 0; i < cfg->num_bblocks; ++i) {
 234                 MonoBasicBlock *bb = cfg->bblocks [i];
 235
 236                 printf ("DFRONT %s BB%d: ", mono_method_full_name (cfg->method, TRUE), bb->block_num);
 237                 mono_blockset_print (cfg, bb->dfrontier, NULL, -1);
 238         }
 239 #endif
 240
 241 #if 0
 242         /* this is a check for the dominator frontier */
 243         for (i = 0; i < m->num_bblocks; ++i) {
 244                 MonoBasicBlock *x = m->bblocks [i];
 245
 246                 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
 247                         MonoBasicBlock *w = m->bblocks [j];
 248                         int k;
 249                         /* x must not strictly dominates w */
 250                         if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
 251                                 g_assert_not_reached ();
 252
 253                         for (k = 0; k < m->num_bblocks; ++k)
 254                                 m->bblocks [k]->flags &= ~BB_VISITED;
 255
 256                         check_dominance_frontier (x, x);
 257                 }
 258         }
 259 #endif
 260
 261         cfg->comp_done |= MONO_COMP_DFRONTIER;
 262 }
 263
 264 static inline void
 265 df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
 266 {
 267         int i;
 268
 269         mono_bitset_foreach_bit (set, i, m->num_bblocks) {
 270                 mono_bitset_union_fast (dest, m->bblocks [i]->dfrontier);
 271         }
 272 }
 273
 274 MonoBitSet*
 275 mono_compile_iterated_dfrontier (MonoCompile *m, MonoBitSet *set)
 276 {
 277         MonoBitSet *result;
 278         int bitsize, count1, count2;
 279
 280         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
 281         result = mono_bitset_mem_new (mono_mempool_alloc0 (m->mempool, bitsize), m->num_bblocks, 0);
 282
 283         df_set (m, result, set);
 284         count2 = mono_bitset_count (result);
 285         do {
 286                 count1 = count2;
 287                 df_set (m, result, result);
 288                 count2 = mono_bitset_count (result);
 289         } while (count2 > count1);
 290
 291         return result;
 292 }
 293
 294 void
 295 mono_compile_dominator_info (MonoCompile *cfg, int dom_flags)
 296 {
 297         if ((dom_flags & MONO_COMP_DOM) && !(cfg->comp_done & MONO_COMP_DOM))
 298                 compute_dominators (cfg);
 299         if ((dom_flags & MONO_COMP_DFRONTIER) && !(cfg->comp_done & MONO_COMP_DFRONTIER))
 300                 compute_dominance_frontier (cfg);
 301 }
 302
 303 //#define DEBUG_NATURAL_LOOPS
 304
 305 /*
 306  * code to detect loops and loop nesting level
 307  */
 308 void
 309 mono_compute_natural_loops (MonoCompile *cfg)
 310 {
 311         int i, j, k;
 312         MonoBitSet *in_loop_blocks;
 313         int *bb_indexes;
 314
 315         g_assert (!(cfg->comp_done & MONO_COMP_LOOPS));
 316
 317         in_loop_blocks = mono_bitset_new (cfg->num_bblocks + 1, 0);
 318         for (i = 0; i < cfg->num_bblocks; ++i) {
 319                 MonoBasicBlock *n = cfg->bblocks [i];
 320
 321                 for (j = 0; j < n->out_count; j++) {
 322                         MonoBasicBlock *h = n->out_bb [j];
 323                         /* check for back-edge from n to h */
 324                         if (n != h && mono_bitset_test_fast (n->dominators, h->dfn)) {
 325                                 GSList *todo;
 326
 327                                 /* already in loop_blocks? */
 328                                 if (h->loop_blocks && g_list_find (h->loop_blocks, n)) {
 329                                         continue;
 330                                 }
 331
 332                                 mono_bitset_clear_all (in_loop_blocks);
 333                                 if (h->loop_blocks) {
 334                                         GList *l;
 335
 336                                         for (l = h->loop_blocks; l; l = l->next) {
 337                                                 MonoBasicBlock *b = l->data;
 338                                                 if (b->dfn)
 339                                                         mono_bitset_set_fast (in_loop_blocks, b->dfn);
 340                                         }
 341                                 }
 342                                 todo = g_slist_prepend (NULL, n);
 343
 344                                 while (todo) {
 345                                         MonoBasicBlock *cb = (MonoBasicBlock *)todo->data;
 346                                         todo = g_slist_delete_link (todo, todo);
 347
 348                                         if ((cb->dfn && mono_bitset_test_fast (in_loop_blocks, cb->dfn)) || (!cb->dfn && g_list_find (h->loop_blocks, cb)))
 349                                                 continue;
 350
 351                                         h->loop_blocks = g_list_prepend (h->loop_blocks, cb);
 352                                         cb->nesting++;
 353                                         if (cb->dfn)
 354                                                 mono_bitset_set_fast (in_loop_blocks, cb->dfn);
 355
 356                                         for (k = 0; k < cb->in_count; k++) {
 357                                                 MonoBasicBlock *prev = cb->in_bb [k];
 358                                                 /* add all previous blocks */
 359                                                 if (prev != h && !((prev->dfn && mono_bitset_test_fast (in_loop_blocks, prev->dfn)) || (!prev->dfn && g_list_find (h->loop_blocks, prev)))) {
 360                                                         todo = g_slist_prepend (todo, prev);
 361                                                 }
 362                                         }
 363                                 }
 364
 365                                 /* add the header if not already there */
 366                                 if (!((h->dfn && mono_bitset_test_fast (in_loop_blocks, h->dfn)) || (!h->dfn && g_list_find (h->loop_blocks, h)))) {
 367                                         h->loop_blocks = g_list_prepend (h->loop_blocks, h);
 368                                         h->nesting++;
 369                                 }
 370                         }
 371                 }
 372         }
 373         mono_bitset_free (in_loop_blocks);
 374
 375         cfg->comp_done |= MONO_COMP_LOOPS;
 376
 377         /* Compute loop_body_start for each loop */
 378         bb_indexes = g_new0 (int, cfg->num_bblocks);
 379         {
 380                 MonoBasicBlock *bb;
 381
 382                 for (i = 0, bb = cfg->bb_entry; bb; i ++, bb = bb->next_bb) {
 383                         if (bb->dfn)
 384                                 bb_indexes [bb->dfn] = i;
 385                 }
 386         }
 387         for (i = 0; i < cfg->num_bblocks; ++i) {
 388                 if (cfg->bblocks [i]->loop_blocks) {
 389                         /* The loop body start is the first bblock in the order they will be emitted */
 390                         MonoBasicBlock *h = cfg->bblocks [i];
 391                         MonoBasicBlock *body_start = h;
 392                         GList *l;
 393
 394                         for (l = h->loop_blocks; l; l = l->next) {
 395                                 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
 396
 397                                 if (cb->dfn && bb_indexes [cb->dfn] < bb_indexes [body_start->dfn]) {
 398                                         body_start = cb;
 399                                 }
 400                         }
 401
 402                         body_start->loop_body_start = 1;
 403                 }
 404         }
 405         g_free (bb_indexes);
 406
 407 #ifdef DEBUG_NATURAL_LOOPS
 408         for (i = 0; i < cfg->num_bblocks; ++i) {
 409                 if (cfg->bblocks [i]->loop_blocks) {
 410                         MonoBasicBlock *h = (MonoBasicBlock *)cfg->bblocks [i]->loop_blocks->data;
 411                         GList *l;
 412                         printf ("LOOP START %d\n", h->block_num);
 413                         for (l = h->loop_blocks; l; l = l->next) {
 414                                 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
 415                                 printf (" BB%d %d %p\n", cb->block_num, cb->nesting, cb->loop_blocks);
 416                         }
 417                 }
 418         }
 419 #endif
 420
 421 }
 422
 423 static void
 424 clear_idominators (MonoCompile *cfg)
 425 {
 426         guint i;
 427
 428         for (i = 0; i < cfg->num_bblocks; ++i) {
 429                 if (cfg->bblocks[i]->dominated) {
 430                         cfg->bblocks[i]->dominated = NULL;
 431                 }
 432         }
 433
 434         cfg->comp_done &= ~MONO_COMP_IDOM;
 435 }
 436
 437 static void
 438 clear_loops (MonoCompile *cfg)
 439 {
 440         guint i;
 441
 442         for (i = 0; i < cfg->num_bblocks; ++i) {
 443                 cfg->bblocks[i]->nesting = 0;
 444                 if (cfg->bblocks[i]->loop_blocks) {
 445                         g_list_free (cfg->bblocks[i]->loop_blocks);
 446                         cfg->bblocks[i]->loop_blocks = NULL;
 447                 }
 448         }
 449
 450         cfg->comp_done &= ~MONO_COMP_LOOPS;
 451 }
 452
 453 void
 454 mono_free_loop_info (MonoCompile *cfg)
 455 {
 456     if (cfg->comp_done & MONO_COMP_IDOM)
 457         clear_idominators (cfg);
 458     if (cfg->comp_done & MONO_COMP_LOOPS)
 459         clear_loops (cfg);
 460 }