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