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 /* the simpler, dumber algorithm */
  18 static void
  19 compute_dominators (MonoCompile *m) {
  20         int change = TRUE;
  21         int i, j, bitsize;
  22         MonoBasicBlock *bb;
  23         MonoBitSet *T;
  24         char* mem;
  25
  26         g_assert (!(m->comp_done & MONO_COMP_DOM));
  27
  28         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
  29         /* the first is always the entry */
  30         bb = m->bblocks [0];
  31         mem = mono_mempool_alloc0 (m->mempool, bitsize * (m->num_bblocks + 1));
  32         bb->dominators = mono_bitset_mem_new (mem, m->num_bblocks, 0);
  33
  34         mem += bitsize;
  35         mono_bitset_set (bb->dominators, 0);
  36
  37         T = mono_bitset_mem_new (mem, m->num_bblocks, 0);
  38         mem += bitsize;
  39
  40
  41         for (i = 1; i < m->num_bblocks; ++i) {
  42                 bb = m->bblocks [i];
  43                 bb->dominators = mono_bitset_mem_new (mem, m->num_bblocks, 0);
  44                 mem += bitsize;
  45                 mono_bitset_invert (bb->dominators);
  46
  47 #ifdef DEBUG_DOMINATORS
  48                 printf ("BB%d IN: ", bb->block_num);
  49                 for (j = 0; j < bb->in_count; ++j)
  50                         printf ("%d ", bb->in_bb [j]->block_num);
  51                 printf ("\n");
  52 #endif
  53         }
  54
  55         do {
  56                 change = FALSE;
  57                 for (i = 1; i < m->num_bblocks; ++i) {
  58                         bb = m->bblocks [i];
  59                         mono_bitset_set_all (T);
  60                         for (j = 0; j < bb->in_count; ++j) {
  61                                 if (bb->in_bb [j]->dominators)
  62                                         mono_bitset_intersection (T, bb->in_bb [j]->dominators);
  63                         }
  64                         mono_bitset_set (T, i);
  65                         if (!mono_bitset_equal (T, bb->dominators)) {
  66                                 change = TRUE;
  67                                 mono_bitset_copyto (T, bb->dominators);
  68                         }
  69                 }
  70         } while (change);
  71
  72         m->comp_done |= MONO_COMP_DOM;
  73
  74 #ifdef DEBUG_DOMINATORS
  75         printf ("DTREE %s %d\n", mono_method_full_name (m->method, TRUE),
  76                 mono_method_get_header (m->method)->num_clauses);
  77         for (i = 0; i < m->num_bblocks; ++i) {
  78                 bb = m->bblocks [i];
  79                 printf ("BB%d: ", bb->block_num);
  80                 mono_blockset_print (m, bb->dominators, NULL, -1);
  81         }
  82 #endif
  83 }
  84
  85 static void
  86 compute_idominators (MonoCompile* m) {
  87         char *mem;
  88         int bitsize, i, s, t;
  89         MonoBitSet **T, *temp;
  90         MonoBasicBlock *bb;
  91
  92         g_assert (!(m->comp_done & MONO_COMP_IDOM));
  93
  94         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
  95         mem = mono_mempool_alloc (m->mempool, bitsize * (m->num_bblocks + 1));
  96         T = mono_mempool_alloc (m->mempool, sizeof (MonoBitSet*) * m->num_bblocks);
  97
  98         for (i = 0; i < m->num_bblocks; ++i) {
  99                 bb = m->bblocks [i];
 100                 T [i] = mono_bitset_mem_new (mem, m->num_bblocks, 0);
 101                 mono_bitset_copyto (bb->dominators, T [i]);
 102                 mono_bitset_clear (T [i], i);
 103                 if (mono_bitset_count (bb->dominators) - 1 != mono_bitset_count (T [i])) {
 104                         mono_blockset_print (m, bb->dominators, "dominators", -1);
 105                         mono_blockset_print (m, T [i], "T [i]", -1);
 106                         g_error ("problem at %d (%d)\n", i, bb->dfn);
 107                 }
 108                 mem += bitsize;
 109         }
 110         temp = mono_bitset_mem_new (mem, m->num_bblocks, 0);
 111
 112         for (i = 1; i < m->num_bblocks; ++i) {
 113
 114                 temp = T [i];
 115
 116                 mono_bitset_foreach_bit_rev (temp, s, m->num_bblocks) {
 117
 118                         mono_bitset_foreach_bit_rev (temp, t, m->num_bblocks) {
 119
 120                                 if (t == s)
 121                                         continue;
 122
 123                                 //if (mono_bitset_test_fast (T [s], t))
 124                                 if (mono_bitset_test_fast (m->bblocks [s]->dominators, t))
 125                                         mono_bitset_clear (temp, t);
 126                         }
 127                 }
 128
 129 #ifdef DEBUG_DOMINATORS
 130                 printf ("IDOMSET BB%d %d: ", m->bblocks [i]->block_num, m->num_bblocks);
 131                 mono_blockset_print (m, T [i], NULL, -1);
 132 #endif
 133         }
 134
 135         for (i = 1; i < m->num_bblocks; ++i) {
 136                 bb = m->bblocks [i];
 137                 s = mono_bitset_find_start (T [i]);
 138                 g_assert (s != -1);
 139                 /*fixme:mono_bitset_count does not really work */
 140                 //g_assert (mono_bitset_count (T [i]) == 1);
 141                 t = mono_bitset_find_first (T [i], s);
 142                 g_assert (t == -1 || t >=  m->num_bblocks);
 143                 bb->idom = m->bblocks [s];
 144                 bb->idom->dominated = g_list_prepend (bb->idom->dominated, bb);
 145         }
 146
 147         m->comp_done |= MONO_COMP_IDOM;
 148 }
 149
 150 static void
 151 postorder_visit (MonoBasicBlock *start, int *idx, MonoBasicBlock **array)
 152 {
 153         int i;
 154
 155         /* we assume the flag was already cleared by the caller. */
 156         start->flags |= BB_VISITED;
 157         /*g_print ("visit %d at %p\n", *dfn, start->cil_code);*/
 158         for (i = 0; i < start->out_count; ++i) {
 159                 if (start->out_bb [i]->flags & BB_VISITED)
 160                         continue;
 161                 postorder_visit (start->out_bb [i], idx, array);
 162         }
 163         array [*idx] = start;
 164         (*idx)++;
 165 }
 166
 167 static void
 168 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
 169 {
 170         int i, j;
 171
 172         t->flags |= BB_VISITED;
 173
 174         if (mono_bitset_test_fast (t->dominators, x->dfn)) {
 175                 for (i = 0; i < t->out_count; ++i) {
 176                         if (!(t->flags & BB_VISITED)) {
 177                                 int found = FALSE;
 178                                 check_dominance_frontier (x, t->out_bb [i]);
 179
 180                                 for (j = 0; j < t->out_bb [i]->in_count; j++) {
 181                                         if (t->out_bb [i]->in_bb [j] == t)
 182                                                 found = TRUE;
 183                                 }
 184                                 g_assert (found);
 185                         }
 186                 }
 187         } else {
 188                 if (!mono_bitset_test_fast (x->dfrontier, t->dfn)) {
 189                         printf ("BB%d not in frontier of BB%d\n", t->block_num, x->block_num);
 190                         g_assert_not_reached ();
 191                 }
 192         }
 193 }
 194
 195 #if 0
 196 /* there is a bug in this code */
 197 static void
 198 compute_dominance_frontier_old (MonoCompile *m) {
 199         int i, j, bitsize;
 200         MonoBasicBlock **postorder;
 201         MonoBasicBlock *bb, *z;
 202         char *mem;
 203
 204         g_assert (!(m->comp_done & MONO_COMP_DFRONTIER));
 205
 206         postorder = mono_mempool_alloc (m->mempool, sizeof (MonoBasicBlock*) * m->num_bblocks);
 207         i = 0;
 208         postorder_visit (m->bb_entry, &i, postorder);
 209         /*g_print ("postorder traversal:");
 210         for (i = 0; i < m->num_bblocks; ++i)
 211                 g_print (" B%d", postorder [i]->dfn);
 212         g_print ("\n");*/
 213
 214         /* we could reuse the bitsets allocated in compute_idominators() */
 215         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
 216         mem = mono_mempool_alloc0 (m->mempool, bitsize * m->num_bblocks);
 217
 218         for (i = 0; i < m->num_bblocks; ++i) {
 219                 bb = postorder [i];
 220                 bb->dfrontier = mono_bitset_mem_new (mem, m->num_bblocks, 0);
 221                 mem += bitsize;
 222         }
 223         for (i = 0; i < m->num_bblocks; ++i) {
 224                 bb = postorder [i];
 225                 /* the local component */
 226                 for (j = 0; j < bb->out_count; ++j) {
 227                         //if (bb->out_bb [j] != bb->idom)
 228                         if (bb->out_bb [j]->idom != bb)
 229                                 mono_bitset_set (bb->dfrontier, bb->out_bb [j]->dfn);
 230                 }
 231         }
 232         for (i = 0; i < m->num_bblocks; ++i) {
 233                 bb = postorder [i];
 234                 /* the up component */
 235                 if (bb->idom) {
 236                         z = bb->idom;
 237                         mono_bitset_foreach_bit (z->dfrontier, j, m->num_bblocks) {
 238                                 //if (m->bblocks [j] != bb->idom)
 239                                 if (m->bblocks [j]->idom != bb)
 240                                         mono_bitset_set (bb->dfrontier, m->bblocks [j]->dfn);
 241                         }
 242                 }
 243         }
 244
 245         /* this is a check for the dominator frontier */
 246         for (i = 0; i < m->num_bblocks; ++i) {
 247                 MonoBasicBlock *x = m->bblocks [i];
 248
 249                 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
 250                         MonoBasicBlock *w = m->bblocks [j];
 251                         int k;
 252                         /* x must not strictly dominates w */
 253                         if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
 254                                 g_assert_not_reached ();
 255
 256                         for (k = 0; k < m->num_bblocks; ++k)
 257                                 m->bblocks [k]->flags &= ~BB_VISITED;
 258
 259                         check_dominance_frontier (x, x);
 260                 }
 261         }
 262
 263         m->comp_done |= MONO_COMP_DFRONTIER;
 264 }
 265 #endif
 266
 267 /* this is an implementation of the dominance frontier algorithm described in
 268  * "modern compiler implementation in C" written by Andrew W. Appel
 269  */
 270 static void
 271 compute_dominance_frontier_appel (MonoCompile *m, int n)
 272 {
 273         int i, j;
 274         MonoBasicBlock *bb;
 275
 276         bb = m->bblocks [n];
 277         g_assert (!(bb->flags & BB_VISITED));
 278         bb->flags |= BB_VISITED;
 279
 280         for (i = 0; i < bb->out_count; ++i) {
 281                 MonoBasicBlock *y = bb->out_bb [i];
 282                 if (y->idom != bb) {
 283                         g_assert (!(mono_bitset_test_fast (y->dominators, bb->dfn) && bb->dfn != y->dfn));
 284                         mono_bitset_set (bb->dfrontier, y->dfn);
 285                 }
 286         }
 287
 288
 289         for (i = 0; i < m->num_bblocks; ++i) {
 290                 MonoBasicBlock *c = m->bblocks [i];
 291                 if (c->idom == bb) {
 292                         if (!(c->flags & BB_VISITED))
 293                                 compute_dominance_frontier_appel (m, c->dfn);
 294                         mono_bitset_foreach_bit (c->dfrontier, j, m->num_bblocks) {
 295                                 MonoBasicBlock *w = m->bblocks [j];
 296                                 if (!(mono_bitset_test_fast (w->dominators, bb->dfn) && bb->dfn != w->dfn))
 297                                         mono_bitset_set (bb->dfrontier, w->dfn);
 298                         }
 299                 }
 300         }
 301 }
 302
 303 static void
 304 compute_dominance_frontier (MonoCompile *m)
 305 {
 306         MonoBasicBlock *bb;
 307         char *mem;
 308         int i, j, bitsize;
 309
 310         g_assert (!(m->comp_done & MONO_COMP_DFRONTIER));
 311
 312         for (i = 0; i < m->num_bblocks; ++i)
 313                 m->bblocks [i]->flags &= ~BB_VISITED;
 314
 315         /* we could reuse the bitsets allocated in compute_idominators() */
 316         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
 317         mem = mono_mempool_alloc0 (m->mempool, bitsize * m->num_bblocks);
 318
 319         for (i = 0; i < m->num_bblocks; ++i) {
 320                 bb = m->bblocks [i];
 321                 bb->dfrontier = mono_bitset_mem_new (mem, m->num_bblocks, 0);
 322                 mem += bitsize;
 323         }
 324
 325         compute_dominance_frontier_appel (m, 0);
 326
 327 #if 0
 328         for (i = 0; i < m->num_bblocks; ++i) {
 329                 MonoBasicBlock *x = m->bblocks [i];
 330
 331                 printf ("DFRONT %s BB%d: ", mono_method_full_name (m->method, TRUE), x->block_num);
 332                 mono_blockset_print (m, x->dfrontier, NULL, -1);
 333         }
 334 #endif
 335
 336 #if 1
 337         /* this is a check for the dominator frontier */
 338         for (i = 0; i < m->num_bblocks; ++i) {
 339                 MonoBasicBlock *x = m->bblocks [i];
 340
 341                 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
 342                         MonoBasicBlock *w = m->bblocks [j];
 343                         int k;
 344                         /* x must not strictly dominates w */
 345                         if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
 346                                 g_assert_not_reached ();
 347
 348                         for (k = 0; k < m->num_bblocks; ++k)
 349                                 m->bblocks [k]->flags &= ~BB_VISITED;
 350
 351                         check_dominance_frontier (x, x);
 352                 }
 353         }
 354 #endif
 355
 356         m->comp_done |= MONO_COMP_DFRONTIER;
 357 }
 358
 359 void
 360 mono_compile_dominator_info (MonoCompile *cfg, int dom_flags)
 361 {
 362         if ((dom_flags & MONO_COMP_DOM) && !(cfg->comp_done & MONO_COMP_DOM))
 363                 compute_dominators (cfg);
 364         if ((dom_flags & MONO_COMP_IDOM) && !(cfg->comp_done & MONO_COMP_IDOM))
 365                 compute_idominators (cfg);
 366         if ((dom_flags & MONO_COMP_DFRONTIER) && !(cfg->comp_done & MONO_COMP_DFRONTIER))
 367                 compute_dominance_frontier (cfg);
 368 }
 369
 370 static void
 371 df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
 372 {
 373         int i;
 374
 375         mono_bitset_clear_all (dest);
 376         mono_bitset_foreach_bit (set, i, m->num_bblocks) {
 377                 mono_bitset_union (dest, m->bblocks [i]->dfrontier);
 378         }
 379 }
 380
 381 /* TODO: alloc tmp and D on the stack */
 382 MonoBitSet*
 383 mono_compile_iterated_dfrontier (MonoCompile *m, MonoBitSet *set)
 384 {
 385         MonoBitSet *result, *D;
 386         int bitsize, change = TRUE;
 387
 388         bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
 389         result = mono_bitset_mem_new (mono_mempool_alloc (m->mempool, bitsize), m->num_bblocks, 0);
 390         D = mono_bitset_mem_new (mono_mempool_alloc (m->mempool, bitsize), m->num_bblocks, 0);
 391
 392         df_set (m, result, set);
 393         do {
 394                 change = FALSE;
 395                 df_set (m, D, result);
 396                 mono_bitset_union (D, result);
 397
 398                 if (!mono_bitset_equal (D, result)) {
 399                         mono_bitset_copyto (D, result);
 400                         change = TRUE;
 401                 }
 402         } while (change);
 403
 404         return result;
 405 }
 406
 407 //#define DEBUG_NATURAL_LOOPS
 408
 409 /*
 410  * code to detect loops and loop nesting level
 411  */
 412 void
 413 mono_compute_natural_loops (MonoCompile *cfg)
 414 {
 415         int i, j, k;
 416
 417         g_assert (!(cfg->comp_done & MONO_COMP_LOOPS));
 418
 419         for (i = 0; i < cfg->num_bblocks; ++i) {
 420                 MonoBasicBlock *n = cfg->bblocks [i];
 421
 422                 for (j = 0; j < n->out_count; j++) {
 423                         MonoBasicBlock *h = n->out_bb [j];
 424                         /* check for back-edge from n to h */
 425                         if (n != h && mono_bitset_test (n->dominators, h->dfn)) {
 426                                 GList *todo;
 427
 428                                 n->loop_body_start = 1;
 429
 430                                 /* already in loop_blocks? */
 431                                 if (h->loop_blocks && g_list_find (h->loop_blocks, n))
 432                                         continue;
 433
 434                                 todo = g_list_prepend (NULL, n);
 435
 436                                 while (todo) {
 437                                         MonoBasicBlock *cb = (MonoBasicBlock *)todo->data;
 438                                         todo = g_list_delete_link (todo, todo);
 439
 440                                         if (g_list_find (h->loop_blocks, cb))
 441                                                 continue;
 442
 443                                         h->loop_blocks = g_list_prepend (h->loop_blocks, cb);
 444                                         cb->nesting++;
 445
 446                                         for (k = 0; k < cb->in_count; k++) {
 447                                                 MonoBasicBlock *prev = cb->in_bb [k];
 448                                                 /* add all previous blocks */
 449                                                 if (prev != h && !g_list_find (h->loop_blocks, prev)) {
 450                                                         todo = g_list_prepend (todo, prev);
 451                                                 }
 452                                         }
 453                                 }
 454
 455                                 /* add the header if not already there */
 456                                 if (!g_list_find (h->loop_blocks, h)) {
 457                                         h->loop_blocks = g_list_prepend (h->loop_blocks, h);
 458                                         h->nesting++;
 459                                 }
 460                         }
 461                 }
 462         }
 463
 464         cfg->comp_done |= MONO_COMP_LOOPS;
 465
 466 #ifdef DEBUG_NATURAL_LOOPS
 467         for (i = 0; i < cfg->num_bblocks; ++i) {
 468                 if (cfg->bblocks [i]->loop_blocks) {
 469                         MonoBasicBlock *h = (MonoBasicBlock *)cfg->bblocks [i]->loop_blocks->data;
 470                         GList *l;
 471                         printf ("LOOP START %d\n", h->block_num);
 472                         for (l = h->loop_blocks; l; l = l->next) {
 473                                 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
 474                                 printf (" BB%d %d %p\n", cb->block_num, cb->nesting, cb->loop_blocks);
 475                         }
 476                 }
 477         }
 478 #endif
 479
 480 }
 481
 482 static void
 483 clear_idominators (MonoCompile *cfg)
 484 {
 485         guint i;
 486
 487         for (i = 0; i < cfg->num_bblocks; ++i) {
 488                 if (cfg->bblocks[i]->dominated) {
 489                         g_list_free (cfg->bblocks[i]->dominated);
 490                         cfg->bblocks[i]->dominated = NULL;
 491                 }
 492         }
 493
 494         cfg->comp_done &= ~MONO_COMP_IDOM;
 495 }
 496
 497 static void
 498 clear_loops (MonoCompile *cfg)
 499 {
 500         guint i;
 501
 502         for (i = 0; i < cfg->num_bblocks; ++i) {
 503                 cfg->bblocks[i]->nesting = 0;
 504                 if (cfg->bblocks[i]->loop_blocks) {
 505                         g_list_free (cfg->bblocks[i]->loop_blocks);
 506                         cfg->bblocks[i]->loop_blocks = NULL;
 507                 }
 508         }
 509
 510         cfg->comp_done &= ~MONO_COMP_LOOPS;
 511 }
 512
 513 void
 514 mono_free_loop_info (MonoCompile *cfg)
 515 {
 516     if (cfg->comp_done & MONO_COMP_IDOM)
 517         clear_idominators (cfg);
 518     if (cfg->comp_done & MONO_COMP_LOOPS)
 519         clear_loops (cfg);
 520 }
 521