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