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