mono/metadata/mono-basic-block.c

   1 /*
   2  * mono-basic-block.c: Routines for parsing basic blocks from the IL stream
   3  *
   4  * Authors:
   5  *   Rodrigo Kumpera (rkumpera@novell.com)
   6  *
   7  * Copyright 2010 Novell, Inc (http://www.novell.com)
   8  */
   9
  10 #include <config.h>
  11
  12 #include <mono/metadata/debug-helpers.h>
  13 #include <mono/metadata/metadata-internals.h>
  14 #include <mono/metadata/mono-endian.h>
  15 #include <mono/metadata/mono-basic-block.h>
  16 #include <mono/metadata/opcodes.h>
  17
  18 #include <mono/utils/mono-error-internals.h>
  19 #include <mono/utils/mono-compiler.h>
  20
  21 #define CHECK_ADD4_OVERFLOW_UN(a, b) ((guint32)(0xFFFFFFFFU) - (guint32)(b) < (guint32)(a))
  22 #define CHECK_ADD8_OVERFLOW_UN(a, b) ((guint64)(0xFFFFFFFFFFFFFFFFUL) - (guint64)(b) < (guint64)(a))
  23
  24 #if SIZEOF_VOID_P == 4
  25 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD4_OVERFLOW_UN(a, b)
  26 #else
  27 #define CHECK_ADDP_OVERFLOW_UN(a,b) CHECK_ADD8_OVERFLOW_UN(a, b)
  28 #endif
  29
  30 #define ADDP_IS_GREATER_OR_OVF(a, b, c) (((a) + (b) > (c)) || CHECK_ADDP_OVERFLOW_UN (a, b))
  31 #define ADD_IS_GREATER_OR_OVF(a, b, c) (((a) + (b) > (c)) || CHECK_ADD4_OVERFLOW_UN (a, b))
  32
  33 #define DEBUG_BB 0
  34
  35 enum {
  36         RED,
  37         BLACK
  38 };
  39
  40 #if DEBUG_BB
  41
  42 static void
  43 dump_bb_list (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, const char *msg)
  44 {
  45         printf ("------- %s --- root is %x ---\n", msg, (*root)->start);
  46         while (bb) {
  47                 GSList *tmp;
  48                 printf ("BB start %x end %x left ", bb->start, bb->end);
  49                 if (bb->left)
  50                         printf ("%x", bb->left->start);
  51                 else
  52                         printf ("NIL");
  53
  54                 printf (" right ");
  55                 if (bb->right)
  56                         printf ("%x", bb->right->start);
  57                 else
  58                         printf ("NIL");
  59
  60                 printf (" parent ");
  61                 if (bb->parent)
  62                         printf ("%x", bb->parent->start);
  63                 else
  64                         printf ("NIL");
  65
  66                 printf(" color %s out [", bb->colour == RED ? "red" : "black");
  67
  68                 for (tmp = bb->out_bb; tmp; tmp = tmp->next) {
  69                         MonoSimpleBasicBlock *to = tmp->data;
  70                         printf ("%x ", to->start);
  71                 }
  72                 printf ("] %s\n", bb->dead ? "dead" : "alive");
  73                 bb = bb->next;
  74         }
  75 }
  76
  77 #endif
  78
  79 static void
  80 bb_unlink (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
  81 {
  82         if (from->out_bb)
  83                 from->out_bb = g_slist_remove (from->out_bb, to);
  84 }
  85
  86 static void
  87 bb_link (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to)
  88 {
  89         if (g_slist_find (from->out_bb, to))
  90                 return;
  91         from->out_bb = g_slist_prepend (from->out_bb, to);
  92 }
  93
  94
  95 static MonoSimpleBasicBlock*
  96 bb_grandparent (MonoSimpleBasicBlock *bb)
  97 {
  98         return bb && bb->parent ? bb->parent->parent : NULL;
  99 }
 100
 101 static MonoSimpleBasicBlock*
 102 bb_uncle (MonoSimpleBasicBlock *bb)
 103 {
 104         MonoSimpleBasicBlock *gp = bb_grandparent (bb);
 105         if (gp == NULL)
 106                 return NULL;
 107         if (bb->parent == gp->left)
 108                 return gp->right;
 109         return gp->left;
 110 }
 111
 112 static void
 113 change_node (MonoSimpleBasicBlock *from, MonoSimpleBasicBlock *to, MonoSimpleBasicBlock **root)
 114 {
 115         MonoSimpleBasicBlock *parent = from->parent;
 116         if (parent) {
 117                 if (parent->left == from)
 118                         parent->left = to;
 119                 else
 120                         parent->right = to;
 121         } else {
 122                 *root = to;
 123         }
 124         to->parent = parent;
 125 }
 126
 127 static void
 128 rotate_right (MonoSimpleBasicBlock *parent, MonoSimpleBasicBlock **root)
 129 {
 130         MonoSimpleBasicBlock *bb = parent->left;
 131         if (bb->right) {
 132                 parent->left = bb->right;
 133                 parent->left->parent = parent;
 134         } else
 135                 parent->left = NULL;
 136         bb->right = parent;
 137         change_node (parent, bb, root);
 138         parent->parent = bb;
 139 }
 140
 141 static void
 142 rotate_left (MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
 143 {
 144         MonoSimpleBasicBlock *other = bb->right;
 145         if (other->left) {
 146                 bb->right = other->left;
 147                 bb->right->parent = bb;
 148         } else
 149                 bb->right = NULL;
 150         other->left = bb;
 151         change_node (bb, other, root);
 152         bb->parent = other;
 153 }
 154
 155 /* School book implementation of a RB tree with insert then fix (which requires a parent pointer)
 156  * TODO implement Sedgewick's version that doesn't require parent pointers
 157  */
 158 static void
 159 bb_insert (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root)
 160 {
 161         MonoSimpleBasicBlock *parent, *uncle, *grandparent;
 162         int bb_start = bb->start;
 163
 164         parent = *root;
 165         do {
 166                 if (bb_start < parent->start) {
 167                         if (parent->left == NULL) {
 168                                 parent->left = bb;
 169                                 break;
 170                         }
 171                         parent = parent->left;
 172                 } else {
 173                         if (parent->right == NULL) {
 174                                 parent->right = bb;
 175                                 break;
 176                         }
 177                         parent = parent->right;
 178                 }
 179         } while (parent);
 180         g_assert (parent);
 181         bb->parent = parent;
 182
 183         bb->colour = RED;
 184
 185         do {
 186                 if (bb->parent == NULL) {
 187                         bb->colour = BLACK;
 188                         break;
 189                 }
 190
 191                 if (bb->parent->colour == BLACK)
 192                         break;
 193
 194                 uncle = bb_uncle (bb);
 195                 if (uncle && uncle->colour == RED) {
 196                         grandparent = bb_grandparent (bb);
 197
 198                         bb->parent->colour = BLACK;
 199                         uncle->colour = BLACK;
 200                         grandparent->colour = RED;
 201                         bb = grandparent;
 202                         continue;
 203                 }
 204
 205                 grandparent = bb_grandparent (bb);
 206                 if ((bb == bb->parent->right) && (bb->parent == grandparent->left)) {
 207                         rotate_left (bb->parent, root);
 208                         bb = bb->left;
 209                 } else if ((bb == bb->parent->left) && (bb->parent == grandparent->right)) {
 210                         rotate_right (bb->parent, root);
 211                         bb = bb->right;
 212                 }
 213
 214                 grandparent = bb_grandparent (bb);
 215                 bb->parent->colour = BLACK;
 216                 grandparent->colour = RED;
 217                 if ((bb == bb->parent->left) && (bb->parent == grandparent->left))
 218                         rotate_right (grandparent, root);
 219                 else
 220                         rotate_left (grandparent, root);
 221                 break;
 222         } while (TRUE);
 223 }
 224
 225 static gboolean
 226 bb_idx_is_contained (MonoSimpleBasicBlock *bb, int target)
 227 {
 228         return bb->start <= target && target < bb->end;
 229 }
 230
 231 /*
 232  * Split the basic blocks from @first at @target.
 233  * @hint is a guess of a very close to the target basic block. It is probed before the RB tree as it's often possible
 234  * to provide a near to exact guess (next block splits, switch branch targets, etc)
 235  *
 236  */
 237 static MonoSimpleBasicBlock*
 238 bb_split (MonoSimpleBasicBlock *first, MonoSimpleBasicBlock *hint, MonoSimpleBasicBlock **root, guint target, gboolean link_blocks, MonoMethod *method, MonoError *error)
 239 {
 240         MonoSimpleBasicBlock *res, *bb = first;
 241
 242         if (bb_idx_is_contained (hint, target)) {
 243                 first = hint;
 244         } else if (hint->next && bb_idx_is_contained (hint->next, target)) {
 245                 first = hint->next;
 246         } else {
 247                 first = *root;
 248                 do {
 249                         if (bb_idx_is_contained (first, target))
 250                                 break;
 251                         if (first->start > target)
 252                                 first = first->left;
 253                         else
 254                                 first = first->right;
 255                 } while (first);
 256         }
 257
 258         if (first == NULL) {
 259                 mono_error_set_not_verifiable (error, method, "Invalid instruction target %x", target);
 260                 return NULL;
 261         }
 262
 263         if (first->start == target)
 264                 return first;
 265
 266         res = g_new0 (MonoSimpleBasicBlock, 1);
 267         res->start = target;
 268         res->end = first->end;
 269         res->next = first->next;
 270         res->out_bb = first->out_bb;
 271         res->dead = TRUE;
 272
 273         first->end = res->start;
 274         first->next = res;
 275         first->out_bb = NULL;
 276
 277         if (link_blocks)
 278                 bb_link (first, res);
 279         bb_insert (bb, res, root);
 280
 281         return res;
 282 }
 283
 284 static void
 285 bb_liveness (MonoSimpleBasicBlock *bb)
 286 {
 287         GPtrArray* mark_stack = g_ptr_array_new ();
 288         GSList *tmp;
 289
 290         /*All function entry points (prologue, EH handler/filter) are already marked*/
 291         while (bb) {
 292                 if (!bb->dead)
 293                         g_ptr_array_add (mark_stack, bb);
 294                 bb = bb->next;
 295         }
 296
 297         while (mark_stack->len > 0) {
 298                 MonoSimpleBasicBlock *block = g_ptr_array_remove_index_fast (mark_stack, mark_stack->len - 1);
 299                 block->dead = FALSE;
 300
 301                 for (tmp = block->out_bb; tmp; tmp = tmp->next) {
 302                         MonoSimpleBasicBlock *to = tmp->data;
 303                         if (to->dead)
 304                                 g_ptr_array_add (mark_stack, to);
 305                 }
 306         }
 307
 308         g_ptr_array_free (mark_stack, TRUE);
 309 }
 310
 311 /*This doesn't returns endfilter because it's not useful to split at its boundary.
 312 Endfilter must be the last instruction of a filter clause and MS enforces this, so we can't have
 313 dead code after it.
 314 */
 315 static gboolean
 316 mono_opcode_has_static_branch (int opcode)
 317 {
 318         switch (opcode) {
 319         case MONO_CEE_RET:
 320         case MONO_CEE_THROW:
 321         case MONO_CEE_RETHROW:
 322         case MONO_CEE_ENDFINALLY:
 323                 return TRUE;
 324         }
 325         return FALSE;
 326 }
 327
 328
 329 static void
 330 bb_formation_il_pass (const unsigned char *start, const unsigned char *end, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 331 {
 332         unsigned const char *ip = start;
 333         int value, size;
 334         guint cli_addr, offset;
 335         MonoSimpleBasicBlock *branch, *next, *current;
 336         const MonoOpcode *opcode;
 337
 338         current = bb;
 339
 340         while (ip < end) {
 341                 cli_addr = ip - start;
 342                 size = mono_opcode_value_and_size (&ip, end, &value);
 343                 if (size < 0) {
 344                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 345                         return;
 346                 }
 347
 348                 while (current && cli_addr >= current->end)
 349                         current = current->next;
 350                 g_assert (current);
 351
 352                 opcode = &mono_opcodes [value];
 353                 switch (opcode->argument) {
 354                 case MonoInlineNone:
 355                         ip++;
 356                         if (!mono_opcode_has_static_branch (value) || ip >= end)
 357                                 break;
 358                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 359                                 return;
 360
 361                         bb_unlink (current, next);
 362                         current = next;
 363                         break;
 364                 case MonoInlineString:
 365                 case MonoInlineType:
 366                 case MonoInlineField:
 367                 case MonoInlineTok:
 368                 case MonoInlineSig:
 369                 case MonoShortInlineR:
 370                 case MonoInlineI:
 371                         ip += 5;
 372                         break;
 373
 374                 case MonoInlineMethod:
 375                         ip += 5;
 376                         if (value != MONO_CEE_JMP || ip >= end)
 377                                 break;
 378                         if (!(next = bb_split (bb, current, root, ip - start, FALSE, method, error)))
 379                                 return;
 380
 381                         bb_unlink (current, next);
 382                         current = next;
 383
 384                         break;
 385                 case MonoInlineVar:
 386                         ip += 3;
 387                         break;
 388                 case MonoShortInlineVar:
 389                 case MonoShortInlineI:
 390                         ip += 2;
 391                         break;
 392                 case MonoInlineR:
 393                 case MonoInlineI8:
 394                         ip += 9;
 395                         break;
 396                 case MonoShortInlineBrTarget:
 397                 case MonoInlineBrTarget:
 398                         if (opcode->argument == MonoShortInlineBrTarget) {
 399                                 offset = cli_addr + 2 + (signed char)ip [1];
 400                                 ip += 2;
 401                         } else {
 402                                 offset = cli_addr + 5 + (gint32)read32 (ip + 1);
 403                                 ip += 5;
 404                         }
 405
 406                         branch = bb_split (bb, current, root, offset, TRUE, method, error);
 407                         if (!branch)
 408                                 return;
 409
 410                         /*If we splitted the current BB*/
 411                         if (offset < cli_addr && branch->start > current->start)
 412                                 current = branch;
 413                         if (ip < end) {
 414                                 next = bb_split (bb, current, root, ip - start, opcode->flow_type != MONO_FLOW_BRANCH, method, error);
 415                                 if (!next)
 416                                         return;
 417                         } else {
 418                                 next = NULL;
 419                         }
 420
 421                         bb_link (current, branch);
 422                         if (next && opcode->flow_type == MONO_FLOW_BRANCH && next != branch) {
 423                                 bb_unlink (current, next);
 424                                 current = next;
 425                         }
 426                         break;
 427                 case MonoInlineSwitch: {
 428                         MonoSimpleBasicBlock *tmp;
 429                         guint32 j, n = read32 (ip + 1);
 430
 431                         ip += 5;
 432                         offset = cli_addr + 5 + 4 * n;
 433                         if (!(next = bb_split (bb, current, root, offset, TRUE, method, error)))
 434                                 return;
 435
 436                         bb_link (current, next);
 437                         tmp = next;
 438
 439                         for (j = 0; j < n; ++j) {
 440                                 if (ip >= end) {
 441                                         mono_error_set_not_verifiable (error, method, "Invalid switch instruction %x", cli_addr);
 442                                         return;
 443                                 }
 444                                 if (!(next = bb_split (bb, next, root, offset + (gint32)read32 (ip), TRUE, method, error)))
 445                                         return;
 446                                 bb_link (current, next);
 447                                 ip += 4;
 448                         }
 449                         current = tmp;
 450                         break;
 451                 }
 452                 default:
 453                         mono_error_set_not_verifiable (error, method, "Invalid instruction %x", *ip);
 454                         return;
 455                 }
 456         }
 457         if (ip != end)
 458                 mono_error_set_not_verifiable (error, method, "Invalid last instruction");
 459 }
 460
 461 static void
 462 bb_formation_eh_pass (MonoMethodHeader *header, MonoSimpleBasicBlock *bb, MonoSimpleBasicBlock **root, MonoMethod *method, MonoError *error)
 463 {
 464         int i;
 465         int end = header->code_size;
 466         /*We must split at all points to verify for targets in the middle of an instruction*/
 467         for (i = 0; i < header->num_clauses; ++i) {
 468                 MonoExceptionClause *clause = header->clauses + i;
 469                 MonoSimpleBasicBlock *try_block, *handler;
 470
 471                 if (!(try_block = bb_split (bb, bb, root, clause->try_offset, TRUE, method, error)))
 472                         return;
 473
 474                 handler = bb_split (bb, try_block, root, clause->handler_offset, FALSE, method, error);
 475                 if (!handler)
 476                         return;
 477                 handler->dead = FALSE;
 478
 479                 if (clause->flags == MONO_EXCEPTION_CLAUSE_FILTER) {
 480                         MonoSimpleBasicBlock *filter = bb_split (bb, try_block, root, clause->data.filter_offset, FALSE, method, error);
 481                         if (!filter)
 482                                 return;
 483                         filter->dead = FALSE;
 484                 }
 485
 486                 if (clause->try_offset + clause->try_len < end && !bb_split (bb, try_block, root, clause->try_offset + clause->try_len, FALSE, method, error))
 487                         return;
 488
 489                 if (clause->handler_offset + clause->handler_len < end && !bb_split (bb, handler, root, clause->handler_offset + clause->handler_len, FALSE, method, error))
 490                         return;
 491         }
 492 }
 493
 494 /*
 495  * mono_basic_block_free:
 496  *
 497  * Release the memory associated with the list of basis blocks @bb.
 498 */
 499 void
 500 mono_basic_block_free (MonoSimpleBasicBlock *bb)
 501 {
 502         while (bb) {
 503                 MonoSimpleBasicBlock *next = bb->next;
 504                 if (bb->out_bb)
 505                         g_slist_free (bb->out_bb);
 506                 g_free (bb);
 507                 bb = next;
 508         }
 509 }
 510
 511 /*
 512  * mono_basic_block_split:
 513  *
 514  * Return the list of basic blocks of method. Return NULL on failure and set @error.
 515 */
 516 MonoSimpleBasicBlock*
 517 mono_basic_block_split (MonoMethod *method, MonoError *error)
 518 {
 519         MonoSimpleBasicBlock *bb, *root;
 520         const unsigned char *start, *end;
 521         MonoMethodHeader *header = mono_method_get_header (method);
 522         start = header->code;
 523         end = start + header->code_size;
 524
 525         mono_error_init (error);
 526
 527         if (!header) {
 528                 mono_error_set_not_verifiable (error, method, "Could not decode header");
 529                 return NULL;
 530         }
 531
 532         bb = g_new0 (MonoSimpleBasicBlock, 1);
 533         bb->start = 0;
 534         bb->end = end - start;
 535         bb->colour = BLACK;
 536         bb->dead = FALSE;
 537
 538         root = bb;
 539         bb_formation_il_pass (start, end, bb, &root, method, error);
 540         if (!mono_error_ok (error))
 541                 goto fail;
 542
 543         bb_formation_eh_pass (header, bb, &root, method, error);
 544         if (!mono_error_ok (error))
 545                 goto fail;
 546
 547         bb_liveness (bb);
 548
 549 #if DEBUG_BB
 550         dump_bb_list (bb, &root, g_strdup_printf("AFTER LIVENESS %s", mono_method_full_name (method, TRUE)));
 551 #endif
 552
 553         mono_metadata_free_mh (header);
 554         return bb;
 555
 556 fail:
 557         mono_metadata_free_mh (header);
 558         mono_basic_block_free (bb);
 559         return NULL;
 560 }
 561
 562 /*
 563  * mono_opcode_value_and_size:
 564  *
 565  * Returns the size of the opcode starting at *@ip, or -1 on error.
 566  * Value is the opcode number.
 567 */
 568 int
 569 mono_opcode_value_and_size (const unsigned char **ip, const unsigned char *end, int *value)
 570 {
 571         const unsigned char *start = *ip, *p;
 572         int i = *value = mono_opcode_value (ip, end);
 573         int size = 0;
 574         if (i < 0 || i >= MONO_CEE_LAST)
 575                 return -1;
 576         p = *ip;
 577
 578         switch (mono_opcodes [i].argument) {
 579         case MonoInlineNone:
 580                 size = 1;
 581                 break;
 582         case MonoInlineString:
 583         case MonoInlineType:
 584         case MonoInlineField:
 585         case MonoInlineMethod:
 586         case MonoInlineTok:
 587         case MonoInlineSig:
 588         case MonoShortInlineR:
 589         case MonoInlineI:
 590         case MonoInlineBrTarget:
 591                 size = 5;
 592                 break;
 593         case MonoInlineVar:
 594                 size = 3;
 595                 break;
 596         case MonoShortInlineVar:
 597         case MonoShortInlineI:
 598         case MonoShortInlineBrTarget:
 599                 size = 2;
 600                 break;
 601         case MonoInlineR:
 602         case MonoInlineI8:
 603                 size = 9;
 604                 break;
 605         case MonoInlineSwitch: {
 606                 guint32 entries;
 607                 if (ADDP_IS_GREATER_OR_OVF (p, 5, end))
 608                         return -1;
 609                 entries = read32 (p + 1);
 610                 if (entries >= (0xFFFFFFFFU / 4))
 611                         return -1;
 612                 size = 4 + 4 * entries;
 613                 break;
 614         }
 615         default:
 616                 g_error ("Invalid opcode %d argument %d max opcode %d\n", i, mono_opcodes [i].argument, MONO_CEE_LAST);
 617         }
 618
 619         if (ADDP_IS_GREATER_OR_OVF (p, size, end))
 620                 return -1;
 621
 622         return (p - start) + size;
 623 }
 624
 625 /*
 626  * mono_opcode_size:
 627  *
 628  * Returns the size of the opcode starting at @ip, or -1 on error.
 629 */
 630 int
 631 mono_opcode_size (const unsigned char *ip, const unsigned char *end)
 632 {
 633         int tmp;
 634         return mono_opcode_value_and_size (&ip, end, &tmp);
 635 }
 636