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