mono/mini/dominators.c

   1 /**
   2  * \file
   3  * Dominator computation on the control flow graph
   4  *
   5  * Author:
   6  *   Dietmar Maurer (dietmar@ximian.com)
   7  *   Paolo Molaro (lupus@ximian.com)
   8  *
   9  * (C) 2003 Ximian, Inc.
  10  * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
  11  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  12  */
  13 #include <string.h>
  14 #include <mono/metadata/debug-helpers.h>
  15 #include <mono/metadata/mempool.h>
  16 #include <mono/metadata/mempool-internals.h>
  17
  18 #include "mini.h"
  19
  20 #ifndef DISABLE_JIT
  21
  22 /*
  23  * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
  24  * it is the entry bblock.
  25  */
  26 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
  27
  28 /*
  29  * Compute dominators and immediate dominators using the algorithm in the
  30  * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
  31  * Timothy J. Harvey, and Ken Kennedy:
  32  * http://citeseer.ist.psu.edu/cooper01simple.html
  33  */
  34 static void
  35 compute_dominators (MonoCompile *cfg)
  36 {
  37         int bindex, i, bitsize;
  38         MonoBasicBlock *entry;
  39         MonoBasicBlock **doms;
  40         gboolean changed;
  41
  42         g_assert (!(cfg->comp_done & MONO_COMP_DOM));
  43
  44         bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
  45
  46         entry = cfg->bblocks [0];
  47
  48         doms = g_new0 (MonoBasicBlock*, cfg->num_bblocks);
  49         doms [entry->dfn] = entry;
  50
  51         if (cfg->verbose_level > 1) {
  52                 for (i = 0; i < cfg->num_bblocks; ++i) {
  53                         int j;
  54                         MonoBasicBlock *bb = cfg->bblocks [i];
  55
  56                         printf ("BB%d IN: ", bb->block_num);
  57                         for (j = 0; j < bb->in_count; ++j)
  58                                 printf ("%d ", bb->in_bb [j]->block_num);
  59                         printf ("\n");
  60                 }
  61         }
  62
  63         changed = TRUE;
  64         while (changed) {
  65                 changed = FALSE;
  66
  67                 for (bindex = 0; bindex < cfg->num_bblocks; ++bindex) {
  68                         MonoBasicBlock *bb = cfg->bblocks [bindex];
  69                         MonoBasicBlock *idom;
  70
  71                         idom = NULL;
  72                         for (i = 0; i < bb->in_count; ++i) {
  73                                 MonoBasicBlock *in_bb = bb->in_bb [i];
  74                                 if ((in_bb != bb) && doms [in_bb->dfn]) {
  75                                         idom = in_bb;
  76                                         break;
  77                                 }
  78                         }
  79                         if (bb != cfg->bblocks [0])
  80                                 g_assert (idom);
  81
  82                         while (i < bb->in_count) {
  83                                 MonoBasicBlock *in_bb = bb->in_bb [i];
  84
  85                                 if (HAS_DFN (in_bb, entry) && doms [in_bb->dfn]) {
  86                                         /* Intersect */
  87                                         MonoBasicBlock *f1 = idom;
  88                                         MonoBasicBlock *f2 = in_bb;
  89
  90                                         while (f1 != f2) {
  91                                                 if (f1->dfn < f2->dfn)
  92                                                         f2 = doms [f2->dfn];
  93                                                 else
  94                                                         f1 = doms [f1->dfn];
  95                                         }
  96
  97                                         idom = f1;
  98                                 }
  99                                 i ++;
 100                         }
 101
 102                         if (idom != doms [bb->dfn]) {
 103                                 if (bb == cfg->bblocks [0])
 104                                         doms [bb->dfn] = bb;
 105                                 else {
 106                                         doms [bb->dfn] = idom;
 107                                         changed = TRUE;
 108                                 }
 109
 110                                 //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
 111                         }
 112                 }
 113         }
 114
 115         /* Compute bb->dominators for each bblock */
 116         for (i = 0; i < cfg->num_bblocks; ++i) {
 117                 MonoBasicBlock *bb = cfg->bblocks [i];
 118                 MonoBasicBlock *cbb;
 119                 MonoBitSet *dominators;
 120                 char *mem;
 121
 122                 mem = (char *)mono_mempool_alloc0 (cfg->mempool, bitsize);
 123
 124                 bb->dominators = dominators = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
 125                 mem += bitsize;
 126
 127                 mono_bitset_set_fast (dominators, bb->dfn);
 128
 129                 if (bb->dfn) {
 130                         for (cbb = doms [bb->dfn]; cbb->dfn; cbb = doms [cbb->dfn])
 131                                 mono_bitset_set_fast (dominators, cbb->dfn);
 132
 133                         bb->idom = doms [bb->dfn];
 134                         if (bb->idom)
 135                                 bb->idom->dominated = g_slist_prepend_mempool (cfg->mempool, bb->idom->dominated, bb);
 136                 }
 137
 138                 /* The entry bb */
 139                 mono_bitset_set_fast (dominators, 0);
 140         }
 141
 142         g_free (doms);
 143
 144         cfg->comp_done |= MONO_COMP_DOM | MONO_COMP_IDOM;
 145
 146         if (cfg->verbose_level > 1) {
 147                 printf ("DTREE %s %d\n", mono_method_full_name (cfg->method, TRUE),
 148                         cfg->header->num_clauses);
 149                 for (i = 0; i < cfg->num_bblocks; ++i) {
 150                         MonoBasicBlock *bb = cfg->bblocks [i];
 151                         printf ("BB%d(dfn=%d) (IDOM=BB%d): ", bb->block_num, bb->dfn, bb->idom ? bb->idom->block_num : -1);
 152                         mono_blockset_print (cfg, bb->dominators, NULL, -1);
 153                 }
 154         }
 155 }
 156
 157 #if 0
 158
 159 static void
 160 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
 161 {
 162         int i, j;
 163
 164         t->flags |= BB_VISITED;
 165
 166         if (mono_bitset_test_fast (t->dominators, x->dfn)) {
 167                 for (i = 0; i < t->out_count; ++i) {
 168                         if (!(t->flags & BB_VISITED)) {
 169                                 int found = FALSE;
 170                                 check_dominance_frontier (x, t->out_bb [i]);
 171
 172                                 for (j = 0; j < t->out_bb [i]->in_count; j++) {
 173                                         if (t->out_bb [i]->in_bb [j] == t)
 174                                                 found = TRUE;
 175                                 }
 176                                 g_assert (found);
 177                         }
 178                 }
 179         } else {
 180                 if (!mono_bitset_test_fast (x->dfrontier, t->dfn)) {
 181                         printf ("BB%d not in frontier of BB%d\n", t->block_num, x->block_num);
 182                         g_assert_not_reached ();
 183                 }
 184         }
 185 }
 186
 187 #endif
 188
 189 /**
 190  * Compute dominance frontiers using the algorithm from the same paper.
 191  */
 192 static void
 193 compute_dominance_frontier (MonoCompile *cfg)
 194 {
 195         char *mem;
 196         int i, j, bitsize;
 197
 198         g_assert (!(cfg->comp_done & MONO_COMP_DFRONTIER));
 199
 200         for (i = 0; i < cfg->num_bblocks; ++i)
 201                 cfg->bblocks [i]->flags &= ~BB_VISITED;
 202
 203         bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
 204         mem = (char *)mono_mempool_alloc0 (cfg->mempool, bitsize * cfg->num_bblocks);
 205
 206         for (i = 0; i < cfg->num_bblocks; ++i) {
 207                 MonoBasicBlock *bb = cfg->bblocks [i];
 208                 bb->dfrontier = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
 209                 mem += bitsize;
 210         }
 211
 212         for (i = 0; i < cfg->num_bblocks; ++i) {
 213                 MonoBasicBlock *bb = cfg->bblocks [i];
 214
 215                 if (bb->in_count > 1) {
 216                         for (j = 0; j < bb->in_count; ++j) {
 217                                 MonoBasicBlock *p = bb->in_bb [j];
 218
 219                                 if (p->dfn || (p == cfg->bblocks [0])) {
 220                                         while (p != bb->idom) {
 221                                                 mono_bitset_set_fast (p->dfrontier, bb->dfn);
 222                                                 p = p->idom;
 223                                         }
 224                                 }
 225                         }
 226                 }
 227         }
 228
 229 #if 0
 230         for (i = 0; i < cfg->num_bblocks; ++i) {
 231                 MonoBasicBlock *bb = cfg->bblocks [i];
 232
 233                 printf ("DFRONT %s BB%d: ", mono_method_full_name (cfg->method, TRUE), bb->block_num);
 234                 mono_blockset_print (cfg, bb->dfrontier, NULL, -1);
 235         }
 236 #endif
 237
 238 #if 0
 239         /* this is a check for the dominator frontier */
 240         for (i = 0; i < m->num_bblocks; ++i) {
 241                 MonoBasicBlock *x = m->bblocks [i];
 242
 243                 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
 244                         MonoBasicBlock *w = m->bblocks [j];
 245                         int k;
 246                         /* x must not strictly dominates w */
 247                         if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
 248                                 g_assert_not_reached ();
 249
 250                         for (k = 0; k < m->num_bblocks; ++k)
 251                                 m->bblocks [k]->flags &= ~BB_VISITED;
 252
 253                         check_dominance_frontier (x, x);
 254                 }
 255         }
 256 #endif
 257
 258         cfg->comp_done |= MONO_COMP_DFRONTIER;
 259 }
 260
 261 static inline void
 262 df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
 263 {
 264         int i;
 265
 266         mono_bitset_foreach_bit (set, i, m->num_bblocks) {
 267                 mono_bitset_union_fast (dest, m->bblocks [i]->dfrontier);
 268         }
 269 }
 270
 271 MonoBitSet*
 272 mono_compile_iterated_dfrontier (MonoCompile *m, MonoBitSet *set)
 273 {
 274         MonoBitSet *result;
 275         int bitsize, count1, count2;
 276
 277         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
 278         result = mono_bitset_mem_new (mono_mempool_alloc0 (m->mempool, bitsize), m->num_bblocks, 0);
 279
 280         df_set (m, result, set);
 281         count2 = mono_bitset_count (result);
 282         do {
 283                 count1 = count2;
 284                 df_set (m, result, result);
 285                 count2 = mono_bitset_count (result);
 286         } while (count2 > count1);
 287
 288         return result;
 289 }
 290
 291 void
 292 mono_compile_dominator_info (MonoCompile *cfg, int dom_flags)
 293 {
 294         if ((dom_flags & MONO_COMP_DOM) && !(cfg->comp_done & MONO_COMP_DOM))
 295                 compute_dominators (cfg);
 296         if ((dom_flags & MONO_COMP_DFRONTIER) && !(cfg->comp_done & MONO_COMP_DFRONTIER))
 297                 compute_dominance_frontier (cfg);
 298 }
 299
 300 /*
 301  * code to detect loops and loop nesting level
 302  */
 303 void
 304 mono_compute_natural_loops (MonoCompile *cfg)
 305 {
 306         int i, j, k;
 307         MonoBitSet *in_loop_blocks;
 308         int *bb_indexes;
 309
 310         g_assert (!(cfg->comp_done & MONO_COMP_LOOPS));
 311
 312         in_loop_blocks = mono_bitset_new (cfg->num_bblocks + 1, 0);
 313         for (i = 0; i < cfg->num_bblocks; ++i) {
 314                 MonoBasicBlock *n = cfg->bblocks [i];
 315
 316                 for (j = 0; j < n->out_count; j++) {
 317                         MonoBasicBlock *h = n->out_bb [j];
 318                         /* check for single block loops */
 319                         if (n == h) {
 320                                 h->loop_blocks = g_list_prepend_mempool (cfg->mempool, h->loop_blocks, h);
 321                                 h->nesting++;
 322                         }
 323                         /* check for back-edge from n to h */
 324                         else 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 = (MonoBasicBlock *)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_mempool (cfg->mempool, 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_mempool (cfg->mempool, 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         if (cfg->verbose_level > 1) {
 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 ("\tBB%d %d %p\n", cb->block_num, cb->nesting, cb->loop_blocks);
 416                                 }
 417                         }
 418                 }
 419         }
 420 }
 421
 422 static void
 423 clear_idominators (MonoCompile *cfg)
 424 {
 425         guint i;
 426
 427         for (i = 0; i < cfg->num_bblocks; ++i) {
 428                 if (cfg->bblocks[i]->dominated) {
 429                         cfg->bblocks[i]->dominated = NULL;
 430                 }
 431         }
 432
 433         cfg->comp_done &= ~MONO_COMP_IDOM;
 434 }
 435
 436 static void
 437 clear_loops (MonoCompile *cfg)
 438 {
 439         guint i;
 440
 441         for (i = 0; i < cfg->num_bblocks; ++i) {
 442                 cfg->bblocks[i]->nesting = 0;
 443                 cfg->bblocks[i]->loop_blocks = NULL;
 444         }
 445
 446         cfg->comp_done &= ~MONO_COMP_LOOPS;
 447 }
 448
 449 void
 450 mono_free_loop_info (MonoCompile *cfg)
 451 {
 452     if (cfg->comp_done & MONO_COMP_IDOM)
 453         clear_idominators (cfg);
 454     if (cfg->comp_done & MONO_COMP_LOOPS)
 455         clear_loops (cfg);
 456 }
 457
 458 #else /* DISABLE_JIT */
 459
 460 void
 461 mono_free_loop_info (MonoCompile *cfg)
 462 {
 463 }
 464
 465 #endif /* DISABLE_JIT */