mono/metadata/mono-basic-block.c

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